동적 배열을 사용하는 자바스크립트에서 일어나는 일

최근 오픈소스에 기여를 하게 되었는데요. 그동안 번역 혹은 오역의 수정만 했지만 이번에는 코드를 수정한 것이 오픈소스 라이브러리에 반영되었습니다. 버그를 수정한 것은 아니고 성능을 향상시킨 수정이었는데요. 사실 정말 간단한 수정이었습니다. 배열을 만들 때, 새로운 빈 배열에 값을 계속 추가하는 방식에서 미리 배열의 크기를 정해놓고 인덱스에 맞게 값을 수정하는 방식이었습니다. 작은 수정이었지만 성능은 놀랍게도 약 47% 향상되었습니다.

커밋 내역

성능 변화

왜 이런 사소한 변화가 성능에 이토록 큰 영향을 주었을까요?

동적 배열

배열이란?

배열과 같은 데이터 구조는 일반적으로 메모리에 순서대로, 연속해서 저장됩니다. 예를 들어 첫 번째 요소가 메모리의 주소 0x1000에 있다면, 배열의 두 번째 요소는 그 다음 메모리 주소(0x1000 + 요소 크기)에 위치합니다. 배열에 인덱스를 사용해 특정 요소에 접근할 때는 배열의 시작 주소 * 요소의 크기 * 인덱스를 사용하면 됩니다. 이 때문에 배열은 O(1)의 시간 복잡도로 요소에 접근할 수 있습니다. 요소가 참조 값이라면 실제 데이터의 저장은 힙 메모리 상의 빈곳에, 그리고 데이터들이 저장된 주소를 스택 메모리에서 순차적, 연속적으로 저장합니다. 즉, foo라는 변수에 저장된 배열의 요소에 접근하는 foo[2]는 컴퓨터가 foo라는 배열이 저장된 곳을 찾고 거기서 힙 주소의 크기 * 2만큼 더한 주소로 이동한 뒤에 그 주소에 저장된 힙 메모리 상의 주소로 가서 요소를 읽도록 하는 것입니다.

이 규칙을 유지하기 위해 배열의 요소는 일정한 크기, 즉 같은 타입이 되어야 합니다. 그래야 요소의 크기 * 인덱스를 통해 정확한 주소 위치에 도달할 수 있기 때문입니다. 그리고 정적 배열 언어에서는안정성 및 효율적인 메모리 관리를 위해 배열의 크기도 미리 지정합니다.

자바스크립트의 배열의 메모리 할당 방식

그러나 자바스크립트는 동적으로 메모리를 할당하는 언어입니다. 즉 자바스크립트는 프로그램이 실행되는 동안 필요한 메모리를 자동으로 할당한다는 뜻입니다. 그래서 자바스크립트에서는 변수를 선언할 때 그 크기를 명시적으로 지정하지 않습니다. 변수를 선언할 때 필요한 메모리는 런타임에 자바스크립트 엔진에 의해 자동으로 할당됩니다. 그리고 배열의 크기가 제한이 없기 때문에 자바스크립트 엔진이 허락하는 한도 내(대부분 2^32 - 1)에서는 배열의 크기를 계속해서 늘릴 수 있습니다.

기본적으로 자바스크립트의 배열도 인덱스를 통한 요소 접근의 시간복잡도는 O(1)입니다. 그렇다면 자바스크립트도 데이터를 연속적으로 저장하는 것 같아 보입니다. 그런데 이미 말한 것처럼 자바스크립트는 동적 배열 언어입니다. 배열의 크기를 명시적으로 지정하지 않고 배열을 만듭니다. 하지만 내부적으로도 배열을 크기를 지정하지 않고 만드는 것은 아닙니다.

내부적으로 할당된 메모리 공간을 초과하면 2배 큰 공간을 가진 메모리에 다시 할당한다.

자바스크립트 엔진마다 자세한 내용은 다르지만 배열을 생성하면 4 ~ 8 개의 요소를 저장할 수 있는 메모리 공간을 할당합니다. 그보다 큰 배열을 할당하면 정확히 필요한 크기 만큼 메모리 공간을 할당하게 됩니다. 이때 배열에 요소를 추가한다면 메모리 공간이 부족하게 되는데요. 이때, 자바스크립트는 2배의 메모리 공간을 새로 할당하여 기존의 배열을 복사해 저장합니다. 이는 시간 복잡도가 O(n)만큼 걸리는 작업입니다. 이후로도 배열의 크기가 2배를 초과할 때마다 O(n)만큼의 시간을 소요하여 배열을 확장합니다. 이때문에 그토록 큰 시간 차이가 나게 됩니다.

소요 시간 비교

자 그럼 배열의 크기가 충분해서 메모리 재할당 및 복사가 필요하지 않은 경우와 push메서드를 이용해 매번 배열의 크기를 변화 시키는 코드를 아주 간단하게 구현하여 속도를 직접 비교해 보겠습니다.

// push를 사용하는 경우
const array = [];

console.time("push");
for (let i = 0; i < 1e7; i++) {
  array.push(i);
}
console.timeEnd("push"); // push: 218.647ms

// 배열의 크기가 충분한 경우
const array = new Array(1e7);

console.time("preDetermined array");
for (let i = 0; i < 1e7; i++) {
  array[i] = i;
}
console.timeEnd("preDetermined array"); // preDetermined array: 11.27ms

실행 시마다 시간은 조금씩 다르게 나오지만 20배정도나 차이나는 것을 볼 수 있습니다. 이 차이는 배열에 추가하는 요소가 많을 수록 더 커질 것입니다. 반대로 배열의 크기가 작으면 거의 차이가 없을 것입니다.

자바스크립트 배열은 배열이 아닐 수도 있다?

ECMAScript는 배열의 구현 사항을 강제하고 있지 않습니다. 그저 배열로 작동해야 한다고 명시할 뿐입니다. 따라서 자바스크립트의 배열은 내부적으로 최적화된 다양한 자료구조를 사용하여 요소를 관리하며, 모든 요소가 연속적으로 메모리에 저장되지 않을 수 있습니다. 배열의 요소가 중간 중간 비어있는 희소 배열이라면 이진 검색 트리(BST)를 사용하기도 합니다. 따라서 배열의 구현체가 엄밀한 의미의 배열과는 다를 수 있지만 배열처럼 기능한다는 것만은 동일합니다.

동적 메모리 할당 언어 짧게 정리

자바스크립트는 동적 메모리 할당 언어는 배열 뿐만 아니라 많은 부분에서 정적 메모리 할당 언어와 차이를 가집니다. 앞서 살펴본 경우처럼 배열, 객체 등의 데이터 저장을 매우 유연하게 할 수 있습니다. 하나의 배열에 number, string, boolean 등 각기 다른 타입의 데이터를 할당할 수 있습니다. 이로 인해 매우 유연한 타입을 가집니다. 다만 이 특징으로 인해 nubmer인 변수에 string의 메서드를 사용해 오류가 발생하는 등의 단점도 가지고 있습니다. 이런 에러를 줄이기 위해 .?(옵셔널 체이닝) 또는 ??(null 병합 연산자)과 같이 런타임 중에 데이터 타입을 검사하여 메서드를 사용하는 등 다양한 방법을 가지고 있기도 합니다.

마지막으로 동적 메모리 언어가 정적 메모리 언어에 비해 느린 경향이 있는데, 이는 자동 메모리 관리를 위한 가비지 컬렉션 혹은 런타입 상의 타입 검사 및 변환, 더 높은 추상화 레벨로 인한 오버헤드가 주된 원인입니다. 성능을 개선하고자 JIT 컴파일러 등을 사용하기도 하지만 최적화 가능성이 정적 메모리 언어보다는 낮습니다.

참고 자료

How Arrays are Implemented in JavaScript