Комментарии 13
Спасибо.
Зачем в такого типа тексте бенчмарки? — Правильно, незачем. Улучшили же! Виват!
Соответственно следующие 10 бит 0b1101100101→ указывают на группу внутри подтаблицы.
Разве не 10 младших бит?
удвоение количества групп в таблице происходит при достижении общей загрузки таблицы (load factor) в 81,25%
В предыдущей реализации load factor действительно был 6,5/8 =0,8125. Однако в свежей реализации его увеличили до 7/8 =0,875
“Ранее в Go для разрешения коллизий в хеш-таблицах использовался метод цепочек, при котором каждый бакет содержал указатель на связанный список элементов с одинаковым хеш-значением.» - ранее это насколько ранее? Мне вот это предложение не давало покоя. Насколько я помню, с go 1.8 в хеш - таблицах метод цепочек, предполагающий списки, уже не используется. Все хранится в одном большом массиве. И действительно:
Начиная с Go 1.8, реализация map в Go перешла с метода цепочек (связные списки в бакетах) на комбинацию открытой адресации и "bucket-ов"
Верно. Но если в bucket'е заканчивались слоты (а их было тоже 8), то динамически создавался т.н. overflow bucket, указатель на который хранился в "оригинальном" bucket'е с открытой адресацией. А если и в том заканчивались слоты, то цепочка overflow bucket'ов продолжалась.
Потому в отдельных случаях производительность map'ы сильно падала, так как "бегая" по таким overflow bucket'ам, получается random memory access и соответственно кэш миссы. Даже специальная оптимизация была, когда load factor map'ы ещё не достиг значения для её grow'инга, а кол-во overflow bucket'ов уже превысило лимит - в этом случае запускался regrow'инг, когда размер map'ы оставался тем же самым, но менялось значение seed'а для функции хэша. Это позволяло перераспределить ключи по bucket'ам и снизить кол-во overflow bucket'ов
А почему в пример с перемещением элементов: A: H1(A) & 0b1111 = 0b0011?
Вопрос. Как мы находим элемент, который был записан в групп 7 в данном примере:
1. Группа 5 заполнена → идём к группе 6.
2. Группа 6 заполнена → идём к группе 7.
3. Группа 7 свободная → записываем туда.
Если при получении хэша, мы получаем группу 5 и после не нахождения элемента в группе 5 мы заканчиваем поиск?
В случае неуспеха, возвращается значение по умолчанию для хранимого типа.
Отличная статья, спасибо!
К сожалению, я не понял описание значений структуры контрольного байта. Мне кажется, что туда закралась ошибка. Поправьте, пожалуйста, если я не прав.
В статье указаны следующие значения для контрольного байта:
1 бит (старший) — флаг занятости (Empty / Deleted / Used), который указывает текущее состояние слота:
0b00000000 (0x00) → Слот пуст (Empty)
0b1xxxxxxx (H2) → Слот занят (Used)
0b10000000 (0x80) → Слот удалён (Deleted) также данное состояние называют Tombstone, по своей сути является маркером для алгоритма пробирования, далее будет более подробно раскрыт смысл данного статуса.
7 бит (младшие) — нижние 7 бит из результата хеширования (H), в случае состояния Used.
Однако кажется, что это не соответствует реализации. В связи с этим, привожу вырезку из документации (документация из веток release 1.24 и master совпадает на момент публикации комментария):
// Each slot in the hash table has a control byte which can have one of three
// states: empty, deleted, and full. They have the following bit patterns:
//
// empty: 1 0 0 0 0 0 0 0
// deleted: 1 1 1 1 1 1 1 0
// full: 0 h h h h h h h // h represents the H2 hash bits
//
// TODO(prattmic): Consider inverting the top bit so that the zero value is empty.
type ctrl uint8
Соответственно, должно быть что-то такое, если я не ошибаюсь:
1 бит (старший) — флаг занятости (Empty / Deleted / Used), который указывает текущее состояние слота:
0b10000000 → Слот пуст (Empty)
0b0hhhhhhh → Слот занят (Used), h соответствуют битам H2
0b11111110 → Слот удалён (Deleted) также данное состояние называют Tombstone, по своей сути является маркером для алгоритма пробирования, далее будет более подробно раскрыт смысл данного статуса.
7 бит (младшие) — нижние 7 бит (H2) из результата хеширования (H), в случае состояния Used.
Предполагаю, что информация о 0x80 / 0x00 взята из документации bitset. Однако, bitset это другое значение, архитектурозависимое и отличное от ctrl. Также привожу документацию на него ниже, где о значениях 0x80 / 0x00 пишут в последнем абзаце:
// bitset represents a set of slots within a group.
//
// The underlying representation depends on GOARCH.
//
// On AMD64, bitset uses one bit per slot, where the bit is set if the slot is
// part of the set. All of the ctrlGroup.match* methods are replaced with
// intrinsics that return this packed representation.
//
// On other architectures, bitset uses one byte per slot, where each byte is
// either 0x80 if the slot is part of the set or 0x00 otherwise. This makes it
// convenient to calculate for an entire group at once using standard
// arithemetic instructions.
type bitset uint64
Go 1.24: принципы работы и преимущества обновленной map