4 ms·

Just making sure I understand this correctly: so at a high level you're just trading software locks for hardware locks (which are most always more granular)? If

by dcow 9y ago

Just making sure I understand this correctly: so at a high level you're just trading software locks for hardware locks (which are most always more granular)? If you didn't have hardware atomic support, the same "lock free" data structure would be one where locks are held for as few instructions as possible (and that exhibits the same functional characteristics around memory ordering etc.)?

speps 9y ago
No, from what I understand, you can't even do it in software anyway due to how the caches work between cores inside the CPU. Watching this was enlightening to say the least (and the presenter is very good): https://www.youtube.com/watch?v=ZQFzMfHIxng https://www.youtube.com/watch?v=ZQFzMfHIxng
- glandium 9y ago
  Huh, that first example is comparing apples and oranges. This is the "slow" lock-free version from there: std::atomic<unsigned long> sum; void do_work(size_t N, unsigned long* a) { for (size_t i = 0; i < N; ++i) sum += a[i]; } It atomically adds for every iteration of the loop. This is the "fast" mutex-based version: unsigned long sum(0); std::mutex M; void do_work(size_t N, unsigned long* a) { unsigned long s = 0; for (size_t i = 0; i < N; ++i) s += a[i]; std::lock_guard<std::mutex> L(M); sum += s; } Here the sum is accumulated before being added to the total. Of course the mutex-based version is faster. Try again with: std::atomic<unsigned long> sum; void do_work(size_t N, unsigned long* a) { unsigned long s = 0; for (size_t i = 0; i < N; ++i) s += a[i]; sum += s; }
  - dcow 9y ago
    I think one of the questions at the end covers this. The speaker admits the lock choice is a gimmick and reiterates that the time sink is related to thrashing on the cache line.
    - glandium 9y ago
      I haven't watched the video up to the end, but, how do you think mutexes work under the hood? They use atomic operations. So the cache line thrashing happens in both cases. Edit: come to think of it, they only use compare-and-exchange, which I guess is lighter on the cache lines.
- dcow 9y ago
  Finally made it through this. Very interesting talk and it confirms my understanding that lock free is not wait free and that with hardware atomic instructions you're delegating the locking to the hardware but still relying on correctly placed memory barriers to guarantee the consistency you need.
deleted 9y ago
[deleted]
chrisseaton 9y ago
> Just making sure I understand this correctly: so at a high level you're just trading software locks for hardware locks But the use of hardware ‘locks’ here has the ‘lock-free’ property. (‘Lock-free’ and ‘locks’ do not use exactly the same definition of ‘lock’.)
- dkersten 9y ago
  Exactly. Its about blocking vs making guaranteed forward progress.
  - scott_s 9y ago
    To support what dkersten said: there's a trade-off when deciding to go with lock-free or lock-based structures. Lock-based structures tend to have less synchronization instructions in total, but the inherent mutual exclusion means that usually only one thread can make progress at a time. (And the cheap locks are non-deterministic as to who gets the lock next.) Lock-free algorithms tend to have more synchronization instructions in total, but all threads tend to be able to make progress at all times. In general, lock-based structures and algorithms are better in low contention situations, and lock-free structures and algorithms are better in high contention situations. The intuition is that in low contention (either few threads, or few interfering threads), there's little harm in forcing mutual exclusion, so it's not worth paying a bunch more synchronization instructions. But in high contention (lots of threads, or lots of interfering threads), mutual exclusion can mean that most of the threads are sitting idle waiting for the right to do some work, so it's worth it to pay a bit more overhead so the whole system can more often progress.
    - gpderetta 9y ago
      > Lock-based structures tend to have less synchronization instructions in total, but the inherent mutual exclusion means that usually only one thread can make progress at a time [...]. Lock-free algorithms tend to have more synchronization instructions in total, but all threads tend to be able to make progress at all times. technically not correct. In a lock based implementation, it is possible that no thread is making progress, i.e. no guarantees. Lock free is the guarantee that at least one thread makes progress. Wait free is the guarantee that all threads might be making progress.

by dcow 9y ago

speps 9y ago

No, from what I understand, you can't even do it in software anyway due to how the caches work between cores inside the CPU. Watching this was enlightening to say the least (and the presenter is very good): https://www.youtube.com/watch?v=ZQFzMfHIxng https://www.youtube.com/watch?v=ZQFzMfHIxng

glandium 9y ago
Huh, that first example is comparing apples and oranges. This is the "slow" lock-free version from there: std::atomic<unsigned long> sum; void do_work(size_t N, unsigned long* a) { for (size_t i = 0; i < N; ++i) sum += a[i]; } It atomically adds for every iteration of the loop. This is the "fast" mutex-based version: unsigned long sum(0); std::mutex M; void do_work(size_t N, unsigned long* a) { unsigned long s = 0; for (size_t i = 0; i < N; ++i) s += a[i]; std::lock_guard<std::mutex> L(M); sum += s; } Here the sum is accumulated before being added to the total. Of course the mutex-based version is faster. Try again with: std::atomic<unsigned long> sum; void do_work(size_t N, unsigned long* a) { unsigned long s = 0; for (size_t i = 0; i < N; ++i) s += a[i]; sum += s; }
- dcow 9y ago
  I think one of the questions at the end covers this. The speaker admits the lock choice is a gimmick and reiterates that the time sink is related to thrashing on the cache line.
  - glandium 9y ago
    I haven't watched the video up to the end, but, how do you think mutexes work under the hood? They use atomic operations. So the cache line thrashing happens in both cases. Edit: come to think of it, they only use compare-and-exchange, which I guess is lighter on the cache lines.
dcow 9y ago
Finally made it through this. Very interesting talk and it confirms my understanding that lock free is not wait free and that with hardware atomic instructions you're delegating the locking to the hardware but still relying on correctly placed memory barriers to guarantee the consistency you need.

deleted 9y ago

[deleted]

chrisseaton 9y ago

> Just making sure I understand this correctly: so at a high level you're just trading software locks for hardware locks But the use of hardware ‘locks’ here has the ‘lock-free’ property. (‘Lock-free’ and ‘locks’ do not use exactly the same definition of ‘lock’.)

dkersten 9y ago
Exactly. Its about blocking vs making guaranteed forward progress.
- scott_s 9y ago
  To support what dkersten said: there's a trade-off when deciding to go with lock-free or lock-based structures. Lock-based structures tend to have less synchronization instructions in total, but the inherent mutual exclusion means that usually only one thread can make progress at a time. (And the cheap locks are non-deterministic as to who gets the lock next.) Lock-free algorithms tend to have more synchronization instructions in total, but all threads tend to be able to make progress at all times. In general, lock-based structures and algorithms are better in low contention situations, and lock-free structures and algorithms are better in high contention situations. The intuition is that in low contention (either few threads, or few interfering threads), there's little harm in forcing mutual exclusion, so it's not worth paying a bunch more synchronization instructions. But in high contention (lots of threads, or lots of interfering threads), mutual exclusion can mean that most of the threads are sitting idle waiting for the right to do some work, so it's worth it to pay a bit more overhead so the whole system can more often progress.
  - gpderetta 9y ago
    > Lock-based structures tend to have less synchronization instructions in total, but the inherent mutual exclusion means that usually only one thread can make progress at a time [...]. Lock-free algorithms tend to have more synchronization instructions in total, but all threads tend to be able to make progress at all times. technically not correct. In a lock based implementation, it is possible that no thread is making progress, i.e. no guarantees. Lock free is the guarantee that at least one thread makes progress. Wait free is the guarantee that all threads might be making progress.