why adding first item into collection much slower than second?

user_1518100 0
Viewed 102

I came across huge performance difference between adding 1st and 2nd item into a collection(tried ArrayList and HashSet), but I cannot explain why. Have searched but didn't find any answer.

public class Main {

    public static void main(String[] args) {
        // also tried HashSet
        // also tried new ArrayList<>(2)
        ArrayList<String> collection = new ArrayList<>();
        long t1 = System.nanoTime();
        collection.add("a");
        long t2 = System.nanoTime();
        collection.add("b");
        long t3 = System.nanoTime();
        System.out.println(String.valueOf(t2 - t1) + "\n"
                + String.valueOf(t3 - t2));
        //typical output:
        //4399
        //1201
    }
}

Some guess:

  • because collection is lazily initialzed when adding 1st item?
  • or I used the wrong way to measure performance?
  • or related to how jvm works(which is beyond my knowledge)?

Environment: jdk11, win10, intellij.

timing arraylist collections java performance
2 Answers

All your three guesses are correct :)

You are asking a good question. Just be warned: Microbenchmarks are so treacherous that you may easily come to a completely wrong assumption about the speed of the parts of your code. You were right with the lazy initialization, but it was rather a good luck :)

The most important thing is that you are right with your guess that you "used the wrong way to measure performance".

You cannot measure the speed of a Java application like this. It is simply not possible. The process is too random and too dependent on many other factors, especially JIT (Just in Time optimization) in runtime.

Try have a look e.g. here: https://www.baeldung.com/java-microbenchmark-harness, try to run it and think how it works.

TL;DR: The JVM must be be first "warmed-up", then you have to run the tested code multiple times and calculate an average time. And still there might be a lot of optimization which causes that some code is not executed at all :)

If you don't want to play with the microbenchmark library, at least move your code into a method and call the method 20 times. I just did it (only replaced \n with ---) and the result is like this:

10800---1400
1500---200
600---100
500---100
700---100
400---100
400---100
400---100
400---100
500---100
400---100
400---100
400---100
400---100
300---100
400---100
300---100
500---100
400---100
300---100

As you can see, the warming up was the most significant factor. However the influence of the lazy initialization is also visible.

user_28868910

This is because Of lazily initialized. when you are running this line

ArrayList<String> collection = new ArrayList<>();

it is only holding a reference to the list but the actual memory allocation does not happen for that list. But when you are adding the very first element to the collection then it is first allocating memory for the next 10 elements of the List (10 is the default size of array list) after that adding the first value. Results of the next 9 elements will take less time to insert but again for the 11th element, it will take more time than previous.

    public static void main(String[] args) {

    ArrayList<String> collection = new ArrayList<>();
    
    for (int i = 0; i < 12; i++) {
          long t1 = System.nanoTime();
          collection.add("a");
          long t2 = System.nanoTime();
          System.out.println("Index : "+ (i+1) +": Time: "+ String.valueOf(t2 - t1));
    }
    /** Output:
     *  Index : 1: Time: 6800
        Index : 2: Time: 800
        Index : 3: Time: 500
        Index : 4: Time: 700
        Index : 5: Time: 600
        Index : 6: Time: 500
        Index : 7: Time: 600
        Index : 8: Time: 600
        Index : 9: Time: 500
        Index : 10: Time: 500
        Index : 11: Time: 2800
        Index : 12: Time: 500
     */

}
user_92453060
Related