Производительность ArrayList<Integer> по сравнению с int[]

По умолчанию емкость ArrayList может в два раза превышать количество содержащихся в нем элементов. Итак, если вы знаете предполагаемый размер, укажите начальную вместимость . Если размер неизвестен, обрежьте, когда закончите добавлять элементы.

Однако основное различие между ArrayList<Integer> и int[] заключается в разнице между Integer и int: первый является объектом, и каждый объект хранит некоторые метаданные для JVM (тип среды выполнения, хеш-код идентификации и т. д.) в дополнение к своим полям. что делает его несколько больше обычного int. Размер этих метаданных не указан и может варьироваться. Вы можете измерить его следующим образом:

public class Test {
    
    static final int elements = 10_000_000;
    
    private static long usedMemory() {
        var r = Runtime.getRuntime();
        return r.totalMemory() - r.freeMemory();
    }
    
    static void measure(String name, Runnable code) {
        System.gc(); // clean up previous tests
        long start = usedMemory();
        code.run();
        long end = usedMemory();
        System.out.println(name + " ".repeat(35 - name.length()) + " used " + (double)(end - start) / elements + " bytes/element");
    }
    
    public static void main(String[] args) {
        measure("int[]", () -> { 
            var a = new int[elements];
        });
        measure("Integer[] with small numbers", () -> {
            var a = new Integer[elements];
            for (int i = 0; i < elements; i++) {
                a[i] = i % 64;
            }
        });
        measure("Integer[] with large numbers", () -> {
            var a = new Integer[elements];
            for (int i = 0; i < elements; i++) {
                a[i] = i;
            }
        });
        measure("ideal capacity ArrayList<Integer>", () -> {
            var a = new ArrayList<Integer>(elements);
            for (int i = 0; i < elements; i++) {
                a.add(i);
            }           
        });
        measure("auto sized ArrayList<Integer>", () -> {
            var a = new ArrayList<Integer>();
            for (int i = 0; i < elements; i++) {
                a.add(i);
            }
        });
    }
}

На моей JVM это печатает:

int[]                               used 4.1809328 bytes/element
Integer[] with small numbers        used 4.1949816 bytes/element
Integer[] with large numbers        used 20.7624576 bytes/element
ideal capacity ArrayList<Integer>   used 20.8476584 bytes/element
auto sized ArrayList<Integer>       used 30.3283208 bytes/element

То есть на этой JVM объект Integer занимает 16 байт, а ссылка на объект 4 байта (если бы моя куча была достаточно большой, вместо этого ей понадобилось бы 8 байт). Если Integer содержит небольшие числа, объекты Integer будут использоваться повторно, и вы платите только за ссылку. Напротив, если объекты Integer содержат большие числа, для каждого элемента создается новый Integer.

ArrayList идеальной емкости имеет размер массива ссылок. ArrayList с автоматическим ростом может быть в два раза больше, чем необходимо.