[V8] Map
JavaScript 객체는 실행 도중에도 자유롭게 프로퍼티를 추가하거나 삭제할 수 있다. 따라서 C++ 객체처럼 컴파일 시점에 객체의 구조와 각 필드의 위치를 완전히 확정하기 어렵다.
그렇다고 프로퍼티에 접근할 때마다 객체 내부를 처음부터 검색한다면 성능이 크게 떨어진다. V8은 이를 해결하기 위해 객체의 구조를 별도의 객체로 관리하는데, 이 구조가 Map이다.
V8의 Map은 다른 JavaScript 엔진에서 Hidden Class, Shape, Structure라고도 부르는 개념과도 유사하다.
Map
V8 Heap에 존재하는 모든 HeapObject는 자신을 설명하는 Map을 가진다.
객체의 첫 번째 필드에는 일반적으로 그 객체의 Map 을 가리키는 Tagged Pointer가 저장된다. 따라서 V8은 두 객체의 Map 포인터를 비교하는 것만으로 두 객체의 구조가 같은지 빠르게 확인할 수 있다.
객체에 값만 저장되고 그 값의 의미와 위치를 해석하는 정보가 Map에 저장된다.
Map에는 대표적으로 다음과 같은 정보가 들어있다.
- 객체의 크기
- 객체의 종류를 나타내는
InstanceType - In-object Property가 시작되는 위치
- 객체가 가진 프로퍼티 개수
ElementsKind- Prototype
DescriptorArray- 다른 Map으로의 전이 정보
- …
Map 자체도 Heap에 존재하는 HeapObject이기 때문에 Map도 자신의 Map Pointer를 가지고 일반적인 Map의 Map은 특별한 MetaMap을 가리킨다.
다음 두 객체는 프로퍼티 이름과 추가 순서가 같다.
1
2
3
4
5
6
7
const a = {};
a.x = 10;
a.y = 20;
const b = {};
b.x = 30;
b y = 40;
두 객체의 값은 다르지만 구조는 같다.
1
2
3
4
5
6
7
a
x -> 10
y -> 20
b
x -> 30
y -> 40
따라서 a객체와 b객체는 같은 Map을 공유할 수 있다.
Map은 프로퍼티의 실제 값을 저장하기 않는다. a.x의 10과 b.x의 30은 각각의 객체에 저장되고 Map에는 x라는 프로퍼티가 존재하며 그 값이 어느 위치에 저장되는지를 설명하는 정보가 들어있다.
반면 프로퍼티를 다른 순서로 추가하면 다른 Map이 만들어질 수 있다.
1
2
3
4
5
6
7
const a = {};
a.x = 10;
a.y = 20;
const b = {};
b.x = 40;
b y = 30;
최종적으로 두 객체 모두 x와 y를 가지지만 프로퍼티가 추가된 순서가 다르다.
V8의 Map은 프로퍼티가 추가된 순서까지 반영하므로 두 객체는 일반적으로 서로 다른 Map을 사용한다. 같은 이름의 프로퍼티를 같은 순서로 추가한 객체들이 같은 Hidden Class를 공유하는 것이 기본 원칙이다.
Map Transition
빈 객체에 프로퍼티가 추가되면 객체의 구조가 바뀐다.
V8은 기존 Map 자체를 수정하기보다는 새로운 구조를 표현하는 Map을 만들고 객체의 Map Pointer를 새로운 Map으로 변경한다. 이를 Map Transition이라고 한다.
1
2
3
4
const obj = {};
obj.x = 10;
obj.y = 20;
Map의 변화는 다음과 같이 표현할 수 있다.
1
2
3
4
5
6
7
Map0 : {}
- add x
|
Map1: {x}
- add y
|
Map2: {x, y}
처음 생성된 빈 객체는 Map0을 사용한다.
x가 추가되면 {x} 구조를 표현하는 Map1로 전이하고 y가 추가되면 {x, y} 구조를 표현하는 Map2로 전이한다.
객체에 실제로 저장되는 Map Pointer도 다음과 같이 변경된다.
1
2
3
4
5
obj.map = Map0
obj.x = 10
obj.map = Map1
obj.y = 20
obj.map = Map2
Transition Tree
하나의 Map에서 서로 다른 프로퍼티가 추가될 수 있으므로 Map 전이는 트리 형태가 될 수 있다.
1
2
3
4
5
6
7
const a = {};
a.x = 1;
a.y = 2;
const b = {};
b.x = 3;
b.z = 4;
두 객체는 빈 객체에서 x를 추가할 때까지 같은 경로를 사용한다.
1
2
3
Map0{} -> Map1{x}
Map1{x} -> Map2{x, y}
Map2{x} -> Map3{x, z}
Map1에서 y가 추가되면 Map2로 이동하고 z가 추가되면 Map3로 이동한다.
V8은 이러한 전이 관계를 이용해 기존에 만들어진 Map을 재사용한다.
예를 들어 다른 빈 객체에 x, y를 같은 순서로 추가하면 새로운 Map을 매번 생성하는 대신 기존의 전이 경로를 따라갈 수 있다.
Map의 전이 정보는 상황에 따라 하나의 약한 참조, IC Handler 또는 TransitionArray 형태로 저장될 수 있다. 전이 대상이 여러 개라면 TransitionArray가 프로퍼티 이름과 대상 Map의 관계를 관리한다.
또한 각 Map은 이전 Map을 가리키는 Back Pointer를 가질 수 있다.
1
Map0 <- Map1 <- Map2
이를 통해 전이 트리를 반대 방향으로 따라가 초기 Map까지 올라갈 수 있다.
DescriptorArray
Map이 객체의 구조를 설명하려면 각 프로퍼티에 대한 구체적인 정보가 필요하다. 이 정보는 주로 Map이 가리키는 DescriptorArray에 저장된다.
Descriptor에는 대략 다음과 같은 정보가 포함된다.
- Property Key
- Property Kind
- Property Attributes
- Property Location
- Property Constness
- Property Representation
- Field Index
- Field Type
여기서 field index는 실제 값이 저장된 위치를 찾는데 사용된다.
일반적인 Data Field의 값은 객체 내부 또는 PropertyArray에 저장되고 DescriptorArray에는 그 값을 찾기 위한 메타데이터가 저장된다.
DescriptorArray 공유
전이 관계에 있는 여러 Map은 하나의 DescriptorArray를 공유할 수 있다. 이때 각 Map은 DescriptorArray 전체를 사용하는 것이 아니라 자신이 사용할 Descriptor의 개수를 별도로 가진다.
프로퍼티는 추가된 순서대로 DescriptorArray에 배치되므로 전이 경로에 있는 Map들이 앞부분을 공유할 수 있다. 이를 통해 Map마다 별도의 DescriptorArray를 생성하는데 필요한 메모리를 줄인다.
전이 트리가 갈라지는 경우에는 공유할 수 없는 Descriptor가 생기므로 새로운 DescriptorArray가 만들어질 수 있다.
프로퍼티 값의 저장 위치
Map과 DescriptorArray는 프로퍼티의 구조와 위치를 설명하지만 실제 값은 주로 객체 내부나 별도의 저장소에 존재한다.
V8의 Named Property 저장 방식은 크게 다음과 같이 나눌 수 있다.
In-object Property
객체 자체의 메모리 공간에 값이 저장된다.
JSObject의 Property “a”, Property”b”에 저장되는 값이 In-object Property이고 별도의 객체를 한 번 더 참조하지 않아도 되므로 가장 빠르게 접근할 수 있다.
Property Array
객체 내부에 남은 공간이 없다면 값이 별도의 PropertyArray에 저장될 수 있다.
여기서 JSObject의 Extra Properties가 가리키는 FixedArray에 저장되는 값이 Property Array이다. DescriptorArray에는 해당 프로퍼티가 In-object Field인지 PropertyArray의 몇 번째 위치에 저장되어 있는지에 대한 정보가 들어있다.
PropertyArray에 저장된 Fast Property는 한 번의 추가적인 간접 참조가 필요하다.
Dictionary Property
프로퍼티가 매우 동적으로 추가되거나 삭제되는 객체는 Fast Properties 대신 Dictionary Properties를 사용할 수 있다.
Dictionary Mode에서는 프로퍼티 이름, 값, 속성 정보가 객체별 Dictionary에 함께 저장된다.
프로퍼티 추가와 삭제에는 유리하지만 Map과 DescriptorArray를 이용한 고정 오프셋 접근 및 일부 인라인 캐시 최적화를 적용하기 어려워 일반적으로 Fast Properties보다 접근 비용이 크다.
