[concurrency-interest] Looking for a data struture

Martin Buchholz martinrb at google.com
Mon Dec 22 02:13:32 EST 2014


It seems reasonable for the user of CLQ to retain a "handle" to the
Node inserted into a CLQ, so that remove or contains can be O(1).  An
Iterator is vaguely close to such a handle (but you don't need to be
able to iterate).  You could experiment with adding such a thing to
CLQ - an insert method that returns a wrapper around the internal
Node.  Latest version in jsr166 CVS.

The remove method would look something like:

          return casItem(p, item, null);

You can't physically unlink the Node because you don't have access to
the predecessor Node, as remove(Object) does ... so garbage deleted
Nodes might build up.  But you can skip over any deleted successor
Nodes, somewhat mitigating this problem.

http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concurrent/ConcurrentLinkedQueue.java?view=markup

NodeList seems vaguely relevant.
http://code.google.com/p/guava-libraries/issues/detail?id=1285

On Sun, Dec 21, 2014 at 6:35 PM, Luke Sandberg <lukeisandberg at gmail.com> 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 list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>


More information about the Concurrency-interest mailing list