[concurrency-interest] Queue quest

Mark Thornton mthornton at optrak.com
Wed Apr 9 03:54:53 EDT 2014


On Tuesday, 8 April 2014, 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 ;)
>
>  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 mentioned.
>

There is one more case where you expect most queues to never contain more
than one (or perhaps two elements), in which case you keep that element in
the main object and never need to create an array at all.

Mark Thornton



>
>
>>  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
>>
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20140409/7a0c62ee/attachment-0001.html>


More information about the Concurrency-interest mailing list