[concurrency-interest] Looking for a data struture

Vitaly Davidovich vitalyd at gmail.com
Mon Dec 22 12:17:37 EST 2014


>
> RE: AtomicReferenceArray.  If i had a strict bound on the number of items,
> i would just allocate it to be that large and use an atomic int
> (getAndIncrement()) to find the next available slot and then remove would
> just be to assign the slot to null.  Iteration would have to read a
> potentially large number of slots, but iterating an array should be
> sufficiently fast that you wouldn't really notice.


How about maintaining a set of fixed size AtomicReferenceArrays that are
allocated on-demand (i.e. when you overflow capacity of existing ones)? To
facilitate iteration, you could maintain a bitmask associated with each ARA
that indicates which slots have a value (this is assuming they're sparse --
otherwise, filtered iteration should be fine).

On Mon, Dec 22, 2014 at 11:10 AM, Luke Sandberg <lukeisandberg at gmail.com>
wrote:

> Thanks for all the responses!
>
> RE: CHM. For the thread-renaming usecase we used CHM for a while but it
> consistently ended up as one of the highest contention points (as measured
> by lock wait times) in some of our applications.  Also there is a fairly
> high fixed overhead.
>
> RE: AtomicReferenceArray.  If i had a strict bound on the number of items,
> i would just allocate it to be that large and use an atomic int
> (getAndIncrement()) to find the next available slot and then remove would
> just be to assign the slot to null.  Iteration would have to read a
> potentially large number of slots, but iterating an array should be
> sufficiently fast that you wouldn't really notice.
>
> RE: CLQ with some extra method.  I had thought it would have been nice to
> have CLQ return a Node object for this usecase.  Though if i wouldn't be
> able to physically remove the node then it seems simpler to just build my
> own Trieber stack and implement remove by nulling out the 'item' field in
> the Node object.
>
>
> On Mon, Dec 22, 2014 at 6:24 AM, Aaron Grunthal <
> aaron.grunthal at infinite-source.de> wrote:
>>
>> On 22.12.2014 03:35, Luke Sandberg wrote:
>>
>>> I have come across a few situations where i am looking for a
>>> datastructure and i feel like i keep coming up short.
>>>
>>> The situation is analogous to the 'waiters' list in
>>> java.util.concurrent.FutureTask.
>>>
>>> Basically, I need to be able to publish a non-null object reference into
>>> a data structure where
>>> * order doesn't matter (insertion order would be nice, but i don't care
>>> that much)
>>> * add and remove identity semantics
>>> * concurrent iteration (weakly consistent is fine)
>>> * add/remove are non-blocking
>>>
>>> CLQ is an obvious choice but removal is O(n), another choice would a
>>> simple synchronized identity hash set which is fine but the lock + high
>>> entry overhead is a deal breaker.
>>>
>>> An AtomicReferenceArray would be super easy, but i can't put a bound on
>>> the number of items.
>>>
>>
>> You say that it's super easy, but how would you handle finding a free
>> slot for insertion in constant or logarithmic time? Since you mention that
>> order doesn't matter that seems to suggest it doesn't behave in a
>> stack-like manner.
>>
>>
>>  Also, it would be fine for the code that adds items, to store additional
>>> state (an index, a 'Node' reference), in order to facilitate removal.
>>>
>>> The best thing i have seen from looking around appears to be something
>>> like what FutureTask does to implement 'awaitDone', but even there
>>> removeWaitier() is O(n).  that seems like a pretty good compromise when
>>> lists are short, but what would be a better solution when lists are long?
>>>
>>> Just to motivate this a little bit, the two cases I am looking at in
>>> particular are:
>>>
>>> * maintaining a set of threads associated with a server 'request'
>>> (threads enter/exit when they start executing tasks associated with the
>>> request)
>>> * maintaining a set of futures to be cancelled (futures are removed when
>>> they complete to avoid pinning their referents).
>>>
>>> Any pointers or ideas?
>>>
>>>
>>>
>>> _______________________________________________
>>> 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20141222/2c33cc41/attachment.html>


More information about the Concurrency-interest mailing list