> is an ability to push asynchronous messages/events there (usually from different threads), and to get them back (usually from one single thread) – in FIFO order, of course.
It is worth noting that FIFO only holds for messages coming from a single thread. If you have one thread posting keyboard events and another mouse events it is very possible that the reader will get them in the "wrong" order, even with tens of milliseconds separating them from the user's POV.
Now it seems obvious when I say it, but it is easy to forget that when you develop the reader side, especially since most of the times the ordering will hold. This leads to intermittent and non-obvious bugs down the line.
On the other hands, if you fully acknowledge the lack of ordering guarantee, you can use that to make a more efficient queue by using one-buffer-and-lock-per-thread. Each producer fills its own lock-protected queue, and the reader just needs to find a non-empty queue, lock it and pop an item, without any penalty for the other threads.
Of course, the inter-thread ordering will be even worse but you keep the ordering of events from one producer, which was the only actual guarantee you had to begin with in the naive version.
> make a more efficient queue by using one-buffer-and-lock-per-thread.
How the reader would block on such a distributed queue when it's empty (without creating one single mutex, which would re-establish the single contention point)? If there is no way to block while waiting for input, it means polling, and polling is a Really Bad Thing...
The reader scans all queues, without locking. If one is non-empty, then you lock it and pop an item. Only if are all queues are empty then you hit the slow path and wait on a synchronization primitive (condition variable).
Of course if you can assume that the queue will always be very busy, you can ditch that too and poll instead. Polling is often bad, but not always. When things go very fast, it can be more efficient.
A good example of that occurs with the new storage NVM Express storage technologies and Linux, where the traditional I/O completion interrupt used until now is starting to bottleneck: https://lwn.net/Articles/663879/
Each queue has its own mutex (or better, use N lock free queues), but they would all share a single signaling object. As signaling is the slow path and it is rare, it is fine to contend in that case. You can't use a condition variable directly, but can build an event signaling object on top of a condvar and (another) mutex.
It is worth noting that FIFO only holds for messages coming from a single thread. If you have one thread posting keyboard events and another mouse events it is very possible that the reader will get them in the "wrong" order, even with tens of milliseconds separating them from the user's POV.
Now it seems obvious when I say it, but it is easy to forget that when you develop the reader side, especially since most of the times the ordering will hold. This leads to intermittent and non-obvious bugs down the line.
On the other hands, if you fully acknowledge the lack of ordering guarantee, you can use that to make a more efficient queue by using one-buffer-and-lock-per-thread. Each producer fills its own lock-protected queue, and the reader just needs to find a non-empty queue, lock it and pop an item, without any penalty for the other threads.
Of course, the inter-thread ordering will be even worse but you keep the ordering of events from one producer, which was the only actual guarantee you had to begin with in the naive version.