Вглубь std::unordered_map: магические числа

Все любители кодокопания заканчивают либо хорошо, либо плохо. Мне повезло. Поэтому я решила написать свою первую статью на Хабре.

Как всё начиналось

Мой друг игрался со вставкой в unordered_map и заметил странную закономерность в изменении параметра bucket_count с ростом числа элементов в таблице.

Эксперимент показал, что рехэширование происходит при вставке соответственно 14го, 30го, 60го, 128го, 258го, 542го, 1110го, 2358го и так далее. Это дал следующий код:

#include <unordered_map> #include <iostream>  int main () {      std::unordered_map <int, int> 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 ссылается на _M_h. Следующие пара шагов нам дают:

Это шаблон базового типа 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+1)*2+1 = 517, ближайшее простое — 521, а у нас — 541… Аналогично 1109 и 2357 не соответствуют расчётам.

На этом моменте я конкретно задумалась, но к счастью, моё внимание привлёк огромный массив чисел в начале файла. Это и есть тот самый _Primes<>::__primes:

Согласно этому массиву, всё работает верно (это легко проверить). Ура. Мы нашли разгадку.

Заключение

Мы получили, что искомая последовательность формируется по принципу «ближайшее простое, большее 2(n+1), где n — предыдущий член последовательности». С оговоркой на то, что простые числа берутся из некоторого заданного массива. Почему он именно такой — неизвестно. Предположу, что часть простых пропущена из соображений памяти.

Также, невыясненным остался вопрос, почему при вставке одного элемента число сегментов возрастает сразу до 13. Может быть, вы знаете?

Жду замечаний и предложений в комментариях 🙂

P.S. Судя по тому, что новая библиотека работает как код из tr1, tr1 действительно был внесён в новый стандарт.