prataprc / cmap Goto Github PK

Along with memory book-keeping accessor functions can count number of compact() operations triggered by remove() access and number of retry operation due to recursive compacts and concurrent updates.

Compute the min, max and average depth of the trie as part of Stats{}.

Right now len() API does a full table walk to count the number of items indexed. Since we cannot guarantee point-in-time-snapshot, why don't we maintain n_count that gets atomically incremented or decremented for insert/delete operations. This can make len() call very cheap.

We calculate hamming distance by counting ones in u32 type. We are using u32::count_ones() for this purpose. Not sure how rust will compile to target platform. More research is needed to understand this cost of count_ones for different platforms.

When we compile bin/perf with pprof feature and run it via valgrind there seem to be memory-leaks. Is that normal ?

$ cargo build --release --bin perf --features=perf,pprof
$ valgrind --leak-check=full --show-leak-kinds=all --track-origins=yes ~/.cargo/target/release/perf --loads 1000000 --gets 100000

Results in:

==79781== LEAK SUMMARY:
==79781==    definitely lost: 327,104 bytes in 2 blocks
==79781==    indirectly lost: 17,563,648 bytes in 4,096 blocks
==79781==      possibly lost: 0 bytes in 0 blocks
==79781==    still reachable: 24,606,855 bytes in 12,003 blocks
==79781==         suppressed: 0 bytes in 0 blocks

New items are always indexed in the Node{} type, which holds an array of atomi-ptr to child. For Insert and Remove operation, which is going to modify the array, we will have to do CoW (Copy-no-Write) operation to handle concurrent writes. But for updating
older child pointer with new updated item we can use AtomicStore and avoid CoW.

Not sure about the performance advantages this might bring. If we find that there is no performance improvement, then we can replace AtomicPtr with Box.

Right now data-structure using SeqCst ordering for atomic operation, which is the strictest variant. Explore more relaxed ordering and measure performance improvements. May be some one with deeper experience with atomic instructions and its
implication on CPU execution can throw more light.