Кэш в 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 ключей Map vs Object на 3 разных наборах данных:
общее время (мс) в зависимости от размера кэша 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.