Post

[V8] JSArray & ElementsKind

[V8] JSArray & ElementsKind

JavaScript Array

JavaScript 배열은 다음과 같은 특징이 있다.

  • 크기가 동적으로 변한다.
  • 서로 다른 타입의 값을 저장할 수 있다.
  • 중간 인덱스가 비어 있을 수 있다.
  • 일반 객체처럼 이름이 있는 프로퍼티도 가질 수 있다.

정리하자면 JavaScript 배열은 객체이면서 정수 인덱스를 특별하게 처리하는 자료구조이다.


V8의 JSArray

V8은 JavaScript 배열을 내부적으로 JSArray 객체로 표현한다.

현재 V8 소스에서는 JSARRAY는 JSObject를 상속하고 배열 전용 필드로 length를 추가로 가진다.

따라서 JSArray는 일반 객체의 기능을 그대로 가지고 있다.

  • Map
  • named properties
  • indexed elements
  • prototype
  • 배열 전용 length

JSArray의 내부 구조

Map

JSArray의 구조와 메타데이터를 설명하는 Map을 가리킨다.

Map에는 다음과 같은 정보가 포함된다.

  • 객체의 타입
  • 객체 크기
  • 프로퍼티 구조
  • 프로토타입
  • ElementKind

특히 ElementKind는 JSArray 본체에 별도 필드로 있는 것이 아니라 JSArray가 가리키는 Map의 bit_field2에 저장된다. 현재 V8 소스에서는 ElementKind에 6비트를 사용한다. 따라서 배열의 ElementKind가 바뀌면 새로운 ElementKind를 가진 Map으로 전이될 수 있다.

properties

문자열 이름을 사용하는 일반 프로퍼티의 저장소이다.

1
2
const arr = [1, 2, 3];
arr.name = "string";

여기서 name은 배열 원소가 아니라 named property이다.

elements

정수 인덱스로 접근하는 배열 원소의 실제 저장소를 가리킨다.

V8은 named property와 indexed elements를 서로 다른 저장소에 관리한다. 이를 통해 배열 인덱스 접근과 일반 객체 프로퍼티 접근을 각각 최적화할 수 있다.

length

JavaScript에서 볼 수 있는 배열의 length이다.

중요한 점은 length와 backing store의 capacity가 항상 같지는 않다.

  • length -> JavaScript에서 보이는 배열 길이
  • capacity -> elements backing store가 실제로 확보한 공간

예를 들어 push()를 효율적으로 처리하기 위해 backing store가 현재 length보다 큰 공간을 미리 할당할 수 있다.


Elements Backing Store

JSArray 본체에 모든 원소가 직접 들어가는 것은 아니다.

Map 글에서도 썼던 사진이지만 다시 한번 언급을 하면 JSObject의 Elements는 별도의 객체를 가리키고 Elements Backing Store라고 부르며 그 Backing Store에 값이 저장된다.

주로 다음과 같이 분류된다.

ElementsKindbacking store
SMI/OBJECT 계열FixedArray
DOUBLE 계열FixedDoubleArray
Sparse 배열NumberDictionary 계열

V8 소스는 fast mode에서 backing store를 사용하고 slow mode에선 숫자 인덱스를 키로 사용하는 해시 테이블을 사용한다.


ElementsKind

전에도 정리했지만 JavaScript 언어 수준에서는 정수와 실수가 모두 number이다. 하지만 V8 내부에선 다르게 분류한다.

  • 작은 정수는 smi
  • 실수는 double
  • 객체나 문자열은 tagged value
  • 원소가 비어 있는 배열은 holey
  • 지나치게 희소한 배열은 dictionary

ElementsKind는 배열의 원소가 현재 어떤 형태로 저장되어 있는지를 나타내는 메타데이터이다.

이를 통해 V8은 원소를 읽을 때 매번 모든 타입을 확인하지 않고 해당 ElementKind에 맞는 전용 코드를 사용할 수 있다.


현재 V8에는 여러 ElementsKind가 존재하지만 다음 여섯 가지 fast ElementsKind에만 집중하면 된다.

ElementsKind의미
PACKED_SMI_ELEMENTS빈 공간 없이 SMI만 저장
HOLEY_SMI_ELEMENTSsmi와 hole 저장
PACKED_DOUBLE_ELEMENTS빈 공간 없이 double 저장
HOLEY_DOUBLE_ELEMENTSdouble과 hole 저장
PACKED_ELEMENTS빈 공간 없이 일반 Tagged Value 저장
`HOLEY_ELEMENTS일반 Tagged Value와 hole 저장

PACKED_SMI_ELEMENTS

모든 원소가 SMI로 표현 가능한 작은 정수이고 빈 공간이 없다.

PACKED_DOUBLE_ELEMENTS

double 전용 backing store인 FixedDoubleArray를 사용할 수 있다.

double을 각각 HeapNumber 객체로 생성하지 않고 raw double 값을 저장할 수 있다.

PACKED_ELEMENTS

서로 다른 JavaScript 값을 저장할 수 있는 일반적인 ElementsKind이다.

PACKED_ELEMENTS의 ELEMENTS는 모든 값이 실제 객체다가 아니라 일반 Tagged Value를 저장할 수 있다는 의미이다.


PACKED와 HOLEY

ElementsKind는 저장되는 값의 종류뿐 아니라 배열의 빈 인덱스가 존재하는지도 구분한다.

PACKED

0부터 length - 1까지 모든 인덱스가 원소에 존재한다.

1
2
index : 0 1 2
value : 1 2 3

HOLEY

배열 중간에 원소가 존재하지 않는 인덱스가 있다.

1
2
index : 0   1  2
value : 1 hole 3

또는 먼 인덱스게 값을 저장해도 hole이 생긴다.

1
2
const arr = [1, 2, 3];
array[10] = 11;
1
1, 2, 3, hole, hole, hole ... hole, 11

Holey 배열에서는 원소를 읽을 때 해당 위치가 hole인지 확인해야 하고 경우에 따라 프로토타입 체인까지 조사해야한다. 따라서 packed 배열보다 처리 과정이 복잡하다.

undefined와 Hole은 다르다.

1
2
const arr1 = [1, undefined, 3];
const arr2 = [1, , 3];
1
2
arr1 : 실제 "undefined" 라는 값이 존재
arr2 : 해당 인덱스 자체가 존재하지 않는 hole

Elements 전이

ElementsKind는 배열에 새로운 종류의 값이 들어오면 더 일반적인 형태로 바뀔 수 있다.

1
2
3
4
5
6
7
8
const arr = [1, 2, 3];
// PACKED_SMI_ELEMENTS

arr.push(4.5);
// PACKED_DOUBLE_ELEMENTS

arr.push("hello");
// PACKED_ELEMENTS

일반적으로 전이는 더 구체적인 표현에서 더 일반적인 표현으로 진행된다. 예를 들어 double이 들어와 PACKED_DOUBLE_ELEMENTS가 된 배열에서 그 값을 다시 정수로 바꾼다고 해서 자동으로 PACKED_SMI_ELEMENTS로 돌아가지는 않는다. 하지만 2025년 2월부터 Array.pprototype.fill()에는 일부 repacking을 허용하는 예외가 추가되었으므로 절대로 역이전하지 않는다라고는 할 수 없게 됐다.


DICTIONARY_ELEMENTS

배열이 지나치게 희소하면 연속 backing store을 유지하는 것이 메모리 낭비가 된다.

1
2
const arr = [];
arr[10000]; = 1;

이를 그대로 FixedArray로 표현하면 대부분의 공간이 hole이 된다.

이런 경우 V8은 배열을 dictionary 형태로 전환하여 slow elements kind로 분류한다.

Dictionary 표현은 희소 배열의 메모리를 절약하지만 일반적인 연속 배열처럼 주소 계산만으로 원소에 접근할 수 없으므로 fast elements보다 접근 비용이 크다.


This post is licensed under CC BY 4.0 by the author.