Why the first time to add object into ArrayList or LinkedList require much more time?

Question

I am testing the performance of ArrayList and LinkedList. The result is what I expected. The ArrayList is generally better for random access and every insertion into LinkedList requires similar time. But I found that the first time for adding the object into ArrayList or LinkedList requires much more time than other.

I have tested the codes on Mac and Linux , the situation is similar. You can download the code and the full result from here.

java PlayArrayList       
0 to 10, elapsedTime: 716362
10 to 20, elapsedTime: 19765
20 to 30, elapsedTime: 10895

$ java PlayLinkedList 
0 to 10, elapsedTime: 704209
10 to 20, elapsedTime: 5867
20 to 30, elapsedTime: 5378

PS: They are measured in nanoseconds.

/* Untilty Class for measuring elapsed time */
public class BenmarkTimer {
    private long startTime;
    private long endTime;

    /* Getter */
    public long getStartTime(){
        return startTime;
    }

    public long getEndTime(){
        return endTime;
    }

    /* Setter */
    private void setStartTime(long t){
        startTime = t;
    }

    private void setEndTime(long t){
        endTime = t;
    }

    /* Method */
    public void start(){
        setStartTime(System.nanoTime());
    } 

    public long end(){
        setEndTime(System.nanoTime());
        return getDuration();
    }

    public void cancel(){
        setStartTime(0);
        setEndTime(0);
    }

    public long getDuration(){
        return getEndTime() - getStartTime();
    }

    /* Unit testing */
    public static void main (String [] args){
        BenmarkTimer timer = new BenmarkTimer();
        timer.start();
        System.out.println("Hello, World for timer");
        timer.end();
        long t = timer.getDuration();
        System.out.println("Start time "+ timer.getStartTime());
        System.out.println("End time "+ timer.getEndTime());
        System.out.println("Elaped time "+ t);
    }
}


import java.util.*;

public class PlayArrayList{
    private int itemCount;
    private BenmarkTimer timer;
    private List<Integer> list; 

    public PlayArrayList(){
        itemCount = 0;
        timer = new BenmarkTimer();
        list = getList();
    }

    public long addTenIntegers(){
        timer.start();
        for (int i=itemCount; i<(itemCount + 10); i++ ) {
            list.add(i);
        }
        long elapsedTime = timer.end();
        itemCount += 10;

        return elapsedTime;
    }

    public long randomRemove(){
        Random r = new Random();
        int s = list.size();
        int i = r.nextInt(s);

        timer.start();
        list.remove(i);
        return timer.end();
    }

    public String toString(){
        return list.toString();
    }

    /* Factory method */
    protected List<Integer> getList(){
        return new ArrayList<Integer>();
    }

    public static void main (String [] args){
        PlayArrayList playAList = new PlayArrayList();

        /* Add 99 integers */
        long elapsedTime;
        for (int i=0; i<10; i++){
            elapsedTime = playAList.addTenIntegers();
            System.out.print(i*10 + " to " + (i*10+10));
            System.out.println(", elapsedTime: "+ elapsedTime);
        }

        System.out.println("Array content");
        System.out.println(playAList.toString());


        /* Remove 99 integer */
        for (int i=0; i<99; i++){
            elapsedTime = playAList.randomRemove();
            System.out.print("Remove a integer");
            System.out.println(", elapsedTime: "+ elapsedTime);
        }

    }
} 

import java.util.*;

public class PlayLinkedList extends PlayArrayList{
    /* Factory method */
    @Override
    protected List<Integer> getList(){
        return new LinkedList<Integer>();
    }

    public static void main (String [] args){
        PlayLinkedList playAList = new PlayLinkedList();

        /* Add 99 integers */
        long elapsedTime;
        for (int i=0; i<10; i++){
            elapsedTime = playAList.addTenIntegers();
            System.out.print(i*10 + " to " + (i*10+10));
            System.out.println(", elapsedTime: "+ elapsedTime);
        }

        System.out.println("Array content");
        System.out.println(playAList.toString());


        /* Remove 99 integer */
        for (int i=0; i<99; i++){
            elapsedTime = playAList.randomRemove();
            System.out.print("Remove a integer");
            System.out.println(", elapsedTime: "+ elapsedTime);
        }

    }
}

Does the first `elapsedTime` also account for the time needed to instantiate the `ArrayList` or `LinkedList`? — Zim-Zam O'Pootertoot, Jul 16 '13 at 22:36
I will not download a random zip file. Can't you just post the relevant parts of the code? — jlordo, Jul 16 '13 at 22:37
possible duplicate of [How do I write a correct micro-benchmark in Java?](http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) — Luiggi Mendoza, Jul 16 '13 at 22:40
The times suggest that there is an approximate 700msecs overhead in both cases. What happens if you pass the list as a parameter in addTenElements function? — kon psych, Jul 16 '13 at 23:02
The main reason is that you're not fulfilling a right micro benchmark. For this, refer to the possible dup question. — Luiggi Mendoza, Jul 16 '13 at 23:03

score 0 · Answer 1 · edited May 23 '17 at 11:56

I guess the main cause of this problem is the rule 4 from here, the initialization effects of new class. I created another object first to do the operation for initialization. The class used at the first time always requires longer time for initialization. After that, the duration of the operation will be much shorter.

   PlayArrayList playAListInit = new PlayArrayList();
   long firstTime = playAListInit.addTenIntegers();
   System.out.println("First time: "+ firstTime);

   PlayArrayList playAList = new PlayArrayList();

Then the result will look like:

java PlayArrayList
First time: 710000
0 to 10, elapsedTime: 6000
10 to 20, elapsedTime: 12000
20 to 30, elapsedTime: 9000

Why the first time to add object into ArrayList or LinkedList require much more time?

1 Answers1