Benchmarks for different data structures

# Benchmarks
We benchmarked different data structures for counting MAC addresses:
- Bitmap (original)
- Optimized bitmap 1 - inlined functions
- Optimized bitmap 2 - manual inlined functions
- Bitmap with critical sections
- std::unordered_set
- Set 1 - C++ implementation
- Set 2 - with bucket generation values
- Set 3 - C implementation

For each we benchmarked two separate steps:

- inserting a MAC address (done at a high frequency during the counting bucket time)
- resetting the counter (done once at the start of each counting bucket)

For a good counting result, the first is more important as it avoids missing WiFi frames.

## Bitmap Solution (original)

This is the original implementation. The bitmap solution remembers seen IDs by using a 65536 bits array. Each bit stands for 1 ID. IDs are composed of the last 2 bytes of the MAC address and mapped as index in the bit array.

```c++
typedef uint32_t bitmap_t;
enum { BITS_PER_WORD = sizeof(bitmap_t) * CHAR_BIT };
#define WORD_OFFSET(b) ((b) / BITS_PER_WORD)
#define BIT_OFFSET(b) ((b) % BITS_PER_WORD)

// The bitmap requires 2**16 = 65536 entries,
// while using 32 bit integers, we need 65536 / 32 = 2048 integers
DRAM_ATTR bitmap_t seen_ids_map[2048];
int seen_ids_count = 0;

IRAM_ATTR void set_id(bitmap_t *bitmap, uint16_t id) {
bitmap[WORD_OFFSET(id)] |= ((bitmap_t)1 << BIT_OFFSET(id));
}

IRAM_ATTR int get_id(bitmap_t *bitmap, uint16_t id) {
bitmap_t bit = bitmap[WORD_OFFSET(id)] & ((bitmap_t)1 << BIT_OFFSET(id));
return bit != 0;
}

/** remember given id
* returns 1 if id is new, 0 if already seen this is since last reset
*/
IRAM_ATTR int add_to_bucket(uint16_t id) {
if (get_id(seen_ids_map, id)) {
return 0; // already seen
} else {
set_id(seen_ids_map, id);
seen_ids_count++;
return 1; // new
}
}

void reset_bucket() {
memset(seen_ids_map, 0, sizeof(seen_ids_map));
seen_ids_count = 0;
}
```

## Optimized bitmap 1 - inlined functions

Counting within `add_to_bucket` was removed because it wasn't used.

The functions `set_id()` and `get_id()` were inlined. This is the primary performance increase by skipping the function call overhead.

```c++
typedef uint32_t bitmap_t;
enum { BITS_PER_WORD = sizeof(bitmap_t) * CHAR_BIT };
#define WORD_OFFSET(b) ((b) / BITS_PER_WORD)
#define BIT_OFFSET(b) ((b) % BITS_PER_WORD)

// The bitmap requires 2**16 = 65536 entries,
// while using 32 bit integers, we need 65536 / 32 = 2048 integers
DRAM_ATTR bitmap_t seen_ids_map[2048];

inline IRAM_ATTR void set_id(bitmap_t *bitmap, uint16_t id) {
bitmap[WORD_OFFSET(id)] |= ((bitmap_t)1 << BIT_OFFSET(id));
}

inline IRAM_ATTR int get_id(bitmap_t *bitmap, uint16_t id) {
bitmap_t bit = bitmap[WORD_OFFSET(id)] & ((bitmap_t)1 << BIT_OFFSET(id));
return bit != 0;
}

/** remember given id
* returns 1 if id is new, 0 if already seen this is since last reset
*/
IRAM_ATTR int add_to_bucket(uint16_t id) {
if (get_id(seen_ids_map, id)) {
return 0; // already seen
} else {
set_id(seen_ids_map, id);
return 1; // new
}
}

void reset_bucket() {
memset(seen_ids_map, 0, sizeof(seen_ids_map));
}
```

## Optimized bitmap 2 - manual inlined functions

The functions `set_id()` and `get_id()` were removed and the content was integrated and optimized into the `add_to_bucket()` function by hand.

```c++
typedef uint32_t bitmap_t;
enum { BITS_PER_WORD = sizeof(bitmap_t) * CHAR_BIT };
#define WORD_OFFSET(b) ((b) / BITS_PER_WORD)
#define BIT_OFFSET(b) ((b) % BITS_PER_WORD)

// The bitmap requires 2**16 = 65536 entries,
// while using 32 bit integers, we need 65536 / 32 = 2048 integers
DRAM_ATTR bitmap_t seen_ids_map[2048];

/** remember given id
* returns 1 if id is new, 0 if already seen this is since last reset
*/
IRAM_ATTR int add_to_bucket(uint16_t id) {
uint16_t mask = (bitmap_t)1 << BIT_OFFSET(id);
uint16_t word = WORD_OFFSET(id);
if (seen_ids_map[word] & mask) {
return 0;
}
seen_ids_map[word] |= mask;
return 1;
}

void reset_bucket() {
memset(seen_ids_map, 0, sizeof(seen_ids_map));
}
```

## Bitmap with critical sections

In this version, the access to `macs_wifi`, `macs_ble`, `seen_ids_map_wifi`, and `seen_ids_ble` have been protected by critical sections to prevent data races.

```c++
typedef uint32_t bitmap_t;
enum { BITS_PER_WORD = sizeof(bitmap_t) * CHAR_BIT };
#define WORD_OFFSET(b) ((b) / BITS_PER_WORD)
#define BIT_OFFSET(b) ((b) % BITS_PER_WORD)

// The bitmap requires 2**16 = 65536 entries,
// while using 32 bit integers, we need 65536 / 32 = 2048 integers
// Separate maps per sniff type: a shared map would let a WiFi id and an
// unrelated BLE id collide with each other, doubling the effective
// collision rate whenever both radios are active at once.
// Each map is only allocated when its sniffer is actually built in, so a
// WiFi-only or BLE-only build doesn't waste 8 KiB of DRAM on the other map.
#if defined(LIBPAX_WIFI)
DRAM_ATTR bitmap_t seen_ids_map_wifi[2048];
#endif
#if defined(LIBPAX_BLE)
DRAM_ATTR bitmap_t seen_ids_map_ble[2048];
#endif

volatile uint16_t macs_wifi = 0;
volatile uint16_t macs_ble = 0;

volatile uint8_t channel = 0; // channel rotation counter

// Guards the seen_ids maps: add_to_bucket() (WiFi/BLE RX task, either core)
// sets individual bits while reset_bucket() (report timer task) memsets the
// whole map, so without this a reset could race with a concurrent bit-set.
static portMUX_TYPE bucket_mux = portMUX_INITIALIZER_UNLOCKED;

/** remember given id in the bitmap for the given sniff type
* returns 1 if id is new, 0 if already seen this is since last reset
* Hot-path critical function - highly optimized
*/
IRAM_ATTR int add_to_bucket(uint16_t id, snifftype_t sniff_type) {
bitmap_t *map;
#if defined(LIBPAX_WIFI) && defined(LIBPAX_BLE)
map = (sniff_type == MAC_SNIFF_BLE) ? seen_ids_map_ble : seen_ids_map_wifi;
#elif defined(LIBPAX_BLE)
map = seen_ids_map_ble;
#elif defined(LIBPAX_WIFI)
map = seen_ids_map_wifi;
#else
return 0; // neither sniffer built in, nothing to track
#endif
uint16_t word_idx = WORD_OFFSET(id);
uint32_t bit_mask = ((bitmap_t)1 << BIT_OFFSET(id));

portENTER_CRITICAL(&bucket_mux);
bool already_seen = map[word_idx] & bit_mask;
if (!already_seen) {
map[word_idx] |= bit_mask;
}
portEXIT_CRITICAL(&bucket_mux);

return already_seen ? 0 : 1;
}

void reset_bucket() {
portENTER_CRITICAL(&bucket_mux);
macs_wifi = 0;
macs_ble = 0;
#if defined(LIBPAX_WIFI)
memset(seen_ids_map_wifi, 0, sizeof(seen_ids_map_wifi));
#endif
#if defined(LIBPAX_BLE)
memset(seen_ids_map_ble, 0, sizeof(seen_ids_map_ble));
#endif
portEXIT_CRITICAL(&bucket_mux);
}
```

## std::unordered_set
Inserting an ID takes more than 90 times longer than the inlined bitmap solutions. So it was not considered further.

This was expected as the existing solution is already minimal: only setting one bit. No hashing. Static memory allocation. Constant performance `O(1)`.

A hashset also would had benefits, as it could decrease collisions (counting two different MACs as the same) if the full address is hashed into a hash of more than 2 bytes.

## Set 1 - C++ implementation

The set is based on linear probing.

The set does not calculate a hash value because the IDs are already randomized.

The id with the value 0 is reserved for free buckets.

```c++
namespace libpax {

template
class SeenIdsSet_1 {
static_assert(CAPACITY < 32768);

public:
SeenIdsSet_1() : m_count(0) {
memset(m_ids, 0, sizeof(m_ids));
}

uint16_t get_count() {
return m_count;
}

void reset() {
memset(m_ids, 0, sizeof(m_ids));
m_count = 0;
}

bool insert_id(uint16_t id) {
if (m_count == CAPACITY) {
ESP_LOGW("SeenIdsSet_1", "Can not insert ID, capacity reached.");
return false;
}
uint16_t index = id % DOUBLE_CAPACITY;
while (m_ids[index] != 0) {
if (m_ids[index] == id) {
return false;
}
if (index == DOUBLE_CAPACITY_MINUS_1) {
index = 0;
}
else {
index++;
}
}
m_ids[index] = id;
m_count++;
return true;
}

private:
static constexpr uint16_t DOUBLE_CAPACITY = CAPACITY * 2;

static constexpr uint16_t DOUBLE_CAPACITY_MINUS_1 = DOUBLE_CAPACITY - 1;

uint16_t m_ids[DOUBLE_CAPACITY];

uint16_t m_count;
};
```

## Set 2 - with bucket generation values

The bitmap solution's `seen_ids_map` must be cleared after each interval by resetting the complete map back to zero. This takes significant time. The idea of the set is to reduce the duration of this operation by using generation values for each bucket. A bucket is set when the generation value equals the current generation value of the set. To reset the complete set we increment the set's generation value by 1. This makes the `reset()` method of the set very efficient.

The set is based on linear probing.

The set does not calculate a hash value because the IDs are already randomized.

The set could be adjusted to use complete MAC addresses instead of the last 2 bytes of the MAC.

```c++
namespace libpax {

template
class SeenIdsSet_2 {
static_assert(CAPACITY < 32768);

public:
SeenIdsSet_2() : m_count(0), m_generation(1) {
memset(m_generations, 0, sizeof(m_generations));
}

uint16_t get_count() {
return m_count;
}

void reset() {
if (m_generation == UINT16_MAX) {
m_generation = 1;
memset(m_generations, 0, sizeof(m_generations));
}
else {
m_generation++;
}
m_count = 0;
}

bool insert_id(uint16_t id) {
// The inset_id() method can end in an infinite loop if size is CAPACITY * 2.
if (m_count == CAPACITY) {
ESP_LOGW("SeenIdsSet_2", "Can not insert ID, capacity reached.");
return false;
}
uint16_t index = id % DOUBLE_CAPACITY;
while (m_generations[index] == m_generation) {
if (m_ids[index] == id) {
return false;
}
if (index == DOUBLE_CAPACITY_MINUS_1) {
index = 0;
}
else {
index++;
}
}
m_ids[index] = id;
m_generations[index] = m_generation;
m_count++;
return true;
}

private:
static constexpr uint16_t DOUBLE_CAPACITY = CAPACITY * 2;

static constexpr uint16_t DOUBLE_CAPACITY_MINUS_1 = DOUBLE_CAPACITY - 1;

uint16_t m_count;

uint16_t m_generation;

uint16_t m_ids[DOUBLE_CAPACITY];

uint16_t m_generations[DOUBLE_CAPACITY];
};

} // namespace libpax
```

## Set 3 - C implementation

A C version was implemented to check if it is more efficient than the C++ implementation. It compares to set 1.

```c++
#define SEEN_IDS_CAPACITY 1024
#define SEEN_IDS_DOUBLE_CAPACITY 2048
#define SEEN_IDS_DOUBLE_CAPACITY_MINUS_1 2047

static uint16_t seen_ids[SEEN_IDS_DOUBLE_CAPACITY];

static uint16_t seen_ids_count = 0;

void seen_ids_set_reset() {
seen_ids_count = 0;
memset(seen_ids, 0, sizeof(seen_ids));
}

uint16_t seen_ids_set_get_count() {
return seen_ids_count;
}

bool seen_ids_set_insert_id(uint16_t id) {
if (seen_ids_count == SEEN_IDS_CAPACITY) {
ESP_LOGW("SeenIdsSet2", "Can not insert ID, capacity reached.");
return false;
}
uint16_t index = id % SEEN_IDS_DOUBLE_CAPACITY;
while (seen_ids[index] != 0) {
if (seen_ids[index] == id) {
return false;
}
if (index == SEEN_IDS_DOUBLE_CAPACITY_MINUS_1) {
index = 0;
}
else {
index++;
}
}
seen_ids[index] = id;
seen_ids_count++;
return true;
}
```

# Results

We benched the performance of the resetting functions of the solutions. Each function was called 1000 times and we measured the duration it took to complete.

## Reset

| Solution | Function | Duration |
| :---------------------------- | :------------------ | -------:|
| bitmap | reset_bucket() | 16.541 us |
| bitmap - inlined | reset_bucket() | 16.376 us |
| bitmap - manual inlined | reset_bucket() | 16.372 us |
| bitmap with critical sections | reset_bucket() | 17.757 us |
| set 1 - C++ impl | reset() | 8.298 us |
| set 2 - with generation values | reset() | 226 us |
| set 3 - C impl | seen_ids_set_reset() | 8.347 us |
| std::unordered_set | clear() | 8.571 us |

## Insert

We benched the performance of the inserting methods of the solutions. Each function was called 1000 times and we measured the duration it took to complete. The same IDs have been inserted 2 times to simulate collisions.

The values are time per inserted id.

Two tested versions are slower than the original implementation:

- the optimized bitmal with critical section
- std::unordered_set

# Memory Usage

The original bitmap solution's, the optimized bitmap solution's, and the bitmap with critical sections solutions's `seen_ids_map` take 8 KBytes static memory in total. The original solution takes 4 additional bytes for the `seen_ids_count` value.

The set 1 and 3 use 2 bytes memory per bucket. The bucket count is twice the capacity. With a capacity of 1024 IDs, the set takes `2 bytes * 2 * 1024 = 4 KB` memory. Additionally it has a 2 bytes counter value.

The set 2 uses 4 bytes per bucket: 2 byte for the ID and 2 byte for the generation value. With a capacity of 1024 IDs, the set takes `4 bytes * 2 * 1024 = 8 KB` memory. Additionally it has a 2 bytes counter value and a 2 bytes generation value.

The memory usage of the sets can be reduced by reducing the capacity.

The memory usage of std::unordered_set depends on the implementation. It uses the heap.

# Concurrency Issues

All implementations other than the one with critical section have race conditions. The impact is slightly different between the implementations. For simplicity, here only looking into the bitmap version:

```
volatile uint16_t macs_wifi = 0;

void reset_bucket() {
// ...
macs_wifi = 0;
// ...
}

void mac_add(uint8_t *paddr, snifftype_t sniff_type) {
// ...
macs_wifi++;
// ...
}
```

1. Task 1 (mac_add): 'macs_wifi' read to register x
2. Task 2 (reset_bucket): 'macs_wifi' write 0
3. Task 1 (mac_add): register x add 1
4. Task 1 (mac_add): register x write to 'macs_wifi'

The variable 'macs_wifi' will not be resetted to 0. It will have the previous value incremented by 1. This is a critical issue as it effectively doubles the time bucket.

```
bitmap_t seen_ids_map_wifi[2048];

void reset_bucket() {
// ...
memset(seen_ids_map_wifi, 0, sizeof(seen_ids_map_wifi));
// ...
}

int add_to_bucket(uint16_t id) {
// ...
seen_ids_map_wifi[word_idx] |= bit_mask;
// ...
}
```

1. Task 1 (add_to_bucket): map-entry read to register x
2. Task 2 (reset_bucket): map-entry write 0
3. Task 1 (add_to_bucket): bit-mask read to register y
4. Task 1 (add_to_bucket): or register x and y to register z
5. Task 1 (add_to_bucket): register z write to map_entry

The map-entry will not be resetted to 0. Not as critical, as only this one chunk of the bucket is not reset.

# Take Aways

- The bitmap has the advantage of scaling at O(1) which does not actually matter much as long as count is lower than 1k.
- The optimized bitmap 1 solution with inlined `set_id()` and `get_id()` functions has the most efficient insert while the custom set 2 with generation values has the most efficient reset. The performance of the inserts is more important than the performance of the resets.
- The sets 1 and 3 have the least memory usage when capacity is below 2048 IDs.
- The performance impact of critical section is huge in our tests.

# Conclusion

We would recommend further testing with a variant that removes critical section but to counter act the race conditions:
- decrease chunk size from 32 to 8 bit
- use `std::atomic` for counters (overhead of incrementing goes down from 1.257 us to 47 us)

An alternative could be to enable/disable callback during reset (not yet tested).

No source file, test, benchmark command, or specific implementation target is named. Start by locating the add_to_bucket and reset_bucket entry points and the SeenIdsSet_1/SeenIdsSet_2 implementations, then determine which data structure the issue expects to change. Done would require a decided scope and reproducible benchmark results comparing insertion and reset performance.

Written by the indexing model from the issue text.