ConcurrentLinkedQueue vs. ConcurrentLinkedDeque

classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

ConcurrentLinkedQueue vs. ConcurrentLinkedDeque

Christian Schudt
Hello,
 
I've had performance problems (high CPU) in my app and after research I suspected ConcurrentLinkedQueue to be a possible source (due to [1], [2]).
 
Although I am still not sure it's really the source for my problem, I discovered significant performance differences between ConcurrentLinkedQueue and ConcurrentLinkedDeque:
 
    public static void main(String[] args) {

        Queue<String> queue = new ConcurrentLinkedDeque<>();
        String a = "a";
        String b = "b";
        queue.offer(a);
        for (int i = 0; ; i++) {
            if (i % 1024 == 0) {
                System.out.println("i = " + i);
            }
            queue.offer(b);
            queue.remove(b);
        }
    }

ConcurrentLinkedDeque is much faster! (Just replace it with ConcurrentLinkedQueue, the output becomes very slow)

Not sure, if this is related to JDK-8054446 [2] or if it's "normal".
Any comments?

Is there any reason to prefer ConcurrentLinkedQueue over ConcurrentLinkedDeque?

(I am using JDK 8u60.)

Kind regards,
Christian

[1]: https://perfstories.wordpress.com/2012/08/01/why-does-cpu-utilization-happen-sometimes/
[2]: https://bugs.openjdk.java.net/browse/JDK-8054446

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentLinkedQueue vs. ConcurrentLinkedDeque

Martin Buchholz-3
It's not really expected.  The expectation is (as is written in the source)

     * Empirically, microbenchmarks suggest that this class adds about
     * 40% overhead relative to ConcurrentLinkedQueue, which feels as
     * good as we can hope for.

You're using "interior removes" (remove(Object), which the
implementations support, but we have sometimes regretted that.  If we
could outlaw interior removes, the code would be much simpler.

I'll poke at this a bit.

On Fri, Feb 26, 2016 at 4:58 AM, Christian Schudt
<[hidden email]> wrote:

> Hello,
>
> I've had performance problems (high CPU) in my app and after research I suspected ConcurrentLinkedQueue to be a possible source (due to [1], [2]).
>
> Although I am still not sure it's really the source for my problem, I discovered significant performance differences between ConcurrentLinkedQueue and ConcurrentLinkedDeque:
>
>     public static void main(String[] args) {
>
>         Queue<String> queue = new ConcurrentLinkedDeque<>();
>         String a = "a";
>         String b = "b";
>         queue.offer(a);
>         for (int i = 0; ; i++) {
>             if (i % 1024 == 0) {
>                 System.out.println("i = " + i);
>             }
>             queue.offer(b);
>             queue.remove(b);
>         }
>     }
>
> ConcurrentLinkedDeque is much faster! (Just replace it with ConcurrentLinkedQueue, the output becomes very slow)
>
> Not sure, if this is related to JDK-8054446 [2] or if it's "normal".
> Any comments?
>
> Is there any reason to prefer ConcurrentLinkedQueue over ConcurrentLinkedDeque?
>
> (I am using JDK 8u60.)
>
> Kind regards,
> Christian
>
> [1]: https://perfstories.wordpress.com/2012/08/01/why-does-cpu-utilization-happen-sometimes/
> [2]: https://bugs.openjdk.java.net/browse/JDK-8054446
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentLinkedQueue vs. ConcurrentLinkedDeque

Martin Buchholz-3
I had completely forgotten about
https://bugs.openjdk.java.net/browse/JDK-8054446
Repeated offer and remove on ConcurrentLinkedQueue lead to an OutOfMemoryError

which is fixed in jdk9, but not backported to jdk8
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentLinkedQueue vs. ConcurrentLinkedDeque

Christian Schudt
I’ve seen that. Is that also the reason for the worse performance?


> Am 26.02.2016 um 18:01 schrieb Martin Buchholz <[hidden email]>:
>
> I had completely forgotten about
> https://bugs.openjdk.java.net/browse/JDK-8054446
> Repeated offer and remove on ConcurrentLinkedQueue lead to an OutOfMemoryError
>
> which is fixed in jdk9, but not backported to jdk8


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentLinkedQueue vs. ConcurrentLinkedDeque

Martin Buchholz-3
Seems very likely.  You could try to prove it...

On Fri, Feb 26, 2016 at 9:04 AM, Christian Schudt
<[hidden email]> wrote:
> I’ve seen that. Is that also the reason for the worse performance?

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentLinkedQueue vs. ConcurrentLinkedDeque

Haim Yadid
Hi Martin 
I wrote a simple JMH benchmark to prove it.
When using ConcurrenLinkedQueue without your fix at JDK-8054446 it is extremely slow your fix solves the problem 
Here are the results :

Benchmark                          Mode  Cnt         Score         Error                 Units
QBench.measureABQ           thrpt    5  17031943.831 ± 8468127.395  ops/s
QBench.measureCLD           thrpt    5  15410606.543 ±  551687.064  ops/s
QBench.measureCLQFixed  thrpt    5  27674624.318 ± 1849425.328  ops/s
QBench.measureCLQOrig    thrpt    5      5527.394 ±    2371.913        ops/s

Here is the code :




import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.Setup;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Threads;
import org.openjdk.jmh.annotations.Warmup;

import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.ConcurrentLinkedDeque;

import java.util.concurrent.ExecutionException;


@Fork(1)
@Threads(1)
@BenchmarkMode({Mode.Throughput})
@Warmup(iterations = 5)
@Measurement(iterations = 5)
public class QBench {
static final String a = "a";
static final String b = "b";
public static final int NUM_PRE = 1;
@State(Scope.Benchmark)
public static class ArrayBlockingQueueState {
Queue<String> queue = new ArrayBlockingQueue<String>(1000);
@Setup
public void setup() throws ExecutionException, InterruptedException {
for(int i=0;i<NUM_PRE;i++) queue.offer(a);
}
}
@Benchmark
public Object measureABQ(final ArrayBlockingQueueState arrayBlockingQueueState) throws Exception {
Queue queue = arrayBlockingQueueState.queue;
queue.offer(b);
return queue.remove(b);

}



@State(Scope.Benchmark)
public static class ConcurrentLinkedDequeState {
Queue<String> queue = new ConcurrentLinkedDeque<>();
@Setup
public void setup() throws ExecutionException, InterruptedException {
for(int i=0;i<NUM_PRE;i++) queue.offer(a);
}
}
@Benchmark
public Object measureCLD(final ConcurrentLinkedDequeState concurrentLinkedDequeState) throws Exception {
Queue queue = concurrentLinkedDequeState.queue;
queue.offer(b);
return queue.remove(b);
}


@State(Scope.Benchmark)
public static class ConcurrentLinkedQueueState {
Queue<String> queue = new ConcurrentLinkedQueue<>();
@Setup
public void setup() throws ExecutionException, InterruptedException {
for(int i=0;i<NUM_PRE;i++) queue.offer(a);
}
}

@Benchmark
public Object measureCLQFixed(final ConcurrentLinkedQueueState concurrentLinkedQueueState) throws Exception {
Queue queue = concurrentLinkedQueueState.queue;
queue.offer(b);
return queue.remove(b);
}

@State(Scope.Benchmark)
public static class ConcurrentLinkedQueueOrigState {
Queue<String> queue = new java.util.concurrent.ConcurrentLinkedQueue<>();
@Setup
public void setup() throws ExecutionException, InterruptedException {
for(int i=0;i<NUM_PRE;i++) queue.offer(a);
}
}

@Benchmark
public Object measureCLQOrig(final ConcurrentLinkedQueueOrigState state) throws Exception {
Queue queue = state.queue;
queue.offer(b);
return queue.remove(b);
}
}

On Fri, Feb 26, 2016 at 7:14 PM, Martin Buchholz <[hidden email]> wrote:
Seems very likely.  You could try to prove it...

On Fri, Feb 26, 2016 at 9:04 AM, Christian Schudt
<[hidden email]> wrote:
> I’ve seen that. Is that also the reason for the worse performance?

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest



--
Haim Yadid | Performization Expert 
Performize-IT | t +972-54-7777132
www.performize-it.com

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentLinkedQueue vs. ConcurrentLinkedDeque

Christian Schudt
Hi,

thanks for proving :-)

Do you think it’s fairly safe to assume, that the OOM issue (JDK-8054446) is also the cause for a high CPU usage?

We use CLQ in a simple LRU cache implementation, where a remove() happens every time an element is added to or get from cache (in order to rearrange elements for the least-recently-used logic). After a few hours/days our app has very high CPU, maybe because the remove() takes longer and longer…

This seems to be the same issue:
https://issues.apache.org/jira/browse/AMQ-5337

Ok, even when it’s fixed in JDK 9, when would you use a CLQ over a CLDeque? Is it „only“ to save 40% performance when only needing a queue? (of course still worth it). Maybe the public JavaDoc should mention it.

Best,
Christian


> Am 27.02.2016 um 15:00 schrieb Haim Yadid <[hidden email]>:
>
> Hi Martin
> I wrote a simple JMH benchmark to prove it.
> When using ConcurrenLinkedQueue without your fix at JDK-8054446 it is extremely slow your fix solves the problem
> Here are the results :
>
> Benchmark                          Mode  Cnt         Score         Error                 Units
> QBench.measureABQ           thrpt    5  17031943.831 ± 8468127.395  ops/s
> QBench.measureCLD           thrpt    5  15410606.543 ±  551687.064  ops/s
> QBench.measureCLQFixed  thrpt    5  27674624.318 ± 1849425.328  ops/s
> QBench.measureCLQOrig    thrpt    5      5527.394 ±    2371.913        ops/s
>
> Here is the code :
>
>
>
>
> import org.openjdk.jmh.annotations.Benchmark;
> import org.openjdk.jmh.annotations.BenchmarkMode;
> import org.openjdk.jmh.annotations.Fork;
> import org.openjdk.jmh.annotations.Measurement;
> import org.openjdk.jmh.annotations.Mode;
> import org.openjdk.jmh.annotations.Scope;
> import org.openjdk.jmh.annotations.Setup;
> import org.openjdk.jmh.annotations.State;
> import org.openjdk.jmh.annotations.Threads;
> import org.openjdk.jmh.annotations.Warmup;
>
> import java.util.Queue;
> import java.util.concurrent.ArrayBlockingQueue;
> import java.util.concurrent.ConcurrentLinkedDeque;
>
> import java.util.concurrent.ExecutionException;
>
>
> @Fork(1)
> @Threads(1)
> @BenchmarkMode({Mode.Throughput})
> @Warmup(iterations = 5)
> @Measurement(iterations = 5)
> public class QBench {
>   static final String a = "a";
>   static final String b = "b";
>   public static final int NUM_PRE = 1;
>   @State(Scope.Benchmark)
>   public static class ArrayBlockingQueueState {
>     Queue<String> queue = new ArrayBlockingQueue<String>(1000);
>     @Setup
>     public void setup() throws ExecutionException, InterruptedException {
>       for(int i=0;i<NUM_PRE;i++) queue.offer(a);
>     }
>   }
>   @Benchmark
>   public Object measureABQ(final ArrayBlockingQueueState arrayBlockingQueueState) throws Exception {
>     Queue queue = arrayBlockingQueueState.queue;
>     queue.offer(b);
>     return queue.remove(b);
>
>   }
>
>
>
>   @State(Scope.Benchmark)
>   public static class ConcurrentLinkedDequeState {
>     Queue<String> queue = new ConcurrentLinkedDeque<>();
>     @Setup
>     public void setup() throws ExecutionException, InterruptedException {
>       for(int i=0;i<NUM_PRE;i++) queue.offer(a);
>     }
>   }
>   @Benchmark
>   public Object measureCLD(final ConcurrentLinkedDequeState concurrentLinkedDequeState) throws Exception {
>     Queue queue = concurrentLinkedDequeState.queue;
>     queue.offer(b);
>     return  queue.remove(b);
>   }
>
>
>   @State(Scope.Benchmark)
>   public static class ConcurrentLinkedQueueState {
>     Queue<String> queue = new ConcurrentLinkedQueue<>();
>     @Setup
>     public void setup() throws ExecutionException, InterruptedException {
>       for(int i=0;i<NUM_PRE;i++) queue.offer(a);
>     }
>   }
>
>   @Benchmark
>   public Object measureCLQFixed(final ConcurrentLinkedQueueState concurrentLinkedQueueState) throws Exception {
>     Queue queue = concurrentLinkedQueueState.queue;
>     queue.offer(b);
>     return queue.remove(b);
>   }
>
>   @State(Scope.Benchmark)
>   public static class ConcurrentLinkedQueueOrigState {
>     Queue<String> queue = new java.util.concurrent.ConcurrentLinkedQueue<>();
>     @Setup
>     public void setup() throws ExecutionException, InterruptedException {
>       for(int i=0;i<NUM_PRE;i++) queue.offer(a);
>     }
>   }
>
>   @Benchmark
>   public Object measureCLQOrig(final ConcurrentLinkedQueueOrigState state) throws Exception {
>     Queue queue = state.queue;
>     queue.offer(b);
>     return queue.remove(b);
>   }
> }
>
> On Fri, Feb 26, 2016 at 7:14 PM, Martin Buchholz <[hidden email]> wrote:
> Seems very likely.  You could try to prove it...
>
> On Fri, Feb 26, 2016 at 9:04 AM, Christian Schudt
> <[hidden email]> wrote:
> > I’ve seen that. Is that also the reason for the worse performance?
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
>
> --
> Haim Yadid | Performization Expert
> Performize-IT | t +972-54-7777132
> www.performize-it.com


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentLinkedQueue vs. ConcurrentLinkedDeque

Martin Buchholz-3
Well done! Y'all guilted me into backporting to jdk8
https://bugs.openjdk.java.net/browse/JDK-8150780
There's even a test.

On Sat, Feb 27, 2016 at 1:47 PM, Christian Schudt
<[hidden email]> wrote:

> Hi,
>
> thanks for proving :-)
>
> Do you think it’s fairly safe to assume, that the OOM issue (JDK-8054446) is also the cause for a high CPU usage?
>
> We use CLQ in a simple LRU cache implementation, where a remove() happens every time an element is added to or get from cache (in order to rearrange elements for the least-recently-used logic). After a few hours/days our app has very high CPU, maybe because the remove() takes longer and longer…
>
> This seems to be the same issue:
> https://issues.apache.org/jira/browse/AMQ-5337
>
> Ok, even when it’s fixed in JDK 9, when would you use a CLQ over a CLDeque? Is it „only“ to save 40% performance when only needing a queue? (of course still worth it). Maybe the public JavaDoc should mention it.
>
> Best,
> Christian
>
>
>> Am 27.02.2016 um 15:00 schrieb Haim Yadid <[hidden email]>:
>>
>> Hi Martin
>> I wrote a simple JMH benchmark to prove it.
>> When using ConcurrenLinkedQueue without your fix at JDK-8054446 it is extremely slow your fix solves the problem
>> Here are the results :
>>
>> Benchmark                          Mode  Cnt         Score         Error                 Units
>> QBench.measureABQ           thrpt    5  17031943.831 ± 8468127.395  ops/s
>> QBench.measureCLD           thrpt    5  15410606.543 ±  551687.064  ops/s
>> QBench.measureCLQFixed  thrpt    5  27674624.318 ± 1849425.328  ops/s
>> QBench.measureCLQOrig    thrpt    5      5527.394 ±    2371.913        ops/s
>>
>> Here is the code :
>>
>>
>>
>>
>> import org.openjdk.jmh.annotations.Benchmark;
>> import org.openjdk.jmh.annotations.BenchmarkMode;
>> import org.openjdk.jmh.annotations.Fork;
>> import org.openjdk.jmh.annotations.Measurement;
>> import org.openjdk.jmh.annotations.Mode;
>> import org.openjdk.jmh.annotations.Scope;
>> import org.openjdk.jmh.annotations.Setup;
>> import org.openjdk.jmh.annotations.State;
>> import org.openjdk.jmh.annotations.Threads;
>> import org.openjdk.jmh.annotations.Warmup;
>>
>> import java.util.Queue;
>> import java.util.concurrent.ArrayBlockingQueue;
>> import java.util.concurrent.ConcurrentLinkedDeque;
>>
>> import java.util.concurrent.ExecutionException;
>>
>>
>> @Fork(1)
>> @Threads(1)
>> @BenchmarkMode({Mode.Throughput})
>> @Warmup(iterations = 5)
>> @Measurement(iterations = 5)
>> public class QBench {
>>   static final String a = "a";
>>   static final String b = "b";
>>   public static final int NUM_PRE = 1;
>>   @State(Scope.Benchmark)
>>   public static class ArrayBlockingQueueState {
>>     Queue<String> queue = new ArrayBlockingQueue<String>(1000);
>>     @Setup
>>     public void setup() throws ExecutionException, InterruptedException {
>>       for(int i=0;i<NUM_PRE;i++) queue.offer(a);
>>     }
>>   }
>>   @Benchmark
>>   public Object measureABQ(final ArrayBlockingQueueState arrayBlockingQueueState) throws Exception {
>>     Queue queue = arrayBlockingQueueState.queue;
>>     queue.offer(b);
>>     return queue.remove(b);
>>
>>   }
>>
>>
>>
>>   @State(Scope.Benchmark)
>>   public static class ConcurrentLinkedDequeState {
>>     Queue<String> queue = new ConcurrentLinkedDeque<>();
>>     @Setup
>>     public void setup() throws ExecutionException, InterruptedException {
>>       for(int i=0;i<NUM_PRE;i++) queue.offer(a);
>>     }
>>   }
>>   @Benchmark
>>   public Object measureCLD(final ConcurrentLinkedDequeState concurrentLinkedDequeState) throws Exception {
>>     Queue queue = concurrentLinkedDequeState.queue;
>>     queue.offer(b);
>>     return  queue.remove(b);
>>   }
>>
>>
>>   @State(Scope.Benchmark)
>>   public static class ConcurrentLinkedQueueState {
>>     Queue<String> queue = new ConcurrentLinkedQueue<>();
>>     @Setup
>>     public void setup() throws ExecutionException, InterruptedException {
>>       for(int i=0;i<NUM_PRE;i++) queue.offer(a);
>>     }
>>   }
>>
>>   @Benchmark
>>   public Object measureCLQFixed(final ConcurrentLinkedQueueState concurrentLinkedQueueState) throws Exception {
>>     Queue queue = concurrentLinkedQueueState.queue;
>>     queue.offer(b);
>>     return queue.remove(b);
>>   }
>>
>>   @State(Scope.Benchmark)
>>   public static class ConcurrentLinkedQueueOrigState {
>>     Queue<String> queue = new java.util.concurrent.ConcurrentLinkedQueue<>();
>>     @Setup
>>     public void setup() throws ExecutionException, InterruptedException {
>>       for(int i=0;i<NUM_PRE;i++) queue.offer(a);
>>     }
>>   }
>>
>>   @Benchmark
>>   public Object measureCLQOrig(final ConcurrentLinkedQueueOrigState state) throws Exception {
>>     Queue queue = state.queue;
>>     queue.offer(b);
>>     return queue.remove(b);
>>   }
>> }
>>
>> On Fri, Feb 26, 2016 at 7:14 PM, Martin Buchholz <[hidden email]> wrote:
>> Seems very likely.  You could try to prove it...
>>
>> On Fri, Feb 26, 2016 at 9:04 AM, Christian Schudt
>> <[hidden email]> wrote:
>> > I’ve seen that. Is that also the reason for the worse performance?
>>
>> _______________________________________________
>> Concurrency-interest mailing list
>> [hidden email]
>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>
>>
>>
>> --
>> Haim Yadid | Performization Expert
>> Performize-IT | t +972-54-7777132
>> www.performize-it.com
>

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentLinkedQueue vs. ConcurrentLinkedDeque

Martin Buchholz-3
In reply to this post by Christian Schudt
On Sat, Feb 27, 2016 at 1:47 PM, Christian Schudt
<[hidden email]> wrote:
> Ok, even when it’s fixed in JDK 9, when would you use a CLQ over a CLDeque? Is it „only“ to save 40% performance when only needing a queue? (of course still worth it). Maybe the public JavaDoc should mention it.

It's funny you ask that.  I love ConcurrentLinkedDeque, but mostly for
the cool tech ("it's impossible to safely update a lock-free doubly
linked list"), but I don't have a good example of when you need it -
in practice a concurrent queue is usually good enough.
ConcurrentLinkedQueue is simpler and uses less computing resources

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentLinkedQueue vs. ConcurrentLinkedDeque

Peter Levart


On 02/28/2016 07:14 AM, Martin Buchholz wrote:
On Sat, Feb 27, 2016 at 1:47 PM, Christian Schudt
[hidden email] wrote:
Ok, even when it’s fixed in JDK 9, when would you use a CLQ over a CLDeque? Is it „only“ to save 40% performance when only needing a queue? (of course still worth it). Maybe the public JavaDoc should mention it.
It's funny you ask that.  I love ConcurrentLinkedDeque, but mostly for
the cool tech ("it's impossible to safely update a lock-free doubly
linked list"), but I don't have a good example of when you need it -
in practice a concurrent queue is usually good enough.
ConcurrentLinkedQueue is simpler and uses less computing resources

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:

    http://cr.openjdk.java.net/~plevart/jdk9-dev/ConcurrentLinkedDeque.Insert/webrev.01/

Regards, Peter

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentLinkedQueue vs. ConcurrentLinkedDeque

Martin Buchholz-3
On Sun, Feb 28, 2016 at 5:19 AM, Peter Levart <[hidden email]> 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) {
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest