[concurrency-interest] Looking for a data struture

Luke Sandberg lukeisandberg at gmail.com
Mon Dec 22 11:10:21 EST 2014


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
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20141222/b867f9e4/attachment-0001.html>


More information about the Concurrency-interest mailing list