Implementing Queues for Event-Driven Programs(ithare.com)
ithare.com
Implementing Queues for Event-Driven Programs
http://ithare.com/implementing-queues-for-event-driven-programs/
6 comments
> 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...
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/
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.
Well, a FIFO queue respects causality, whether breaking it is OK depends on the application.
Do educated adults find the cartoons of hares to usefully or enjoyably complement the text?
Statistically - yep. See http://ithare.com/facelift-for-no-bugs/ - only 10 out of 160 said that they don't like the cartoons.
BTW, there is a "very beta" way to turn them off - use http://ithare.com/visitor-settings/ (NB: "No!" option doesn't really work yet)...
BTW, there is a "very beta" way to turn them off - use http://ithare.com/visitor-settings/ (NB: "No!" option doesn't really work yet)...
Some, yes. [0]
[0] http://i.imgur.com/Y5X3h96.png
[0] http://i.imgur.com/Y5X3h96.png
Haha OK, thanks! I don't mind the cartoon of the queue at the top but for some reason I don't like having a little cartoon lagomorph appear in a speech bubble by the paragraphs while I'm reading.
I like them. Reminds me to take a moment to destress every now and then and not take things too seriously as I am wont to do.
From the first code example:
> Yep, notifying outside of lock is usually BETTER. Otherwise the other thread would be released but will immediately run into our own lock above our own lock above, causing unnecessary (and Very Expensive) context switch
Is this true and if so, on which platform(s)? Aren't most mutex/condition variable implementations optimized to avoid this case by deferring the condition signal to the mutex unlock?
Additionally, in the implementation of kill() in the latter examples, there should be notify_all() instead of notify_one().
> Yep, notifying outside of lock is usually BETTER. Otherwise the other thread would be released but will immediately run into our own lock above our own lock above, causing unnecessary (and Very Expensive) context switch
Is this true and if so, on which platform(s)? Aren't most mutex/condition variable implementations optimized to avoid this case by deferring the condition signal to the mutex unlock?
Additionally, in the implementation of kill() in the latter examples, there should be notify_all() instead of notify_one().
That would be relying on the OS to do the right thing. One problem is that on some platform or for some usage pattern, then mutex and notifying object will be two independent objects, so the OS would have no way of knowing that it should not immediately wake up the notified threads.
Furthermore, it is a good rule of thumb anyway: hold the mutex for the shortest time possible. The corresponding pattern is to hold a mutex, copy the data you need to a local copy, release the mutex and then do the processing on the local copy. Sometimes, the processing can have unknown dependency and so it avoids potential deadlocks caused by some function called during processing trying to take a lock that is held be another thread.
Basically, never hold a lock while calling functions. You never know what might be hidden behind them now and will be hidden in the future.
Furthermore, it is a good rule of thumb anyway: hold the mutex for the shortest time possible. The corresponding pattern is to hold a mutex, copy the data you need to a local copy, release the mutex and then do the processing on the local copy. Sometimes, the processing can have unknown dependency and so it avoids potential deadlocks caused by some function called during processing trying to take a lock that is held be another thread.
Basically, never hold a lock while calling functions. You never know what might be hidden behind them now and will be hidden in the future.
> One problem is that on some platform or for some usage pattern, then mutex and notifying object will be two independent objects, so the OS would have no way of knowing that it should not immediately wake up the notified threads.
On all significant platforms I know, condition wait works like this:
Did you have a platform in mind that works differently from this?
Additionally, when you unlock a mutex before signalling the condition, another thread may be scheduled in between that may invalidate the condition that was signalled. This may introduce a race condition.
I signal my condition variables with mutexes locked because it's easier to guarantee correctness that way.
On all significant platforms I know, condition wait works like this:
condition_wait(locked_mutex, condition_to_wait);
Did you have a platform in mind that works differently from this?
Additionally, when you unlock a mutex before signalling the condition, another thread may be scheduled in between that may invalidate the condition that was signalled. This may introduce a race condition.
I signal my condition variables with mutexes locked because it's easier to guarantee correctness that way.
The optimization you are talking about is called wait morphing. Linux futexes have support for this optimization, and glibc pthread_cond_signal did support it at one point. I'm not sure wether they still do though.
Unless you are writing hard realtime systems where you can make use of the strict scheduling guarantees of SCHED_FIFO, signaling while holding the lock is never necessary nor sufficient for correctness. The waiter must be checking the condition in a loop anyway.
Unless you are writing hard realtime systems where you can make use of the strict scheduling guarantees of SCHED_FIFO, signaling while holding the lock is never necessary nor sufficient for correctness. The waiter must be checking the condition in a loop anyway.
> Additionally, when you unlock a mutex before signalling the condition, another thread may be scheduled in between that may invalidate the condition that was signalled. This may introduce a race condition.
And if you unlock the mutex after signalling the condition, another thread can be still scheduled in between the call to notify() and whatever-notified-thread-which-starts-to-run (and can still invalidate whatever-conditions-it-can-invalidate). There is absolutely no guarantee whatsoever that notified-thread gets to your mutex first (not that it really should matter for correctness in any sane program BTW).
> I signal my condition variables with mutexes locked because it's easier to guarantee correctness that way.
There is no difference in guarantees in practice whether you notify within or after; I'm not even sure that there is any difference in theory (exactly because the thread-which-was-notified is not guaranteed to get mutex first).
And if you unlock the mutex after signalling the condition, another thread can be still scheduled in between the call to notify() and whatever-notified-thread-which-starts-to-run (and can still invalidate whatever-conditions-it-can-invalidate). There is absolutely no guarantee whatsoever that notified-thread gets to your mutex first (not that it really should matter for correctness in any sane program BTW).
> I signal my condition variables with mutexes locked because it's easier to guarantee correctness that way.
There is no difference in guarantees in practice whether you notify within or after; I'm not even sure that there is any difference in theory (exactly because the thread-which-was-notified is not guaranteed to get mutex first).
> Aren't most mutex/condition variable implementations optimized to avoid this case by deferring the condition signal to the mutex unlock?
Yes, _some_ but not _all_ implementations are doing it; however, as it is not really guaranteed (and actually is a workaround for poorly written programs) - standing recommendation is still to notify after the lock (which can be better, can be the same, but won't be worse than doing it within), see for example http://en.cppreference.com/w/cpp/thread/condition_variable/n...:
"The notifying thread does not need to hold the lock on the same mutex as the one held by the waiting thread(s); in fact doing so is a pessimization, since the notified thread would immediately block again, waiting for the notifying thread to release the lock. However, some implementations (in particular many implementations of pthreads) recognize this situation and avoid this "hurry up and wait" scenario by transferring the waiting thread from the condition variable's queue directly to the queue of the mutex within the notify call, without waking it up."
> Additionally, in the implementation of kill() in the latter examples, there should be notify_all() instead of notify_one().
In MOST cases, it didn't matter (as there was only one blocking thread - the one reading), but yes, there was one case when it was indeed important. Fixed now, THANKS!
Yes, _some_ but not _all_ implementations are doing it; however, as it is not really guaranteed (and actually is a workaround for poorly written programs) - standing recommendation is still to notify after the lock (which can be better, can be the same, but won't be worse than doing it within), see for example http://en.cppreference.com/w/cpp/thread/condition_variable/n...:
"The notifying thread does not need to hold the lock on the same mutex as the one held by the waiting thread(s); in fact doing so is a pessimization, since the notified thread would immediately block again, waiting for the notifying thread to release the lock. However, some implementations (in particular many implementations of pthreads) recognize this situation and avoid this "hurry up and wait" scenario by transferring the waiting thread from the condition variable's queue directly to the queue of the mutex within the notify call, without waking it up."
> Additionally, in the implementation of kill() in the latter examples, there should be notify_all() instead of notify_one().
In MOST cases, it didn't matter (as there was only one blocking thread - the one reading), but yes, there was one case when it was indeed important. Fixed now, THANKS!
Pthreads on Linux encourage holding the lock during a signal or broadcast (http://linux.die.net/man/3/pthread_cond_signal):
The pthread_cond_broadcast() or pthread_cond_signal()
functions may be called by a thread whether or not it
currently owns the mutex that threads calling
pthread_cond_wait() or pthread_cond_timedwait() have
associated with the condition variable during their waits;
however, if predictable scheduling behavior is required,
then that mutex shall be locked by the thread calling
pthread_cond_broadcast() or pthread_cond_signal().
Since most platforms defer condition signalling to mutex unlocks, the way the code is now written will cause more spurious wakeups and context switching than necessary.
The pathological case in scheduling goes like this:
I would say it's usually better to signal your condition variables with mutexes locked unless you know you're running on a platform with flaky condition variables. Easier to guarantee correctness and avoid spurious wakeups that way.
related note: cppreference.com is a terrible resource. It was worse 10 years ago, but it's not improved much. I would not trust the weasel wording ("some implementations" etc) in the link you posted, what it says about pthreads contradicts the pthread man pages (that encourage signal while holding lock)
The pathological case in scheduling goes like this:
1. Reader A enters pop_front on an empty queue, goes to wait on the condition variable
2. Writer W enters push_back, adds an element to list and releases mutex and get pre-empted (on line 25 first example)
3. Reader B enters pop_front, sees queue not empty, pops element and leaves
4. Writer W signals condition, wakes up Reader A
5. Reader A wakes up but the queue is empty, goes back to sleep causing unnecessary context switch and trashing the TLB
I would say it's usually better to signal your condition variables with mutexes locked unless you know you're running on a platform with flaky condition variables. Easier to guarantee correctness and avoid spurious wakeups that way.
related note: cppreference.com is a terrible resource. It was worse 10 years ago, but it's not improved much. I would not trust the weasel wording ("some implementations" etc) in the link you posted, what it says about pthreads contradicts the pthread man pages (that encourage signal while holding lock)
From what I've seen (YMMV), chances of it happening are MUCH smaller than chances of getting context switch under the lock (with lots of threads running into this lock and having their own context switches), because of spending more time under the lock than it is really necessary (and ANY call, especially kernel call at 300+ clocks, is a LOT of time). Strictly speaking, it needs to be measured, but until that point - I'm keeping my mutex locks as small as possible.
On Linux, another way to signal arbitrary events instead of an anonymous pipe is via eventfd(2).
Added it, THANKS!
Regarding "Removing locks completely", the author laments not knowing of any readily available library providing the blocking-on-necessary support.
I suggest looking into Event Counts, which can be used to non-intrusively add blocking behavior to most lock free queues; they are the non-blocking world equivalent of condition variables. Facebook's Folly library provides a readily available open source implementation of Event Counts.
I suggest looking into Event Counts, which can be used to non-intrusively add blocking behavior to most lock free queues; they are the non-blocking world equivalent of condition variables. Facebook's Folly library provides a readily available open source implementation of Event Counts.
THANKS! I've added it (not 100% sure how it would work in practice, but certainly looks interesting).
You are welcome. Note that the event count is a general synchronization primitive, the one in folly is just an implementation.
BTW, you can build an efficient event count on top of eventfd, so you can even poll/select it.
BTW, you can build an efficient event count on top of eventfd, so you can even poll/select it.
> In the extreme cases (and ultra-small sizes like 2 or 3), we can even run into deadlocks (!).
If this happens to you, you're doing it wrong. You have deadlocks; they just aren't happening "usually" unless you're "unlucky"... but happen they will!
Build your program to run correctly when all queues are buffer size of 1. If it doesn't work, you're doing it wrong.
Now raise the buffer sizes to something reasonable to reduce the performance frictions of too-strict scheduling. You will never have deadlocks.
If this happens to you, you're doing it wrong. You have deadlocks; they just aren't happening "usually" unless you're "unlucky"... but happen they will!
Build your program to run correctly when all queues are buffer size of 1. If it doesn't work, you're doing it wrong.
Now raise the buffer sizes to something reasonable to reduce the performance frictions of too-strict scheduling. You will never have deadlocks.
Agreed. If having deadlocks, then there's likely a cyclic dependency the programmer/author didn't consider. This happens a lot in streaming/data-flow code. Worse, something in the queue that's wonky. Seems to happen on multi-arch lockless FIFO's when the authors didn't consider corner cases of architectures with more relaxed coherence, or architected features (e.g., 128 vs. 64-byte cache lines).
> If this happens to you, you're doing it wrong.
Except for some corner cases - you're right, probably I should add a note about it...
Except for some corner cases - you're right, probably I should add a note about it...
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.