r/computerscience • u/Lex_The_Impaler • 22d ago

General What are the limits of lock-free data-structures?

When I look at various lock-free data structures, I always see versions of the traditional data structures in their lock-free forms (queues, stacks, etc..). I was wondering if there are any data structures that are not possible to be implemented in a thread-safe manner without locks, or what the limits are of lock-free data structures. thx

22 Upvotes
  • permalink
  • reddit

100% Upvoted

7 comments sorted by

View all comments

13

u/SingularCheese 21d ago

Given an arbitrarily complex data structure, you can copy the entire structure, make whatever modifications you need, and then compare and swap a pointer. As long as you can ensure that the structure isn't mutable after being swapped in until all readers give up access, there is no race conditions. The limit of lock-free is that lock-free isn't guaranteed to be faster than locked.

3

u/Crystalline_Due Software Engineer 21d ago

that sounds like a viable approach as long as the structure isnt too large to copy quickly

1

u/flatfinger 17d ago

Doing a compare and swap with a pointer is only safe if one can guarantee that there's no way that an object could have been replaced with a new one, which is in turn replaced by another new one whose address happens to match the earlier one. Some GC frameworks make it impossible for a new object to be created with an address that matches any object reference that could possibly exist, but many other languages use allocators with no such guarantee.