Majkeee Majkeee - 7 months ago 19
Java Question

Why is initial capacity important for deleting from ArrayList?

For my work I have done some tests for time chart.
I have come to something that surprised me and need help understanding it.

I used few data structures as queue and wanted to know how deleting is fast according to number of items. And arraylist with 10 items, deleting from front and not set initial capacity is much slower than the same with set initial capacity (to 15). Why? And why it's same at 100 items.

Here's the chart:
enter image description here

Data Structures: L - implements List, C - set initial capacity, B - removing from back, Q - implements Queue

EDIT:
Appending relevant piece of code

new Thread(new Runnable() {
@Override
public void run()
{
long time;
final int[] arr = {10, 100, 1000, 10000, 100000, 1000000};
for (int anArr : arr)
{
final List<Word> temp = new ArrayList<>();
while (temp.size() < anArr) temp.add(new Item());

final int top = (int) Math.sqrt(anArr);

final List<Word> first = new ArrayList<>();
final List<Word> second = new ArrayList<>(anArr);
...
first.addAll(temp);
second.addAll(temp);
...

SystemClock.sleep(5000);

time = System.nanoTime();
for (int i = 0; i < top; ++i) first.remove(0);
Log.d("al_l", "rem: " + (System.nanoTime() - time));

time = System.nanoTime();
for (int i = 0; i < top; ++i) second.remove(0);
Log.d("al_lc", "rem: " + (System.nanoTime() - time));

...
}
}
}).start();

Answer

I too was able to replicate it by creating the code below. However, I noticed that whatever is run first (the set capacity vs non-set capacity) is the one that will take the longest. I assume this is some kind of optimization, maybe the JVM, or some kind of Caching?

public class Test {



public static void main(String[] args) {
        measure(-1, 10); // switch with line below
        measure(15, 10); // switch with line above
        measure(-1, 100);
        measure(15, 100);
    }

    public static void measure(int capacity, long numItems) {
        ArrayList<String> arr = new ArrayList<>();

        if (capacity >= 1) {
            arr.ensureCapacity(capacity);
        }

        for (int i = 0; i <= numItems; i++) {
            arr.add("T");
        }
        long start = System.nanoTime();

        for (int i = 0; i <= numItems; i++) {
            arr.remove(0);
        }

        long end = System.nanoTime();
        System.out.println("Capacity: " + capacity + ", " + "Runtime: "
                + (end - start));
    }
}