[concurrency-interest] Queue quest

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


On Tue, Apr 8, 2014 at 7:01 PM, Sergey Mashkov <comm at sergey-mashkov.net>wrote:

> √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 ;)


Absolutely, the bigger question is behavior under contention.


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


However, in the case of high throughput the chance of objects dying young
is higher.


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

The downside with a fixed quantity in the queue is the consensus amongst
writers it requires.
The question is if it is possible to "cheat".


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


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


More information about the Concurrency-interest mailing list