Перевод О реализации структуры данных Map в V8

В стандарте 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.jssize: 0, buckets: 2, capacity: 4size: 5, buckets: 4, capacity: 8size: 9, buckets: 8, capacity: 16size: 17, buckets: 16, capacity: 32size: 33, buckets: 32, capacity: 64size: 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.jsinitial size: 100, buckets: 64, capacity: 128size: 99, buckets: 64, capacity: 128size: 31, buckets: 32, capacity: 64size: 15, buckets: 16, capacity: 32size: 7, buckets: 8, capacity: 16size: 3, buckets: 4, capacity: 8size: 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-разработке?