자바 arrayList addAll 메서드 : 어디서 오버헤드가 걸리는지 간단하게 분석해 봅시다.

어레이리스트의 addAll 메서드의 성능에 대한 글이 간혹 보입니다. 메서드 내부를 뜯어 보면서, 어디서 오버헤드가 걸리는지 알아보도록 하겠습니다.

 

 

---

 먼저 Main 클래스의 main 함수 내에 있는 코드는 아래와 같습니다.

 

 생각보다 복잡하지 않습니다. 그냥 단순히 90개의 Integer를 x에 넣어놓고 List x에 있는 것들을 모두 y에 add하는 작업을 하는 코드입니다. addAll 안으로 들어가 보겠습니다.

 

 

 가장 먼저 보이는 것은 c를 toArray로 바꾸는 것입니다. 즉, ArrayList c를 Array로 바꾸는 작업을 먼저 하는데요. 여기서 무슨 일을 하는지 안으로 들어가 보겠습니다. 일단 581번째 줄의 c는 무엇을 의미할까요? 90개의 Integer가 들어있는 ArrayList를 의미합니다.

 

 

 안에 들어가 보니 Arrays.copyOf의 리턴값을 리턴하네요. elementData는 c의 실 데이터를 의미합니다. 그리고 c는 Integer가 90개 들어있는 List를 의미하니까 size는 90이 되겠네요. 안으로 들어가 봅시다.

 

 

 그러면 또 copyOf를 호출합니다. 무엇인지는 잘 모르겠지만, 안으로 들어가 보겠습니다.

 

 

 보니까, newLength의 길이만큼의 새 Object 배열을 생성하거나, newInstnace를 호출하는데요.

 

 

 설명을 보면, componentType의 길이 length의 Array를 생성한다고 되어 있습니다. Create a new array라는 문구를 주의깊게 보시면 됩니다. 그리고 arrayCopy 함수가 호출됩니다.

 

 

 호출 스택은 위와 같습니다. 여기까지 일어난 일을 정리해 보겠습니다. c.toArray()를 호출하면, 내부적으로 c의 size만큼의 길이를 가지는 배열을 생성합니다. 그리고, c의 내용을 새로 생성한 배열에 복사합니다. 단순히, 해당 List의 원소를 가져와서 다른 List에 넣으면 되는 것을 굳이 새롭게 Array를 생성한다. 오버헤드로 걸릴 수 있는 부분입니다.

 

 

---

 이제, List에 해당 내용들을 넣는 코드를 보겠습니다.

 

 다시 583번째 줄부터 보겠습니다. ensureCapacityInternal 함수가 있습니다. 이 함수 안으로 들어가 보겠습니다.

 

 

 그러면, 내부적으로 ensureExplicitCapacity를 호출하는데요.

 

 

 이 메서드를 보면, 비어있는 경우에, DEFAULT_CAPACITY와 mincapacity중에 최댓값을 리턴하고, 그렇지 않으면, 그냥 minCapacity를 돌려줍니다. 리턴값을 가지고, ensureExplicitCapacity를 호출합니다.

 

 

 그러면, if문 조건에 따라서 grow를 호출하게 되는데요. 만약에 addAll의 대상체인 List보다 mincapacity가 큰 경우에는 grow를 호출하게 됩니다.

 

 

 그러면 이 함수의 내부만 보면 되겠군요. newCapacity는 oldCapacity의 1.5배라는 것은 아실 거니다. 여기서, 260번째 if문과 262번째 if문이 있는데요. 엄청나게 큰 배열이 아닌 이상 262번째 줄에 걸릴 일은 없습니다. 고로, 260번째 줄만 보면 되는데요. 1.5배로 확장된 크기보다 newCapacity가 더 크다면, newCapacity만큼의 새로운 배열을 할당합니다.

 

 그러면 현재 List a에 List k를 append 할 때 a의 size보다 k의 size가 월등하게 클 때, 이야기가 달라질 수도 있다는 의미입니다.

 

 

---

 일단, ArrayList의 capacity가 x라고 가정하겠습니다.

 

 

 계속 add가 호출이 되어서, x에서 1.5x로 capacity가 증가했을 때, 새로 생성한 배열의 크기는 1.5x, 값을 넣거나 복사한 횟수는 1.5x, 회수된 크기는 x입니다. 즉, 0.5x만큼을 add하기 위해 1.5x의 배열을 생성하고, 값을 넣거나 복사해야 하는 횟수가 1.5x, 회수해야 하는 게 x라는 의미입니다. 각각, 1만큼 add가 일어날 때 마다, 복사 3, 생성 3, 삭제 2만큼의 비용이 든다는 의미입니다.

 

 

 addAll을 호출한다면 어떨까요? 대충 기존 List의 길이 x, 뒤에 추가될 List 길이가 7x라고 해 보겠습니다. 그러면 먼저 toArray로, 임시 배열에 추가될 List가 복사됩니다. 다음에 ensureXXX로 공간이 확장되고, arrayCopy로 내용이 복사되는데요. 길이가 x인 List의 용량은 많아봤자 1.5x를 넘어가지는 않습니다. 따라서, grow 메서드의 260번째 줄의 if문에 걸리기 때문에, 아래와 같이 복사가 됩니다.

 

 

 그러면 원소 하나당 복사 비용 2, 생성 비용 2, 삭제 비용 1.x만큼 듭니다. 이는, 기존 List에 비해 월등히 길이가 긴 List를 기존 List의 뒤에 addAll 할 때 상황입니다. 네. 생각보다 괜찮은 효율입니다. 그리고 이 링크의 3번째 답변과 일맥 상통하는 부분이기도 합니다. 그 답변을 보시면, addAll이 1개씩 추가하는 것보다 3배의 performance를 보여주었는데요. 이는 1개씩 추가할 때, 10개, 15개, 22개, 33개 이렇게 확장을 해 나가는 데 비해서, 25개를 한 번에 추가할 때 한 번에 25개의 크기를 가지는 List를 만들었기 때문입니다.

 

 그런데, 길이가 100만인 배열에 길이가 10, 20짜리인 ArrayList를 addAll 메서드로 추가하면 이야기가 달라질 수 있어요. 왜냐하면, 임시 배열에 생성한 후에 copy를 하고, 그 다음에 본 List에 copy를 하기 때문인데요.

 

 

 x짜리 List에 0.5x짜리 List를 append를 하는데 필요한 기댓값은 복사 및 대입이 4, 생성 4, 삭제 3임을 알 수 있어요. 그냥 add 메서드를 호출했을 때 3, 3, 2에 비하면 생각보다 큽니다. 단지, arrayCopy 등으로 노란색으로 칠한, 대입과 복사 비용은 어느 정도 커버를 칠 수 있을 겁니다만..

 

 

 임시배열이 추가로 생성된다는 것 자체는 피해갈 수 없는 오버헤드입니다. 당연하게도 List 1개짜리를 가지고 계속 addAll을 호출하면, temp 배열이 생성되는 오버헤드는 생각보다 매우 뼈아프게 다가올 겁니다.

 

 

---

 여기서 끝나면 섭하니, 제가 어제 1시간 동안 삽질했던 것도 같이 공유해 보겠습니다. 대략 t개 정도의 데이터가 있습니다. 이 중에서, PK를 하나 주었을 때 mybatis의 foreach로 k개 단위로 묶어서 m개를 insert 할 때와, 안 묶고 insert 쿼리를 m개 날렸을 때 성능을 test 하기 위해서 아래와 같은 코드를 짰습니다.

 

 

 moo 클래스를 보면, x만 있습니다. x를 pk로 할려고 합니다. x에는 1부터 10까지의 pk가 있습니다. 다음에 10번 y에 List x를 추가합니다. y.get(lo).x에 랜덤하게 뽑은 값을 넣었습니다. 대충 Random variable 범위는 1에서 20억까지. 이 정도면 완벽할 거 같습니다. 그렇게 해서 DB에 넣었더니 왠걸? pk에는 중복된 키가 들어갈 수 없다는 메세지가 자꾸 뜹니다.

 

 

  문제 상황을 단순화 시키면 위와 같습니다. y.get(10).x에 10101010을 넣어보겠습니다. 그러면, 110개의 아이템을 돌 동안, 1010만 1010이라는 값이 몇 번 출력되나 봅시다.

 

 

 90번째 원소의 x값이 10101010인 것을 볼 수 있습니다. 왜 그럴까요? List에 들어있는 것은 실값이 아닌 참조형입니다. 참조값이 복사되면, 가리키는 대상만 복사가 됩니다. 즉, 아래와 같은 일이 발생합니다.

 

 

 '참조값이 복사되는 상황'은 간과하시면 안 되는 부분입니다.