Hello everyone, I just published a crate beach_map. I had to get a little creative with the name but it’s just a slotmap.
A slotmap is a data structure designed to provide fast access and iteration while also using a unique identifier that does not get invalidated*.
To me it feels like a vector and a hashmap had a baby.
The implementation is simple, you have 3 vectors: ids, slots and data.
-
ids stores tuples (usize, version), usize is a data index or a node inside a linked list of available ids and version is generic, defaulting to u32
-
slots is used when removing items, it maps each element with its id in the ids vector
-
data just stores the elements
When you want to access an element you use its id composed of (usize, version) the usize is an index into the ids vector, if the versions match, you jump to the data vector and get your value.
There is already a slotmap crate using a different approach. It provides serde (de)serialization and secondary map. I’m planning to implement serde at some point but I don’t like secondary maps, I feel it’s way too easy to desynchronise them and end up with a broken state. Also, you can store usize number of elements and shrink the allocated space of a BeachMap.
I made some small tests on my computer to see how my implementation compare performance wise:
-
Insertion 3 times slower than SlotMap and 1.5 times slower than HopSlotMap
-
Removal similar
-
Iteration 8 times faster
*You can have an issue if the type wraps and you try to get a value with a key with the exact version one wrap back, but you can choose the type so if you really don’t want this to happen you can use a u64 or u128, it’s a little over kill but you can.