7

I have a piece of code that gets all the elements from a queue. I do not care about the state of the queue afterwards and I can be assured the queue will not be modified while I am removing the elements from it.

I was initially using an iterator to pull the elements because I thought it would be faster than polling the elements...

but i ran the following test:

ConcurrentLinkedQueue<Object> queue = new ConcurrentLinkedQueue<>();
for (int i=0; i < 1000000; i++)
    queue.add(new Object());

LinkedList<Object> list = new LinkedList<>();
long start = System.currentTimeMillis();
for (Object object: queue)
    list.add(object);
long time1 = System.currentTimeMillis() - start;

list = new LinkedList<>(); 
start = System.currentTimeMillis();
Object object;
while ((object = queue.poll()) != null)
    list.add(object);
long time2 = System.currentTimeMillis() - start;

System.out.println(time1 + " " + time2);

I got the following output (average over 100 runs)

1169 46

My question is: Why is poll faster than iterate? It is completely unintuitive to me because poll will have to modify the queue and iterate will only have to look at the state.

edit --- Gray was right

I ran it in a loop and got the output (should have done this in the first place)

1180 46
1422 25
287 32
14 26
226 26
236 25
12 26
14 25
13 25
13 26
13 25
268 25
13 25
14 176
13 26
13 26
13 25
13 25
13 26
13 24
13 26
13 25
...
nikdeapen
  • 1,581
  • 3
  • 15
  • 27
  • 1
    At a guess? Iteration is trickier in the presence of concurrency. – Louis Wasserman Sep 20 '13 at 18:00
  • 2
    have you tried running the above code several times. before actual reading the values? That allows the hotspot to compile the code. The difference seems is just too big. i ran it 10 times and results varies in both ways. – Claudiu Sep 20 '13 at 18:09
  • 1
    run the code repeatedly. eventually the iterator wins. and toArray is probably even faster. – ZhongYu Sep 20 '13 at 18:13

1 Answers1

12

My question is: Why is poll faster than iterate? It is completely unintuitive to me because poll will have to modify the queue and iterate will only have to look at the state.

This seems to be, as @csoroiu points out, a hotspot compiler issue. Given how Java works, it is very important that you "warm up" your application before you start doing timing calls like this.

If I run your tests 100 times in a method I initially saw vastly different performance due to GC overhead and other JVM magic. However, after adding some .clear() methods and a System.gc() at the end of the method, the performance numbers were more consistent with the iterator winning:

108 143
89 152
83 148
78 140
79 153
90 155
...

See Peter's answer here for some more details: CPU execution time in Java

For a ton of more information about how to properly do micro-benchmarking like this, see this exhaustive answer: How do I write a correct micro-benchmark in Java?

Gray
  • 115,027
  • 24
  • 293
  • 354
  • it is interesting to me tho that iterate requires much more of a warmup than poll – nikdeapen Sep 20 '13 at 18:22
  • No @nikdeapen, that performance cycle moves up and down. The iterator starts to win again in the future. I'm pretty surprised by these results. – Gray Sep 20 '13 at 18:24
  • Ok. After adding `.clear()` and `System.gc()` calls to the method, the numbers stabilized with the iterator being consistently ahead @nikdeapen. – Gray Sep 20 '13 at 18:29
  • @Gray for better results (if you haven't already done so) place each loop body in a separate method. – assylias Sep 20 '13 at 18:30
  • 1
    I see similar results with sub-methods @assylias. I would have been surprised if it made a difference. You think the methods help with hotpot inlining? – Gray Sep 20 '13 at 18:38
  • Yes because main can be compiled while the first loop is running for example and will be optimised for that loop but not necessarily the second one. And it can then be decompiled when the second loop starts - so you might not end up with the best code for both. – assylias Sep 20 '13 at 19:31