В стандарте ECMAScript 2015, известном как ES6, появилось много новых JavaScript-коллекций, таких, как Map, Set, WeakMap и WeakSet. Они, судя по всему, стали отличным дополнением к стандартным возможностям JavaScript. Они получили широкое применение в различных библиотеках, в приложениях, в ядре Node.js. Сегодня мы поговорим о коллекции Map, попытаемся разобраться с особенностями её реализации в V8 и сделаем некоторые практические выводы, основанные на полученных знаниях.
Стандарт ES6 не содержит чёткого указания на подход, который должен быть использован для реализации поддержки структуры данных Map. В нём лишь даны некоторые подсказки по возможным способам её реализации. Там же приведены сведения об ожидаемых от Map показателях производительности:
Объект Map должен быть реализован либо с использованием хеш-таблиц, либо с применением других механизмов, которые, в среднем, обеспечивают доступ к элементам коллекции за сублинейное время. Структуры данных, используемые в спецификации объекта Map, предназначены лишь для описания наблюдаемой семантики объектов Map. Они не задумывались как реальная модель реализации этих объектов.
Как видно, спецификация даёт тем, кто создаёт JS-движки, большую свободу. Но при этом здесь нет определённых указаний, касающихся конкретного подхода, используемого для реализации Map, его производительности, характеристик потребления памяти. Если в критически важной части вашего приложения используются структуры данных Map, и если вы записываете в такие структуры данных большие объёмы информации, то основательные знания о реализации Map, определённо, принесут вам большую пользу.
У меня есть опыт Java-разработки, я привык к коллекциям Java, когда можно выбирать между различными реализациями интерфейса Map и даже выполнять тонкую настройку выбранной реализации в том случае, если соответствующий класс это поддерживает. Более того, в Java всегда можно почитать опенсорсный код любого класса стандартной библиотеки и познакомиться с его реализацией (она, конечно, может в новых версиях меняться, но только в направлении повышения эффективности). Именно поэтому я не смог удержаться от того, чтобы изучить особенности работы объектов Map в V8.
Прежде чем мы начнём, хочу отметить, что то, о чём речь пойдёт ниже, относится к движку V8 8.4, который встроен в свежую dev-версию Node.js (если точнее, то речь идёт о коммите 238104c). Вам не нужно ожидать чего-то, выходящего за пределы спецификации.
Алгоритм, лежащий в основе реализации Map
В первую очередь скажу о том, что структуры данных Map основаны на хеш-таблицах. Ниже я исхожу из предположения о том, что вы знаете о том, как работают хеш-таблицы. Если же вы с хеш-таблицами не знакомы, то вам стоит сначала о них почитать (здесь, например) и уже потом продолжать чтение этой статьи.
Если у вас есть значительный опыт работы с объектами Map, то вы уже могли заметить противоречие. А именно, хеш-таблицы не гарантируют возврата элементов в некоем постоянном порядке при их переборе. А в спецификации ES6 указано, что для реализации объекта Map необходимо, при его обходе, выдавать элементы в том порядке, в котором они были в него добавлены. В результате «классический» алгоритм для реализации Map не подходит. Но возникает такое ощущение, что его, с некоторыми изменениями, всё же можно использовать.
V8 использует так называемые «детерминированные хеш-таблицы», предложенные Тайлером Клоузом. Следующий псевдокод, основанный на TypeScript, демонстрирует основные структуры данных, используемые при реализации таких хеш-таблиц:
interface Entry {
key: any;
value: any;
chain: number;
}
interface CloseTable {
hashTable: number[];
dataTable: Entry[];
nextSlot: number;
size: number;
}
Здесь интерфейс CloseTable представляет хеш-таблицу. Он содержит массив hashTable, размер которого эквивалентен количеству хеш-контейнеров. Элемент массива с индексом N соответствует N-ному хеш-контейнеру и хранит индекс его головного элемента, находящегося в массиве dataTable. А этот массив содержит записи таблицы в порядке их вставки в неё. Записи представлены интерфейсом Entry. И наконец, у каждой записи есть свойство chain, которое указывает на следующую запись в цепочке записей хеш-контейнера (или, точнее, в односвязном списке).
Каждый раз, когда в таблицу вставляют новую запись, она сохраняется в элементе массива dataTable с индексом nextSlot. Этот процесс, кроме того, требует обновления данных в соответствующем хеш-контейнере, что приводит к тому, что вставленная запись становится новым последним элементом односвязного списка.
Когда запись удаляют из таблицы, то она удаляется из dataTable (например, путём записи в её свойства key и value значения undefined). Затем запись, предшествующая ей, и запись, следующая за ней, связываются друг с другом напрямую. Как вы могли заметить, это означает, что все удалённые записи продолжают занимать место в dataTable.
А теперь — последний кусочек нашей головоломки. Когда таблица оказывается полна записей (и актуальных, и удалённых), она должна быть перехеширована (перестроена) с увеличением её размера. Размер таблицы может быть изменён и в сторону уменьшения.
Благодаря такому подходу обход структуры данных Map равносилен обходу массива dataTable. Это гарантирует сохранение порядка вставки записей в таблицу и соблюдение требования стандарта. Учитывая это, я ожидаю, что большинство JS-движков (если не все) используют детерминированные хеш-таблицы в качестве одного из механизмов, лежащих в основе реализации Map.
Практическое исследование алгоритма
Давайте рассмотрим несколько примеров, позволяющих нам исследовать алгоритм на практике. Предположим, у нас имеется CloseTable с 2 хеш-контейнерами (hastTable.length), общая ёмкость которой составляет 4 элемента (dataTable.length). Эту таблицу заполняют следующим содержимым:
// Предположим, что мы используем хеш-функцию, возвращающую
// то, что она получает на вход, то есть function hashCode(n) { return n; }
table.set(0, 'a'); // => хеш-контейнер 0 (0 % 2)
table.set(1, 'b'); // => хеш-контейнер 1 (1 % 2)
table.set(2, 'c'); // => хеш-контейнер 0 (2 % 2)
Внутреннее представление таблицы, получившейся в этом примере, может выглядеть так:
const tableInternals = {
hashTable: [0, -1],
dataTable: [
{
key: 0,
value: 'a',
chain: 2 // индекс <2, 'c'>
},
{
key: 1,
value: 'b',
chain: -1 // -1 означает последнюю запись списка
},
{
key: 2,
value: 'c',
chain: -1
},
// пустой слот
],
nextSlot: 3, // указывает на пустой слот
size: 3
}
Если удалить запись, воспользовавшись методом table.delete(0), то хеш таблица будет выглядеть так, как показано ниже:
const tableInternals = {
hashTable: [0, 1],
dataTable: [
{
key: undefined, // удалённая запись
value: undefined,
chain: 2
},
{
key: 1,
value: 'b',
chain: -1
},
{
key: 2,
value: 'c',
chain: -1
},
// пустой слот
],
nextSlot: 3,
size: 2 // новый размер
}
Если мы добавим в таблицу ещё пару записей, то она будет нуждаться в перехешировании. Этот процесс мы подробно обсудим немного ниже.
Тот же подход может быть применён и при реализации структур данных Set. Единственное отличие заключается в том, что эти структуры данных не нуждаются в свойстве value.
Теперь, когда мы разобрались с тем, что стоит за объектами Map в V8, мы готовы к тому, чтобы двинуться дальше.
Детали реализации
Реализация структуры данных Map в V8 написана на C++, после чего JS-коду дан доступ к соответствующим механизмам. Основная часть кода, имеющего отношение к Map, находится в классах OrderedHashTable и OrderedHashMap. Мы уже знаем о том, как работают эти классы. Если же вы хотите сами взглянуть на их код, то мы можете найти его здесь, здесь и здесь.
Так как нас особенно интересуют практические подробности о реализации Map в V8, нам, для начала, надо понять то, как задаётся ёмкость таблицы.
Ёмкость таблицы
В V8 ёмкость хеш-таблицы (структуры данных Map) всегда равна некоей степени двойки. Если говорить о коэффициенте использования хеш-контейнеров, то он всегда представлен числом 2. То есть, максимальная ёмкость таблицы — это 2 * number_of_buckets — 2, умноженное на количество хеш-контейнеров. При создании пустого объекта Map в его внутренней хеш-таблице имеется 2 хеш-контейнера. В результате ёмкость такого объекта равняется 4 записям.
Существует ограничение на максимальную ёмкость объектов Map. В 64-битных системах это будет около 16,7 миллиона записей. Это ограничение объясняется особенностями представления структур данных Map в куче. Мы поговорим об этом позже.
И наконец, коэффициент увеличения или уменьшения таблицы тоже всегда представлен произведением некоего числа на 2. Это значит, что после того, как в описываемую таблицу будет добавлено 4 записи, следующая операция вставки вызовет необходимость в перехешировании таблицы, в ходе которого размер таблицы увеличится в два раза. При уменьшении размеров таблицы, она, соответственно, может стать в 2 раза меньше.
Для того чтобы убедиться в том, что то, что я увидел в исходном коде, работает именно так, как я понял, я модифицировал код движка V8, встроенный в Node.js, сделав так, чтобы в объектах Map было бы доступным новое свойство buckets, содержащее сведения о количестве хеш-контейнеров. Результаты этой модификации вы можете найти здесь. В этой особой сборке Node.js можно запустить следующий скрипт:
const map = new Map();
let prevBuckets = 0;
for (let i = 0; i < 100; i++) {
if (prevBuckets !== map.buckets) {
console.log(`size: ${i}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);
prevBuckets = map.buckets;
}
map.set({}, {});
}
Этот скрипт просто вставляет в структуру данных Map 100 записей. Вот что выводится в консоли после его запуска:
$ ./node /home/puzpuzpuz/map-grow-capacity.js
size: 0, buckets: 2, capacity: 4
size: 5, buckets: 4, capacity: 8
size: 9, buckets: 8, capacity: 16
size: 17, buckets: 16, capacity: 32
size: 33, buckets: 32, capacity: 64
size: 65, buckets: 64, capacity: 128
Как видно, когда таблица заполняется, то, при каждом изменении её размера, она увеличивается в 2 раза. Попробуем теперь добиться уменьшения таблицы, удаляя из неё элементы:
const map = new Map();
for (let i = 0; i < 100; i++) {
map.set(i, i);
}
console.log(`initial size: ${map.size}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);
let prevBuckets = 0;
for (let i = 0; i < 100; i++) {
map.delete(i);
if (prevBuckets !== map.buckets) {
console.log(`size: ${map.size}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);
prevBuckets = map.buckets;
}
}
Вот что выведет этот скрипт:
$ ./node /home/puzpuzpuz/map-shrink-capacity.js
initial size: 100, buckets: 64, capacity: 128
size: 99, buckets: 64, capacity: 128
size: 31, buckets: 32, capacity: 64
size: 15, buckets: 16, capacity: 32
size: 7, buckets: 8, capacity: 16
size: 3, buckets: 4, capacity: 8
size: 1, buckets: 2, capacity: 4
Тут, опять же, видно, что размер таблицы уменьшается каждый раз, когда в ней оказывается меньше чем number_of_buckets / 2 элементов.
Хеш-функция
До сих пор мы не касались вопроса о том, как V8 вычисляет хеш-коды для ключей, сохраняемых в объектах Map. А это — важный вопрос.
Для значений, которые можно отнести к числовым, используется та или иная хорошо известная хеш-функция с низкой вероятностью коллизии.
Для строковых значений выполняется вычисление хеш-кода, который основан на самих этих значениях. После этого данный код кешируется во внутреннем заголовке.
И, наконец, для объектов хеши вычисляют на основе случайного числа, а то, что получилось затем кешируется во внутреннем заголовке.
Временная сложность операций с объектами Map
Большинство операций, производимых над структурами данных Map, вроде set или delete, требуют поиска по этим структурам данных. Так же как и в случае с «классическими» хеш-таблицами, временная сложность поиска в нашем случае — это O(1).
Представим себе наихудший сценарий развития событий, когда таблица полностью заполнена, то есть, в ней заняты N из N мест. Все записи при этом принадлежат единственному хеш-контейнеру, а искомая запись находится в самом конце цепочки записей. В подобном сценарии для поиска этой записи понадобится выполнить N действий.
С другой стороны, в наилучшем сценарии, когда таблица заполнена, и при этом в каждом хеш-контейнере находится всего 2 записи, поиск записи потребует всего 2 действий.
Определённые операции в хеш-таблицах выполняются очень быстро, но к операции перехеширования это не относится. Временная сложность операции перехеширования — это O(N). Она требует выделения в куче новой хеш-таблицы. Более того, перехеширование выполняется по необходимости, как часть операций по вставке элементов в таблицу или удаления их из неё. Поэтому, например, вызов map.set() может оказаться гораздо «дороже», чем ожидается. Но, к счастью, операция перехеширования выполняется достаточно редко.
Потребление памяти
Конечно, хеш-таблица, лежащая в основе Map, должна быть как-то сохранена в куче. Она хранится в так называемом «вспомогательном хранилище». И тут нас ждёт ещё один интересный факт. Вся таблица (а, значит, и всё то, что помещено в Map) хранится в единственном массиве фиксированной длины. Устройство этого массива показано на следующем рисунке.
Массив, используемый для хранения структур данных Map в памяти
Отдельные части массива имеют следующее назначение:
- Заголовок: содержит информацию общего характера, например, сведения о количестве хеш-контейнеров или о количестве элементов, удалённых из
Map. - Сведения о хеш-контейнерах: тут хранятся данные о контейнерах, которые соответствуют массиву
hashTableиз нашего примера. - Записи хеш-таблицы: здесь хранятся данные, соответствующие массиву
dataTable. А именно, здесь находятся сведения о записях хеш-таблицы. Сведения о каждой записи занимают три ячейки массива. В одной хранится ключ, во второй — значение, в третьей — «указатель» на следующую запись в цепочке.
Если говорить о размере массива, то его можно примерно оценить как N * 3,5. Здесь N — это ёмкость таблицы. Для того чтобы понять то, что это значит в плане потребления памяти, давайте представим, что у нас имеется 64-битная система, и то, что выключена возможность V8 по сжатию указателей. В таком случае для хранения каждого элемента массива понадобится 8 байт. В результате для хранения структуры данных Map, в которой содержится примерно 1 миллион записей, понадобится 29 Мб памяти в куче.
Итоги
В этом материале мы разобрали много всего, имеющего отношение к структуре данных Map в JavaScript. Подведём итоги:
- В V8 для реализации
Mapиспользуются детерминированные хеш-таблицы. Весьма вероятно то, что так же эта структура данных реализована и в других JS-движках. - Механизмы, поддерживающие работу
Map, реализованы на C++, после чего представлены в виде API, который доступен из JavaScript. - Если говорить о временной сложности операций, выполняемых с объектами
Map, то они, так же, как и при работе с «классическими» хеш-таблицами, имеют сложностьO(1). При этом временная сложность операции перехеширования — этоO(N). - В 64-битных системах при отключённом сжатии указателей структура данных
Mapс 1 миллионом записей нуждается в 29 Мб памяти, выделяемой в куче. - Большинство того, что мы здесь обсудили, справедливо и для структур данных
Set.
Пользуетесь ли вы объектами Map в JavaScript-разработке?
Автор: ru_vds
