4 ms·

Just curious, but is there a reason why you didn’t just use a single lock-less queue? Per-thread work queues sounds like a perfectly serviceable solution but I

Just curious, but is there a reason why you didn’t just use a single lock-less queue? Per-thread work queues sounds like a perfectly serviceable solution but I can imagine it an advantage to hide that added complexity behind a lock-less queue (which could in fact be implemented using multiple queues internally, but I think that’s just one of multiple ways to implement such a thing)

brandmeyer 7y ago
In my case, the complexity was hidden behind the interface to the threadpool. This particular process wasn't the only thing in the system. I wanted the worker threads to go to sleep when there wasn't work to do.
dragontamer 7y ago
> use a single lock-less queue I dare say that Multiple-producer + multiple-consumer lockless queues are not "difficult", but straight up "impossible" to write. You MUST make a decision early on: 1. Settle on single-consumer / single-producer ("True" parallelism of 2x threads best case) on the queue, retaining the "first-in / first-out" property of the queue. 2. Decide that "first-in / first-out" is unnecessary in your use case, and generalize to multiple-producer / multiple-consumer code. After all, it is impossible to define first-in / first-out if you cannot define an insertion order, or consuming order. If you decide on a defined insertion order, it is equivalent to deciding upon a "single" producer protected by a spinlock or mutex. (And lo-and-behold, all your code is just a very, very complex mutex). Ditto for the consumer side. ------- You CAN write 1x consumer + 1x producer lockless queues with defined total ordering. You CAN have "many" consumers sequentially "acting" as the 1x consumer, or "many" producers "acting" as the 1x producer (by sequentially choosing one through CAS-loops or mutexes). But I dare say, 30x consumers each being a "consumer 1 at a time" isn't really a multi-consumer queue, its a 1x consumer queue with a mutex on the front-end :-) ------- Deciding upon a 1x producer / Multi-consumer (or the inverse: multi-producer / 1x consumer) queue is just a grossly inefficient queue. If you cannot define the insertion order, then you cannot define the removal order. Similarly, if you cannot define the removal order, you cannot define the insertion order. You might as well "undefine the order completely" to have better performance. ------- In any case, your assumption here has a gross amount of complexity you're ignoring. Lockless queues are NOT an item to be trifled with.
- w0utert 7y ago
  Not sure if I'm following. In many (most?) multiple-producer/multiple-consumer cases it is completely irrelevant if the work-queue guarantees a strict insertion/removal order, as long as the queue is 'fair' (time in queue is distributed evenly over all work items). If that's all you need, a lock-free implementation using atomic operations does not have to be complicated, or what am I missing here?
  - dragontamer 7y ago
    A "work-queue" doesn't have strict ordering in many multithreaded programs. But a "queue" or "fifo" is expected to have a strict ordering. The confusion comes in because many programmers expect a strict-ordering on "work-queues", especially because many work-queues are made out of simple queues or fifos. The big decision point for many is finally deciding, and/or realizing, that strict-ordering is not necessary in many pragmatic use cases. But this also comes with a double-edge sword: many algorithms require strict-ordering of tasks. --------- Take a Breadth First Search, as an example. One core assumption of BFS is that the first solution you come across will be the solution closest to the root. Ex: If searching for "Checkmate" in a chess puzzle, the BFS implementation will ALWAYS find the shortest checkmate. Lets say you're in a situation with "many checkmates", checkmate in 5-moves, checkmate in 7-moves... etc. etc. But you want to absolutely find the shortest one. BFS is clearly the answer. But ONLY if your queue is strictly FIFO. Now if you parallelize the BFS search by replacing the true FIFO queue with a pseudo-FIFO parallel queue, its no longer guaranteed to find the shortest checkmate.
- namibj 7y ago
  Actually, this is very feasible by overprovisioning to get enough padding to use the approach described in Section 5.3 of [0]. That way you get a really fast fast-path. [0]: Marcos K. Aguilera, Kimberly Keeton, Stanko Novakovic, and Sharad Singhal. 2019. Designing Far Memory Data Structures: Think Outside the Box. In Proceedings of the Workshop on Hot Topics in Operating Systems (HotOS ’19). Association for Computing Machinery, New York, NY, USA, 120–126. DOI: https://doi.org/10.1145/3317550.3321433 https://doi.org/10.1145/3317550.3321433

brandmeyer 7y ago

In my case, the complexity was hidden behind the interface to the threadpool. This particular process wasn't the only thing in the system. I wanted the worker threads to go to sleep when there wasn't work to do.

dragontamer 7y ago

> use a single lock-less queue I dare say that Multiple-producer + multiple-consumer lockless queues are not "difficult", but straight up "impossible" to write. You MUST make a decision early on: 1. Settle on single-consumer / single-producer ("True" parallelism of 2x threads best case) on the queue, retaining the "first-in / first-out" property of the queue. 2. Decide that "first-in / first-out" is unnecessary in your use case, and generalize to multiple-producer / multiple-consumer code. After all, it is impossible to define first-in / first-out if you cannot define an insertion order, or consuming order. If you decide on a defined insertion order, it is equivalent to deciding upon a "single" producer protected by a spinlock or mutex. (And lo-and-behold, all your code is just a very, very complex mutex). Ditto for the consumer side. ------- You CAN write 1x consumer + 1x producer lockless queues with defined total ordering. You CAN have "many" consumers sequentially "acting" as the 1x consumer, or "many" producers "acting" as the 1x producer (by sequentially choosing one through CAS-loops or mutexes). But I dare say, 30x consumers each being a "consumer 1 at a time" isn't really a multi-consumer queue, its a 1x consumer queue with a mutex on the front-end :-) ------- Deciding upon a 1x producer / Multi-consumer (or the inverse: multi-producer / 1x consumer) queue is just a grossly inefficient queue. If you cannot define the insertion order, then you cannot define the removal order. Similarly, if you cannot define the removal order, you cannot define the insertion order. You might as well "undefine the order completely" to have better performance. ------- In any case, your assumption here has a gross amount of complexity you're ignoring. Lockless queues are NOT an item to be trifled with.

w0utert 7y ago
Not sure if I'm following. In many (most?) multiple-producer/multiple-consumer cases it is completely irrelevant if the work-queue guarantees a strict insertion/removal order, as long as the queue is 'fair' (time in queue is distributed evenly over all work items). If that's all you need, a lock-free implementation using atomic operations does not have to be complicated, or what am I missing here?
- dragontamer 7y ago
  A "work-queue" doesn't have strict ordering in many multithreaded programs. But a "queue" or "fifo" is expected to have a strict ordering. The confusion comes in because many programmers expect a strict-ordering on "work-queues", especially because many work-queues are made out of simple queues or fifos. The big decision point for many is finally deciding, and/or realizing, that strict-ordering is not necessary in many pragmatic use cases. But this also comes with a double-edge sword: many algorithms require strict-ordering of tasks. --------- Take a Breadth First Search, as an example. One core assumption of BFS is that the first solution you come across will be the solution closest to the root. Ex: If searching for "Checkmate" in a chess puzzle, the BFS implementation will ALWAYS find the shortest checkmate. Lets say you're in a situation with "many checkmates", checkmate in 5-moves, checkmate in 7-moves... etc. etc. But you want to absolutely find the shortest one. BFS is clearly the answer. But ONLY if your queue is strictly FIFO. Now if you parallelize the BFS search by replacing the true FIFO queue with a pseudo-FIFO parallel queue, its no longer guaranteed to find the shortest checkmate.
namibj 7y ago
Actually, this is very feasible by overprovisioning to get enough padding to use the approach described in Section 5.3 of [0]. That way you get a really fast fast-path. [0]: Marcos K. Aguilera, Kimberly Keeton, Stanko Novakovic, and Sharad Singhal. 2019. Designing Far Memory Data Structures: Think Outside the Box. In Proceedings of the Workshop on Hot Topics in Operating Systems (HotOS ’19). Association for Computing Machinery, New York, NY, USA, 120–126. DOI: https://doi.org/10.1145/3317550.3321433 https://doi.org/10.1145/3317550.3321433