Перераспределение связано с увеличением lookup range, это ограничение поиска. Ну и вставка не произойдет пока перераспределение не приведёт к тому что место вставки не окажется в пределах lookup range от начального слота. А данные и так хорошо распределены, большая часть без коллизий вообще ну и допустим меньше процента с глубиной списка коллизий до 6. Но вот этот самый один процент при большом количестве данных всегда ведёт к росту.
> Итак, max_load_factor у всех равен 0,5, и я хотел измерить скорость работы
Здесь лукавство, соотносить скорость надо не при равном max_load_factor, т.к. данная таблица растёт не только в зависимости от него. Сравнивать можно только при равном bucket_count.
Может я что-то не так делаю, но статистика соотношения load_factоr при вставке одинакового количества элементов по сравнению с unordered_map (MS, по степени двойки) у меня получается такая:
1000000 — 0.48 против 0.95
2000000 — 0.24 против 0.95
4000000 — 0.12 против 0.95
8000000 — 0.06 против 0.95 — (!!! 16 кратный запас, сравнивать можно если делать reserve(16X))
> Но если вас не смущает возможность неожиданного перераспределения
Если не смущает, что при некотором «везении» этот контейнер может съесть всю доступную память.
Таблица имеет тенденцию к росту если в ней есть хоть один непрерывно занятый диапазон, длина которого превышает lookup range. Вероятность того, что слот будет иметь тенденцию к росту всегда ненулевая если число занятых слотов превышает диапазон поиска. Можно её даже посчитать, — если рассматривать свободные слоты как случайную выборку на диапазоне, это вероятность того, что максимальное расстояние между соседними элементами в ней будет больше чем lookup range. Т.е. вероятность того, что при выборке K из N элементов ни один из них не попадет в произвольно выбранный диапазон длины R. Комбинаторика, берем число сочетаний из N по K, вычитаем число сочетаний из (N-R) по K, соотносим. В общем там куча восклицательных знаков, ну да это и неважно. Интуитивно понятно что она инвариант при масштабировании. Т.е. даже чтобы сохранить эту вероятность, таблица и диапазон должны расти пропорционально. Но диапазон рассчитывается как логарифм от размера таблицы, т.е. имеет арифметическую прогрессию при геометрической прогрессии роста таблицы. Поэтому с ростом таблицы вероятность попасть на слот с тенденцией к росту растет.
Кстати, в этой таблице rehash рекурсивный.
По сути таблица растёт пока максимальный список коллизий не будет размещён практически линейно. Конечно это будет быстро… если хватит памяти. Робин Гуд помогает, но незначительно. Ну т.е. вот есть какое-то распределение, получаем коллизию, локальное уплотнение занятых слотов превышает максимальный lookup range, таблица растёт. При росте получаем совершенно новое распределение и никто не гарантирует что в нём не получится нового плотного места которое в свою очередь приведёт к новому росту и т.д. Слишком всё случайно. Даже коллизий много не надо, потому что рост таблицы происходит не просто из-за коллизии а из-за неукладывания в lookup range. Т.е. на небольших объёмах оно конечно дорастает до состояния perfect hash, но вот на 20 миллионах данных с достаточно хорошим распределением я протестировать таблицу так и не смог, вероятность локальных уплотнений растёт, что приводит к постоянному росту таблицы, просто памяти не хватило.
Константин Осипов: Еще пара слов о недостатках этой истории с хэшированием… у вас может так получиться, что сервер №3 находится рядом с сервером №1, а между серверами №2 и №3 такое большое полукольцо — практически половина данных.
На самом деле проблемы с распределением в consistent hashing нет, надо просто дать случайности поработать. Для этого каждому серверу дают не один а например 256 диапазонов. И два сервера 512 раз бросив кубик получат красивое деление 50/50. Добавляется третий сервер, ещё 256 случайностей распределят хэши ровно по трети. Более того, при этом новый сервер получит примерно по равной части от каждой ноды, а это значит, что нагрузка на перенос данных будет распределена по всему кластеру. См. cassandra virtual nodes.
Здесь лукавство, соотносить скорость надо не при равном max_load_factor, т.к. данная таблица растёт не только в зависимости от него. Сравнивать можно только при равном bucket_count.
Может я что-то не так делаю, но статистика соотношения load_factоr при вставке одинакового количества элементов по сравнению с unordered_map (MS, по степени двойки) у меня получается такая:
1000000 — 0.48 против 0.95
2000000 — 0.24 против 0.95
4000000 — 0.12 против 0.95
8000000 — 0.06 против 0.95 — (!!! 16 кратный запас, сравнивать можно если делать reserve(16X))
> Но если вас не смущает возможность неожиданного перераспределения
Если не смущает, что при некотором «везении» этот контейнер может съесть всю доступную память.
Кстати, в этой таблице rehash рекурсивный.
На самом деле проблемы с распределением в consistent hashing нет, надо просто дать случайности поработать. Для этого каждому серверу дают не один а например 256 диапазонов. И два сервера 512 раз бросив кубик получат красивое деление 50/50. Добавляется третий сервер, ещё 256 случайностей распределят хэши ровно по трети. Более того, при этом новый сервер получит примерно по равной части от каждой ноды, а это значит, что нагрузка на перенос данных будет распределена по всему кластеру. См. cassandra virtual nodes.