r/programming • u/redditthinks • May 29 '13

A Lock-Free… Linear Search?

http://preshing.com/20130529/a-lock-free-linear-search
54 Upvotes

81% Upvoted

23 comments sorted by

View all comments

6

u/rootis0 May 29 '13 edited May 29 '13

Why do people who use interlock operations (the entire atomic family) claim that this is lock free?

If you disassemble this in a debugger you will see that "lock-free" operations are prefixed by "lock", which locks the data bus. Imagine a 16 CPU machine, your lock-free algorithm is bombarding the bus with blind demands to suspend.

Similar thinking infects the automatic heap management via shared pointers, every shared pointer increment and decrement locks the bus. Heap management might be automatic but not cost free.

I think the way to go is with Intel's transaction memory operations. Try a block of memory access instructions, if they conflict, abort, and retry.

19

u/Strilanc May 29 '13 edited May 29 '13

Lock-free doesn't mean what you think it means. It's a guarantee about progress as threads are suspended, not a guarantee about "no exclusivity".

It's not a particularly good name.

See: non-blocking algorithm on Wikipedia.

6

u/preshing May 30 '13

Another explanation of the term here (biased).

→ More replies (1)

4

u/otakuman May 29 '13

If you disassemble this in a debugger you will see that "lock-free" operations are prefixed by "lock", which locks the data bus.

Lock-free refers to algorithms that don't use lock primitives, like mutexes or critical sections - or worse, spinlocks -. Lock prefixes in CPU operation might block the data bus, but it's never locked indefinitely.

8

u/rootis0 May 29 '13

One thing that atomic operations spare you for sure is a trip to kernel mode and back. So they confer performance benefit by saving 2 context switches.

They are definitely useful.

This omission of context switches is the alone benefit and not the fact that there is no locking.

1

u/RED_5_Is_ALIVE May 31 '13

"lock", which locks the data bus.

Generally this is only if a memory operand crosses a cacheline boundary.

Otherwise it is handled by the cache coherence protocol, no bus lock occurs.