내 큐는 왜 느릴까
자바스크립트는 내장되어있는 큐가 없다보니 코딩테스트에서 시간 복잡도를 빠르게 하려면 큐를 직접 구현해야한다.
일반적인 배열의 shift 메서드는 배열의 맨 앞 원소를 반환하지만 결국 마지막 원소까지 전부 shift 시켜야하기 때문에 O(1) 가 아닌 O(N) 이 소모된다.
그래서 아주 간단하게 큐를 작성해보면, 아래와 같이 생각해볼 수 있을 것 같다.
객체로 간단하게 큐 구현해보기
정확히는 앞이나 뒤에서 모두 원소를 O(1) 로 꺼낼 수 있는 deque 인데,
간단하게 items 라는 객체에서 left, right 인덱스를 통해 바로 접근할 수 있도록 하는 것이다.
javascript
class Queue {
left = 0;
right = 0;
items = {};
dequeue() {
if(this.isEmpty()) {
return null;
}
const result = this.items[this.left];
delete this.items[this.left];
this.left += 1;
this.clean();
return result;
}
isEmpty() {
return this.left === this.right;
}
peek() {
if(this.isEmpty()) {
return null;
}
return this.items[this.left];
}
last() {
if(this.isEmpty()) {
return null;
}
return this.items[this.right - 1];
}
enqueue(value) {
this.items[this.right] = value;
this.right += 1;
}
pop() {
if(this.isEmpty()) {
return null;
}
this.right -= 1;
const result = this.items[this.right];
delete this.items[this.right];
this.clean();
return result;
}
clean() {
if(this.left === this.right) {
this.left = 0;
this.right = 0;
}
}
}
Dequeue, delete
여기서 dequeue 메서드를 살펴보면, delete this.items[this.left] 를 통해서 items 객체에서 제거하고 있다.
delete 하는 이유는 당연하게도 메모리를 아끼기 위해서였다. 그리고 delete 하는데 O(1) 밖에 걸리지 않기 때문에 그렇게 큰 문제가 생기지 않을 것이라고 생각했었는데, 뒤에서 이야기하겠지만 굉장히 큰 실수였다.
javascript
dequeue() {
if(this.isEmpty()) {
return null;
}
const result = this.items[this.left];
delete this.items[this.left];
this.left += 1;
this.clean();
return result;
}
이러한 점이 왜 잘못되었는지 알려면 우리가 쓰고 있는 node.js 의 엔진에 대해서 알아봐야한다.
V8
TurboFan, Ignition
node.js 의 내부 엔진인 V8 은 우리가 작성한 코드를 내부적으로 최적화하는, 2단계의 실행 파이프라인을 사용한다.
- Ignition (바이트코드 인터프리터) : 코드를 빠르게 실행하면서 객체가 어떤 모양과 타입을 가지는지(타입 피드백) 등을 수집
- TurboFan (최적화 JIT 컴파일러) : Hot(자주 실행되는) 한 함수들을 최적화한 기계어 코드를 생성. 여기서 TurboFan 은 Ignition 에서 얻은 피드백 등을 사용하여 코드를 최적화한다.
89549.png
이렇게 피드백 을 통해 코드를 최적화하기 때문에 V8 은 자바스크립트 코드를 훨씬 더 빠르게 실행할 수 있다. 반면, 함수가 너무 복잡하게 폴리모픽(Polymorphic, 다양한 형태를 가진, 즉 예측 하기 힘든) 한 경우에는 코드를 최적화하기 어렵다. 따라서 아예 최적화된 코드가 없거나 최적화된 코드에서 실행이 불가능해서 최적화되지 않은 코드로 실행되는(’탈출’ 혹은 deoptimize 라고 부르는듯 하다) 경우가 많다.
폴리모픽의 예시를 보자.
javascript
1 function getX(obj) {
2 return obj.x; // 이 부분이 폴리모픽 상태가 됨
3 }
4
5 const obj1 = { x: 1, y: 2 }; // Shape A
6 const obj2 = { x: 3, z: 4 }; // Shape B (y 대신 z)
7
8 // getX는 Shape A와 Shape B, 두 가지 형태의 객체를 받음
9 getX(obj1);
10 getX(obj2);
obj1 은 x, y 프로퍼티를 가지고 있고, obj2 는 x, z 프로퍼티를 가지고 있다.
따라서 Shape A (x, y 프로퍼티), Shape B (x, z 프로퍼티) 2가지가 존재하고, getX 는 2가지의 형태를 받을 수 있다.
obj.x 부분은 Shape A 가 들어올지, Shape B 가 들어올지에 따라 각각 최적화된 코드로 넘어갈 수 있다.
위의 경우에는 어느정도 최적화를 하는데 큰 문제가 없지만 조금 더 복잡한 상황이면 (보통 4개 이상?) 최적화 하기가 힘들어진다.
이런 경우를 메가모픽이라고 부르는 듯 하다.
반대로 하나의 Shape 으로 고정되면 모노모픽 이라고 한다.
javascript
1 function getX(obj) {
2 return obj.x; // 이 부분이 메가모픽 상태가 됨
3 }
4
5 // 매번 다른 Shape의 객체를 생성하여 함수 호출
6 for (let i = 0; i < 10; i++) {
7 let obj = { x: i };
8 if (i % 2 === 0) obj.a = 1;
9 if (i % 3 === 0) obj.b = 1;
10 if (i % 4 === 0) obj.c = 1;
11 // ... 이런 식으로 계속 다른 Shape가 만들어짐
12 getX(obj);
13 }
이렇게 모노모픽, 혹은 적당한 수준의 폴리모픽은 V8 의 인라인 캐시를 통해 최적화된 코드를 만들고 빠른 경로를 미리 만들어둔다.
최적화된 코드에서는 런타임에 객체의 히든 클래스를 검사하는 가드가 포함되고, 일치하지 않는다면 디옵트(탈출, 인터프리터로 실행) 된다.
Hidden Class (Shape)
자바스크립트는 동적 언어이지만, V8 은 내부적으로 객체에 구조를 부여하기 위해 히든 클래스라는 것을 사용한다. 히든 클래스는 어떤 프로퍼티가 있고, 메모리 어디에 저장되는지 등을 나타내는 내부 디스크립터다.
코드로 간단하게 살펴보면,
javascript
let o = {};
o.a = "foo";
o.b = "bar";
o.c = "baz";
31421.png
이렇게 o.a → o.b → o.c 순으로 프로퍼티를 추가했으면 위의 이미지처럼 a → b → c 순으로 디스크립터가 추가되면서 히든 클래스가 만들어진다.
히든 클래스는 Offset 을 저장한다.
여기서 주의할 점은 “순서” 이다.
a → b → c 순으로 프로퍼티를 추가한 객체와, c → b → a 순서로 프로퍼티를 추가한 객체는 서로 다른 히든 클래스를 갖는다.
javascript
let o = {};
o.a = "foo";
o.b = "bar";
o.c = "baz";
let x = {};
x.c = "baz";
x.b = "bar";
x.a = "foo";
o 와 x 는 결국 a,b,c 의 프로퍼티를 갖겠지만 서로 다른 히든 클래스를 갖는다. 프로퍼티가 추가될 때마다 새로운 히든 클래스를 만들게 되는데, 그 이유는 프로퍼티가 메모리 어디에 저장되어 있는지를 저장하는 오프셋 을 저장하기 때문이다.
프로퍼티를 추가할 때를 기준으로 offset 이 정해지는데, a → b → c 순으로 정하는 offset 은 당연히 c → b → a 순으로 정하는 offset 과 다르다.
이렇게 offset 을 가지고 특정 프로퍼티에 빠르게 접근이 가능하기 때문에 히든 클래스가 중요한 것이고, 히든 클래스에 순서가 영향을 미치는 이유이다.
히든클래스를 통해 V8 은 매번 딕셔너리에서 프로퍼티를 찾는 대신, 고정 오프셋을 사용해서 프로퍼티에 접근할 수 있다.
o.a, o.b, o.c 처럼 a b c 의 해시값을 딕셔너리에서 검색할 필요가 없이 오프셋을 통해 바로 접근할 수 있게 되는 것이다. (C++ 의 구조체처럼)
따라서 프로퍼티의 생성 순서와 일관성이 중요하다. 일관된 shape 는 성능에 영향을 줄 수 있다.
딕셔너리 모드
히든클래스로 프로퍼티의 오프셋을 저장하고 프로퍼티가 추가될 때마다 새로운 히든 클래스로 “전이” 되다가 너무 비효율적이게 되면 해당 객체를 딕셔너리 모드로 전환한다고 한다. 이렇게 딕셔너리 모드로 전환되면 해시 테이블(딕셔너리)에 프로퍼티를 저장하게 되기 때문에 프로퍼티의 추가, 삭제는 유연해진다. 대신 당연히 모든 프로퍼티로의 접근이 느려진다. (인라인 캐시와 고정 오프셋을 사용하지 못하기 때문)
여기서 딕셔너리 모드로 전환되는 일반적인 방법이 바로 delete 이다. delete 를 사용하는 경우 V8 은 이 객체가 고정된 구조(모노모픽처럼) 라고 생각하기 보단 동적으로 사용된다고 판단하여 딕셔너리 모드로 들어가게 된다. 결국 여기서 고려해볼수 있는 점은, 속도와 메모리효율의 트레이드오프이다. delete 를 사용하는 대신 null 이나 undefined 로 바꿈으로써 딕셔너리 모드로 전환되는 것을 막을 수 있지만 그만큼 메모리는 지속적으로 사용될 것이다.
Elements Kind
자바스크립트에서 배열도 사실 그냥 객체이다. arr[0] 은 키가 0 인 프로퍼티일 뿐이다. 하지만 V8 은 배열에 대해서 조금 더 특별하게 최적화 한다. 정확히는 배열이라고 전부 다 동일하게 최적화하는건 아니고, 규칙성에 맞게 최적화를 한다.
아래에서 볼, 객체가 가지는 원소의 타입에 맞게 최적화된다. (= Elements Kind 에 맞게 최적화)
타입이 달라지면
javascript
const array = [1, 2, 3];
// elements kind: PACKED_SMI_ELEMENTS
array.push(4.56);
// elements kind: PACKED_DOUBLE_ELEMENTS
엔진의 레벨에서 바라보면, array = [1, 2, 3] 의 경우는 PACKED_SMI_ELEMENTS 로 판별한다. 여기서 SMI 는 Small Integer 이다.
그런데 array.push(4.56) 을 하고 나면 PACKED_DOUBLE_ELEMENTS 로 바뀐다.
javascript
array.push('x');
// elements kind: PACKED_ELEMENTS
마지막으로 문자열을 넣으면, PACKED_ELEMENTS 로 바뀐다.
Holey
javascript
const array = [1, 2, 3, 4.56, 'x'];
// elements kind: PACKED_ELEMENTS
array.length; // 5
array[9] = 1; // array[5] until array[8] are now holes
// elements kind: HOLEY_ELEMENTS
length 가 5인 배열에, 갑자기 9번째 인덱스에 1을 넣고 있다. 이 경우에는 array[5] ~ array[8] 까지 구멍이 생긴다.
이러면 PACKED_ELEMENTS 에서 HOLEY_ELEMENTS 로 바뀌게 된다.
73913.png
이 그림은 2025.02.28 이전의 그림인데 자세히보면 화살표의 방향이 위에서 아래로만 되어있다. 즉, 한 번 HOLEY 가 되면 되돌아갈 수 없다는 의미였는데 2025.02.28 이후에는 예외가 하나 생겼다고 한다.
Array.prototype.fill 를 통해서 모든 홀을 채우면, PACKED 로 돌아갈 수 있다고 한다.
hole 이 생기게 되면, V8 은 매번 hole 이 있는지 여부를 체크해야하는 로직이 최적화에 포함되고, hole 인지 구분하기 위해 상위 프로토타입까지 거슬러 올라가기때문에 PACKED 보다 최적화가 비효율적이다.
더 나은 큐를 만들기
기존의 큐 방식을 살펴보자.
javascript
// 기존 방식(최적화가 잘 되지 않음)
let queue = {};
let head = 0, tail = 0;
function enqueue(x) {
queue[tail++] = x;
}
function dequeue() {
if (tail > head) {
let x = queue[head];
delete queue[head++];
return x;
}
}
처음에는 queue 안에서 0, 1, 2… 같은 순서로 인덱스가 증가하기 때문에 객체가 배열처럼 동작한다.
따라서 SMI(Small Integer) elements kind 로 최적화 된다.
그러나 delete 를 하게 되면 0부터 hole 이 생기게 된다. 따라서 PACKED → HOLEY 로 최적화 효율이 다소 안좋아지게 된다.
그러다가 delete 를 많이 하다보면 head 와 tail 의 숫자는 매우 큰 반면 실제로 객체에 저장된 값은 몇 개 없을 수도 있다. 다시 말해, offset 을 통해서 접근하려고 보니까 앞에 hole 이 너무 많아서 매우 큰 offset 을 통해서 접근해야 하는 것이다.
이럴 때는 V8 이 배열처럼 최적화하는 것은 비효율적이라고 판단해 딕셔너리 모드로 전환해버릴 수 있다. 이렇게 되면 히든 클래스와 offset 을 사용할 수도 없게 되고, 인라인 캐시 입장에서는 매번 offset 을 통해서 접근했는데, 딕셔너리 모드로 전환되다보니 캐싱된 값이 달라지므로 인라인 캐시도 유지할 수 없다.
이제부터는 최적화 로직은 거의 사용하지 못하게 되므로 속도가 느려진다.
Delete 를 안쓰는 방법
delete 를 안쓰면서 메모리 효율도 높일 수 있는 방법은 뭐가 있을까?
- 원형 큐(고정 크기)
javascript
// 원형 큐
const capacity = 1024;
let queueArr = new Array(capacity);
let head = 0, tail = 0;
function enqueue(x) {
if ((tail + 1) % capacity === head) throw Error("queue full");
queueArr[tail] = x;
tail = (tail + 1) % capacity;
}
function dequeue() {
if (head === tail) return undefined;
const x = queueArr[head];
queueArr[head] = undefined;
head = (head + 1) % capacity;
return x;
}
위의 코드와 같은 원형 큐를 한 번 살펴보자.
고정된 크기의 원형 큐를 한 번 보면, hole 이 생기지 않고 index 도 0부터 쌓이기 때문에 PACKED_SMI 를 유지할 수 있다.
지금처럼 고정된 큐의 경우에는 리사이징을 할 수 없기 때문에, 리사이징까지 고려하면 아래와 같이 생각해볼 수 있을 것 같다.
대신 아무래도 동적인 크기가 가능해지기 때문에 완전히 모노모픽을 유지하기는 힘들고, 미리 capacity 를 크게 잡아둔다거나 하는 방식으로 너무 빈번한 리사이징이 일어나지 않도록 크기를 잘 잡는게 중요할 것 같다.
javascript
class Queue {
constructor(initialCapacity = 16) {
this.capacity = initialCapacity;
this.queue = new Array(this.capacity);
this.head = 0;
this.tail = 0;
this.size = 0;
}
enqueue(x) {
if (this.size === this.capacity) {
this._grow();
}
this.queue[this.tail] = x;
this.tail = (this.tail + 1) % this.capacity;
this.size++;
}
dequeue() {
if (this.size === 0) return undefined;
const x = this.queue[this.head];
this.queue[this.head] = undefined; // 슬롯 정리 (GC-friendly)
this.head = (this.head + 1) % this.capacity;
this.size--;
if (this.capacity > 16 && this.size <= this.capacity / 4) {
this._shrink();
}
return x;
}
peek() {
return this.size === 0 ? undefined : this.queue[this.head];
}
isEmpty() {
return this.size === 0;
}
_grow() {
const newCapacity = this.capacity * 2;
this._resize(newCapacity);
}
_shrink() {
const newCapacity = Math.floor(this.capacity / 2);
this._resize(newCapacity);
}
_resize(newCapacity) {
const newQueue = new Array(newCapacity);
for (let i = 0; i < this.size; i++) {
newQueue[i] = this.queue[(this.head + i) % this.capacity];
}
this.queue = newQueue;
this.capacity = newCapacity;
this.head = 0;
this.tail = this.size;
}
}
Subscribe to hoeeeeeh
Get the latest posts delivered right to your inbox
