[concurrency-interest] Queue quest

√iktor Ҡlang viktor.klang at gmail.com
Tue Apr 8 17:44:11 EDT 2014


No probs!


On Tue, Apr 8, 2014 at 7:28 PM, Ariel Weisberg <ariel at weisberg.ws> wrote:

>  Hi,
>
> I apologize for stomping on your thread. I misread and thought you said
> unbounded.
>
> Regards,
> Ariel
>
>
> On Tue, Apr 8, 2014, at 01:18 PM, Ariel Weisberg wrote:
>
> Hi,
>
> I am interested in a unbounded blocking multiple producer single consumer
> queue. I was thinking of taking
> https://github.com/netty/netty/blob/master/common/src/main/java/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 LinkedTransferQueue?
>
> 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).
>
> Regards,
> Ariel
> 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 <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
>  Sergey
>
>  √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?
>
>  --
>
>   Cheers,
>>  _______________________________________________
>  Concurrency-interest mailing list
>  Concurrency-interest at cs.oswego.edu
>  http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
>
>  _______________________________________________
>  Concurrency-interest mailing list
>  Concurrency-interest at cs.oswego.edu
>  http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
>
>
>
> --
>  Cheers,
>>
>   *_______________________________________________*
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>


-- 
Cheers,
√
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20140408/50fafd73/attachment.html>


More information about the Concurrency-interest mailing list