5 ms·

Lock-free programming for the masses

188 points by antouank 10y ago

RossBencina 10y ago
The library is called "reagent". It's for Ocaml. From what I gather skimming the post, the operations are: "swap" (synchronous rendezvous exchange similar to CSP channels maybe) and "upd" (similar to CAS). With composition operators (sequential, conjunction, disjunction). The implementation aggregates composed operations into a transaction. It looks as though the operators would let you implement something along the lines of Go's select() for example. From the post: > The key idea behind the implementation is that the reagent transaction executes in two phases. The first phase involves collecting all the compare-and-swap (CAS) operations necessary for the transaction, and the second phase is invoking a k-CAS operation (emulated in software) > Reagents are less expressive than STM, which provides serializability. But in return, Reagents provide stronger progress guarantee (lock-freedom) over STM (obstruction-freedom) Interesting.
- vardump 10y ago
  > second phase is invoking a k-CAS operation (emulated in software) Sounds like a normal CAS performed on a pointer.
  - naasking 10y ago
    It synchronizes multiple CAS operations an ensures they all execute "atomically" upon k-CAS completion.
- kaeluka 10y ago
  It's based on the (fantastic!) paper by Aaron Turon: www.ccs.neu.edu/home/turon/reagents.pdf
programLyrique 10y ago
This library is built upon multicore Ocaml. We've spoken about multicore OCaml for a long time, and apparently, the last tentative of it is being developed. When will multicore Ocaml land into the stable version of the compiler?
- kcsrk 10y ago
  (I work on multicore OCaml) Multicore OCaml has been steadily under development, with the latest updates here: https://ocaml.io/w/Multicore https://ocaml.io/w/Multicore. While I can't promise when multicore lands in trunk, a stable-alpha version installable through opam should be ready in the next few weeks.
naasking 10y ago
See the LtU post [1] for the paper backing this project. [1] http://lambda-the-ultimate.org/node/5237 http://lambda-the-ultimate.org/node/5237
asb 10y ago
There was a little bit of discussion when this was previously on HN: https://news.ycombinator.com/item?id=11893911 https://news.ycombinator.com/item?id=11893911 (linking for completeness - I'm really glad this has seen more attention after resubmission!)
novaleaf 10y ago
as a 'expert' multithreading programmer, i can confidently say that most developers should stay away from fine-graned multithreading (generally speaking of course). You will have much greater productivity gains and less debugging headaches (race conditions!) If you architct your program to be coarse-grained (modules running asynchronously, but each module not multithreaded) or even better, the entire app being single threaded and just fork it to scale horizontally.
- MaulingMonkey 10y ago
  Even if you have a legitimate need to get fine-grained, for me the most common use of lock free programming is to implement the underlying infrastructure for task based systems, where the individual tasks desperately try to stay away from multi-threading hazards - by e.g. keeping shared data immutable (no need for 'lock-free programming'), and keeping mutated data task-local (not shared between threads, and thus again no need for 'lock-free programming'.) Forking / multi-process architectures are of course the logical extension of this - where you're making the entire program state task local, just to be sure. Rule 37: There is no 'overkill.' There is only 'open fire' and 'I need to reload.'
deadgrey19 10y ago
This sounded so promising until the OCaml part. The problem is, the masses don't program in OCaml. They program in C# or Java, or C++. So this is really lock-free programming for OCaml, which is a lot less relevant.
- wolfgke 10y ago
  In the original paper (see https://news.ycombinator.com/item?id=11908821 https://news.ycombinator.com/item?id=11908821) it is impplemented in Scala.
  - deadgrey19 10y ago
    How is that different? Neither Scala nor OCaml rank in the top 10 programming languages according to several metrics/organisations [1-5]. Keeping in mind that programming language use is a heavily skewed distribution, OCaml and Scala have almost zero usage relative to the big ones. So, again I must ask, how is this relevant to the masses? [1] http://www.tiobe.com/tiobe_index http://www.tiobe.com/tiobe_index [2] http://pypl.github.io/PYPL.html http://pypl.github.io/PYPL.html [3] http://spectrum.ieee.org/computing/software/the-2015-top-ten-programming-languages http://spectrum.ieee.org/computing/software/the-2015-top-ten... [4] http://redmonk.com/sogrady/2016/02/19/language-rankings-1-16/ http://redmonk.com/sogrady/2016/02/19/language-rankings-1-16... [5] http://www.codingdojo.com/blog/9-most-in-demand-programming-languages-of-2016/ http://www.codingdojo.com/blog/9-most-in-demand-programming-...
Animats 10y ago
It's time for better CPU support for atomic operations. "Backoff, retry, blocking and signalling" is a hack. What we really need is machine level support for short memory transactions. This would be an extension of fence hardware. What's needed is a CPU instruction to fence a critical section and lock up two cache lines while you manipulate them from one CPU, with other CPUs locked out. Transactions should have a hardware instruction cycle limit, so you can't lock up the other CPUs for very long. Then you could do swaps, sets, appends to lists, and such with straightforward code. This locking would be local to the two cache lines - unless two CPUs are trying to hit the same two cache lines, there's no delay. Why two cache lines? That lets you do moves and swaps, and maybe some list and queue manipulation. Those can all be completed in a few instruction cycles.
- hacknat 10y ago
  What happens in a preemption? An OS would have to manage this on a per-process level to ensure that a lock doesn't stick around on a preemption. Now the OS has to remember locking info per-process. Also, on resumption of a process, an OS would need a way of locking, but bypassing the lock to set the registers that have been manipulated, without other CPUs interfering. Your idea is nifty, but it would be a nightmare to implement.
- pizlonator 10y ago
  How is this any better than using a high-speed adaptive lock? I would claim that it's strictly worse, since it limits you to only two cache lines, doesn't have adequate interaction with the OS scheduler, and doesn't scale gracefully for longer critical sections.
  - davidtgoldblatt 10y ago
    I assume interrupts would be disabled or deferred during this section, so you get stronger guarantees on worst-case behavior; hence the bound on the number of cycles a thread is allowed to execute for. On one of the less common unixes (Sun's maybe? I don't totally remember), you could set a bit in some thread-specific part of memory to indicate that you were uninterruptible. If the OS saw that bit was set, it would set a "you need to yield" bit in the same part of memory and then allow the thread to continue (and penalize threads that abused the feature). As a practical matter, I suspect that the scheme proposed wouldn't have advantages over a careful use of HTM. I also suspect that the "lock two cachelines" thing is harder to implement than it sounds. The way Intel implements atomic operations that span cachelines now involves waiting for a interconnect quiescence period (taking O(microseconds)). What's proposed here is strictly more general.
dwarman 10y ago
I always thought "lock free" meant no hidden pauses in execution - a write is a write and a read is a read. The primitives described here will block. How is that different in effect from a lock, albeit one implemented down in the library rather than explicitly by the user? My lock free mechanisms never blocked. And they're used in thousands of emedded devices without failures.

188 points by antouank 10y ago

The library is called "reagent". It's for Ocaml. From what I gather skimming the post, the operations are: "swap" (synchronous rendezvous exchange similar to CSP channels maybe) and "upd" (similar to CAS). With composition operators (sequential, conjunction, disjunction). The implementation aggregates composed operations into a transaction. It looks as though the operators would let you implement something along the lines of Go's select() for example. From the post: > The key idea behind the implementation is that the reagent transaction executes in two phases. The first phase involves collecting all the compare-and-swap (CAS) operations necessary for the transaction, and the second phase is invoking a k-CAS operation (emulated in software) > Reagents are less expressive than STM, which provides serializability. But in return, Reagents provide stronger progress guarantee (lock-freedom) over STM (obstruction-freedom) Interesting.

vardump 10y ago
> second phase is invoking a k-CAS operation (emulated in software) Sounds like a normal CAS performed on a pointer.
- naasking 10y ago
  It synchronizes multiple CAS operations an ensures they all execute "atomically" upon k-CAS completion.
kaeluka 10y ago
It's based on the (fantastic!) paper by Aaron Turon: www.ccs.neu.edu/home/turon/reagents.pdf

programLyrique 10y ago

This library is built upon multicore Ocaml. We've spoken about multicore OCaml for a long time, and apparently, the last tentative of it is being developed. When will multicore Ocaml land into the stable version of the compiler?

kcsrk 10y ago
(I work on multicore OCaml) Multicore OCaml has been steadily under development, with the latest updates here: https://ocaml.io/w/Multicore https://ocaml.io/w/Multicore. While I can't promise when multicore lands in trunk, a stable-alpha version installable through opam should be ready in the next few weeks.

naasking 10y ago

See the LtU post [1] for the paper backing this project. [1] http://lambda-the-ultimate.org/node/5237 http://lambda-the-ultimate.org/node/5237

asb 10y ago

There was a little bit of discussion when this was previously on HN: https://news.ycombinator.com/item?id=11893911 https://news.ycombinator.com/item?id=11893911 (linking for completeness - I'm really glad this has seen more attention after resubmission!)

novaleaf 10y ago

as a 'expert' multithreading programmer, i can confidently say that most developers should stay away from fine-graned multithreading (generally speaking of course). You will have much greater productivity gains and less debugging headaches (race conditions!) If you architct your program to be coarse-grained (modules running asynchronously, but each module not multithreaded) or even better, the entire app being single threaded and just fork it to scale horizontally.

MaulingMonkey 10y ago
Even if you have a legitimate need to get fine-grained, for me the most common use of lock free programming is to implement the underlying infrastructure for task based systems, where the individual tasks desperately try to stay away from multi-threading hazards - by e.g. keeping shared data immutable (no need for 'lock-free programming'), and keeping mutated data task-local (not shared between threads, and thus again no need for 'lock-free programming'.) Forking / multi-process architectures are of course the logical extension of this - where you're making the entire program state task local, just to be sure. Rule 37: There is no 'overkill.' There is only 'open fire' and 'I need to reload.'

deadgrey19 10y ago

This sounded so promising until the OCaml part. The problem is, the masses don't program in OCaml. They program in C# or Java, or C++. So this is really lock-free programming for OCaml, which is a lot less relevant.

wolfgke 10y ago
In the original paper (see https://news.ycombinator.com/item?id=11908821 https://news.ycombinator.com/item?id=11908821) it is impplemented in Scala.
- deadgrey19 10y ago
  How is that different? Neither Scala nor OCaml rank in the top 10 programming languages according to several metrics/organisations [1-5]. Keeping in mind that programming language use is a heavily skewed distribution, OCaml and Scala have almost zero usage relative to the big ones. So, again I must ask, how is this relevant to the masses? [1] http://www.tiobe.com/tiobe_index http://www.tiobe.com/tiobe_index [2] http://pypl.github.io/PYPL.html http://pypl.github.io/PYPL.html [3] http://spectrum.ieee.org/computing/software/the-2015-top-ten-programming-languages http://spectrum.ieee.org/computing/software/the-2015-top-ten... [4] http://redmonk.com/sogrady/2016/02/19/language-rankings-1-16/ http://redmonk.com/sogrady/2016/02/19/language-rankings-1-16... [5] http://www.codingdojo.com/blog/9-most-in-demand-programming-languages-of-2016/ http://www.codingdojo.com/blog/9-most-in-demand-programming-...

Animats 10y ago

It's time for better CPU support for atomic operations. "Backoff, retry, blocking and signalling" is a hack. What we really need is machine level support for short memory transactions. This would be an extension of fence hardware. What's needed is a CPU instruction to fence a critical section and lock up two cache lines while you manipulate them from one CPU, with other CPUs locked out. Transactions should have a hardware instruction cycle limit, so you can't lock up the other CPUs for very long. Then you could do swaps, sets, appends to lists, and such with straightforward code. This locking would be local to the two cache lines - unless two CPUs are trying to hit the same two cache lines, there's no delay. Why two cache lines? That lets you do moves and swaps, and maybe some list and queue manipulation. Those can all be completed in a few instruction cycles.

hacknat 10y ago
What happens in a preemption? An OS would have to manage this on a per-process level to ensure that a lock doesn't stick around on a preemption. Now the OS has to remember locking info per-process. Also, on resumption of a process, an OS would need a way of locking, but bypassing the lock to set the registers that have been manipulated, without other CPUs interfering. Your idea is nifty, but it would be a nightmare to implement.
pizlonator 10y ago
How is this any better than using a high-speed adaptive lock? I would claim that it's strictly worse, since it limits you to only two cache lines, doesn't have adequate interaction with the OS scheduler, and doesn't scale gracefully for longer critical sections.
- davidtgoldblatt 10y ago
  I assume interrupts would be disabled or deferred during this section, so you get stronger guarantees on worst-case behavior; hence the bound on the number of cycles a thread is allowed to execute for. On one of the less common unixes (Sun's maybe? I don't totally remember), you could set a bit in some thread-specific part of memory to indicate that you were uninterruptible. If the OS saw that bit was set, it would set a "you need to yield" bit in the same part of memory and then allow the thread to continue (and penalize threads that abused the feature). As a practical matter, I suspect that the scheme proposed wouldn't have advantages over a careful use of HTM. I also suspect that the "lock two cachelines" thing is harder to implement than it sounds. The way Intel implements atomic operations that span cachelines now involves waiting for a interconnect quiescence period (taking O(microseconds)). What's proposed here is strictly more general.

dwarman 10y ago

I always thought "lock free" meant no hidden pauses in execution - a write is a write and a read is a read. The primitives described here will block. How is that different in effect from a lock, albeit one implemented down in the library rather than explicitly by the user? My lock free mechanisms never blocked. And they're used in thousands of emedded devices without failures.