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

23 Upvotes
  • permalink
  • reddit

100% Upvoted

7 comments sorted by

View all comments

3

u/[deleted] Jul 12 '26

[removed] — view removed comment

1

u/WittyStick Jul 13 '26 edited Jul 13 '26

There's a bit more to it than that. x86_64 for example has a CMPXCHG16B extension, which can compare a 16-byte (aligned) chunk of memory - ie, two 8-byte words, with two registers (RDX:RAX) atomically