[concurrency-interest] Queue quest

Sergey Mashkov comm at sergey-mashkov.net
Tue Apr 8 13:01:51 EDT 2014

√iktor Ҡlang писал 2014-04-08 09:17:
> 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 :-)

Of course efficiency is very depends on usecase and criteria. In some 
cases lock-free algorithms could be even more expensive than old-school 
onces. So lock-free is not gold bullet that could rule all of us ;)

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

Agree, my point was that if you don't have preallocated array then you 
have two options: linked list of elements or linked list of small 
buffers. If you have linked list then you have to pay for GC overhead in 
case of high throughput. If you have list of chunks then enlarge logic 
will be difficult to make lock-free so it will have lock somewhere 
anyway or very dangerous loops/ifs that will eat time during spins. Also 
if you want to have it bounded then it will increase complexity even 
more. You actually have third option: use something like copy on write 
array list but it will lead to big overhead on copying everything so it 
will die very quickly so this options is just a joke :) This is why I 
don't think it could be implemented to conform all requirements you 

>> 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 [1]
>> _______________________________________________
>> Concurrency-interest mailing list
>> Concurrency-interest at cs.oswego.edu
>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest [1]
> --
>  Cheers,
> Links:
> ------
> [1] http://cs.oswego.edu/mailman/listinfo/concurrency-interest

More information about the Concurrency-interest mailing list