1

Yesterday I ran a benchmark in Java 17 where I repeatedly created a new Arraylist and Linkedlist and added 10.000.000 Elements to it.

By the nature of a LinkedList adding elements (creating a LinkedObject an putting it at the end) should be much faster than adding to an ArrayList. (Copying whole array in anotherone that is slightly larger.)

Are native functions like arraycopy() really that much faster? The only thing the LinkedList was better at was merging two LinkedLists together.

Alex R
  • 11,364
  • 15
  • 100
  • 180
  • 3
    Does this answer your question? [Performance differences between ArrayList and LinkedList](https://stackoverflow.com/questions/10656471/performance-differences-between-arraylist-and-linkedlist) – Melchizedek Nov 05 '21 at 09:27
  • 7
    [This answer](https://stackoverflow.com/a/323889/40342) summarizes why you should basically never use `LinkedList`. Even Joshua Bloch (who wrote `LinkedList`) [never users it](https://twitter.com/joshbloch/status/583813919019573248). – Joachim Sauer Nov 05 '21 at 09:28
  • ArrayList only has to copy when it reallocates, which is infrequent. And it doesn't have to do any bookkeeping otherwise, or generate compressed references for links, basically just memset up to the allocation limit. (JVM JIT optimizers probably aren't smart enough to optimize away multiple reallocations and just allocate the final size in the first place). – Peter Cordes Nov 05 '21 at 09:49
  • @Nikolas: As [discussed in comments on the answer here](https://stackoverflow.com/questions/69851017/why-is-an-arraylist-always-faster-than-a-linkedlist#comment123474625_69851318), the accepted answer on [Performance differences between ArrayList and LinkedList](https://stackoverflow.com/q/10656471) is only about inserting in the middle, not at the end, which is what makes ArrayList slower in that case, but not in this case. Not a good duplicate, unless there are other answers that do cover the general case, or something that includes this case. – Peter Cordes Nov 05 '21 at 11:59

1 Answers1

2

Most of the time, adding to an ArrayList won't allocate a new array, since the implementation increases the size of the backing array by 50% when it needs to grow.

This may sound wasteful from a memory perspective, but even a worst-case scenario for a growing ArrayList uses less memory than LinkedList - each entry in a linked list costs an object header + 3 references (prev/value/next), whereas a worst-case growing ArrayList has only 1.5 references per entry (i.e., the array cells used, plus 50% which are as-yet unused).

Anywho, according to my calculations, this means that adding 10 million entries to a default-initiated ArrayList will result in some 35 array-copying actions, which isn't very much. (And yes, System.arraycopy is fast.)

Finally, if you give your array an initial capacity of 10_000_000, there will be zero array copies made. You can try that to see how much the copying really costs.

gustafc
  • 28,465
  • 7
  • 73
  • 99
  • There's a canonical Q&A ([Performance differences between ArrayList and LinkedList](https://stackoverflow.com/q/10656471)) which suggests that ArrayList is slower to create. Since there are reasons why that's not true, that Q&A should get fixed. – Peter Cordes Nov 05 '21 at 09:51
  • 1
    35 array-copying actions, but most of them while it's still small, so not writing the whole final size 36 times. `size * (1 + 1/1.5 + 1/1.5^2 ...)` which converges to about size x 2. – Peter Cordes Nov 05 '21 at 09:54
  • @Hulk: It'd probably be good if a Java performance expert made some edits in the accepted answer, then. Or we can get a new answer written that covers the same broad generalities without misinformation, and maybe get some attention in chat to correct via voting. It isn't a duplicate of the more general Q&A you linked, and specific answers there don't compare time to add N elements to a fresh container. [When to use LinkedList over ArrayList in Java?](https://stackoverflow.com/a/322722) talks about add/delete time, but neglects the fact that ArrayList is fastest for insert at the end. – Peter Cordes Nov 05 '21 at 10:34
  • Another answer on [When to use LinkedList over ArrayList in Java?](https://stackoverflow.com/a/7507740) does have this benchmark, time to add N elements, showing ArrayList way faster, but the only thing it points out is that edit/remove is slower for ArrayList when the numbers actually show it about the same. – Peter Cordes Nov 05 '21 at 10:37
  • 1
    @PeterCordes the accepted answer there is not *wrong* and answers the question asked there (which is, despite the title, focussed on adding and deleting in the middle). However, it does not explain the misconception that caused this question here (how ArrayLists allocate arrays, and with which capacity). That is explained in answers to the more general question. – Hulk Nov 05 '21 at 10:46
  • @Hulk: Ah thanks, I didn't read the question in [Performance differences between ArrayList and LinkedList](https://stackoverflow.com/q/10656471) in enough detail. So not a duplicate of this at all. – Peter Cordes Nov 05 '21 at 10:52
  • 1
    @PeterCordes we can easily simulate the behavior to get the exact number, i.e. `int copies = 0, copied = 0; for(int cap = 10; cap < 10_000_000; cap *= 1.5) { copies++; copied += cap; } System.out.println(copies + " copy operations, copied " + copied + " refs total");`, giving us 27,690,301 refs. Then, we should consider that `LinkedList` creates 10M node objects the size of five to six refs into the Eden space, to be copied to the Survivor space on the next GC. Which is twice the amount of `ArrayList`’s copying actions, even when the nodes are promoted to the Old Gen right on the first GC. – Holger Jan 06 '22 at 11:48
  • 2
    Thinking about it, even the *initialization* of 10M node objects with header and three references performs as many memory writes as the array initialization and 35 copying operations together (assuming a JVM capable of optimizing `Arrays.copyOf(…)`, like HotSpot). – Holger Jan 06 '22 at 12:06