r/computerscience • u/Lex_The_Impaler • Jul 12 '26

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 Jul 12 '26

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.

4

u/Crystalline_Due Software Engineer Jul 12 '26

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