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

21–28 of 28 posts

Re: Implementing Queues for Event-Driven Programs

#21

Post by no-bugs »

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…

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

Re: Implementing Queues for Event-Driven Programs

#22

Post by no-bugs »

Myrmornis wrote: post #13

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

Re: Implementing Queues for Event-Driven Programs

#23

Post by no-bugs »

gpderetta wrote: post #12

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…

THANKS! I've added it (not 100% sure how it would work in practice, but certainly looks interesting).

Re: Implementing Queues for Event-Driven Programs

#25

Post by gpderetta »

no-bugs wrote: post #23
gpderetta wrote: post #12

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…

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.

Re: Implementing Queues for Event-Driven Programs

#26

Post by gpderetta »

no-bugs wrote: post #21
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…

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

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.

Re: Implementing Queues for Event-Driven Programs

#28

Post by Koromix »

no-bugs wrote: post #21
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…

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

Post reply on HN