Java Array/ArrayList/LinkedList performance

Question

I used the following code to test the performance between Array/ArrayList/LinkedList

import java.util.ArrayList;
import java.util.LinkedList;

public class Main3 {
    public static void main(String[] args) throws Exception{

        int n = 20000000;
        long bt = 0, et = 0;

        int[] a0 = new int[n];
        ArrayList<Integer> a1 = new ArrayList<>(n);
        LinkedList<Integer> a2 = new LinkedList<>();
        Integer[] a3 = new Integer[n];

        bt = System.currentTimeMillis();
        for(int i=0; i<n; i++){
            a0[i] = i;
        }
        et = System.currentTimeMillis();
        System.out.println("===== loop0 time =======" + (et - bt));

        bt = System.currentTimeMillis();
        for(int i=0; i<n; i++){
            a1.add(i);
        }
        et = System.currentTimeMillis();
        System.out.println("===== loop1 time =======" + (et - bt));

        bt = System.currentTimeMillis();
        for(int i=0; i<n; i++){
            a2.add(i);
        }
        et = System.currentTimeMillis();
        System.out.println("===== loop2 time =======" + (et - bt));


        bt = System.currentTimeMillis();
        for(int i=0; i<n; i++){
            a3[i] = i;
        }
        et = System.currentTimeMillis();
        System.out.println("===== loop3 time =======" + (et - bt));
    }
}

The result is

===== loop0 time =======11
===== loop1 time =======6776
===== loop2 time =======17305
===== loop3 time =======56

Why the ArralyList/LinkedList is so slower than array ? How could I improve the performance.

env: Java: jdk1.8.0_231

Thanks

Don't run your own benchmarks. You'll do it wrong, and you don't need to do it (you can surely find existing proper benchmarks). Secondly, even ignoring your faulty benchmark, that's just the way it is. Arrays are the fastest, but they have a fixed size. If you need a List, then ArrayList is your best bet, and LinkedList has very few actual use cases. — Kayaman
– Kayaman, Commented Nov 28, 2019 at 11:11
hi, no matter how bad my benchmark program, the performance problem is there. As this link stackoverflow.com/questions/19389609/… said, I can ignore the performance. But the real case is I can't. The ArrayList is so slow and have a big influence on my job. So could you give some useful advice not just pay attention on how bad the benchmark code. Thanks. — z xt
– z xt, Commented Nov 28, 2019 at 11:21
I voted to reopen the question, I think OP is right, the question is not about benchmarking, it is about improving performances of his code. OP needs to add the code he wants to be looked up though — Bentaye
– Bentaye, Commented Nov 28, 2019 at 12:04

rghome · Accepted Answer · 2019-11-28 13:03:55Z

There are potential inaccuracies in your benchmark, but the overall ranking of the results is probably correct. You may get faster results for all of the benchmarks if you "warm-up" the code before taking timings to allow the JIT compiler to generate native code and optimise it. Some benchmark results may be closer or even equal.

Iterating over an int array is going to be much faster than iterating over a List of Integer objects. A LinkedList is going to be slowest of all. These statements assume the optimiser doesn't make radical changes.

Let's look at why:

An int array (int[]) is a contiguous area of memory containing your 4 byte ints arranged end-to-end. The loop to iterate over this and set the elements just has to work its way through the block of memory setting each 4 bytes in turn. In principle an index check is required, but in practice the optimiser can realise this isn't necessary and remove it. The JIT compiler is well able to optimise this kind of thing based on native CPU instructions.

An ArrayList of Integer objects contains an array of references which point to individual Integer objects (or are null). Each Integer object will have to be allocated separately (although Java can re-use Integers of small numbers). There is an overhead to allocate new objects and in addition the reference may be 8 bytes instead of 4. Also, if the list size is not specified (though it is in your case) the internal array may need to be reallocated. There is an overhead due to calling the add method instead of assigning to the array directly (the optimizer may remove this though).

Your array of Integer benchmark is similar to the array list but doesn't have the overhead of the list add method call (which has to track the list size). Probably your benchmark overstates the difference between this array and the array list though.

A LinkedList is the worst case. Linked lists are optimised for inserting in the middle. They have references to point to the next item in the list and nodes to hold those references in addition to the Integer object that needs allocating. This is a big memory overhead that also requires some initialisation and you would not use a linked list unless you were expecting to insert a lot of elements into the middle of the list.

user3663845 · Accepted Answer · 2023-06-16 12:57:19Z

While the previous answer is true, LinkedList is in fact quite a bit slower than it needs to be. I have written quite a few JMH benchmarks that compare ArrayList, LinkedList, and two linked list implementations I wrote myself. The reason I wrote those implementations had nothing to do with performance. It's just that I also find LinkedList rather impractical. It sticks too closely to the List interface and does not provide the operations I expect a linked list to have.

I only created the JMH tests to make sure my own implementations wouldn't be too much slower than LinkedList. To my surprise, however, for any measurement I did, my own implementations performed substantially better - sometimes even orders of magnitude better!

I wrote a blog post that discusses the JMH tests. My conclusion was: unless you want to use LinkedList as a kind of queue, pushing/popping elements from the head or tail of the list, there really is no good reason for using it.

Collectives™ on Stack Overflow

Java Array/ArrayList/LinkedList performance

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related