Перейти к основному содержимому

Оптимизация хеш-таблиц: скрытие хеш-кода

· 5 мин. чтения
[Сатья Гунасекеран](https://twitter.com/_gsathya), хранитель хеш-кодов

ECMAScript 2015 ввел несколько новых структур данных, таких как Map, Set, WeakSet и WeakMap, которые используют хеш-таблицы под капотом. Этот пост описывает последние улучшения в том, как V8 v6.3+ хранит ключи в хеш-таблицах.

Хеш-код​

Хеш-функция используется для сопоставления данного ключа с местоположением в хеш-таблице. Хеш-код — это результат выполнения этой хеш-функции над данным ключом.

В V8 хеш-код — это просто случайное число, независимое от значения объекта. Поэтому мы не можем вычислить его повторно, а значит, нам нужно хранить его.

Для объектов JavaScript, использованных как ключи, ранее хеш-код хранился как приватный символ в объекте. Приватный символ в V8 похож на Symbol, за исключением того, что он не перечисляем и недоступен из пользовательского JavaScript.

function GetObjectHash(key) {
  let hash = key[hashCodeSymbol];
  if (IS_UNDEFINED(hash)) {
    hash = (MathRandom() * 0x40000000) | 0;
    if (hash === 0) hash = 1;
    key[hashCodeSymbol] = hash;
  }
  return hash;
}

Этот подход работал хорошо, так как нам не нужно было резервировать память под поле хеш-кода до момента добавления объекта в хеш-таблицу, когда в объекте создавался новый приватный символ.

V8 также мог оптимизировать поиск символа хеш-кода так же, как поиск любого другого свойства, используя систему IC, обеспечивая очень быстрый доступ к хеш-коду. Это работает хорошо для монополиморфных IC-запросов, когда ключи имеют одинаковый скрытый класс. Однако большинство реального кода не следует этой модели, и ключи часто имеют разные скрытые классы, что приводит к медленным мегаполиморфным IC-запросам хеш-кода.

Еще одной проблемой подхода с приватным символом было то, что при записи хеш-кода происходила переход скрытого класса в ключевом объекте. Это приводило к слабой полиморфности кода не только для поиска хеш-кода, но также и для других свойств ключей и к дезоптимизации оптимизированного кода.

Хранилища объектов JavaScript​

Объект JavaScript (JSObject) в V8 использует два слова (помимо заголовка): одно слово для указателя на хранилище элементов и другое слово для указателя на хранилище свойств.

Хранилище элементов используется для хранения свойств, которые выглядят как индексы массива, тогда как хранилище свойств используется для хранения свойств, ключами которых являются строки или символы. Подробнее об этих хранилищах вы можете узнать из поста в блоге V8 Камилло Бруни.

const x = {};
x[1] = 'bar';      // ← хранится в элементах
x['foo'] = 'bar';  // ← хранится в свойствах

Скрытие хеш-кода​

Самое простое решение для хранения хеш-кода — это увеличить размер объекта JavaScript на одно слово и хранить хеш-код прямо в объекте. Однако это тратило бы память на объекты, которые не добавляются в хеш-таблицу. Вместо этого мы могли бы попытаться хранить хеш-код в хранилище элементов или свойств.

Хранилище элементов представляет собой массив, содержащий его длину и все элементы. Здесь трудно что-либо сделать, так как хранение хеш-кода в зарезервированном слоте (например, в 0-м индексе) все равно бы тратило память, если объект не используется как ключ в хеш-таблице.

Давайте рассмотрим хранилище свойств. Существует два вида структур данных, используемых в качестве хранилища свойств: массивы и словари.

В отличие от массива, используемого в хранилище элементов, который не имеет верхнего предела, массив, используемый в хранилище свойств, имеет верхний предел в 1022 значения. V8 переходит на использование словаря при превышении этого предела из соображений производительности. (Я слегка упрощаю: V8 может использовать словарь и в других случаях, но существует фиксированный верхний предел количества значений, которые можно хранить в массиве.)

Итак, существует три возможных состояния для хранилища свойств:

  1. пустое (нет свойств)
  2. массив (может хранить до 1022 значений)
  3. словарь

Давайте обсудим каждый из них.

Хранилище свойств пусто​

В случае пустого хранилища мы можем напрямую сохранить хэш-код в этом смещении в объекте JSObject.

Хранилище свойств — массив​

V8 представляет целые числа меньше 231 (на 32-битных системах) в неупакованном виде, как Smi. В Smi наименее значащий бит используется как метка для отличия его от указателей, а остальные 31 бит содержат само значение целого числа.

Обычно массивы хранят свою длину как Smi. Поскольку мы знаем, что максимальная ёмкость этого массива составляет только 1022, нам нужно всего 10 бит для хранения длины. Оставшиеся 21 бит можно использовать для хранения хэш-кода!

Хранилище свойств — словарь​

В случае словаря мы увеличиваем размер словаря на 1 слово, чтобы хранить хэш-код в отдельном слоте в начале словаря. Мы можем позволить себе потенциально потратить одно слово памяти в этом случае, потому что пропорциональное увеличение размера не такое большое, как в случае массива.

С этими изменениями поиск хэш-кода больше не требует прохождения сложного механизма поиска свойств JavaScript.

Улучшение производительности​

Бенчмарк SixSpeed отслеживает производительность Map и Set, и эти изменения привели к улучшению на ~500%.

Это изменение также привело к улучшению на 5% в базовом тесте ARES6.

Это также привело к улучшению на 18% в одном из тестов в наборе бенчмарков Emberperf, который тестирует Ember.js.