Java ArrayList Add Method

Java의 ArrayList는 원소를 추가할 때마다 동적으로 그 공간을 확장한다. 만약 size가 3씩 늘어나는 ArrayList에 2개씩 원소를 추가한다고 가정하자. 우선 초기 ArrayList에는 3개의 공간이 할당되어 있을 것이다. 이후 2개씩 원소가 계속 추가될 경우, 처음에는 3개의 공간에 2개의 원소를 모두 할당 가능하다. 하지만 추가로 2개의 원소를 더 할당하고자 할 때에는 공간을 확장해주어야 한다. 이때, 공간을 자주 확장하게 된다면 공간을 새로 할당하는 데 걸리는 시간이 늘어나게 되어 전체 성능을 저하시킬 수 있다.
반대로 공간이 부족한 상태에서 100개의 공간씩 추가로 할당해준다면 낭비되는 공간이 많아진다는 단점이 존재한다.
실제로 우리가 Java에서 사용하는 ArrayList는 너무 자주 공간을 추가로 할당하고 있지도 않으며 메모리 낭비도 발생하지 않고 있다. Java에서는 add 메소드를 어떻게 구현하고 있기 때문일까?

Java 6

Java 6의 jdk 소스코드 중 ArrayList의 add 메소드를 살펴보았다.

add 메소드에서는 ArrayList의 끝에 매개변수로 받은 배열의 원소를 할당한다. 할당에 성공하였을 때 true라는 boolean 값을 리턴하고 있다. ArrayList에 할당하고자 하는 원소는 generic type E로 작성되어 있었고, add를 하기 위해 가장 먼저 호출하는 함수는 ensureCapacity 함수였다. 이 함수의 매개변수로는 e를 추가했을 때의 ArrayList size를 넘겨주고 있었다.

ensureCapacity 함수에서는 원소가 할당되기 이전의 oldCapacity, 매개변수로 넘어온 최소로 필요한 공간의 개수인 minCapacity를 비교하고 있다. 필요한 공간의 개수가 더 클 경우 공간을 추가로 생성해야 한다. 이때 추가로 생성할 newCapacity는 현재 배열의 1.5배 + 1에 해당한다. newCapacity의 값이 필요로 하는 공간(minCapacity)보다 작을 경우에는 newCapacity만큼의 공간을 새로 추가하는 것이 아니라 minCapacity만큼의 공간을 추가하고 있다. 마지막으로 Arrays.copyOf 명령어를 통해 배열을 복사하고 있다.
Arrays.copyOf는 값만 복사하는 shallow copy이므로 원본 배열이 보존되고 copy한 새로운 배열이 생성된다. 이때 원본 배열은 더이상 참조될 곳이 없어지므로 GC를 위해 marked 된다.

현재 배열 사이즈의 1.5배씩 증가하게 함으로써 앞에 언급했던 (1) 너무 자주 배열의 크기를 늘어나게 하는 문제, (2) 한번에 너무 많은 크기를 할당하여 공간의 낭비를 발생하게 한 문제를 해결하고 있다.

Java 7

Java 7의 jdk 소스코드 중 ArrayList의 add 메소드를 살펴보았다. Java 6에서와 동일하다. 따라서 차이가 존재하는 ensureCapacity 부분에 대해서만 살펴본다.

1.5배씩 공간을 추가 할당했던 Java 6에서와 달리 Java 7에서는 grow라는 함수를 통해 newCapacity(추가로 생성할 공간 사이즈)를 oldCapacity + (oldCapacity >> 1)로 설정하고 있다.

newCapacity = oldCapacity + (oldCapacity >> 1)
	    = oldCapacity + oldCapacity * 0.5
 	    = oldCapacity * 1.5 

Java 6에서의 newCapacity-1의 값이 Java 7에서의 newCapacity 값에 해당한다. 또한 Java 6에서와는 달리 Java7에서는 newCapacity가 커질 수 있는 값에 한계가 존재한다. MAX_ARRAY_SIZE로 지정해둔 수보다 커질 경우에는 hugeCapacity 함수의 리턴값으로 newCapacity가 재설정된다.

hugeCapacity를 통해 MAX_ARRAY_SIZE와 minCapacity를 비교하여 minCapacity가 더 클 경우 Integer의 최대값인 2^31 - 1(2,147,483,647)을 리턴하고 MAX_ARRAY_SIZE가 더 클 경우 MAX_ARRAY_SIZE를 리턴하고 있다.

Java 8

Java 8의 jdk 소스코드 중 ArrayList의 add 메소드를 살펴보았다. Java 6,7에서와 동일하나 호출하는 함수 명이 ensureCapacity가 아니라 ensureCapacityInternal이다.

ensureExplicitCapacity 이후의 로직은 Java7과 동일하다. Java8과 차이가 있는 부분은 ensureCapacityInternal 함수 부분이다. 해당 함수에서는 빈 배열에 최초로 원소를 add 하는 경우에 대한 case를 고려해 코드가 작성되어 있다. Java 6과 7에서는 생성자를 통해 생성하면 자동으로 10의 공간을 갖는 array가 생성되었다. 하지만 Java 8에서는 생성자를 통해 빈 배열을 생성하고 add가 발생하는 시점에 10의 공간을 할당해준다.

정리

Arrays.copyOf를 사용하여 원본 값을 보존한 채 새로운 객체를 생성하고 원본 배열 객체는 더이상 참조되지 않으므로 GC를 위해 marking 한다. 추후 GC는 이 marked 된 참조되지 않는 객체를 sweep하게 된다.

[참조] jdk6 소스코드
https://hg.openjdk.java.net/jdk6/jdk6/jdk/file/tip/src/share/classes/java/util/ArrayList.java
[참조] jdk7 소스코드
http://hg.openjdk.java.net/jdk7/jdk7/jdk/file/00cd9dc3c2b5/src/share/classes/java/util/ArrayList.java#l28
[참조] jdk8 소스코드
https://hg.openjdk.java.net/jdk8/jdk8/jdk/file/tip/src/share/classes/java/util/ArrayList.java
[참조] https://stackoverflow.com/questions/23245386/how-does-memory-allocation-of-an-arraylist-work/23245487
[참조] https://stackoverflow.com/questions/26925556/why-the-new-capacity-of-arraylist-is-oldcapacity-3-2-1
[참조] https://stackoverflow.com/questions/4450628/arraylist-how-does-the-size-increase