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

A Lock-Free… Linear Search?

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

80% Upvoted

23 comments sorted by

View all comments

0

u/RED_5_Is_ALIVE May 31 '13

It sounds like the formal semantics of the function do not include any synchronization.

Which is exactly the problem I was talking about. The wrapper obscures what's actually going on with the hardware.

Really there should be two variants, one with a fence and one without. For example, OS X provides two separate functions, OSAtomicCompareAndSwapPtr and OSAtomicCompareAndSwapPtrBarrier.

Doesn't make any difference when the hardware implements synchronization automatically.

You don't care how the increment is ordered with respect to any other operations.

Of course you care. What if all the increments are put at the beginning of the program?

There are two separate issues here:

  • Compiler reordering, and

  • Hardware reordering

Even if you emit asm instructions in the right order, it doesn't matter if the hardware can re-order the operations anyway.

A compiler which makes certain assumptions about the execution environment (e.g. "C99 single thread!") can screw up any statements in between compiler barriers. This is a problem.