Piggybacking this question for people interested in the topic:
Which everyday high level data structures you use are built on lock-free implementations?
Clojure's maps/vectors (which are persistent data structures) come to mind for me, for one.
I've written some memory allocators that use lock-free allocation maps. In this case, a 4kb granularity allocator that used compressed free-bitmaps for usage in both userspace and kernelspace.
The entire thing was lock-free, so allocations would never stall on a lock, even if the allocator had to decompress a bitmap (the way compression worked was by looking for free memory ranges and then replacing them by a range expression, which saved a few MB of memory per Gigabyte of memory available, as well as ordering largely free memory blocks to the start of the bitmap list to reduce seek time). Despite the complexity in the allocator, it could serve any number of threads without ever locking up. The worst case was a long latency if a thread had to scan the entire free list for a free block (It would switch to a different allocation behaviour if a thread had more than a dozen failed allocation attempts).
A bunch of ring buffers I've worked with are atomic (ie, lock free), probably the most common application of lock-free stuff.
Interesting! Is this work public somewhere perhaps?
I'm currently working on a similar technique (though with smaller blocks, currently ranging 64-1024 bytes - basically any 5 power-of-twos) for a lock-free allocator intended for real time embedded systems. I use a 32-bit word for each 1024 byte "page", and have a tree structure inside of the word (it takes 31 bits to cover 5 power-of-two ranges).
My code (which only allocs and never frees at the moment) is here:
https://github.com/microsoft/mimalloc
https://github.com/microsoft/mimalloc/blob/master/include/mimalloc-atomic.h
https://plv.mpi-sws.org/genmc/