6 ms·

Lock elision in the GNU C library

71 points by AndreyKarpov 14y ago

davidw 14y ago
Am I the only one with a weird enough mind to have pictured Ellison (Larry) locked in the GNU C Library? Perhaps chained in a buffer with a never ending loop of "join us now and share the software"... Very interesting article in any case.
- hinathan 14y ago
  I did that too. Weird.
jws 14y ago
About using the Intel "Transactional Synchronization Extension"† (TSX) from the upcoming Haswell processors to provide a "fast path" to lock code. The code would first attempt to just do what it wants, but within a memory transaction. If the memory transaction cannot commit, there is a conflict from another core or thread, then it goes to the regular slow path with the locks. If applied at the right granularity almost all of your atomic operations should succeed with the TSX path and you will rarely invoke the heavier lock based code. There is talk of performance measurement, but no numbers in the article, probably because Haswell isn't released. ␄ † http://software.intel.com/en-us/blogs/2012/11/06/exploring-intel-transactional-synchronization-extensions-with-intel-software http://software.intel.com/en-us/blogs/2012/11/06/exploring-i...
Symmetry 14y ago
Interesting. Haskell (or at least GHC) uses software transactional memory pretty heavily. They currently use llvm as the back end, though, so won't benefit from these changes in glibc. I wonder if whatever library used there by default will start to incorporate these features anytime soon?
- sparky 14y ago
  The libc one uses is orthogonal to the compiler, modulo support for any language extensions the libc might use. LLVM supports glibc just fine, and will use it by default on Linux systems. That said, whether GHC can make more use of glibc's TSX support (as opposed to generating TSX instructions itself) than any arbitrary C program depends on any impedance mismatch that may exist between the elided lock wrappers and GHC's own STM semantics. No idea if GHC has a way to reason about libc-managed locks.
callan 14y ago
HLE is a pretty nifty implementation (note: I work for Intel) and an interesting use of CISC. IA instructions can optionally contain a prefix, such as LOCK, address and operand override (use 16, 32, or 64 bits), and repeat (REP). For example, in Linux, a single "REP STOS" (repeat store string) instruction is used to zero-out the kernel's BSS region. REP can also be added to instructions that don't use it, and the CPU will simply ignore it--this is defined behavior. For HLE, using REP in front of certain instructions on a spinlock will begin or end a single memory transaction without actually writing the spinlock value. Of course, on older CPUs, the REP will be ignored and the spinlock read/write will occur. On CPUs that support HLE: if another memory agent accesses the spinlock, the transaction will be canceled.
rayiner 14y ago
I think TSX is one of the most exciting architectural advancements to come around in a long time. There are lots of situations where memory could theoretically be modified by multiple threads simultaneously, but where conflicts will almost never occur in practice. Applications tend to be coded to avoid writes to the same memory from multiple cores not just for correctness reasons but because it causes cache lines to bounce between cores. However, because of the theoretical possibility of simultaneous access, you still have to use a relatively heavyweight lock to ensure correctness. TSX promises to lower the overhead dramatically in such cases. I don't think it's clear yet how it will be implemented, but Dave Kanter over at RWT has speculated it will leverage the cache coherence protocol: http://www.realworldtech.com/haswell-tm http://www.realworldtech.com/haswell-tm. To support cache coherency, cores already communicate with each other about reads and writes to cache lines. Multiple cores can have a line in their cache, but if any core modifies their copy, they have to send a message to the other cores signaling that their old copies are invalid (somewhat more technical description: http://www.di.unipi.it/~vannesch/SPA%202010-11/Silvia.pdf http://www.di.unipi.it/~vannesch/SPA%202010-11/Silvia.pdf). Kanter speculates that TSX uses this existing mechanism to cheaply support transactions. During a transaction, each core keeps track of the cache lines it has read or written to during the transaction. If it gets a message that another thread has written to a line it read from, or otherwise read from a line it wrote to, it aborts the transaction. Otherwise, the transaction commits successfully. This theoretically allows transactions that don't conflict to be handled completely locally to the core.
- haberman 14y ago
  This only seems to help the uncontended case though; under contention it sounds like things will be just as expensive as before (or even more so). Correct me if I'm wrong but this sounds like "shared-state multithreading will be faster, as long as you don't have any parallelism." There is no free lunch in shared-memory architectures. But there are lots of techniques for addressing the problem. One of my favorite ones these days is to have a set of states, one per CPU, that each program writes to in its fast path, that can then be periodically merged into a global state.
  - rayiner 14y ago

71 points by AndreyKarpov 14y ago

Am I the only one with a weird enough mind to have pictured Ellison (Larry) locked in the GNU C Library? Perhaps chained in a buffer with a never ending loop of "join us now and share the software"... Very interesting article in any case.

hinathan 14y ago
I did that too. Weird.

jws 14y ago

About using the Intel "Transactional Synchronization Extension"† (TSX) from the upcoming Haswell processors to provide a "fast path" to lock code. The code would first attempt to just do what it wants, but within a memory transaction. If the memory transaction cannot commit, there is a conflict from another core or thread, then it goes to the regular slow path with the locks. If applied at the right granularity almost all of your atomic operations should succeed with the TSX path and you will rarely invoke the heavier lock based code. There is talk of performance measurement, but no numbers in the article, probably because Haswell isn't released. ␄ † http://software.intel.com/en-us/blogs/2012/11/06/exploring-intel-transactional-synchronization-extensions-with-intel-software http://software.intel.com/en-us/blogs/2012/11/06/exploring-i...

Symmetry 14y ago

Interesting. Haskell (or at least GHC) uses software transactional memory pretty heavily. They currently use llvm as the back end, though, so won't benefit from these changes in glibc. I wonder if whatever library used there by default will start to incorporate these features anytime soon?

sparky 14y ago
The libc one uses is orthogonal to the compiler, modulo support for any language extensions the libc might use. LLVM supports glibc just fine, and will use it by default on Linux systems. That said, whether GHC can make more use of glibc's TSX support (as opposed to generating TSX instructions itself) than any arbitrary C program depends on any impedance mismatch that may exist between the elided lock wrappers and GHC's own STM semantics. No idea if GHC has a way to reason about libc-managed locks.

callan 14y ago

HLE is a pretty nifty implementation (note: I work for Intel) and an interesting use of CISC. IA instructions can optionally contain a prefix, such as LOCK, address and operand override (use 16, 32, or 64 bits), and repeat (REP). For example, in Linux, a single "REP STOS" (repeat store string) instruction is used to zero-out the kernel's BSS region. REP can also be added to instructions that don't use it, and the CPU will simply ignore it--this is defined behavior. For HLE, using REP in front of certain instructions on a spinlock will begin or end a single memory transaction without actually writing the spinlock value. Of course, on older CPUs, the REP will be ignored and the spinlock read/write will occur. On CPUs that support HLE: if another memory agent accesses the spinlock, the transaction will be canceled.

rayiner 14y ago

I think TSX is one of the most exciting architectural advancements to come around in a long time. There are lots of situations where memory could theoretically be modified by multiple threads simultaneously, but where conflicts will almost never occur in practice. Applications tend to be coded to avoid writes to the same memory from multiple cores not just for correctness reasons but because it causes cache lines to bounce between cores. However, because of the theoretical possibility of simultaneous access, you still have to use a relatively heavyweight lock to ensure correctness. TSX promises to lower the overhead dramatically in such cases. I don't think it's clear yet how it will be implemented, but Dave Kanter over at RWT has speculated it will leverage the cache coherence protocol: http://www.realworldtech.com/haswell-tm http://www.realworldtech.com/haswell-tm. To support cache coherency, cores already communicate with each other about reads and writes to cache lines. Multiple cores can have a line in their cache, but if any core modifies their copy, they have to send a message to the other cores signaling that their old copies are invalid (somewhat more technical description: http://www.di.unipi.it/~vannesch/SPA%202010-11/Silvia.pdf http://www.di.unipi.it/~vannesch/SPA%202010-11/Silvia.pdf). Kanter speculates that TSX uses this existing mechanism to cheaply support transactions. During a transaction, each core keeps track of the cache lines it has read or written to during the transaction. If it gets a message that another thread has written to a line it read from, or otherwise read from a line it wrote to, it aborts the transaction. Otherwise, the transaction commits successfully. This theoretically allows transactions that don't conflict to be handled completely locally to the core.

haberman 14y ago
This only seems to help the uncontended case though; under contention it sounds like things will be just as expensive as before (or even more so). Correct me if I'm wrong but this sounds like "shared-state multithreading will be faster, as long as you don't have any parallelism." There is no free lunch in shared-memory architectures. But there are lots of techniques for addressing the problem. One of my favorite ones these days is to have a set of states, one per CPU, that each program writes to in its fast path, that can then be periodically merged into a global state.
- rayiner 14y ago