ArrayList capacity size increasing strange behavio

问题:

When ArrayList wants to store more elements than actual capacity it increases the capacity. It is very cost efficient operation since we actually copy all data from previous ArrayList to new ArrayList with larger capacity. However I wonder that maybe some operations with capacity are not proceeded when ArrayList just needs more space - but much before. I wonder what takes such long time for "slow indexes" from my output and increasing capacity is my only one idea. Here is my code:

import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.List;

public class MainArr {
    ArrayList<Integer> normalList = new ArrayList<Integer>();

    public static void main(String[] args) throws Exception {
        MainArr m = new MainArr();
        m.addElements();
    }

    public void addElements() throws Exception {
        long startTime = System.currentTimeMillis();
        for (int j = 0; j < 20000000; j++) {
            if (j % 500000 == 0) {
            System.out.println("j:" + j + " capacity:" + getCapacity(this.normalList));
        }
        long addTime = System.currentTimeMillis();
        this.normalList.add(j);
        if (System.currentTimeMillis() - addTime > 50) {
            System.out.println("slow index-" + j + " - time:" + (System.currentTimeMillis() - addTime));
        }
    }
    System.out.println("End after:" + (System.currentTimeMillis() - startTime));
}

int getCapacity(List al) throws Exception {
    Field field = ArrayList.class.getDeclaredField("elementData");
    field.setAccessible(true);
    return ((Object[]) field.get(al)).length;
    }
}

Output:

j:0 capacity:0
j:500000 capacity:540217
j:1000000 capacity:1215487
j:1500000 capacity:1823230
j:2000000 capacity:2734845
j:2500000 capacity:2734845
j:3000000 capacity:4102267
j:3500000 capacity:4102267
j:4000000 capacity:4102267
slow index-4102267 - time:1203 //We need more space in ArrayList.That's why it takes some time.
j:4500000 capacity:6153400
j:5000000 capacity:6153400
j:5500000 capacity:6153400
j:6000000 capacity:6153400
j:6500000 capacity:9230100
slow index-6758010 - time:1477 //We dont need to increase capacity. But we stop for a moment...
j:7000000 capacity:9230100 //... and we have the same capacity
j:7500000 capacity:9230100
j:8000000 capacity:9230100
j:8500000 capacity:9230100
j:9000000 capacity:9230100
j:9500000 capacity:13845150 // Somehow capacity is increased insanely fast
j:10000000 capacity:13845150
j:10500000 capacity:13845150
j:11000000 capacity:13845150
j:11500000 capacity:13845150
j:12000000 capacity:13845150
slow index-12426474 - time:3168 //We dont need to increase capacity. But we stop for a moment...
j:12500000 capacity:13845150 //... and we have the same capacity
j:13000000 capacity:13845150
j:13500000 capacity:13845150
j:14000000 capacity:20767725  // Somehow capacity is increased insanely fast
j:14500000 capacity:20767725
slow index-14639924 - time:144  
j:15000000 capacity:20767725
j:15500000 capacity:20767725
j:16000000 capacity:20767725
j:16500000 capacity:20767725
j:17000000 capacity:20767725
j:17500000 capacity:20767725
j:18000000 capacity:20767725
j:18500000 capacity:20767725
j:19000000 capacity:20767725
j:19500000 capacity:20767725
slow index-19980735 - time:218
End after:6990

回答1:

ArrayList code is optimized to start the capacity at 10, and grow it by 1.5 times each time when more space is needed.

You can detect precise grows points with a modified version of your program:

public void addElements() throws Exception {
    int lastCap = -1;
    for (int j = 0; j < 1000000; j++) {
        this.normalList.add(j);
        int cap = getCapacity(this.normalList);
        if (cap != lastCap) {
            System.out.println("size:" + normalList.size() + " capacity:" + cap);
            lastCap = cap;
        }
    }
}

int getCapacity(List al) throws Exception {
    Field field = ArrayList.class.getDeclaredField("elementData");
    field.setAccessible(true);
    return ((Object[]) field.get(al)).length;
}

This prints the following numbers:

size:1 capacity:10
size:11 capacity:15
size:16 capacity:22
size:23 capacity:33
size:34 capacity:49
size:50 capacity:73
size:74 capacity:109
... // And so on

The source code responsible for growing the list is in ensureCapacity method, it goes as follows:

int newCapacity = (oldCapacity * 3)/2 + 1;

This is an equivalent of integer multiplication by 1.5.

回答2:

In order to improve performance try to define big capacity on the ArrayList instantiation. For instance:

List<Users> users = new ArrayList<>(100000);
users.add(new User("John", "Doe"));

This will help you only in cases you know the desired capacity beforehand`. If you do not know how many instances will be there consider using another data structures.

For instance, take a look at implementations of the Queue interface, specifically to the LinkedList. This data structure has a constant time of adding a new element but is bad for getting elements by index when they are in the middle of the list. Note that LinkedList also implements the List interface, as well as ArrayList so the following syntax is valid:

List<Users> users = new LinkedList<>();
users.add(new User("John", "Doe"));

回答3:

Every time you call the add function, it will call the ensureCapacity functions with size+1 as the minCapacity parameter (the size of the list, not the array behind the list).

You can see the code of ensureCapacity below:

 public void ensureCapacity(int minCapacity) {
         modCount++;
         int oldCapacity = elementData.length;
         if (minCapacity > oldCapacity) {
             Object oldData[] = elementData;
             int newCapacity = (oldCapacity * 3)/2 + 1;
             if (newCapacity < minCapacity)
                 newCapacity = minCapacity;
             // minCapacity is usually close to size, so this is a win:
             elementData = Arrays.copyOf(elementData, newCapacity);
         }
     }

Notice that it will create a new array only if the minCapacity parameter is larger than the current size of the array.

EDIT (thank you @Jyotsana Nandwani):

In JDK 1.7, new way to calculate resize is :

int newCapacity = oldCapacity + (oldCapacity >> 1)

where right shift operator makes sure to increase the capacity by 50% of old capacity, i.e. 1.5 times