최근 면접 이야기
최근 기술면접에서 다음과 같은 질문을 받았다.
"JS에서 Array에 모든 데이터를 Array에 넣고, find()로 찾으면 되지, 왜 굳이 객체를 사용할까요?"
이 질문에 대해
"find()는 O(N)이지만, 객체는 프로퍼티를 통해 값을 조회할 수 있어서 O(1)이기 때문에 사용한다고 생각합니다."
라고 대답했고, 다음과 같은 꼬리질문들이 이어지기 시작했다.
- 객체는 어떻게 값을 저장하길래 O(1)인가요?
- 객체는 값을 가져올 때 항상 O(1)인가요? 정말인가요?
최근 학습했던 JS와 V8의 메모리 구조와 관리 내용을 기반으로 알고 있던 지식을 버무려 답하고자 했다. 생각하는 시간을 가질수록 머리가 하얘져서, 객체의 프로퍼티 - 값 형태에 집착했고, 해시 구조로 저장된다는 답을 드렸다.
그 이후에도 계속해서 질문들이 이어졌고, 이미 한 번 엉켜져버린 탓에 그 무엇에도 자신있게 상세한 대답을 드리지 못했다.
- 해시 형태로 저장된다고 하셨는데, 그럼 객체는 해시 테이블인가요?
- 메모리에 해시 테이블이 어떤 구조로 올라가나요?
면접이 끝난 후에 부정확했던 개념들에 대해, 다시 한 번 인지하기 위해 정리하는 글이다.
이 포스팅에서는 V8의 객체가 어떻게 저장되고 사용되는지에 초점을 맞춰 정리해보려고 한다.
JS 객체는 해시 테이블이 아니다
객체는 프로퍼티 - 값의 형태고, 직관적으로 user.name과 같은 접근은 O(1)인 것처럼 보인다. 이러한 특징들 때문에 해시 테이블인가? 라고 생각의 혼선이 생겼었다. 하지만 정확하게는 틀렸다.
적어도 V8엔진 위의 자바스크립트는, Hidden Class의 Map 구조로 생성되며, Fast Property Access 방식을 통해 성능을 최적화한다. 이 구조는 클래스 기반 언어의 필드를 고정된 순서로 저장하는 방식과 유사하며, 객체의 프로퍼티들이 특정 오프셋에 정적으로 매핑되도록 최적화되어있다. 즉, 초기에는 고정된 내부 메모리 레이아웃을 따른다는 말이다.
히든 클래스
더 자세하게 이해하기 위해, 자바스크립트가 동적 타입 언어라는 것을 상기할 필요가 있다. 컴파일 단계에서 객체가 어떤 구조가 될 지 알 수없기 때문에, V8은 히든 클래스를 이용해 구조적인 패턴을 감지하고 최적화한다.
V8의 히든 클래스 설명에 따르면, Map은 히든 클래스 자체, DescriptorArray는 Map이 가진 프로퍼티 순차 리스트와 위치 정보, 마지막으로 TransitionArray는 Map에서 Map으로 전이될 때의 간선으로, 이를 통해 트랜지션 트리를 형성하고 객체 구조의 모양(shape)가 같을 경우 동일한 히든 클래스를 재사용한다.
이런 매커니즘을 기반으로 히든 클래스는, 동일한 구조를 가진 객체는 동일한 히든 클래스를 사용하며, 이를 위해 객체에 프로퍼티를 추가할 때 마다 다른 히든 클래스를 사용한다.
예제 코드를 통해 어떻게 히든 클래스가 생성되는지 알아보자.
function User(name, age) {
this.name = name;
this.age = age;
}
const user1 = new User("Alice", 30);
객체 생성 직후, name, age 프로퍼티 추가에 각각의 히든 클래스를 생성한다. 최초 텅 빈 히든 클래스(Map0)에서 시작해 프로퍼티가 추가되는 순서에 따라 Transition Chain을 생성한다. 이 때 DescriptorArray에는 name, age 프로퍼티가 순서대로 구성되고, 여러 Map에서 공유될 수 있다. 아래의 그림에서, Map2까지 같은 DescriptorArray를 공유하여 히든 클래스를 구성한다.
그럼 왜 이런 구조를 설계했을까? V8에서는 동적 타입 언어의 특성 때문에, 런타임에 객체가 어떤 구조일지 알 수 없기 때문에, 히든 클래스를 추적하여 어떤 구조인지 파악해나가기 위함이라고 한다. 이 히든 클래스를 통해 V8이 구조 패턴을 감지하고 최적화를 수행할 수 있다고 언급한다.
만약, 같은 User을 통해 생성된 새로운 user가 다른 프로퍼티들을 갖게 된다면 어떻게 될까?
const user2 = new User("Bob", 28);
user2.gender = "M";
user2.phoneNumber = "010-0000-0000";
user를 선언하고 최초 할당하는 순간까지는 같은 구조이기 때문에 동일한 Map2 히든 클래스를 사용하게 된다.
하지만 프로퍼티 추가 순서가 바뀌거나 조건에 따라 다른 구조가되면, 이 둘은 다른 클래스를 가지게 된다. user2는 Map4라는 다른 히든 클래스를 가지게 되었다. 이렇게 다른 히든 클래스를 가지는 객체는 인라인 캐싱에서 효율적으로 동작하지 않는다.
실제로 객체에 많은 프로퍼티가 추가되거나 삭제되면 DescriptorArray와 히든 클래스를 유지하는데 많은 오버헤드가 발생할 수 있다.
이를 방지하기 위해 V8은 Slow Property도 지원한다. 이 Slow Property를 가진 객체는 소위 Dictionary Mode가 되어 해당 객체는 딕셔너리에 직접 저장되어 더 이상 히든 클래스를 통해 공유되지 않는다.
인라인 캐시
인라인 캐시(IC)는 특정 프로퍼티 접근이 반복될 때, 해당 오프셋 정보를 캐싱하여 다시 계산하지 않도록 한다. 이를 통해 반복적인 객체 접근 시 빠른 속도를 유지할 수 있다. 객체가 호출될 때 마다 객체 참조를 통해 힙에서 직접 객체를 조회하는 것이 아닌, 미리 캐싱된 데이터를 참조하는 것이다.
인라인 캐시는 다음과 같은 상태를 거친다.
- Uninitialized: 처음 호출되는 시점. 전체 탐색을 수행해 프로퍼티를 찾고, 히든 클래스와 offset을 기록한다.
- Monomorphic: 항상 같은 객체가 들어올 경우, 캐싱하게 된다.
- Polymorphic: 2~4가지 정도의 다양한 구조가 반복될 경우
- Megamorphic: 5개 이상의 다양한 구조가 등장한 경우 - 최적화 불가능
위의 user1, user2를 예시로 간단하게 코드를 작성해보았다.
function logName(user) {
console.log(user.name);
}
const u1 = { name: 'Alice' }; // Map1
const u2 = { name: 'Bob' }; // Map1 → Monomorphic 유지
const u3 = { name: 'Charlie', age: 25 }; // Map2 → Polymorphic 전환
// 첫 번째 호출: 모노모픽 상태로 최적화
logName(u1); // IC가 {name: string} 구조에 특화
// 두 번째 호출: 같은 구조이므로 최적화 유지
logName(u2); // 캐시 히트
// 세 번째 호출: 다른 구조로 인해 폴리모픽으로 전환
logName(u3); // IC가 여러 구조를 처리하도록 변경, 성능 저하
우리가 아는 해시 함수를 통한 해시 구조도 항상 O(1)을 보장하는 것은 아니다. 해시 충돌이나 리사이징 등 다양한 비용이 숨어있다. 객체의 프로퍼티를 통한 값의 조회 역시 항상 O(1)일 수는 없는데, 다음과 같은 대표적인 경우에 인라인 캐시의 대상에서 제외되고, Fast Property 구조는 깨진다.
// 1. 메가모픽 상태
function logName(user) {
console.log(user.name);
}
// 너무 많은 다른 구조의 객체들
const users = [
{ name: 'Alice' },
{ name: 'Bob', age: 25 },
{ name: 'Charlie', age: 30, city: 'Seoul' },
{ name: 'David', age: 35, city: 'Busan', job: 'Engineer' },
{ name: 'Eve', age: 40, city: 'Daegu', job: 'Designer', hobby: 'Reading' }
// ... 더 많은 다른 구조들
];
users.forEach(logName); // 메가모픽 상태로 전환
// IC가 포기하고 일반적인 프로퍼티 룩업 사용// 2. 동적인 프로퍼티 변경
function processUser(user) {
console.log(user.name);
}
const user = { name: 'Alice' };
processUser(user); // 최적화됨
// 런타임에 프로퍼티 추가
user.age = 25; // 히든 클래스 변경
user.city = 'Seoul'; // 또 다른 히든 클래스
// delete 연산은 기존의 히든 클래스 구조와 DescriptorArray를 무효화시키고
// V8이 해당 객체를 Dictonary Mode로 전환시킨다.
delete user.age;
processUser(user); // 딕셔너리 모드로 전환
// 3. 너무 많은 프로퍼티
const bigObject = {};
for (let i = 0; i < 2000; i++) {
bigObject[`prop${i}`] = i;
}
객체 접근이 느려지는 코드 패턴을 피하자
동적으로 프로퍼티를 추가하거나 객체 생성에서 프로퍼티 순서나 구조가 달라지는 코드를 지양해야한다. 가능한 동일한 객체 구조를 유지하며 동적으로 프로퍼티를 추가하지 말고, 기본 구조 안에서 undefined를 활용하는 것이 좋다.
이런 패턴은 자연스레 작성하게 되는데, 개발 시에 보통 도메인 객체 혹은 모델 객체로 출발하여 비즈니스 로직을 작성하고, DTO로 변환하는 로직들을 자주 작성하게 된다. 이 때 기본적인 인터페이스나 클래스를 선언하고, 정적으로 확장해서 사용하지 동적으로 프로퍼티들을 추가하지는 않는다. 아마 고대(?) 오래 전부터 사용되고 발전되어온 언어 사용의 패턴을 현재 시점을 살아가는 우리가 사용하고 있기 때문에, 세부 내용은 모르지만 자연스레 좋은 습관으로 자리잡고 있는 것으로 보인다.
정리
다시 돌아와서, 객체 접근이 O(1)인 이유는 해시 형태이기 때문에 아니라, 프로퍼티가 오프셋으로 정적 매핑 되어있기 때문에, 히든 클래스를 기반으로 고정된 위치(offset)를 알 수 있기 때문이다. 반면, Array또한 INDEX를 프로퍼티로 가진 객체지만, find()는 순회하기 때문에 O(N)의 시간 복잡도를 가진다. 결과적으로 V8이 해시 기반이 아닌 정적 구조로 최적화했기 때문에 객체 접근에 O(1)이 성립하는 것이다.
이 외에도, 아래 V8 레퍼런스들을 참고하면서 알게된 사실들을 정리하면서 마치려고 한다.
Array의 INDEX는 객체의 프로퍼티와 다른 저장소에 저장된다.
배열의 프로퍼티는 Indexed Properties라는 별도 공간에 저장된다고 한다.
(일반적인 객체의 프로퍼티는 Named Properties에 저장된다.)
배열을 최적화하기 위해 V8에서 판단하는 내부 기준(?)이 있다.
V8은 배열의 요소(element)를 내부적으로 SMI(정수), DOUBLE(부동소수점), OBJECT(혼합형)로 나누고,
각 타입마다 PACKED(꽉 찬 배열), HOLEY(중간에 빈 구간이 존재) 여부에 따라 최적화 전략을 다르게 적용한다.
const a = [1, 2, 3] // PACKED_SMI_ELEMENTS
const b = [1, 2.2, 3] // PACKED_DOUBLE_ELEMENTS
const c = [1, 'a', 3] // PACKED_ELEMENTS
const d = [1, , 3] // HOLEY_SMI_ELEMENTS
const e = [1, , 3.3] // HOLEY_DOUBLE_ELEMENTS
const f = [1, , 'a'] // HOLEY_ELEMENTS
-0, NaN, undefined등을 배열에 넣지 말고 등등의 최적화 방법에 대해 자세히 알고 싶다면 https://v8.dev/blog/elements-kinds를 참고하면 되겠다.
References
https://v8.dev/blog/fast-properties
https://v8.dev/docs/hidden-classes
