0

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

z xt
  • 49
  • 1
  • 5
  • 4
    Related: [How do I write a correct micro-benchmark in Java?](https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) – jhamon Nov 28 '19 at 11:08
  • Also take a look at https://stackoverflow.com/a/53356309/1602555 – Karol Dowbecki Nov 28 '19 at 11:10
  • 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 Nov 28 '19 at 11:11
  • hi, no matter how bad my benchmark program, the performance problem is there. As this link https://stackoverflow.com/questions/19389609/array-vs-arraylist-in-performance 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 Nov 28 '19 at 11:21
  • I believe the duplicate link is not a duplicate of this question. You can see this link for array vs ArrayList: https://stackoverflow.com/questions/19389609/array-vs-arraylist-in-performance, although this isn't the whole story. An int[] array is always going to be faster than a List (unless the optimizer does something really clever) as it uses int primitives and a List has to use objects which have to be dereferenced. You can't do anything to change that. In addition, a linked list is not efficient for iterating over as the code has to follow a reference chain. – rghome Nov 28 '19 at 11:43
  • @zxt You should create a new question where you show the code that is so slow because of ArrayList, we might be able to help you improve its performances. – Bentaye Nov 28 '19 at 12:01
  • 2
    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 Nov 28 '19 at 12:04

2 Answers2

0

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.

rghome
  • 8,529
  • 8
  • 43
  • 62
0

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.

user3663845
  • 209
  • 1
  • 2
  • 8