An introduction to lockless algorithms [LWN.net]

An introduction to lockless algorithms

Posted Feb 20, 2021 9:13 UTC (Sat) by pbonzini (subscriber, #60935)
In reply to: An introduction to lockless algorithms by kurogane
Parent article: An introduction to lockless algorithms

Yes, exactly.

On one hand it may not happen on all processors, and details may vary depending on the microarchitecture. On x86 that reordering cannot happen, on ARM and PowerPC it might.

But on the other hand the compiler might always be reordering stuff behind your back. The big insight of the C++ committee was that the same abstraction could cover both processor-level and compiler-level reorderings.

to post comments

An introduction to lockless algorithms

Posted Feb 20, 2021 11:04 UTC (Sat) by kurogane (guest, #83248) [Link] (1 responses)

(thumbs-up sign)

I appreciated this confirmation very much.

An introduction to lockless algorithms

Posted Feb 20, 2021 20:31 UTC (Sat) by danobi (subscriber, #102249) [Link]

Thanks for asking -- had the same questions myself.

An introduction to lockless algorithms

Posted Feb 21, 2021 19:13 UTC (Sun) by khim (subscriber, #9252) [Link] (2 responses)

> On x86 that reordering cannot happen, on ARM and PowerPC it might.

Tiny correction: on x86 it can and will happen. You need memory barriers there, too.

After reading the aforementioned article I was confused for some time: memory barriers arrived on x86 with SSE… yet SMP was supported for more than decade by that time! Some investigation showed that any instruction with lock prefix acts as a memory barrier on x86. But if there are not memory barriers at all… yes, it does happen on x86, too.

An introduction to lockless algorithms

Posted Feb 21, 2021 19:16 UTC (Sun) by khim (subscriber, #9252) [Link]

After looking on that article again I have realized that Jeff added addendum to the end which reveals all the gory details about lock and xchg. So there are no mystery anymore…

An introduction to lockless algorithms

Posted Feb 21, 2021 20:51 UTC (Sun) by pbonzini (subscriber, #60935) [Link]

It can't happen until part 3. :) This article and the next one are only concerned with load-load and store-store reordering, which are not possible on x86.