Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Implementing Queues for Event-Driven Programs

ithare.com

Post reply on HN
Print view View original

11–20 of 28 posts

Re: Implementing Queues for Event-Driven Programs

#11

Post by gpderetta »

exDM69 wrote: post #6
pierrebai wrote: post #3

Earlier quoted context omitted.

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 mu…

> 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: condition_wait(locked_mutex, condition_to_wait); For each thread in the wait list, the condition variable "knows" which…

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.

Re: Implementing Queues for Event-Driven Programs

#12

Post by gpderetta »

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.

Re: Implementing Queues for Event-Driven Programs

#14

Post by heavenlyhash »

> 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.

Re: Implementing Queues for Event-Driven Programs

#15

Post by Koromix »

> 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.

Re: Implementing Queues for Event-Driven Programs

#17

Post by jcbeard »

heavenlyhash wrote: post #14

> 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…

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).

Re: Implementing Queues for Event-Driven Programs

#18

Post by Myrmornis »

aarongolliver wrote: post #16
Myrmornis wrote: post #13

Do educated adults find the cartoons of hares to usefully or enjoyably complement the text?

Some, yes. [0] [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.

Re: Implementing Queues for Event-Driven Programs

#19

Post by no-bugs »

heavenlyhash wrote: post #14

> 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…

> 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...

Re: Implementing Queues for Event-Driven Programs

#20

Post by gpderetta »

Koromix wrote: post #15

> 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 m…

Well, a FIFO queue respects causality, whether breaking it is OK depends on the application.
Post reply on HN