JavaScript shift, unshift의 효율성에 대한 제고

들어가기

저는 지금까지 JavaScript의 배열은 사실 객체이기 때문에, 일반적인 배열의 역할도 하며 리스트의 역할도 하는것으로 알고 있었습니다. 그렇기 때문에 인덱스를 통한 접근이 자유롭게 가능하고, push, pop, shift, unshift와 같은 배열의 추가 제거도 자유롭다고 생각했습니다.
그런데 최근에 Problem Solving을 하던 중 shift와 unshift의 좋지 않은 효율성을 발견하게 되었습니다. 이에 따라 push와 pop의 효율성도 살펴보았는데 이 둘은 괜찮았습니다. 리스트의 역할이 가능하다면 push-pop과 shift-unshift의 차이는 없어야 할텐데 도대체 왜 이 둘의 효율이 다른 것일까요?

shift-unshift의 좋지 않은 효율성

100,000개의 데이터를 push, pop, shift, unshift로 처리했을 때의 처리 시간을 보겠습니다.

push

const solution = () => {
  const time = 100000;
  const arr = [];

  for (let i = 0; i < time; i += 1) {
    const char = arr.push(0);
  }
}

pop

const solution = () => {
  const time = 100000;
  const arr = Array(time).fill(0);

  for (let i = 0; i < time; i += 1) {
    const char = arr.pop();
  }
}

shift

const solution = () => {
  const time = 100000;
  const arr = Array(time).fill(0);

  for (let i = 0; i < time; i += 1) {
    const char = arr.shift();
  }
}

unshift

const solution = () => {
  const time = 100000;
  const arr = [];

  for (let i = 0; i < time; i += 1) {
    const char = arr.unshift(0);
  }
}

결과

왜 shift-unshift는 효율이 좋지 않을까?

이를 알기 위해서는 먼저 JavaScript에서의 배열이 메모리 상에서 어떻게 존재하는지를 알아야 합니다.

밀집 배열(dense array)과 희소 배열(sparse array)

일반적으로 배열이라는 자료 구조의 개념은 동일한 크기의 메모리 공간이 빈틈없이 연속적으로 나열된 자료 구조를 말합니다. 즉, 배열의 요소는 하나의 타입으로 통일되어 있으며 서로 연속적으로 인접해 있습니다. 이러한 일반적인 배열을 밀집 배열(dense array)이라고 합니다. C나 Java에서의 배열이 이와 같습니다.
밀집 배열은 동일한 크기의 메모리 공간이 빈틈없이 연속적으로 나열 되어있기 때문에 메모리의 주소값과 인덱스만 알면 한 번에 원하는 요소에 접근할 수 있습니다.
예를 들어 메모리 주소가 1000 이고, 배열의 요소의 크기가 4byte인 배열에서 인덱스를 기준으로 특정 요소를 찾으면,
1000 + 4(byte) * 2(index) = 1008
즉, 위 배열의 인덱스 2인 요소의 메모리 주소인 1008을 가지고 단번에 접근이 가능합니다. 이처럼 배열은 인덱스를 통해 효율적으로 요소에 접근할 수 있다는 장점이 있습니다.
하지만 배열의 사이사이에 요소를 삽입하거나 삭제하려고 하는 경우에는 다른 요소들을 이동시켜줘야 한다는 단점이 있습니다. 예를 들어, 중간에 삽입을 하게되면 그 뒤의 배열 요소들을 모두 한 칸씩 밀어주어야 하며, 반대로 제거를 하는 경우에는 한 칸씩 당겨주어야 합니다. 이는 배열의 다른 요소들에 영향을 미치므로 효율성이 좋지 않습니다.

하지만 JavaScript의 배열은 일반적인 의미의 배열과 다릅니다. 배열의 요소를 위한 각각의 메모리 공간은 동일한 크기를 갖지 않아도 되며, 연속적으로 이어져 있지 않습니다(리스트 형태). 이와 같이 배열의 요소가 연속적으로 이어져 있지 않는 배열을 희소 배열(sparse array)이라고 합니다.
JavaScript 같은 희소 배열이 밀집배열에 비해 가지고 있는 장점은 삽입과 제거의 연산이 더 빠르게 가능하다는 것입니다. 중간중간 메모리가 비어있기 때문에 그 사이에 삽입을 하거나 제거함으로써 다른 요소들을 건드리지 않고 삽입과 제거를 수행할 수 있습니다.
즉, JavaScript의 배열은 일반적인 배열의 동작을 흉내낸, index와 length를 프로퍼티로 가지고 있는 특수한 객체입니다. 그렇기 때문에 JavaScript 배열의 "index"는 메모리를 참조하기 위해 사용되는 Hash Key 역할도 하지만, 데이터의 "순서"를 보장하는 프로퍼티의 역할도 한다는 것입니다.

결론

그래서 shift와 unshift의 효율이 좋지 않은 이유는, 이 두 메서드가 배열의 앞부분에 동작하여 다른 요소들의 index 변화를 유발하기 때문입니다. push, pop 같은 경우는 배열의 맨 마지막에 동작하므로 다른 요소들의 index 변화가 없지만, shift와 unshift는 다른 요소들의 index를 하나씩 줄여주거나 하나씩 늘려주는 연산이 추가적으로 필요해집니다. 즉, 순서를 보장하기 위해 배열을 순회하면서 나머지 요소들의 index 프로퍼티에도 연산을 수행해주어야 하기 때문에 느려지는 문제가 발생하는 것입니다. 하지만 이럼에도 불구하고 JavaScript의 배열은 희소 배열이기 때문에 일반 밀집 배열들에 비해 삽입과 제거의 연산이 빠른 편입니다.
(index를 통해 배열 요소에 직접 접근하는 방법은 일반 밀집 배열에 비해 조금 느린 편입니다)