[concurrency-interest] ConcurrentLinkedQueue vs. ConcurrentLinkedDeque

Martin Buchholz martinrb at google.com
Sun Feb 28 14:25:19 EST 2016


On Sun, Feb 28, 2016 at 5:19 AM, Peter Levart <peter.levart at gmail.com> wrote:
> ConcurrentLinkedDeque would be very nice if there was a way to get access to
> internal node when adding an element to the deque. One would then be able to
> remove the element in constant time. Something in the lines of this:

People have had similar ideas before.  Google has experimented with
extensions to Collection that exposes internal Node objects, but they
haven't become very popular.  I support the idea in principle, but we
don't know how to best construct such a public API.  The Iterator
interface is similar, and also contains a remove method (unfortunately
with void return).  In some of our other classes (ArrayBlockingQueue)
herculean efforts are required to support Iterator because the current
position of an element is dynamic.  We know how to remove Nodes
efficiently from concurrent double linked lists, but not from single
linked lists.... well ... actually we try to do this for the internal
list of Iterators in ABQ:

        /**
         * Sweeps itrs, looking for and expunging stale iterators.
         * If at least one was found, tries harder to find more.
         * Called only from iterating thread.
         *
         * @param tryHarder whether to start in try-harder mode, because
         * there is known to be at least one iterator to collect
         */
        void doSomeSweeping(boolean tryHarder) {


More information about the Concurrency-interest mailing list