[concurrency-interest] Queue quest

Ariel Weisberg ariel at weisberg.ws
Tue Apr 8 13:18:20 EDT 2014


I am interested in a unbounded blocking multiple producer single
consumer queue. I was thinking of
taking [1]https://github.com/netty/netty/blob/master/common/src/main/ja
va/io/netty/util/internal/MpscLinkedQueue.java and adding a field for
the consumer to populate with it's Thread when parking.

If a producer calling unpark also nulls out the field you can avoid
redundant unparks. You can avoid lost unparks by checking the queue
after populating the field, but before parking. For hot threads there
is no locking to facilitate blocking, and roughly the minimum amount of
locking when unpark needs to be called.

You can convert any MPSC queue this way since the operation of the
queue is independent of the mechanism used for blocking. If the
principal behind blocking and unblocking is sound it will be as good as
the underlying queue.

I know MpscLinkedQueue is originally from Akka. Have you compared it's
non-blocking performance to ConcurrentLinkedQueue or

MPMC I have no ideas. That is obviously a harder problem, but it also
doesn't happen to be my problem. For me MPMC scenarios occur when task
sizes are large. When task sizes are small I don't need work stealing
(or I need it but don't provide it).



On Tue, Apr 8, 2014, at 12:17 PM, √iktor Ҡlang wrote:

Hi Sergey,

On Tue, Apr 8, 2014 at 6:07 PM, Sergey Mashkov
<[2]comm at sergey-mashkov.net> wrote:

Hi Viktor

Well, if it will not make you anger, why don't you mention Java's
LinkedBlockingQueue? In 99% cases it's sufficient so you generally
don't need lock-free algos.

Yep, that's a good fallback, but I figured I'd ask first :)

By the way I don't think it's possible to implement in practice
actually efficient non-blocking queue with no preallocated buffer.

Well, for some definition of efficient :-)
Given that most queues spend their lives either full or empty, a
preallocated buffer may not make sense in case there are many millions
of them and they spend their lives mostly empty.

Kind regards


√iktor Ҡlang писал 2014-04-08 06:38:

Hey everyone,

I thought I'd throw this question out there before I go all out NIH.

Does anybody know of an open source (apache 2 compatible) "minimal
overhead", non-blocking, bounded, non-constant-space (i.e. no
ringbuffer or preallocated size array) multiple-producer
single-consumer/multiple-consumer queues in Java/bytecode?




Concurrency-interest mailing list

[3]Concurrency-interest at cs.oswego.edu



Concurrency-interest mailing list

[5]Concurrency-interest at cs.oswego.edu




Concurrency-interest mailing list

[7]Concurrency-interest at cs.oswego.edu



1. https://github.com/netty/netty/blob/master/common/src/main/java/io/netty/util/internal/MpscLinkedQueue.java
2. mailto:comm at sergey-mashkov.net
3. mailto:Concurrency-interest at cs.oswego.edu
4. http://cs.oswego.edu/mailman/listinfo/concurrency-interest
5. mailto:Concurrency-interest at cs.oswego.edu
6. http://cs.oswego.edu/mailman/listinfo/concurrency-interest
7. mailto:Concurrency-interest at cs.oswego.edu
8. http://cs.oswego.edu/mailman/listinfo/concurrency-interest
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20140408/f2a75dfc/attachment.html>

More information about the Concurrency-interest mailing list