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.

Repo:
https://github.com/ScallyingMyWag/bitsetmap

https://redd.it/1sbro26
@r_cpp