V8 딥다이브 (Array)

V8 Deep Dives: Understanding Array Internals 를 읽고 설명을 더해 정리한 글입니다. Elements kind에 대한 더 자세한 내용은 V8 Elements kinds를 참고하세요.

들어가며

배열은 JavaScript의 핵심 기능 중 하나로, 모든 개발자가 익숙하게 사용하고 있습니다. 이 글에서는 V8이 배열을 내부적으로 어떻게 구현했는지 살펴보려고 합니다.

얼핏 보면 배열은 단순해 보입니다. 연속된 메모리 공간에 데이터를 저장하고, 필요할 때 꺼내 쓰면 끝이니까요. 하지만 실제로는 조금 더 복잡합니다.

배열의 내부 구조

> const arr = [];
undefined

> %DebugPrint(arr);
DebugPrint: 0x3db6370d4e51: [JSArray]
 - map: 0x3de594a433f9 <Map(PACKED_SMI_ELEMENTS)> [FastProperties]
 - prototype: 0x3a5538d05849 <JSArray[0]>
 - elements: 0x357222481309 <FixedArray[0]> [PACKED_SMI_ELEMENTS]
...

elements: ... <FixedArray[0]>를 보면, 배열은 고정 크기 배열을 사용해 데이터를 저장하고 있는데요. V8에서는 이걸 backing store라고 부르고, 현재 크기는 0입니다. 그리고 PACKED_SMI_ELEMENTS라는 elements kind가 있습니다. elements kind는 V8이 배열 연산을 최적화하기 위해 추적하는 메타데이터로, 배열에 어떤 타입의 요소가 저장되어 있는지를 나타냅니다.

PACKED_SMI_ELEMENTS는 가장 구체적인 elements kind로, 배열의 모든 요소가 Smi(Small Integer, 64비트에서 -2³¹ ~ 2³¹-1)임을 의미합니다. 이 메타데이터 덕분에 V8은 불필요한 타입 체크나 값 변환을 생략할 수 있습니다.

이 때 중요한 점은, elements kind는 구체적인 것에서 덜 구체적인 방향으로만 바뀐다는 거예요. PACKED_SMI_ELEMENTS에서 다른 종류로 바뀌면, 해당 배열은 다시 PACKED_SMI_ELEMENTS로 돌아갈 수 없습니다.

요소 추가와 메모리 할당

이제 배열에 첫 번째 요소를 추가하면 내부적으로 어떻게 변하는지 살펴볼게요.

> arr.push(1);
> %DebugPrint(arr);
DebugPrint: 0x3db6370d4e51: [JSArray]
 - elements: 0x0b5615c40a31 <FixedArray[17]> [PACKED_SMI_ELEMENTS]
 - length: 1
 - elements: 0x0b5615c40a31 <FixedArray[17]> {
    0: 1
    1-16: 0x3572224812c1 <the_hole>
 }
...

요소를 1개만 추가했는데, backing store의 크기가 17로 늘어났습니다. elements kind는 여전히 PACKED_SMI_ELEMENTS지만, 주소가 바뀌었어요. 기존 배열을 확장한 게 아니라 새로운 backing store를 할당한 거죠. 0번 인덱스에는 우리가 넣은 1이 들어가 있고, 나머지 1~16번 인덱스에는 the_hole이라는 값이 채워져 있어요.

이건 17 × 8 = 136바이트의 메모리를 사용한다는 뜻이에요. (객체 헤더는 제외). 요소 1개를 저장하는데 136바이트가 할당되어, 요청한 것보다 더 큰 공간이 할당된 셈이죠.

V8은 배열이 커질 때마다 매번 메모리를 재할당하는 비용을 줄이기 위해, 미리 여유 공간을 확보해둡니다. 그래서 요소를 몇 개 더 추가해도 바로 공간이 부족해지지 않아요. 이렇게 하면 push 같은 연산이 평균적으로 O(1) 시간 복잡도를 가질 수 있습니다.

새 크기를 계산하는 공식은 다음과 같아요:

new_capacity = (old_capacity + 50%) + 16

여기서 old_capacity는 기존 배열 크기 + 추가할 요소 수입니다. 우리 경우엔 빈 배열에 1개를 추가했으니 old_capacity = 1이고, 1 + 16 = 17이 된 거죠.

위 출력에서 1-16: ... <the_hole>이라는 부분이 있었는데요. the_hole은 V8이 할당되지 않았거나 삭제된 배열 요소를 표시하기 위해 사용하는 특별한 값이에요. 이건 V8 내부에서만 쓰이고, JavaScript 코드에서는 볼 수 없습니다. 위 예시에서는 사용하지 않는 여유 공간을 초기화하는 데 사용되었어요.

반대로 배열이 축소될 때는 어떨까요? pop()이나 shift() 같은 연산으로 배열 길이가 줄어들면, 절반 이상이 비게 될 경우 backing store도 함께 축소됩니다.

Elements Kind의 전환

앞서 PACKED_SMI_ELEMENTS는 구멍(hole)이 없는 배열을 가정한다고 했는데요. 배열을 특정 방식으로 수정하면 elements kind가 덜 구체적인 것으로 전환됩니다.

> arr[2] = 0;
> %DebugPrint(arr);
...
 - elements: 0x0e61bd5e7501 <FixedArray[17]> [HOLEY_SMI_ELEMENTS]
 - length: 3
 - elements: 0x0e61bd5e7501 <FixedArray[17]> {
    0: 42
    1: 0x357222481669 <the_hole>
    2: 0
    3-16: 0x357222481669 <the_hole>
 }
...

여기서 1번 인덱스를 건너뛰고 2번 인덱스에 값을 할당했어요. 그 결과 elements kind가 PACKED_SMI_ELEMENTS에서 HOLEY_SMI_ELEMENTS로 바뀌었습니다. 이 kind는 배열에 Smi와 hole이 섞여 있을 수 있다는 걸 의미해요.

V8이 배열을 순회하거나 수정할 때 hole을 건너뛰기 위한 추가 체크가 필요하기 때문에, 성능 측면에서 HOLEY는 PACKED보다 약간 느립니다.

Dictionary Elements

지금까지 backing store는 고정 크기 배열(FixedArray)이었는데요. 항상 그런 건 아닙니다. 한 가지 실험을 더 해볼게요.

> arr[32 << 20] = 0;
> %DebugPrint(arr);
...
 - elements: 0x10f6026db0d9 <NumberDictionary[16]> [DICTIONARY_ELEMENTS]
 - length: 33554433
 - elements: 0x10f6026db0d9 <NumberDictionary[16]> {
   - max_number_key: 33554432
   2: 0 (data, dict_index: 0, attrs: [WEC])
   0: 42 (data, dict_index: 0, attrs: [WEC])
   33554432: 0 (data, dict_index: 0, attrs: [WEC])
 }
...

32 << 20은 약 3천만인데요, 이렇게 큰 인덱스에 값을 할당하니, backing store가 FixedArray에서 NumberDictionary로 바뀐 걸 볼 수 있어요. NumberDictionary는 숫자 키에 특화된 해시 테이블입니다. 만약 FixedArray를 그대로 썼다면 3천만 개의 슬롯을 할당해야 했겠지만, 해시 테이블은 실제로 저장된 요소(3개)만큼만 공간을 사용해요.

이런 배열을 **희소 배열(sparse array)**이라고 부르는데, V8이 holes로 인한 메모리 낭비를 막기 위해 자동으로 Dictionary 방식으로 전환한 겁니다. elements kind도 DICTIONARY_ELEMENTS로 바뀌었는데, 이건 V8에서 “slow” 경로를 의미해요. 해시 테이블 조회는 인덱스 직접 접근보다 느리기 때문이죠.

배열 크기 제한

Dictionary로 전환되는 이유는 특정 임계값을 넘었기 때문이에요. FixedArray 기반 배열은 약 ~268MB를 넘을 수 없습니다. 그래서 예시처럼 큰 인덱스에 접근하면 자동으로 Dictionary로 전환됩니다.

Dictionary 기반 배열의 최대 크기는 ECMAScript 명세에 따라 32비트 부호 없는 정수의 최댓값인 2³² - 1로 제한됩니다.

---

결론적으로, 배열 성능을 위해서는 PACKED 상태를 유지하고, 빈 공간이 많은 배열을 피하는 것이 좋습니다.