[concurrency-interest] Looking for a data struture

Aleksandar Prokopec aleksandar.prokopec at gmail.com
Wed Dec 31 05:22:34 EST 2014


Did you consider a concurrent hash map?
It is slightly slower than a data structure based on just a linked list, but it does not sound like you would notice the difference.

Luke Sandberg <lukeisandberg at gmail.com> wrote:
>A doubly linked list that exposes the nodes would have that behavior.
>On Dec 30, 2014 9:23 AM, "Oleksandr Otenko"
><oleksandr.otenko at oracle.com>
>wrote:
>
>>  Do you know a non-concurrent structure that you are looking for?
>>
>> (eg you don't like O(n) for removal of arbitrary items - but is it
>> possible to have *all* operations O(1), even in a non-concurrent
>case?)
>>
>>
>> Alex
>>
>>
>> On 22/12/2014 02: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.
>>
>> 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
>listConcurrency-interest at cs.oswego.eduhttp://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

-- 
Sent from my Android phone with K-9 Mail. Please excuse my brevity.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20141231/5952e2fc/attachment.html>


More information about the Concurrency-interest mailing list