3 ms·
How do you think a lock-free map works? Pretty much every fundamental lock-free data structure is built around pointers. It's true that a static array can wor
by haberman 9y ago
How do you think a lock-free map works?
Pretty much every fundamental lock-free data structure is built around pointers. It's true that a static array can work if you're willing to commit to a fixed size up-front (and pre-allocate that entire fixed size), but that is often too limiting for practical use.
> This is also ignoring the issue that global heap memory allocation locks anyway, so allocating a new object is already taking a lock every time.
Any memory allocator optimized for multi-threaded performance will have a thread-local or CPU-local cache that can allocate without taking a lock.
- CyberDildonics 9y agoNot all lock free maps work the same. The ones I've written didn't use pointers. Even an allocator with a thread local cache will still have to lock to map in more memory. This might be unavoidable all together, but allocating memory from a heap and using the pointer not only is inefficient because of the allocation itself as well as the huge increase in the number of times a system call has to be made, but also due to the fact that access now means you have to jump around in memory to find anything. Resizing contiguous memory is a separate problem, not a show stopper. Multiple buffers with an atomic switch is one way to confront it. Having all writes go to a new buffer while reads try the new buffer first but try the old buffer second if they can't find anything is one way to ensure that all reads stay lock free.