При разработке приложений регулярно возникает задача кэширования каких-то данных, которые из хранилища должны читаться много чаще, чем писаться. Давайте рассмотрим на примере простого теста, когда и на каком механизме эффективнее организовать его для JavaScript-приложения - на Map или на Object.
![new Map() new Map()](https://habrastorage.org/getpro/habr/upload_files/632/e37/2a1/632e372a15d745757cab18a8afa93675.jpg)
Сначала определим некоторые вводные:
кэш у нас будет "стабильным" - то есть мы не будем туда ничего ни добавлять, ни удалять;
ключами для нашего кэша будут выступать короткие строки - в нашем примере 8-символьные;
тестирование производим на Node.js текущей LTS-версии 18.16.0.
Чтобы в наше тестирование не вмешивался Garbage Collector в случайное время, будем вызывать его в явном виде из кода. Для этого разрешим доступ к нему при запуске нашего приложения:
node --expose-gc cache.js
Подготовим тест, который создает кэш определенного размера на Map
и на Object
с одними и теми же парами ключ-значение и прогоняет в нем миллион поисков случайных ключей:
const hrtime = process.hrtime.bigint;
const timeMS = ts => Number(hrtime() - ts)/1e6 | 0;
const limit = 23;
// формируем содержимое кэша из пар ключ-значение
const content = new Array(1 << limit)
.fill()
.map((_, i) => [
i.toString(16).padStart(8, '0') // key
, i // val
]);
console.log('exp | map gen | obj gen | map scan | obj scan');
// прогоняем тесты для размеров от 2^1 до 2^23
for (let pow2 = 1; pow2 <= limit; pow2++) {
const sz = 1 << pow2;
const slice = content.slice(0, sz);
// генерируем кэш на Map
const tsGM = hrtime();
const map = new Map(slice);
const tmGM = timeMS(tsGM);
// генерируем кэш на Object
const tsGO = hrtime();
const obj = Object.fromEntries(slice);
const tmGO = timeMS(tsGO);
// формируем миллион случайных ключей для поиска
const keys = new Array(1e6)
.fill()
.map(_ => ((Math.random() * sz) | 0).toString(16).padStart(8, '0'));
// прогоняем поиск по Map
const tsSM = hrtime();
keys.forEach(v => map.get(v));
const tmSM = timeMS(tsSM);
// прогоняем поиск по Object
const tsSO = hrtime();
keys.forEach(v => obj[v]);
const tmSO = timeMS(tsSO);
// принудительно вызываем Garbage Collector
gc();
console.log(
pow2.toString().padStart(3, ' ')
, '|'
, tmGM.toString().padStart(7, ' ')
, '|'
, tmGO.toString().padStart(7, ' ')
, '|'
, tmSM.toString().padStart(8, ' ')
, '|'
, tmSO.toString().padStart(8, ' ')
);
}
Получаем примерно такой вывод:
exp | map gen | obj gen | map scan | obj scan
1 | 0 | 0 | 64 | 111
2 | 0 | 0 | 76 | 115
3 | 0 | 0 | 75 | 121
4 | 0 | 0 | 82 | 130
5 | 0 | 0 | 85 | 140
6 | 0 | 0 | 90 | 166
7 | 0 | 0 | 85 | 173
8 | 0 | 0 | 88 | 189
9 | 0 | 2 | 88 | 204
10 | 0 | 6 | 93 | 134
11 | 0 | 7 | 95 | 138
12 | 0 | 9 | 96 | 126
13 | 1 | 10 | 107 | 137
14 | 3 | 14 | 120 | 134
15 | 5 | 21 | 131 | 163
16 | 14 | 37 | 160 | 234
17 | 36 | 84 | 270 | 302
18 | 95 | 171 | 439 | 353
19 | 174 | 378 | 498 | 370
20 | 419 | 782 | 533 | 392
21 | 903 | 1665 | 605 | 402
22 | 1903 | 3534 | 618 | 442
23 | 4078 | 11783 | 835 | 500
Уже тут можно увидеть определенные тенденции. Но для большей уверенности прогоним тест трижды и сведем значения на графике:
![Поиск 1M ключей Map vs Object на 3 разных наборах данных:общее время (мс) в зависимости от размера кэша 2^N (меньше - лучше) Поиск 1M ключей Map vs Object на 3 разных наборах данных:общее время (мс) в зависимости от размера кэша 2^N (меньше - лучше)](https://habrastorage.org/getpro/habr/upload_files/5ea/4ab/243/5ea4ab2430699fb029abe253ca074032.png)
общее время (мс) в зависимости от размера кэша 2^N (меньше - лучше)
Выводы предельно кратко:
идеальный размер для
Map
- до 2^12 (4096) ключей, к 2^16 (64K) ключей скорость падает в 1.5 раза;при 2^17 (128K) ключей использовать
Object
уже выгоднее;удивительный факт:
Object
на 1K..16K ключей быстрее в доступе, чем на 32..512.
Для желающих узнать подробнее, почему Map
ведет себя в V8 (Node.js, Chrome, ...) именно так, рекомендую ознакомиться со статьей [V8 Deep Dives] Understanding Map Internals в блоге Andrey Pechkurov.