A fast, contiguous, Windows slot map implementation
Hey guys, I was inspired by a recent post which implemented a hierarchical bitset slot map, and I figured I knew a faster design.
That post:
(https://www.reddit.com/r/cpp/comments/1s06kjv/slot_map_implementation_for_c20/)
This container features stable handles to elements, fast insert, erase, optional versioning, fast iteration through bit scanning intrinsics.
The API deliberately leaves in a good number of sharp edges, I know that is taboo, but I made it as safe as I could without pessimizing the very hot paths.
I would position it in the same realm as something like plf::colony, that is, good for high churn, fast lookups, fast sparse iteration, ECS or game engine workloads.
Compared to a sparse set (sparse + dense array), this slot map should be slower in iteration, and faster in lookups, insert, and erase.
How it works is roughly:
Contiguous VM backed storage,. Contiguous bitset for marking dead slots. Free list is FILO stack intrusively embedded in storage. Iterator scans words with _tzcnt_u64, and pops bits off using _blsr_u64. Lookups are direct access.
There are some benchmarks on the repo, though they are microbenchmarks and not at all conclusive.
The repo documents all the sharp edges I could think of. The biggest sharp edge is: The accessors are not safe against random fuzzed integers. For performance reasons.
Let me know if you have any questions.