Вглубь std::unordered_map: магические числа
Все любители кодокопания заканчивают либо хорошо, либо плохо. Мне повезло. Поэтому я решила написать свою первую статью на Хабре.
Кодокопатель после 6 часов копания
Как всё начиналось
Мой друг игрался со вставкой в unordered_map и заметил странную закономерность в изменении параметра bucket_count с ростом числа элементов в таблице.
Немного матчасти
Unordered map в C++ представляет собой хэш-таблицу. Хэш-таблица даёт околоконстантное время операций за счёт того, что каждый элемент хранится по своему уникальному индексу, вычисляемому через хэш-функцию. При вычислении индекса значение хэш-функции (коротко — хэш) масштабируется на размер таблицы, поэтому он не должен меняться при выполнении операций. Совпадение индексов называется коллизией. Есть несколько стратегий обработки коллизий. В std: unordered_map используется bucket hashing.
Заключается она в том, что элементы с одинаковым хэшем кладутся в соответствующий этому хэшу сегмент (bucket). При возрастании числа коллизий скорость операций с таблицей падает, поэтому необходимо производить рехэширование (rehashing) — увеличивать число сегментов и пересчитывать все хэши элементов, соответственно перевыделять память для таблицы и вставлять их заново. Это дорогостоящая по времени и памяти операция, поэтому приходится искать компромисс между числом коллизий и частотой рехэширования.
Эксперимент показал, что рехэширование происходит при вставке соответственно 14 го, 30 го, 60 го, 128 го, 258 го, 542 го, 1110 го, 2358 го и так далее. Это дал следующий код:
#include
#include
int main () {
std::unordered_map umap;
// заполняем таблицу 2000 элементами - парами чисел
for (int i = 0; i < 2000; i++) {
// выводим число элементов и число сегментов на каждой итерации
std::cout << umap.size() << " " << umap.bucket_count() << std::endl;
umap.insert({i, i+1});
}
}
Получается, размеры таблицы образуют последовательность 13, 29, 59, 127, 257, 541, 1109, 2357. Но откуда берутся эти числа?
(Здесь сразу стоит оговориться, что кто знает, тому очевидно. Интерес представляет внутренняя структура того, как это реализовано.)
Начинаем копать
Первая часть изысканий делается через встроенную в IDE возможность перехода к определениям функций. insert нам даёт:
unordered_map: insert
Отлично. Мы обнаружили, что unordered_map ссылается на _M_h. Следующие пара шагов нам дают:
Нашли _M_h. Ищем _umap_hashtable
Нашли _umap_hashtable
Это шаблон базового типа unordered_map. Там есть параметр, кончающийся на rehash_policy. Звучит как то, что нас интересует! Видно, что параметр определён в std::_detail. Объявим
std::__detail::_Prime_rehash_policy p;Перейдём к определению (используя «Go to definition»). Оно в файле под именем hashtable_policy.h. Лишний раз подтверждает связь хэш-таблицы и unordered_map.
Что-то проясняется
Теперь мы знаем, какие функции дают наши «магические числа». К сожалению, определений в этом файле не нашлось.
Долгожданная реализация
Гугл выдаёт следующее: хэдер с аналогичным названием, но из TR1 (расширение C++ между C++03 и C++11, ставший частью последнего): https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.2/hashtable__policy_8h-source.html
Рассмотрим функцию need_rehash, которая определяет новое количество сегментов (а закон его расчёта мы и ищём):
Почти.
Наш случай — когда функция возвращает true (произойдёт rehashing). Параметр _M_growth_factor, он же _S_growth_factor в новой версии, по дефолту равен 2 (находится поиском по файлу), т.е. размер предварительно удваивается. _M_max_load_factor в дефолтном конструкторе равен 1. Шаблонный класс unordered_map использует именно дефолтные параметры, проверяется это эмпирически с помощью дебаггера.
Двоичный поиск по некоторому массиву _Primes<>::__primes нам даёт первое простое, большее удвоенного размера массива + числа вставленных элементов (1), и устанавливает в него параметр _M_next_resize, определяющий новое число сегментов.
Для первых 6 членов ряда всё ок: (13+1)*2 = 28 → 29, аналогично 59 и 127. Но 257×2+1 = 515, ближайшее простое — 521, а у нас — 541… Аналогично 1109 и 2357 не соответствуют расчётам.
На этом моменте я конкретно задумалась, но к счастью, моё внимание привлёк огромный массив чисел в начале файла. Это и есть тот самый _Primes<>::__primes:
Странное дело
Согласно этому массиву, всё работает верно (это легко проверить). Ура. Мы нашли разгадку.
Заключение
Мы получили, что искомая последовательность формируется по принципу «ближайшее простое, большее 2(n+1), где n — предыдущий член последовательности». С оговоркой на то, что простые числа берутся из некоторого заданного массива. Почему он именно такой — неизвестно. Предположу, что часть простых пропущена из соображений памяти.
Также, невыясненным остался вопрос, почему при вставке одного элемента число сегментов возрастает сразу до 13. Может быть, вы знаете?
Жду замечаний и предложений в комментариях :)
P.S. Судя по тому, что новая библиотека работает как код из tr1, tr1 действительно был внесён в новый стандарт.
