Java 7 이상에서 ArrayList 크기 계산 시 비트 연산자를 활용하는 이유

이전 포스팅에서 ArrayList는 어떻게 동적으로 크기를 늘려줄 수 있는지에 대해 Java 6, 7, 8 버전의 차이를 비교했었다. 

 

2023.10.09 - [One Cookie a day] - ArrayList는 어떻게 동적으로 크기를 늘릴 수 있을까?

ArrayList는 어떻게 동적으로 크기를 늘릴 수 있을까?

 

위 글에서도 알 수 있듯, Java 6에서는 늘려줄 크기를 ( 현재 배열의 크기 * 3 ) / 2 + 1라는 계산식을 통해 계산하였다.

Java 7부터는 늘려줄 크기를 oldCapacity + (oldCapacity >> 1) 라는 계산식을 통해 계산해준다.

 

단순하게, 곱하기와 나눗셈 연산을 하는 것보다 바로 비트를 한 칸씩 이동해주는 것이 CPU 입장에서 더 간단하기 때문에 이렇게 바뀐것이라 생각했는데, 이 이유에 대해 조금 더 작성해보려 한다.

 

결론은, "OverFlow 이슈와 연산 속도의 문제"를 해결하고자 바뀌었다. 

 

위의 포스팅에서도 작성했듯, Java에서 ArrayList의 최대 사이즈는 Integer.MAX_VALUE로 제한을 두고 있다. 내부적으로 배열의 크기를 저장하는 capacity들도 다 int 자료형이기 때문에 int 범위를 넘어갈 수 없다. (배열 인덱스도 생각해보면 int이다!)

그런데, ( 현재 배열의 크기 * 3 ) / 2 + 1라는 연산식에서, Integer.MAX_VALUE의 1/3 이 넘어가는 시점에서 *3을 하면 오버플로우가 발생할 것이다. 

여기서 이미 값이 깨졌으므로 뒤에 있는 연산들을 수행해도 값은 이미 깨졌고, 이로 인해 제대로 연산을 수행할 수 없게된다는 문제가 있다. 6 버전에서는, Integer.MAX_VALUE의 1/3 넘어가는 시점부터 계속 Overflow 를 맞닥뜨리게 되었던 것이다. 

 

 

또한 연산 속도의 측면에서도 생각해볼 수 있는것이, 컴퓨터는 곱하기, 빼기, 나누기 연산을 모두 덧셈형태로 계산한다. 

뺄셈을 수행할 때, 내부적으로는 2의 보수를 취해서 더하는 것을 생각해보면 된다. 

곱하기 연산도, 나누기 연산도 ALU(Arithmetic logic unit)내부에서 덧셈에 기반하여 연산을 수행한다.

위의 기존 식을 생각해보면, 컴퓨터 내부적으로 곱하기 연산을 위해 계속 더하고, 나누기 연산을 위해 2의 보수로 바꿔서 계속 빼주는 작업을 수행하게 될 것이다. 

 

Java 7이상에서 사용하는, 연산식 oldCapacity + (oldCapacity >> 1)는 bit를 shift하는 연산 1번과 기존 값과 더하는 작업만 수행해주면 되므로 연산속도가 당연히 빠를 것이다. 또한 oldCapacity가 Integer.MAX_VALUE라는, 한계 용량에 다다른 경우가 아니라면 Overflow도 Java6에 비해 훨씬 적게 발생할 것이다. 

 

이러한 장점이 있기 때문에, Java 7 이상부터는 비트연산을 채택했다고 보면 될 것이다.