[Javascript] Object의 구조 (V8)

Javascript에서 Object는 거의 모든 것의 근간이 되는 타입이다.
모든 객체들이 Object로 핸들링되고, Key-Value 데이터를 다룰 때도 Object를 쓴다.

그런데 Object는 대체 무슨 구조로 이루어진 녀석일까? 보장하는 성능이나 사용법은 HashMap과 비슷한데, 신기하게도 Hashtable에 따르는 제약이나 관리포인트가 따로 존재하지 않는 것처럼 보인다.

일단 짚고 넘어가야 할 부분은, Object의 구현은 브라우저 엔진마다 다르다는 것이다.
JS 명세는 최소한의 동작 형태만 보장할 뿐이고, 내부 알고리즘은 알아서 하라는 주의이기 때문이다. "해시테이블처럼" 동작하기만 하면 된다.

언어 디자인이 개떡같다보니 뒷단에서 최적화한다고 고생이 많다.

V8 계열의 경우

크롬, 엣지, Node.js 같은 V8 엔진에서 Object은 상태에 따라 변환되는 내부 구조를 지닌다.
Object이 해시테이블이 아니라는 소문이 퍼져있는데, 사실 경우에 따라 해시테이블을 사용하는게 맞긴 하다.

일단 Object는 상황에 따라 2가지의 변신모드를 가진다.

1. Fast 모드: 구조체처럼 최적화됨
2. Dictionary 모드: 해시맵으로 동작 (느림)

처음에 키와 값이 거의 고정된 형태로 생성되면 V8 엔진은 이걸 거의 C의 구조체 값처럼 처리한다. 이 타입을 Hidden class라고 부른다.
이 상태를 Fast 모드라 하고, 이때는 매우 빠르다.

새로운 키가 추가되면 다시 새로운 Hidden class를 생성해서 대응한다.

하지만 fast 모드에서 감당하기 어려운 동작 패턴이 시작되면 Dictionary 모드로 변한다. 그리고 해시테이블처럼 동작한다.
딕셔너리 모드는 fast 모드보다 느리고 최적화도 잘 망가지기 때문에 가급적 사용하지 않으려고 한다. 보통 요소를 삭제하거나 하는 구조화가 어려운 형태의 액션을 수행하면 딕셔너리 모드로 전환이 된다. 키-값쌍이 과도하게 많을 때도 그런다.

var user = { name: 'connor', sex: 'male' }; 
// fast mode로 객체가 생성됨 

delete user.sex;
// dictionary mode로 객체가 변경됨

조금만 더 자세하게 살펴보자

일단 Object 자체에는 hiddenClass, properties, elements의 3개 필드로 구성이 된다.

1. hiddenClass가 아까 말했던 fast 모드에서의 구조체 형태를 정의하는 것이라고 했었다.
2. properties는 일반적인 Object 데이터일때 키-값 쌍을 저장하는 영역이고,
3. elements는 배열일때의 값을 저장하는 영역이다. 그래서 배열은 사실 Object다. 배열의 동작법에 대해서는 따로 정리를 해보겠다. 꽤 복잡한 편이다.
   
   예를 들어 다음과 같이 빈 Object에서 시작해서 필드를 추가한다면, 다음과 같이 HiddenClass를 계속해서 즉시 갱신한다.

사실 다 인터프리팅 언어라서 가능한 짓이다.
여기서 재미있는 부분은, HiddenClasses는 값에 귀속된 것이 아니라 전역에서 트리구조로 관리되는 타입 정보라는 것이다.

그래서 다음과 같이 같은 요소, 같은 순서를 가지는 객체가 2개 이상 존재한다면

const foo = {
    a: 1, 
    b: 3,
}

const bar = {
    a: 4, 
    b: 4444,
}

저 foo와 bar는 같은 HiddenClass를 공유한다.

그리고 HiddenClass로 관리하기 어려울 정도로 키 목록이 굉장히 많아지거나 복잡해지면 dictionary 모드로 전환된다. dictionary 모드는 명백하게 해시테이블로 동작하는게 맞다.

https://source.chromium.org/chromium/chromium/src/+/main:v8/src/objects/hash-table-inl.h;l=39?q=ComputeCapacity&ss=chromium
실제 v8 코드 보면 나온다.
그래서 dictionary 모드일 때는 일반적인 해시테이블처럼 사이즈가 커질때마다 2배의 growing을 거치는 등, 부하 포인트가 좀 존재한다.
해시충돌이나 재할당을 최소화하기 위해 50%의 여유공간을 두는 방식을 사용한다고 한다.
dictionary에 대한 직접적인 capacity 설정이 제공되지 않는건 아쉬운 부분이다.

참조
https://v8.dev/blog/elements-kinds
https://stackoverflow.com/questions/50011721/if-v8-rehashes-when-an-object-grows
https://stackoverflow.com/questions/50044338/how-v8-stores-fast-objects
https://v8.dev/blog/fast-properties?m=1
https://mrale.ph/blog/2015/01/11/whats-up-with-monomorphism.html