3 ms·

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 c

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.
    - gpderetta 9y ago
      there are fairly mainstream machines with more than 100s of hardware threads.
    - dragontamer 9y ago
      The Vega64 GPU that AMD just released has 4096 "threads" operating at one time (actually in flight), with up to 40,960 of them "at the ready" at the hardware level (kinda like Hyperthreading, except GPUs keep up to ~10 threads per "shader core" in memory for quick swap in-and-outs). Subject to memory requirements of course. A program that uses a ton of vGPR Registers on the AMD system may "only" accomplish 4096 threads at a time, and maybe only 5 per core (aka 20,480) of them are needed for maximum occupancy. Its a weird architecture because of how each "thread" shares an instruction pointer (ie: NVidia has 32 threads per wavefront, AMD has 64 workitems per Work Group), so its not "really" the same kind of "thread" as in Linux pthreads. But still, the scope of parallelism on a $500 GPU today is rather outstanding. All of these threads could potentially hit the same global memory at the same time. I mean, if you want bad performance of course, but its entirely possible since the global memory space is shared between all compute units in a GPU.
banachtarski 9y ago
> 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. I can't say I agree here. It really depends on the cost of the swap operation required to make this work. Consider a lock-free map for example. Under high contention, I'd prefer to wait for a lock than copy the map while spinning on an atomic. What would push the needle for me one way or another (with respect to locking vs lockless) is a blend between the probability of contention, the cost of the loop itself, and the cost of the swap.
- scott_s 9y ago
  I don't know what you mean here: "than copy the map while spinning on an atomic." Why would we copy the map? And by "spinning on an atomic", do you mean just spin-waiting on some flag? That's, morally, a lock. A well designed lock free algorithm allows all threads to make progress at the same time, and if there is contention, an alternative that hopefully is not just redoing that same work. The cost is more atomic operations, which means that if there is low contention, you're paying more overhead than needed.

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.
  - gpderetta 9y ago
    there are fairly mainstream machines with more than 100s of hardware threads.
  - dragontamer 9y ago
    The Vega64 GPU that AMD just released has 4096 "threads" operating at one time (actually in flight), with up to 40,960 of them "at the ready" at the hardware level (kinda like Hyperthreading, except GPUs keep up to ~10 threads per "shader core" in memory for quick swap in-and-outs). Subject to memory requirements of course. A program that uses a ton of vGPR Registers on the AMD system may "only" accomplish 4096 threads at a time, and maybe only 5 per core (aka 20,480) of them are needed for maximum occupancy. Its a weird architecture because of how each "thread" shares an instruction pointer (ie: NVidia has 32 threads per wavefront, AMD has 64 workitems per Work Group), so its not "really" the same kind of "thread" as in Linux pthreads. But still, the scope of parallelism on a $500 GPU today is rather outstanding. All of these threads could potentially hit the same global memory at the same time. I mean, if you want bad performance of course, but its entirely possible since the global memory space is shared between all compute units in a GPU.

banachtarski 9y ago

> 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. I can't say I agree here. It really depends on the cost of the swap operation required to make this work. Consider a lock-free map for example. Under high contention, I'd prefer to wait for a lock than copy the map while spinning on an atomic. What would push the needle for me one way or another (with respect to locking vs lockless) is a blend between the probability of contention, the cost of the loop itself, and the cost of the swap.

scott_s 9y ago
I don't know what you mean here: "than copy the map while spinning on an atomic." Why would we copy the map? And by "spinning on an atomic", do you mean just spin-waiting on some flag? That's, morally, a lock. A well designed lock free algorithm allows all threads to make progress at the same time, and if there is contention, an alternative that hopefully is not just redoing that same work. The cost is more atomic operations, which means that if there is low contention, you're paying more overhead than needed.