Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

An Introduction to Lock-Free Programming

preshing.com

Post reply on HN
Print view View original

11–20 of 21 posts

Re: An Introduction to Lock-Free Programming

#11

Post by preshing »

Retric wrote: post #9
preshing wrote: post #7

Earlier quoted context omitted.

Actually, I thought it was pretty clear in the article that it's not ok to use locks (mutexes) under the definition given. I tried pretty hard to use the most widely accepted definition of lock-free, even exchanging e-mails with Maurice Herlihy about it.

In this sense, the lock in lock-free does not refer directly to mutexes, but rather to the possibility of “locking up” in some way, whether it’s deadlock, livelock — or even due to hypothetical thread scheduling decisions made by your worst enemy. Suppose you had an operation that was guaranteed to either add your input to some location in memory or fail gracefully in some fixed amount of time. It's first come first…

Based on your comment, I should probably be more precise and say: "the possibility of 'locking up' the entire application in some way". I'll update the post. There's nothing about this definition that prohibits a single thread from starving.

Re: An Introduction to Lock-Free Programming

#12

Post by sbahra »

rdtsc wrote: post #5

There is also a niche research area of lock-free data structures and algorithms. On a more practical side, check out http://www.liblfds.org/ -- it is a library of lock free data structures in C. (I am not the author). I have successfully used this library in some realtime projects.

http://concurrencykit.org/ is also available, used in several production systems.

Re: An Introduction to Lock-Free Programming

#14

Post by scott_s »

haberman wrote: post #8

Nice article, though I think that any intro-level material on lock-free programming should always include a "don't try this at home for anything important" warning. Until you have some experience with this stuff you will almost certainly make mistakes, but these mistakes might only manifest themselves as crashes in extremely rare circumstances. I wrote my first lock-free code in 2004 based on reading some papers by M…

To support your first point, I implemented Maged's lock-free allocator so we could compare against it (http://www.scott-a-s.com/files/michael.tar.gz), and I never got it working correctly on Itanium. I spent weeks trying to figure out what was wrong. I eventually concluded that I did not understand the Itanium architecture and the algorithms used in the allocator well enough to be confident I could fix it - and that it wasn't worth improving my understanding of either. (I asked Maged if he had any experience with his allocator on Itanium, and he did not.)

Re: An Introduction to Lock-Free Programming

#15

Post by scott_s »

Retric wrote: post #6
tptacek wrote: post #3

The idea that made this click for me 10 years or so ago was that distributed systems express concurrent processes but can't reasonably use locks; model your threads/processes/whatever as if they were nodes in a distributed system, and use distributed system techniques to ensure things converge.

That's not exactly a shared memory model. A better example would be a static look-up table for fixed game state information and a bunch of AI worker threads. With the correct protocol you can even write to that shared memory. For example a sudoku solver where each tread looks for contradictions and then overwrites the shared states with their findings. This works because there is no contradictions, dirty reads are ok…

The article's author uses a less strict defintion of lock free where it's ok to use locks for individual atomic operations like counters.

The author's definition does not allow one to use locks to make individual operations atomic. A process could always crash after obtaining the lock, but before releasing it, causing the entire application to become stuck.

Re: An Introduction to Lock-Free Programming

#16

Post by scott_s »

preshing wrote: post #11
Retric wrote: post #9

Earlier quoted context omitted.

In this sense, the lock in lock-free does not refer directly to mutexes, but rather to the possibility of “locking up” in some way, whether it’s deadlock, livelock — or even due to hypothetical thread scheduling decisions made by your worst enemy. Suppose you had an operation that was guaranteed to either add your input to some location in memory or fail gracefully in some fixed amount of time. It's first come first…

Based on your comment, I should probably be more precise and say: "the possibility of 'locking up' the entire application in some way". I'll update the post. There's nothing about this definition that prohibits a single thread from starving.

I think it's easier to phrase it in the positive sense: at least one thread is always making progress towards completion.

Re: An Introduction to Lock-Free Programming

#17

Post by haberman »

preshing wrote: post #10
haberman wrote: post #8

Nice article, though I think that any intro-level material on lock-free programming should always include a "don't try this at home for anything important" warning. Until you have some experience with this stuff you will almost certainly make mistakes, but these mistakes might only manifest themselves as crashes in extremely rare circumstances. I wrote my first lock-free code in 2004 based on reading some papers by M…

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 a…

> 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).

Re: An Introduction to Lock-Free Programming

#18

Post by preshing »

haberman wrote: post #17
preshing wrote: post #10

Earlier quoted context omitted.

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 a…

> 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).

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.

Re: An Introduction to Lock-Free Programming

#19

Post by ajross »

preshing wrote: post #10
haberman wrote: post #8

Nice article, though I think that any intro-level material on lock-free programming should always include a "don't try this at home for anything important" warning. Until you have some experience with this stuff you will almost certainly make mistakes, but these mistakes might only manifest themselves as crashes in extremely rare circumstances. I wrote my first lock-free code in 2004 based on reading some papers by M…

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 a…

> 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.

Re: An Introduction to Lock-Free Programming

#20

Post by ajross »

preshing wrote: post #18
haberman wrote: post #17

Earlier quoted context omitted.

> 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).

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.

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.
Post reply on HN