Time-consuming problem of inserting 10,000,000 elements into ArrayList and LinkedList

Question

I have some problems when I test the time it takes to insert 10,000,000 elements into ArrayList and LinkedList. When I put the test code at both ends in two main() functions, the time spent on the LinkedList is greater than about ArrayList, which is about twice.

When I put both ends of the code in the same main() method and the ArrayList is inserted first, the ArrayList takes longer than the LinkedList, which is about twice as large. I want to know what happened?
In theory, it should be that ArrayList takes less time.

The first piece of code:

public static void main(String[] args) {
    long begin2 = System.currentTimeMillis();
    List<Integer> l2 = new LinkedList<>();
    for (int i = 0; i < 10000000; i++) {
        l2.add(Integer.MAX_VALUE);
    }
    long end2 = System.currentTimeMillis();
    System.out.println(end2 - begin2); //Time: 12362

}

public static void main(String[] args) {
    long begin1 = System.currentTimeMillis();
    List<Integer> l1 = new ArrayList<>();
    for (int i = 0; i < 10000000; i++) {
        l1.add(Integer.MAX_VALUE);
    }
    long end1 = System.currentTimeMillis();
    System.out.println(end1 - begin1); //Time: 7531
}

Second piece of code:

public static void main(String[] args) {
    long begin1 = System.currentTimeMillis();
    List<Integer> l1 = new ArrayList<>();
    for (int i = 0; i < 10000000; i++) {
        l1.add(Integer.MAX_VALUE);
    }
    long end1 = System.currentTimeMillis();
    System.out.println(end1 - begin1); //Time: 7555

    long begin2 = System.currentTimeMillis();
    List<Integer> l2 = new LinkedList<>();
    for (int i = 0; i < 10000000; i++) {
        l2.add(Integer.MAX_VALUE);
    }
    long end2 = System.currentTimeMillis();
    System.out.println(end2 - begin2); //Time: 3533

 }

The next code makes me even more confused, because the time difference between the two pieces of code is not so obvious：

`public static void main(String[] args) {
        try {
            Thread.sleep(10000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        long begin1 = System.currentTimeMillis();
        List<Integer> l1 = new ArrayList<>();
        for (int i = 0; i < 10000000; i++) {
            l1.add(Integer.MAX_VALUE);
        }
        long end1 = System.currentTimeMillis();
        System.out.println(end1 - begin1); //Time: 4542

        long begin2 = System.currentTimeMillis();
        List<Integer> l2 = new LinkedList<>();
        for (int i = 0; i < 10000000; i++) {
            l2.add(Integer.MAX_VALUE);
        }
        long end2 = System.currentTimeMillis();
        System.out.println(end2 - begin2); //Time: 4325
    }`

Your second piece of code didn't remove the first list from memory, and the JVM was already "warmed up" — OneCricketeer, Jul 16 '19 at 06:09
@aku why is the time difference being small confuse you? Both ArrayList and LinkedList have an amortized insertion time of O(1). The main difference is that ArrayList may have to double its size + copy once it gets past a certain point, and LinkedList just allocates a new node + inserts to the back. — newbane2, Jul 17 '19 at 13:17

newbane2 · Answer 1 · 2019-07-16T12:08:53.673

0

After looking into this a bit more the cause seems to be with JVM

take a look at this code / results

public static void main(String[] args) {

        long begin0 = System.currentTimeMillis();
        List<Integer> l0 = new LinkedList<>();
        for (int i = 0; i < 10000000; i++) {
            l0.add(Integer.MAX_VALUE);
        }
        long end0 = System.currentTimeMillis();
        System.out.println(end0 - begin0); //Time: 12992

        long begin1 = System.currentTimeMillis();
        List<Integer> l1 = new ArrayList<>();
        for (int i = 0; i < 10000000; i++) {
            l1.add(Integer.MAX_VALUE);
        }
        long end1 = System.currentTimeMillis();
        System.out.println(end1 - begin1); //Time: 1277

        long begin2 = System.currentTimeMillis();
        List<Integer> l2 = new LinkedList<>();
        for (int i = 0; i < 10000000; i++) {
            l2.add(Integer.MAX_VALUE);
        }
        long end2 = System.currentTimeMillis();
        System.out.println(end2 - begin2); //Time: 1455
    }

Notice that the first loop that runs takes a significantly longer time than the third loop even though it's the exact same code.

Seems like the cause is startup time overhead

Why is the JVM slow to start?

https://en.wikipedia.org/wiki/Java_performance#Startup_time

edited Jul 16 '19 at 12:08

answered Jul 16 '19 at 06:05

newbane2

130
5

For CPU problems, After I run the code multiple times, the results are almost the same. – naokeziteng Jul 16 '19 at 07:06
For caching problems,ArrayList and LinkedList use different data structures. LinkedList is composed of multiple nodes. Each node is an object of internal class Node, so I think it should not be a cache problem. – naokeziteng Jul 16 '19 at 07:11
For the precision of System.currentTimeMillis(),I use the long type to record the timestamp, and I think the current return value has not reached the magnitude of the precision problem. – naokeziteng Jul 16 '19 at 07:14
For the compiler optimization,I am not familiar with the bytecode instructions. I decompile the .class files and found no big differences. Can you please help analyze it? – naokeziteng Jul 16 '19 at 07:17
So I just ran this myself, it seems like it's most likely something with JVM. I'll edit my original comment with the final results. – newbane2 Jul 16 '19 at 12:02
The JVM should be started successfully before the main() method is executed, so I don't think it is a startup time issue. But the comparison of the next two pieces of code made me confused.I'll edit my question to show this. – naokeziteng Jul 17 '19 at 01:49
Clearly whatever is causing this side effect has to do with some operation going on at the start of the application. Perhaps it's the garbage collector starting up, or some other startup operation running on a different thread. – newbane2 Jul 17 '19 at 13:10

Time-consuming problem of inserting 10,000,000 elements into ArrayList and LinkedList

1 Answers1