4 ms·

Aren't lock free data structures more about reducing the impact of contention than throughput under low contention?

by foota 3y ago

klodolph 3y ago
Depends what you mean by “the impact of contention”. It is possible, if you build a lock-free system, to end up with threads that keep churning and never make forward progress.
loeg 3y ago
Lock free is kind of an overloaded term that can mean a variety of things depending on what the user is thinking. Usually the goal is being able to make forward progress even if one thread is context switched out by the OS scheduler, which might be called wait-free or non-blocking. Using mutexes (unless you can prevent OS scheduling, interrupts, etc) makes this property impossible to achieve. In general, MPSC queues are super fast and there's no real reason to prefer a locked queue.
- adwn 3y ago
  > In general, MPSC queues are super fast and there's no real reason to prefer a locked queue. There's one significant advantage that a locked vector or deque has over MPSC/MPMC queues: the consumers can dequeue all messages in a single operation by locking the vector, swapping it with an empty vector (typically, that's just 3 words), and locking it again. That's such a simple operation that it will typically be as fast or even faster than a single pop-one-message operation in an MPSC/MPMP. Similarly, if the vector is empty, a producer can push any number of messages in a single, constant-time operation.
  - loeg 3y ago
    All true, although I would quibble with: > That's such a simple operation that it will typically be as fast or even faster than a single pop-one-message operation in an MPSC/MPMP. Not if the lock is blocked because one of the writers context switched out! The typical case is good, but the worst case is pretty bad.
tialaramex 3y ago
Under a lock free algorithm, we promise that across our entire system, eventually some progress is made. I can't necessarily point at any specific thread of execution and say "This thread makes progress" but I can say that forward progress is made for the system as a whole. Under a wait free algorithm, we promise that every individual thread eventually makes progress. Suppose I have one really dumb thread which just goes to sleep for 10 seconds in a loop, as well as other threads which do some actual work. If we're a lock free algorithm, it is OK if the 10-second-sleep thread is always chosen to make progress, its "progress" consists of sleeping for 10 seconds, too bad, try again next time. With a wait free algorithm, the threads which actually do useful work will also make at least some progress, eventually despite the 10 second sleeper. Generally we can't say for sure that we e.g. "reduce impact of contention" only that we definitely make some forward progress, on at least one thread eventually.

Aren't lock free data structures more about reducing the impact of contention than throughput under low contention?

by foota 3y ago

Aren't lock free data structures more about reducing the impact of contention than throughput under low contention?

Depends what you mean by “the impact of contention”. It is possible, if you build a lock-free system, to end up with threads that keep churning and never make forward progress.

loeg 3y ago

Lock free is kind of an overloaded term that can mean a variety of things depending on what the user is thinking. Usually the goal is being able to make forward progress even if one thread is context switched out by the OS scheduler, which might be called wait-free or non-blocking. Using mutexes (unless you can prevent OS scheduling, interrupts, etc) makes this property impossible to achieve. In general, MPSC queues are super fast and there's no real reason to prefer a locked queue.

adwn 3y ago
> In general, MPSC queues are super fast and there's no real reason to prefer a locked queue. There's one significant advantage that a locked vector or deque has over MPSC/MPMC queues: the consumers can dequeue all messages in a single operation by locking the vector, swapping it with an empty vector (typically, that's just 3 words), and locking it again. That's such a simple operation that it will typically be as fast or even faster than a single pop-one-message operation in an MPSC/MPMP. Similarly, if the vector is empty, a producer can push any number of messages in a single, constant-time operation.
- loeg 3y ago
  All true, although I would quibble with: > That's such a simple operation that it will typically be as fast or even faster than a single pop-one-message operation in an MPSC/MPMP. Not if the lock is blocked because one of the writers context switched out! The typical case is good, but the worst case is pretty bad.

tialaramex 3y ago

Under a lock free algorithm, we promise that across our entire system, eventually some progress is made. I can't necessarily point at any specific thread of execution and say "This thread makes progress" but I can say that forward progress is made for the system as a whole. Under a wait free algorithm, we promise that every individual thread eventually makes progress. Suppose I have one really dumb thread which just goes to sleep for 10 seconds in a loop, as well as other threads which do some actual work. If we're a lock free algorithm, it is OK if the 10-second-sleep thread is always chosen to make progress, its "progress" consists of sleeping for 10 seconds, too bad, try again next time. With a wait free algorithm, the threads which actually do useful work will also make at least some progress, eventually despite the 10 second sleeper. Generally we can't say for sure that we e.g. "reduce impact of contention" only that we definitely make some forward progress, on at least one thread eventually.