Кэш в JavaScript: не все Map’ы одинаково полезны

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

Сначала определим некоторые вводные:

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

• ключами для нашего кэша будут выступать короткие строки — в нашем примере 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

Уже тут можно увидеть определенные тенденции. Но для большей уверенности прогоним тест трижды и сведем значения на графике:

Выводы предельно кратко:

• идеальный размер для 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.