При разработке приложений регулярно возникает задача кэширования каких-то данных, которые из хранилища должны читаться много чаще, чем писаться. Давайте рассмотрим на примере простого теста, когда и на каком механизме эффективнее организовать его для JavaScript-приложения - на Map или на Object.

new Map()
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 (меньше - лучше)
Поиск 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.

Комментарии (15)


  1. Lazytech
    25.05.2023 07:16
    +3

    Позанудствую: график не слишком понятен, даже оси не подписаны. Какие такие obj(1), map(1) и иже с ними...


    1. Kilor Автор
      25.05.2023 07:16

      ... оформлен не по ГОСТ 2.319-81... ))


      1. Lazytech
        25.05.2023 07:16
        +4

        Прошу подать меня правильно: такая подача материала мешает быстрому усвоению информации. К примеру, для того, чтобы понять, что такое obj(1), map(1) и др., мне пришлось вчитаться в предложение, идущее перед графиком: "Но для большей уверенности прогоним тест трижды <...> ".


        1. Kilor Автор
          25.05.2023 07:16
          -1

          Скорректировал подпись - так более очевидно?


          1. Lazytech
            25.05.2023 07:16

            Уже лучше, но нет предела совершенству. :)


  1. V_asily
    25.05.2023 07:16

    Ну окей, а причина? копали глубже? А то может это просто особенность реализации Map в nodejs указанной версии. С другой версией пробовали?


    1. Kilor Автор
      25.05.2023 07:16

      В статье, указанной в последнем абзаце, как раз рассказывается, как конкретно работает Map "внутри" V8. Если коротко - причина в особенностях используемого в V8 алгоритма хэширования.


  1. Suvitruf
    25.05.2023 07:16

    читаться много чаще, чем писаться

    мы не будем туда ничего добавлять

    Какой-то странный кейс. В какой задаче вам понадобится именно итерировать кэш? Чаще всего из кэша читают, редко когда его нужно целиком прогонять.


    1. Kilor Автор
      25.05.2023 07:16
      +1

      Он здесь не прогоняется целиком и не итерируется, мы просто эмулируем миллион случайных обращений.

      А кейс очень простой - при старте приложения вы можете поднимать некий заранее предрассчитанный кэш, который покрывает 99.9% обращений, а потом только обращаться к нему, не пытаясь его изменить. Вполне очевидно, что попытка добавления этих 0.1% разнообразных значений может со временем непотребно раздуть его.


  1. nin-jin
    25.05.2023 07:16
    -3

    Создание кеша на миллион записей:

    Создание словаря в 2 раза быстрее
    Создание словаря в 2 раза быстрее

    Миллион успешных обращений к кешу:

    Разницы никакой
    Разницы никакой


    1. Kilor Автор
      25.05.2023 07:16

      хм...res &&= cachedVal превратится в 0 при первом же попадании cachedVal === 0, а дальше правая часть просто перестанет выполняться при следующих итерациях


      1. nin-jin
        25.05.2023 07:16
        -1

        А, там циферки в значениях. Поправил:


        1. Kilor Автор
          25.05.2023 07:16

          На миллионном кэше у меня Map : Object получилось 550ms : 400ms = 1.375, тут 454ms : 377ms = 1.20, примерно так же.


  1. dom1n1k
    25.05.2023 07:16

    кэш у нас будет "стабильным" — то есть мы не будем туда ничего ни добавлять, ни удалять;

    Именно здесь и порылась собака: Map рассчитана выдерживать добавления/удаления ключей. А Object отлично подходит для статических данных, но будет деградировать на обновляемых (особенно с удалениями).


    1. Kilor Автор
      25.05.2023 07:16
      -1

      Object отлично подходит для статических данных

      Однако, в нашем тесте до 64K ключей Map показал себя лучше и при отсутствии вставок/удалений.