[Media] AtomicSlotmap - fast and lockfree alternative to Mutex<Slotmap>
![[Media] AtomicSlotmap - fast and lockfree alternative to Mutex<Slotmap>](https://i.redd.it/isk48yqcp8gh1.png)
I've had a unique problem: I've been developing an engine for the past two years where every piece of the game logic is written through wasm/libloaded plugins, hence everything has to be FFI-safe, so I've had to use handles to refer to engine objects like textures and buffers. SlotMap was the perfect solution - but I've always wanted everything to be thread-safe, so my graphics backend has ended up as a huge pile of Mutex<SlotMap<...>>s. Well, about half a year ago, my fascination for lockfree data structures has gotten the best of me and I've decided to write a SlotMap that's lockfree.
The structure is perfect for minimizing latency, as it allows for multiple readers at the same time, while still allowing for insertions to happen (they don't block one another at all). It works perfectly in places like renderers where I, for instance, use wgpu and none of the exposed resources have mutable methods anyways. Note that it cannot return mutable references to items.
This is a data structure so it has plenty of unsafe code, but it has fuzz tests, loom tests, tests meant to run with miri and regular tests, all of which pass. I've been using the crate for the past few months with no issues, actually I intended to release it back then, but oh well, I do love procrastinating (also its kinda scary releasing something like a data structure, but as said, I did my best to make sure its all safe), so here I am doing what I should've done a long time ago. Perhaps someone will find it useful.
Reads, uncontended or not, are fast (worst-case comparable to mutexed slotmap). Uncontended insertions are relatively performant, with singlethreaded insertion tests showing about the same performance as a mutexed slotmap. The worst-case scenario in terms of usage is pure insertions with high contention. I got mixed results because my i5 performed quite well in that scenario (in fact, it somtimes outperformed the Mutex solutions) whereas my M2, depending on the contention, showed different results depending on the exact contention (starting at better performance, then 6x worse at nproc cores at the same time, then 2x worse at nproc * 2 cores at the same time). Note that if ~10% of the operations involve insertions and the rest is reads, which is a more real-life workload, the AtomicSlotMap seems to outperform the mutexed slotmap in all multithreaded tests. Hopefully the benchmarks are relatively true-to-life :)