Why is Queue.poll faster than Iteration? (java.util.concurrent.ConcurrentLinkedQueue)

Question

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
...

Answer 1

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?