An Introduction to Lock-Free Programming

Re:An Introduction to Lock-Free Programming by preshing on Tuesday June 12, 2012 @12:54PM (#4101385)

I totally agree with you about the dangers of lock-free programming, and that every programmer will certainly make mistakes. I feel strongly enough about it that I actually wrote several paragraphs about the importance of stress testing lock-free algorithms, which I eventually decided to break off into a separate post... I might get around to publishing that, we'll see. We're not the first to feel this way :)

> The are actually several levels of lock-freedom defined in the literature: lock-freedom, wait-freedom, and obstruction-freedom. For more info see: http://en.wikipedia.org/wiki/Non-blocking_algorithm

It's true, and I had a hard time reconciling that Wikipedia page with how others had been describing lock-free programming, which is why I spent so much of the post on semantics.

> One benefit of load-linked/store-conditional (often abbreviated LL/SC) is that it avoids the ABA problem

Good point. Though I suspect if you access other cache lines between the LL & SC, it may invalidate the reservation.

> I don't think this is true about x86/64.

It is true about x86/64, at least for the most common, non-SSE instructions and normal, non-write-combined memory. I'll update the post to be more specific. See volume 3, section 8.2.2 of the Intel 64 and IA-32 Developer's Manuals: (http://www.intel.com/content/www/us/en/processors/architectu...)

- Reads are not reordered with other reads. - Writes are not reordered with older reads. - Writes to memory are not reordered with other writes (with a few exceptions for special instructions)

[ Parent | on HN ]

Re:An Introduction to Lock-Free Programming by ajross on Tuesday June 12, 2012 @04:30PM (#4102652)

> It is true about x86/64, at least for the most common, non-SSE instructions and normal, non-write-combined memory

To embellish further and avoid jargon for those who didn't parse this, it basically means "It is true except for the interfaces which explicitly document where it's not.".

Intel CPUs have had a "uncached/write-combining" mode for years (originally specified through special MTRR registers, then in the Page Attribute Table, and most recently in the "non-temporal" MOV instructions in SSE) which officially relaxes the requirements for store ordering. The reason for having two sets of semantics is performance: when dealing with uncached memory (typically memory used by another device, e.g. a video framebuffer) combining a bunch of writes to the same DRAM burst unit (or set of such units) is much faster than doing each word-sized I/O individually.

[ Parent | on HN ]

Re:An Introduction to Lock-Free Programming by haberman on Tuesday June 12, 2012 @02:02PM (#4101796)

> It is true about x86/64

Yes, sorry I misspoke initially about stores being reordered, but it does still appear that stores can be reordered after loads, see: http://bartoszmilewski.com/2008/11/05/who-ordered-memory-fen... . (Your Intel manual reference is surely a more authoritative source but I'm not able to do a deep dive into it at the moment).

[ Parent | on HN ]

Re:An Introduction to Lock-Free Programming by preshing on Tuesday June 12, 2012 @02:14PM (#4101875)

There's no contradiction. Normally, the x86/64 memory model is quite strong, preserving LoadLoad, LoadStore, and StoreStore ordering. But doesn't preserve StoreLoad ordering; eg. stores can be reordered after loads, as you point out. As I understand it, that's mainly because there's a limit to how quickly each store can be seen by other processors.

[ Parent | on HN ]

Re:An Introduction to Lock-Free Programming by ajross on Tuesday June 12, 2012 @04:35PM (#4102684)

I'm pretty sure it's because of the store forwarding hardware. Intel CPUs can return a successful load of a recently-stored address with low latency (basically by keeping a special purpose cache of recent store addresses in the pipeline and returning their values before the actual commit). But that means that the "store" is viewed from the issuing CPU to have committed long before loads that might have been filled by caches on the other CPUs. There's no way to preserve both this optimization and a unified order.

[ Parent | on HN ]