[Перевод] О реализации структуры данных Map в V807.09.2020 17:17

В стандарте 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-разработке?