Кэш в JavaScript: не все Map'ы одинаково полезны
При разработке приложений регулярно возникает задача кэширования каких-то данных, которые из хранилища должны читаться много чаще, чем писаться. Давайте рассмотрим на примере простого теста, когда и на каком механизме эффективнее организовать его для JavaScript-приложения — на Map или на Object.
new Map ()
Сначала определим некоторые вводные:
кэш у нас будет «стабильным» — то есть мы не будем туда ничего ни добавлять, ни удалять
ключами для нашего кэша будут выступать короткие строки — в нашем примере 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 ключей в зависимости от размера кэша 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.
