Java repeated object allocations perfomance impact

Question

Why the LinkedList takes 10x slower than regular array(no new allocations) for big n:

  Deque<Boolean> tail = new LinkedList<>();
  for (int i = 1; i <= n; i++) {
       tail.addFirst(true);
       tail.pollLast();
  }

My first gues was gc time but it takes 100 ms out of 3.5 sec only. Whats the best way to locate the reason behind this?

A linked list requires that a new node be allocated every time an element is added. An array or `ArrayList` doesn't, because you'll allocate a large number of slots all at once to hold the elements. Allocation takes time. — ajb, Jan 02 '17 at 00:06
You can find your answer maybe here. Please look at http://stackoverflow.com/questions/1589813/when-to-use-a-list-over-an-array-in-java . — Büşra GÜL, Jan 02 '17 at 00:37

Stephen C · Accepted Answer · 2017-01-02T00:54:02.323

Whats the best way to locate the reason behind this?

There are many ways:

Turn your example into a proper benchmark and run it using a profiler. Then look where the time is being spent.
Look at the source code for the LinkedList methods you are calling.
Examine the byte codes produced by the Javac compiler for your code and the LinkedList code.
Examine the native code produced by the JIT compiler for your code and the LinkedList code.

(I will leave you to investigate this yourself, since I doubt that it will show anything particularly unexpected.)

My first guess was gc time but it takes 100 ms out of 3.5 sec only.

It is likely that most of the time goes in allocating and initialize the linked list node objects, and in other overheads of the list methods.

If the GC did need to run while building the list, then the GC overhead would be a bit greater in the LinkedList case than the array case. But I suspect that what is actually happening is that the GC is actually reclaiming objects created during code loading and (maybe) JIT compilation. The amount of actual collectable garbage produced during the list / array building should be zero ... in both cases.

It is also possible that your benchmarking methodology is distorting the results. For example, I note that your pollLast call is not doing anything useful ... with respect to building the list. Another problem could be that you are not allowing for JVM warmup effects.

In general, the 10x difference you are seeing corresponds to "received wisdom" on performance of Java lists versus arrays. If you used an ArrayList instead of a LinkedList, the performance would be closer to a bare array, especially if you gave a good estimate for the ArrayList capacity.

Java repeated object allocations perfomance impact

1 Answers1