JS의 객체는 hash table이 아닙니다!

종종 웹상의 문서들을 보면, JS의 객체가 Hash table로 구현된 딕셔너리의 대표적 예시 중 하나로 설명하는 글 들을 찾을 수 있습니다.

하지만, 적어도 V8 엔진을 사용하는 브라우저에 한해서는 이는 사실이 아닙니다.

대표적으로 크롬, 엣지, 웨일 등에서는 아니라고 말 할 수 있겠네요.

다른 엔진을 사용하는 브라우저에서도, 아마 내부적으로 해시 테이블을 사용하지 않을 거란 추측을 이 글을 읽어보시면 하실 수 있으실 겁니다.

객체에 대해서 좀 더 정확히 말해보자면 겉으로 볼 때는, JS의 객체는 Hash table처럼 작동합니다.

왜냐면, JavaScript는 ECMA-262의 표준에 맞춰 동작하기만 하면 되기 때문입니다.

따라서, JS의 객체는 결과적으로 ECMA에서 정한 딕셔너리처럼 보이기만 하면 되는 거고, 내부적으로 Hash table을 사용하라는 강제는 없는거지요!

그러면 제가 어떻게 관련해서 공부했는지에 대해 시간의 흐름 순으로 정리해보겠습니다.

어라? typeOf 결과가 이상하다?

a = [1,2,3];

typeof(a);
// => 'object'

console.log(a);
// => (3) [1, 2, 3]
//		0: 1
//		1: 2
//		2: 3
//		length: 3
//		[[Prototype]]: Array(0)

처음에 뭔가 이상하다는걸 알게 된 건,
클로닝 하는 프로젝트 중에 http get으로 받아오는 데이터가 제대로 array의 데이터형인지를 검사하려고 콘솔을 찍어봤을 때 입니다.

분명 데이터 자체를 콘솔에 올리면 배열로 나오고, 프로토타입도 Array라고 잘 나오는데 typeOf만 돌리면 object로 나오는 겁니다.

뭔가 이상해서 좀 더 찾아보니, 자바스크립트는 모든 데이터를 두 가지 종류로 나눌 수 있다는데,
이 둘은 원시 타입과 참조 타입으로 나눠진다고 합니다.

모든 원시 타입의 데이터는 리터럴 형식으로 저장이 됩니다.

//ex

//case 01 'string'
let name = 'wongue';

//case 02 'number'
let age = '26';

//case 03 'boolean'
let graduate = false;

//case 04 'null'
let money = null;

//case 05 'undefined'
let girlFriend = undefined;
let myHouse; // 선언후 값을 할당하지 않으면 undefined이다.

다섯 개의 종류가 아닌 경우에는, 모두 참조 타입으로 분류됩니다.

(수정.
	Bigint와, Symbol 또한 원시타입입니다!
)

참조 타입이란 객체와 같은 말이고,
자바스크립트의 객체는 할당된 변수에 직접 값을 저장하지 않고 그 자리에 포인터를 저장합니다.

//ex
let obj1 = new Object()
let obj2 = obj1; // obj2 는 이제 obj1과 같은 값을 참조하게 된다.

그러면.. 배열이 딕셔너리인거야?

이제 리스트로 받아온 값이, typeof를 돌리면 object를 뱉어내는 이유를 알았습니다.

근데 뭔가 이상한 점이, 그러면 JS는 배열을 모든 idx에 대한 키 벨류를 가지는 딕셔너리로 구현한 건가? 라는 의문이 들기 시작했습니다.
여기서부터 이제 장대한 삽질을 시작했는데,

일단 결론부터 적자면 V8 엔진, 그러니까 Chromium을 사용하는 브라우저에서는 객체는 hash-table로 구현되지 않았습니다! 왜냐면 동적 타이핑 언어에서 해쉬 테이블은 느리기 때문입니다.

이를 이해하려면 일단, JS의 객체 구조를 알아야 합니다.
위의 이미지는 V8 블로그에서 JS Object를 설명하는 다이어그램입니다.

JS의 객체는 property를 가지는데, properties는 두 분류로 나눠집니다.
key가 0부터 시작하는 정수인, indexed Properties와 key가 문자열에 해당하는 Named Properties입니다.

먼저 주제에 맞게 indexed Properties에 대해서 설명하자면,
위의 다이어그램을 보신 분들은

int[] arr1 = new int[10];

자바스크립트에서의 Array는 우리가 생각하는 위와 같은 예시의 배열과는 구조가 아주 다르다는 점을 알 수 있을 겁니다.

"이거 그냥 키가 int인 딕셔너리인 거잖아"

맞습니다. 그래서 JS에서는 이런 식으로도 배열의 원소를 추가 할 수 있습니다

let listA = [1];
// [1]
listA[2] = 3.3;
// (3) [1, empty, 3.3]
listA[1] = '2.2';
// (3)[1, '2.2', 3.3]

물론 권장되는 방식은 아닙니다.
그 이유는 바로 V8 블로그에서 설명하는 The elements-kind lattice, 를 보면 이해할 수 있습니다.

(이는 간략화 되어있는 예시고, 실제로는 21개의 다른 상태와 그에 따른 최적화가 구현되어있다고 합니다)

격자 안의 화살표가 의미하듯이 배열은 왼쪽 위에서 우하단으로만 이동할 수 있고 그 역은 가능하지 않습니다.

Array가 두 종류의 대비되는 속성에 따라서 분류되어 있는데

PACKED <-> HOLEY 와,
SMI_ELEMENTS <-> DOUBLE_ELEMENTS입니다.

Packed array란 우리가 익히 알고 있는 배열처럼,
idx 0부터 n까지 undefined 된 element 없이 꽉 채워져 있는 배열을 뜻합니다.

반대로 Holey array는 중간에 undefined 된 element가 있는, 구멍이 난 배열을 의미하는 거고요.

SMI element는 Small integers element를 의미합니다.
SMi에 포함될 수 없는 부동 소수점을 가지는 모든 실수는 Double입니다.

정리하자면 배열의 상태가 격자에서 더 아래로 내려갈수록 조작이 느려지기 때문에
가능하면 처음에 배정받은 상태를 유지하는 쪽으로 배열을 관리하시는 게 퍼포먼스 측면에서 유리하게 동작합니다.

다시 위의 예시를 보면,

let listA = [1];  
// [1] => SMi_packed
listA[2] = 3.3; 
// (3) [1, empty, 3.3] => Double Holey
listA[1] = '2.2';
// (3)[1, '2.2', 3] => Object Holey

마지막에 1번 인덱스가 채워지더라도, 배열의 상태는 Holey가 유지되는걸 주의하세요!

그래서 왜 Undef를 조회하면 느려지는건데?

이제 결론 부분입니다.

이를 이해하려면 동적 타이핑 언어의 특징과
최적화 기법의 하나인 hidden class에 관해서 이야기 해야 합니다.

앞에서 설명하는 내용을 듣다 보면
혹시 JS는 데이터 참조 값을 불러오는 동작을 가능한 최대로 피하려는 듯한 인상을 받으셨나요?

"그냥 포인터로 가서 데이터 읽어오면 되는 거 아닌가?
이건 상수 시간 안에 수행 할 수 있는 동작인 거잖아."

정적 언어의 경우에는, 맞습니다.
하지만 JS는 동적 타이핑 언어입니다.

컴파일 시에 변수의 데이터 타입이 결정되지 않는다는 거고,

데이터 타입이 결정되지 않으면 메모리에서 데이터 오프셋을 얼마나 두어야 할지 알 수 없게 되고,

이는 런타임 중에 실제로 데이터가 저장되어있는 위치가 계속 바뀌거나 수정될 수 있다는 의미입니다.

따라서 런타임 중에 자꾸 변할 수 있는 변수의 참조 값을 읽어오는 행위를 동적 서치라고 하고
동적 서치의 비용은 반복되면 엄청나게 비싸지겠죠.

V8 엔진은 이러한 동적 서치를 가능한 줄일 수 있게, 객체의 구현에 Hidden class를 이용했습니다.

Hidden class 제가 이해한 바로 설명하면, 객체의 프로퍼티를 변경할 때마다 새롭게 생성된 데이터의 저장된 위치를 가리키는 포인터들의 무더기입니다.

//ex
function Point(x,y) {
	this.x = x;
	this.y = y;
}

var obj = new Point(1,2);

이런 함수가 실행될때, V8 엔진은 C0이라는 Hidden class를 만들겁니다.

이 선언하는 과정에서, 아직 어떠한 프로퍼티도 생기지 않았기 떄문에, C0 클래스는 비어있습니다.
this.x = x; 가 실행되는 순간에는,

새로운 프로퍼티가 추가되는 과정에서 히든클래스는 새로 생성되어 전환됩니다.

this.y = y;에서는 이렇게 동작하겠군요.

Hidden class의 존재 이유는 바로 인라인 캐싱에 사용되기 위함입니다.

우리가 작성한 코드는 엔진에 들어가서 동작할 바이너리 코드로 조합되기 이전에 함수, 모듈은 그 자체 내용의 복사본으로 교체되는데

이를 인라인 함수라고 하고 객체의 경우에는 자주 치환되어야 하는 상황에는 정보를 미리 캐시에다가 담아놓고

해당 객체가 호출될 때마다 참조를 타고 들어가는 것이 아닌
미리 캐시에다가 준비해 놓은 내용을 바로 불어넣는 걸 말합니다.

이때, 붙여 넣어지는 데이터의 참조 값은 Hidden class에 쓰여있는 것이죠.

히든 클래스의 전환은 객체에 새로운 프로퍼티가 할당될 때 일어난다는 말의 의미는 이렇습니다.

function Point(x,y) {
2    this.x = x;
3    this.y = y;
4  }
5 
7  var obj1 = new Point(1,2);
8  var obj2 = new Point(3,4);
9
10 obj1.a = 5;
11 obj1.b = 10;
12
13 obj2.b = 10;
14 obj2.a = 5;

9번째 줄까지는 obj1과 obj2의 히든클래스는 동일합니다.

하지만, 각 객체에서 a, b 속성이 다르게 추가되는 순간,
이 둘은 다른 클래스를 가지게 됩니다.

이렇게 다른 히든클래스를 가지는 객체는 인라인 캐싱에서 효율적으로 동작하지 않기 때문에,

이러한 스타일의 코드를 작성하는 건 퍼포먼스 측면에서 영 좋지 않습니다.

V8 엔진이 어쩔 수 없이 동적 서치를 실행해야 하기 때문이죠.

결론짓자면,
JS Object가 해시 테이블로 구현되지 않는 이유는,
동적 타이핑 언어인 JS에서는 데이터의 오프셋이 런타임 중에 실시간으로 바뀌게 되고

해시 테이블은 프로퍼티의 생성, 변조에 따라 변경되는 오프셋을 최신 상태로 갱신해 담고 있다고 보장될 수 없기 때문에

엔진에서 데이터를 읽게 되는 모든 과정에 동적 서치가 필요하게 되기 때문입니다.

모든 게 동적 서치를 피하기 위함이므로,
코드를 작성할 때도 이러한 엔진 개발자의 노력을 헛되지 않게 하기 위해서
동적 서치가 최대한 발생하지 않는 방향으로 작성을 하는 게 가장 좋은 퍼포먼스를 발휘할 수 있는 방향이 되겠다는 게 결론이 되겠습니다.

끝으로 쉽게 실수할 수 있는 퍼포먼스 저해 요인이 될 수 있는 예시 코드를 공유해드리겠습니다!

//ex01
let list = Array(3); // -> holey

미리 배열의 크기를 할당하지 마세요!
C++는 가비지 값이 들어가지만, JS에서는 empty가 들어가게되면서,
배열의 상태가 packed에서 holey로 격하되어 버립니다.

//ex02
for (let i = 0, item; (item = items[i]) != null; i++){
  doSomething(item);
}

이 코드는 루프에서 배열의 모든 인덱스를 읽은 뒤, 초과하는 인덱스를 하나 더 읽습니다.
V8 엔진 블로그에서 말하기로는 jQuery에서 종종 사용하는 패턴이라고 하니

레거시 코드들을 사용할 일이 있을경우에 한번 확인해보는게 좋을꺼 같네요!

//ex03
function Maximum(array) {
  let max = 0;
  for (let i = 0; i <= array.length; i++) { // BAD COMPARISON!
    if (array[i] > max) max = array[i];
  }
  return max;
}

for 루프의 마지막 실행에서 i는 배열의 크기를 초과하게 됩니다!

이때는 퍼포먼스 뿐만이 아니라 비교또한 오염되기때문에,
숫자만 비교하는 대신 예외처리를 해야합니다.

V8 블로그에서 length가 10,000일 경우에, 경계값을 잘 설정할 경우에 6배의 성능향상이 일어났다고 합니다!

//ex04
const array = [3, 2, 1, 0];
// PACKED_SMI_ELEMENTS
array.push(-0);
// PACKED_DOUBLE_ELEMENTS

필요치 않은 경우에 -0을 배열에 추가하지 마세요!
이 작업은 퍼포먼스를 떨어트립니다.

//ex05
const arrayLike = {};
arrayLike[0] = 'a';
arrayLike[1] = 'b';
arrayLike[2] = 'c';
arrayLike.length = 3;

이 객체는 인덱스와 length를 지원하고,

Array.prototype.forEach.call(arrayLike, (value, index) => {
	console.log(`${ index }: ${ value}`);
});

이 또한 가능하지만, V8 내부에서 최적화된 배열을 호출하는거보다 퍼포먼스가 떨어집니다.

객체안에 내장된 유사배열을 두번 이상 사용할 예정이면 실 배열로 수정해보는걸 고려해보시죠!

V8 블로그에는 더 많은 예시들이 있지만, 가장 흔하게 실수할만한 여지가 있는 것들 위주로만 가져와 봤습니다.

후기)
ㅋㅋㅋ.. 그냥 받은 데이터가 Array인지 검사하고 싶었을 뿐인데, 
엄청 돌아온거 같지만, 
그래도 공부하면서 얻은게 좀 있는거 같아 뿌듯하네요.

밑에는 제가 공부한 문서들의 출처입니다.
제가 오개념 범벅으로 정리한것 보다 훨씬 더 명료하고 간단하게 설명되어 있으니, 관심이 생기셨으면 꼭 한번 읽어보시는걸 추천드려요.

Javascript Hiddenclass와 최적화 기법
[JavaScript] 히든클래스, 인라인 캐싱 그리고 최적화
자바스크립트 엔진의 최적화 기법 (2) - Hidden class, Inline Caching
V8 엔진에 대해서
[JavaScript] 원시 타입과 참조 타입
Elements kinds in V8
Explaining JavaScript VMs in JavaScript - Inline Caches
Fast properties in V8