[JS] Map이 Object보다 빠른가? 그 이유는 무엇인가?

[JS] Map이 Object보다 빠른가? 그 이유는 무엇인가?

 

우리 서비스에 문제가 하나 생겼다.

실시간 인터렉션에 의하여 데이터들이 화면과 db에서 제거되어야 하는 것이다. 단순이 이런 상황이라면 문제 될 것이 없지만, 다뤄야 할 데이터가 적어도 10만 개 단위란 것이다.

 

코드가 동작하는 흐름은 대충 이러했다.

 

1. 제거할 데이터들의 id를 찾는다.
2. id들을 특정 변수에 몽땅 넣고, UI상에서 즉시 제거한다.
3. 특정 변수를 delete할 데이터의 id 배열의 형태로 서버에 요청을 보낸다. `deleteIds: string[]`
4. 요청 성공 시에 client에 존재하는 상태를 deleteIds 변수와 비교하여 업데이트한다.
   -> refetch 하여 서버 데이터와 100% 동기화하기엔 데이터 개수가 너무 많다.
5. 요청 실패 시에 제거한 데이터들을 복구한다.
6. settle 시 deleteIds 변수를 초기화한다.
7. 반복한다.

 

delete ids 변수와 관련된 로직은 다음과 같다.

• id들을 개별로 삽입.
• 배열의 형태로 변환.
• 특정 id가 있는지 색인.
• 초기화

코드로 간단하게 구현하면?

 

관리할 구조가 배열일 경우.

// 관리할 배열 선언
let deleteDatas = [];

// deleteId를 하나씩 삽입.
for ...
  deleteDatas.push(deleteId);
...

// success
clientDatas = clientDatas.filter((data) => !deleteDatas.includes(data));

// 초기화
deleteDatas = [];

 

관리할 구조가 Object일 경우.

// 관리할 객체 선언
let deleteDatas = {};

// deleteId를 하나씩 삽입.
for ...
  deleteDatas[deleteId] = true;
...

// success
clientDatas = clientDatas.filter((data) => !deleteId[data]);


// 초기화
deleteDatas = {};

 

관리할 구조가 Map일 경우.

// 관리할 Map 선언
let deleteDatas = new Map();


// deleteId를 하나씩 삽입.
for ...
  deleteDatas.set(deleteId, true);
...

// success
clientDatas = clientDatas.filter((data) => !deleteId.get(data));


// 초기화
deleteDatas = new Map();

 

 

위 코드는 삭제 로직을 상당히 단순화한 것이지만, 대충 어떤 느낌이었는지 정도는 이해가 갈 것이다.

기존의 데이터 삭제 로직은 배열로 구성되어 있었다.

 

그래서 테스트를 위한 간단한 코드를 짜보았다.

// 테스트
const clientDatas = Array.from({ length: 10000000 }, (_, index) => `data-${index}`); // 예시 데이터 생성

// 배열 방법
const testArrayMethod = (deleteIds) => {
  let deleteDatas = [];
  console.time(`${deleteIds.length} : Array Method`);
  deleteIds.forEach((id) => deleteDatas.push(id));
  clientDatas.filter((data) => !deleteDatas.includes(data));
  console.timeEnd(`${deleteIds.length} : Array Method`);
};

// 객체 방법
const testObjectMethod = (deleteIds) => {
  let deleteDatas = {};
  console.time(`${deleteIds.length} : Object Method`);
  deleteIds.forEach((id) => (deleteDatas[id] = true));
  clientDatas.filter((data) => !deleteDatas[data]);
  console.timeEnd(`${deleteIds.length} : Object Method`);
};

// Map 방법
const testMapMethod = (deleteIds) => {
  let deleteDatas = new Map();
  console.time(`${deleteIds.length} : Map Method`);
  deleteIds.forEach((id) => deleteDatas.set(id, true));
  clientDatas.filter((data) => !deleteDatas.has(data));
  console.timeEnd(`${deleteIds.length} : Map Method`);
};

// 테스트 실행
const runTest = (deleteIds) => {
  testArrayMethod(deleteIds);
  testObjectMethod(deleteIds);
  testMapMethod(deleteIds);
};

runTest(Array.from({ length: 10 }, (_, i) => `data-${i}`)); // 10개
runTest(Array.from({ length: 100 }, (_, i) => `data-${i}`)); // 100개
runTest(Array.from({ length: 1000 }, (_, i) => `data-${i}`)); // 1000개
runTest(Array.from({ length: 10000 }, (_, i) => `data-${i}`)); // 10000개
runTest(Array.from({ length: 100000 }, (_, i) => `data-${i}`)); // 100000개
runTest(Array.from({ length: 1000000 }, (_, i) => `data-${i}`)); // 1000000개

 

—

 

아래는 테스트 결과이다.

 

배열은 압도적으로 느리고, Map은 압도적으로 빠르단 것을 알 수 있다. 특히 데이터셋이 커질수록 말이다.

 

node test.js                   

                                                                                                                                                                    
10 : Array Method: 466.235ms

10 : Object Method: 4.090s

10 : Map Method: 346.059ms

100 : Array Method: 962.861ms

100 : Object Method: 375.146ms

100 : Map Method: 330.348ms

1000 : Array Method: 9.493s

1000 : Object Method: 2.672s

1000 : Map Method: 1.970s

10000 : Array Method: 1:29.461 (m:ss.mmm)

10000 : Object Method: 1.179s

10000 : Map Method: 678.465ms

100000 : Array Method: 14:26.151 (m:ss.mmm)

100000 : Object Method: 4.916s

100000 : Map Method: 1.529s

1000000 : Array Method: 3:11:11.594 (h:mm:ss.mmm)

1000000 : Object Method: 5.068s

1000000 : Map Method: 2.967s

 

100만 개에서 Array가 보여주는 수치는 정말 말도 안 되는 수치다. 데이터가 커졌을 때 이 정도까지 성능 차이가 벌어진다고? 실제 수치로 확인하니 크게 와닿았다.

 

참고로 Object가 감당할 수 있는 데이터셋의 한계치는500만 개라고 한다.

 

—

 

왜 이런 결과가 나타날까?

 

자바스크립트의 배열은 객체로 구현되어 있다.

const array = {
  '0': ‘id1’,
  '1': ‘id2’,
  '2': ‘id3’,
  '3': ‘id’4,
  'length': 4,
};

이런 것이다.

 

배열은 내부적으로는 객체지만, 우리가 특정한 value가 있는 key를 바로 알지 못한다. 하지만 객체는 key로 값이 할당되어 있는 위치를 바로 확인 가능하다. 배열은 선형 탐색이 필요하고, 그러므로 객체가 배열보다 빠를 수밖에 없다.

 

게다가 자바스크립트는 동적 타이핑 언어이다. 컴파일 시에 변수의 타입이 정해지지 않기 때문에, 메모리를 미리 할당해 놓기가 힘들다. 런타임 중에 데이터의 위치가 계속 바뀔 수 있다는 것이다. 때문에 동적 서치를 하게 되고, 이는 큰 비용이 필요하다.

이를 해결하기 위해 V8엔진에서는 객체의 프로퍼티가 변경될 때마다 그 위치를 저장하는 hidden class가 존재한다.

hidden class는 객체가 생성될 때 구조를 나타내는 숨겨진 클래스를 할당하는 건데, 객체의 프로퍼티와 그 순서를 나타낸다. 객체에 속성이 추가되면 엔진은 hidden class를 다시 최적화해야 한다.

 

자바스크립트에서 object는 이렇게 동적 서치를 피하기 위해 해시테이블을 사용하지 않는다. 

Map은 내부적으로 해시 테이블을 사용하여 데이터를 처리하고 고정된 위치를 찾기 때문에 효율적인 처리가 가능하다.

 

그럼 Map은 동적 서치가 일어나지 않는가?

 

V8에서는 Map을 다음과 같은 방법으로 구현했다.

1. 작은 데이터셋: 객체와 유사한 방식으로 처리하여 빠른 접근.
2. 중간 크기 데이터셋: 배열 기반 접근으로 전환.
3. 큰 데이터셋: 해시 테이블 기반의 최적화된 저장 방식으로 변환.

2번에 대해 좀 더 설명하면 이런 것이다.

[ ['key1', 'value1'], ['key2', 'value2'], ['key3', 'value3'] ]

그렇다. key, value를 갖는 이차원 배열이다.

 

이런 방식은 해시테이블과 같은 구조를 생성할 필요가 없기에 오버헤드가 낮다.

그리고 그냥 객체 형식으로 접근하면 되지 왜 배열 형식으로 접근하냐. 메모리 지역성의 이점 때문이다. 배열은 하드웨어상에서 연속된 메모리 블록에 데이터를 저장하므로 CPU 효율이 높다.

 

크기가 커지면 해시 테이블을 이용하여 최적화하기 때문에, 

속성의 위치가 고정되고, 해시 값을 기준으로 데이터의 위치를 찾아가서 hidden class를 변경할 필요가 없다. 키가 추가되거나 삭제되어도 해시 값만 바꾸면 된다.

 

참고로 이 구현은 V8엔진의 대한 것이고, ECMAInternational에서는 일반적으로 Map은 해시테이블을 사용하여 구현하지만, 성능만 보장된다면 내부 구현은 상관없다고 말한다.

https://tc39.es/ecma262/#sec-map-objects

ECMAScript® 2025 Language Specification

 

 

어쨌든 결국 map을 사용하면 성능이 보장된다는 것이다.

 

그렇다면 무조건 map이 객체보다 좋은가?

그럴 리가.

 

객체는 v8엔진에서 인라인 캐싱을 활용하여 조회 성능을 높였다.

작은 데이터셋 기준으로는 객체에서의 조회가 Map보다 빠를 수 있다. <- 하지만 실제로 내가 진행한 테스트에서는 작은 데이터셋에서도 느린 모습을 보여줬다. 하지만 이는 key가 string 타입일 경우에 해당한다. 만약 key가 int 타입이라면, 객체는 이를 연속적으로 접근할 수 있는 위치로 최적화시킨다. 하지만 Map은 동일한 종류의 최적화는 진행하지 않는다.

 

다만 삽입 삭제가 잦을 경우 객체는 hidden class가 변화되기 때문에 Map의 성능이 우월하다. 아직까지는 객체가 너무 좋지 않아 보이지만, 객체의 장점은 JSON 처리가 가능하다는 것이다. JSON 데이터 구조는 객체를 기본으로 한다.

 

나의 경우 key가 무조건 string 타입이었고, 관리해야 할 데이터셋도 10만 개를 기본적으로 넘겼다. 또한 데이터를 제거하기 위해 id를 일반 JSON객체 형식으로 전달하는 것이 아닌 배열 형식으로 전달해야 하는 조건이 있었다. 따라서 나은 성능을 위해서 Map을 채택하였다. 또한 Map은 Map.keys() 메서드를 제공해 준다.

 

—

 

해프닝.

 

이렇게 최적화를 시켰지만, 그럼에도 Map이 더 느렸다??

 

Map은 따로 import 하여 사용할 필요가 없는 객체이다. 그냥 new Map으로 사용하면 된다. 당연히 그렇게 사용했다.

 

javascript의 Map을 사용해야 하는데, 다 구현하고 테스트를 다 마치고 보니 Openlayers 라이브러리의 Map 객체를 사용했던 것이다.

1000줄 정도 분량의 코드에서 외부 의존성 Map이 import 되어있다는 사실을 바로 인지하지 못했다.

 

그럼에도 테스트까지 정상적으로 작동했다? 이유는 Openlayers의 Map이 BaseObject를 상속받는데, BaseObject에서 객체의 속성을 관리하기 위해 get, set 메서드를 제공해 주기 때문이었다. ES6의 Map에서 제공해 주는 메서드들과 이름도 같았기에 정상적으로 작동했다.;; BaseObject의 get, set 메서드는 자바스크립트 객체로 구현되어 있기 때문에, 내가 사용한 것은 실질적으로 Map이 아니라 객체였다. 사실 Map이긴 하지만.. ㅋ

 

https://openlayers.org/en/latest/apidoc/module-ol_Object-BaseObject.html#set

OpenLayers v10.2.1 API - Class: BaseObject