5 ms·

I think it's worth thinking in terms of the probability of contention per cycle. If the odds of contention is very low, lock-free will be much better (imagine a

I think it's worth thinking in terms of the probability of contention per cycle. If the odds of contention is very low, lock-free will be much better (imagine accessing a shared data structure which is vast compared to the range of usage in a typical use). Also, I think it's worth noting that it's really not that much more complicated than a simple mutex if you use the default sequential consistency memory order on an atomic. When you start attempting to optimize around certain patterns using the weaker memory orders, yea, things get a lot tougher.

yason 9y ago
If the odds for contention are low then something like a futex is pretty snappy, too. Lockless solutions do naturally fit in certain cases. For example, producer-consumer queues where there's only some invariants that need to be respected. There the producer must not overwrite what the consumer hasn't consumed yet and the consumer must not advance to areas that the producer hasn't yet filled. Using a lockless approach both the producer and the consumer can continue to operate as long as they won't step on each others' toes. Instead, using a mutex or read-write locking would basically make the access to the queue mutually exclusive to the producer and consumer. I, myself, like the approach of building my data out of near-immutable blocks and just replacing the references using atomic compare-and-swap, for example.
- banachtarski 9y ago
  Yup using a layer of indirection definitely works well. Regarding the futex, I definitely agree that most futex implementations on most hardware are designed to spin and resolve quickly in low contention scenarios, but this won't be true on all consoles/hardware/OS configurations. For certain cases (like a game engine), I'd be less inclined to rely on the futex to do the right thing.
  - gpderetta 9y ago
    Futex are a linux kernel-level specific waiting primitive [1]. The point of the OP is that mutex implemented on top of a futex has a purely userspace fast path that needs only a single CAS for each acquire and release in the uncontended space, so in this scenario an userspace spin-lock is not often significantly better (a spin lock release only need a store on some machines though). Spin locks are significantly worse in the contended space though. [1] futexes enable Fast Userspace muTEXES, but futex themselves are kernel space and not particularly fast.
    - chriscappuccio 9y ago
      OpenBSD implements futex now, too. Major league userland responsiveness improvements for futex based mutexes.
- gpderetta 9y ago
  There are two-lock queues that allow consumers to mostly run independently from the producers while still using bog-standard locks. Still you are right that lock-free algos really shine in implementing message queues, but mostly because they can be implemented with fewer or cheaper memory operations, so even in the uncontended case, the lock-free queue can shave some cycles. > I, myself, like the approach of building my data out of near-immutable blocks and just replacing the references using atomic compare-and-swap, for example. Yes, one huge advantage of lock free algorithms is that you can have read mostly data structures with no contentions between readers (most rw-lock implementations do require readers to write on some shared state).
jeff571 9y ago
The lock could still be faster. atomic ops are more expensive than regular opcodes even when there is zero contention. On x86, a lock requires only a single atomic opcode and can be released with a normal write (because of TSO). Since it's uncontended it won't spin at all. Therefore, any alternative lock-free algorithm that uses more than a single atomic op is actually more expensive.
scott_s 9y ago
I think it's usually the other way around: when the odds of contention is very low, locks are better. Uncontended lock acquisition is relatively cheap, and it can be done once. The downside of using a lock is that it prevents other threads which are contending for that lock from proceeding, hence why locks are better when contention is low. Lock free algorithms are generally better when the odds of contention are high, as you can devise algorithms that allow all threads to make progress at the same time. In general, this allows more parallelism, but the cost is that it typically requires more overall atomic operations.
- gpderetta 9y ago
  It depends, on high contention, waiting writer threads will only touch a single shared cache line containing the lock (all the time if spinning, once if there is a proper thread queue). In a lock free algo, the writers might be stepping on each other toes all the time, with heavy cache-line pingpoing, which is not good for general throughput. Lock free algos are very good when you have many pure readers and few or occasional writers.
  - scott_s 9y ago
    In my experience, once you get up to the 100s of threads potentially touching global structures, locks impeded scalability significantly. Even if each of those threads is modifying the global data. The key is to design your algorithms around the kind of structures that are amenable to lock free algorithms. (The experience I'm referring to: http://www.scott-a-s.com/files/pldi2017_lf_elastic_scheduling.pdf http://www.scott-a-s.com/files/pldi2017_lf_elastic_schedulin...)
    - banachtarski 9y ago
      Is a program that has 100s of threads realistic?
      - scott_s 9y ago
        Yes. See the paper I linked to. I work on a parallel and distributed dataflow system called IBM Streams. When we have thousands of our operators running on a large system, it is realistic for there to be 100s of threads.
pizlonator 9y ago
Lock-less algorithms sometimes have more CAS instructions on the critical path, so may be slower under zero contention. I think you’re right in many cases though.

yason 9y ago

If the odds for contention are low then something like a futex is pretty snappy, too. Lockless solutions do naturally fit in certain cases. For example, producer-consumer queues where there's only some invariants that need to be respected. There the producer must not overwrite what the consumer hasn't consumed yet and the consumer must not advance to areas that the producer hasn't yet filled. Using a lockless approach both the producer and the consumer can continue to operate as long as they won't step on each others' toes. Instead, using a mutex or read-write locking would basically make the access to the queue mutually exclusive to the producer and consumer. I, myself, like the approach of building my data out of near-immutable blocks and just replacing the references using atomic compare-and-swap, for example.

banachtarski 9y ago
Yup using a layer of indirection definitely works well. Regarding the futex, I definitely agree that most futex implementations on most hardware are designed to spin and resolve quickly in low contention scenarios, but this won't be true on all consoles/hardware/OS configurations. For certain cases (like a game engine), I'd be less inclined to rely on the futex to do the right thing.
- gpderetta 9y ago
  Futex are a linux kernel-level specific waiting primitive [1]. The point of the OP is that mutex implemented on top of a futex has a purely userspace fast path that needs only a single CAS for each acquire and release in the uncontended space, so in this scenario an userspace spin-lock is not often significantly better (a spin lock release only need a store on some machines though). Spin locks are significantly worse in the contended space though. [1] futexes enable Fast Userspace muTEXES, but futex themselves are kernel space and not particularly fast.
  - chriscappuccio 9y ago
    OpenBSD implements futex now, too. Major league userland responsiveness improvements for futex based mutexes.
gpderetta 9y ago
There are two-lock queues that allow consumers to mostly run independently from the producers while still using bog-standard locks. Still you are right that lock-free algos really shine in implementing message queues, but mostly because they can be implemented with fewer or cheaper memory operations, so even in the uncontended case, the lock-free queue can shave some cycles. > I, myself, like the approach of building my data out of near-immutable blocks and just replacing the references using atomic compare-and-swap, for example. Yes, one huge advantage of lock free algorithms is that you can have read mostly data structures with no contentions between readers (most rw-lock implementations do require readers to write on some shared state).

jeff571 9y ago

The lock could still be faster. atomic ops are more expensive than regular opcodes even when there is zero contention. On x86, a lock requires only a single atomic opcode and can be released with a normal write (because of TSO). Since it's uncontended it won't spin at all. Therefore, any alternative lock-free algorithm that uses more than a single atomic op is actually more expensive.

scott_s 9y ago

I think it's usually the other way around: when the odds of contention is very low, locks are better. Uncontended lock acquisition is relatively cheap, and it can be done once. The downside of using a lock is that it prevents other threads which are contending for that lock from proceeding, hence why locks are better when contention is low. Lock free algorithms are generally better when the odds of contention are high, as you can devise algorithms that allow all threads to make progress at the same time. In general, this allows more parallelism, but the cost is that it typically requires more overall atomic operations.

gpderetta 9y ago
It depends, on high contention, waiting writer threads will only touch a single shared cache line containing the lock (all the time if spinning, once if there is a proper thread queue). In a lock free algo, the writers might be stepping on each other toes all the time, with heavy cache-line pingpoing, which is not good for general throughput. Lock free algos are very good when you have many pure readers and few or occasional writers.
- scott_s 9y ago
  In my experience, once you get up to the 100s of threads potentially touching global structures, locks impeded scalability significantly. Even if each of those threads is modifying the global data. The key is to design your algorithms around the kind of structures that are amenable to lock free algorithms. (The experience I'm referring to: http://www.scott-a-s.com/files/pldi2017_lf_elastic_scheduling.pdf http://www.scott-a-s.com/files/pldi2017_lf_elastic_schedulin...)
  - banachtarski 9y ago
    Is a program that has 100s of threads realistic?
    - scott_s 9y ago
      Yes. See the paper I linked to. I work on a parallel and distributed dataflow system called IBM Streams. When we have thousands of our operators running on a large system, it is realistic for there to be 100s of threads.

pizlonator 9y ago

Lock-less algorithms sometimes have more CAS instructions on the critical path, so may be slower under zero contention. I think you’re right in many cases though.