Robin Hood hashing
Jun. 25th, 2014 08:59 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
thedeemonПоигрался на днях в Робин Гуда - это такой вариант open addressing hash table. Open addressing - это когда данные (пары ключ-значение) все хранятся в одном большом массиве, никаких связных списков. По ключу считаем хэш, его отображаем на пространство позиций в массиве, получаем стартовую позицию, от которой уже пляшем. В простейшем случае Linear Probing мы от стартовой позиции просто последовательно идем вправо, пока не найдем нужное значение. Если мы добавляем новое значение, то так же находим стартовую позицию, от нее движемся вправо, пока не найдем свободную ячейку, там и сохраняем. Robin Hood hashing обычно описывается так: он похож на Linear Probing, при добавлении нового элемента мы так же находим стартовую позицию и движемся последовательно вправо, но поглядываем на хэши тех значений, что нам встречаются на пути, и если находим богача - которому повезло иметь более короткий путь от его стартовой позиции до занимаемой - то раскулачиваем и меняемся с ним: на место богача записываем новое значение, после чего продолжаем процесс (последовательное движение вправо) уже с этим богачом в качестве вставляемого. Такое перераспределение богатств заметно снижает число "бедняков" - значений, оказавшихся очень далеко от своей стартовой позиции, а ведь чем дальше от стартовой позиции находится значение, тем дольше до него идти при поиске, и тем больше может потребоваться линий кэша загрузить из памяти.
Когда таблица у нас большая, а значений мало, и хорошая хэш-функция их так хорошо рассредоточила, что каждое значение живет там, куда указывает хэш (на своей стартовой позиции), то все тривиально, и никакой разницы между этими алгоритмами не чувствуется. Интересные вещи начинаются, когда у нескольких разных значений стартовые позиции совпадают (а это начинает происходить очень быстро - см. birthday problem), тогда возникают кластеры - группы подряд идущих занятых ячеек в таблице. Для простоты возьмем утрированный случай, который однако позволяет получить нужную интуицию. Пусть при отображении хэшей на адреса в массиве у нас на отрезок от [0,100) приземлились 200 значений, а на [100,200) ни одного. Тогда в случае Linear Probing кластер будет выглядеть как-то так:
Тут немало значений, которым повезло оказаться на своей стартовой позиции, но хватает и таких, которые оказались очень далеко, к ним надо идти через весь кластер.
А в случае Robin Hood hashing будет выглядеть как-то так:
Богачей, сохранивших свое место, очень мало, но и через весь кластер ни к кому идти не придется, максимум половину кластера. Т.е. worst case тут получился в два раза лучше, а average - на четверть меньше. И тут видно главное свойство Robin Hood hashing, которое не сразу очевидно из типичного описания: все значения в таблице оказываются упорядочены по своим стартовым позициям. Ведь при вставке Робин Гуд всегда отдает место тому, кто беднее, т.е. значению, у которого путь от его стартовой позиции (PSL - path from starting location, он же DIB - distance from initial bucket, он же probe count) больше, т.е. значение с меньшей стартовой позицией вытесняет значение с большей, сдвигая его вправо. Такое понимание позволяет сделать оптимизацию: когда Робин Гуд выгоняет богача из его ячейки, у значений справа от него их стартовые позиции не меньше, чем у этого богача, поэтому вместо того, чтобы продолжать поэлементно сравнивать и совершать обмены-раскулачивания, можно просто сдвинуть вправо сразу весь остаток кластера. Смысл и результат тот же, действий меньше. Другая важная оптимизация, на которую обычно обращают внимание: при поиске значения нам не нужно идти от расчитанной стартовой позиции до конца кластера. Дойдя до значений, у которых стартовая позиция больше, чем у искомого, можно смело остановиться и сообщить о том, что требуемого значения в таблице нет. Это уменьшает среднее время поиска и делает поиск отсутствующих элементов значительно более быстрым.
Удаление. В варианте Linear Probing мы находим удаляемое значение и передвигаем на его место последнее значение из кластера, тем самым укорачивая его.
В варианте Robin Hood hashing делается иначе: найдя удаляемое значение, мы помечаем его ячейку как удаленную, но оставляем память о его хэше. Остается такой tombstone, где написано "здесь был Вася, его хэш был таким-то".
Делается это чтобы не нарушить упорядоченность стартовых позиций. Ведь если оставить ячейку, где было удаляемое значение, пустой, то там потом может оказаться значение, у которого стартовая позиция не меньше, чем у предшествующих, но больше, чем у значений справа от него, что сделает их ненаходимыми. И передвинуть на освободившееся место значение из конца кластера нельзя, опять нарушится упорядоченность. Можно, конечно, сдвинуть влево весь остаток кластера, и ряд блоггеров предлагали так делать, считая это "оптимизацией" (ведь это уменьшает среднее значение PSL и ускоряет поиск), но на практике от этого все делается только медленнее. Во-первых, само передвижение значений занимает порядочное время. А во-вторых, это сильно замедляет вставку. Ведь на самом деле при вставке мы сдвигаем вправо не весь остаток кластера, а лишь до первого могильного камня.
Каждый удаленный элемент с точки зрения вставки делит кластер на две части, делая его effectively вдвое меньше. Так что использование лишь пометок об удалении позволяет сделать и удаление и вставку существенно быстрее, чем при "่оптимизации" с backward shifting. Впрочем, это trade off между скоростью удаления/вставки и скоростью поиска, так что все зависит от сценариев использования.
Сделав свою реализацию и начав тестировать ее с разными типами и случайными значениями, обнаружил, что когда тип ключей - строка, все это работает чудовищно медленно. Сперва, конечно, подумал, что это вычисление хэша или сравнение строк тормозит, но нет, дело совсем в другом. На моих случайных строках использованная хэш-функция оказалась недостаточно равномерной, что привело к тому, что в таблице быстро образуются огромные кластеры. И поскольку сложность одной операции пропорциональна размеру кластера, то сложность n вставок росла как О(n^2). Для сравнения взял чужую готовую реализацию HashMap с Linear Probing (из проекта vibe.d), там эффект в точности тот же, на некоторых замерах выходит в 50 раз медленнее, чем вариант с separate chaining, используемый ассоциативными массивами в D. Для борьбы с этой бедой добавил у себя отслеживание максимального размера кластера при добавлении, и если он превосходит некоторый порог, то таблица удваивается, не дожидаясь, когда ее населенность достигнет обычного предела. Но много раз так удваивать тоже нельзя, а то всю память съест, поэтому еще один параметр ограничивает рост, чтобы размер таблицы был не больше чем во столько-то раз больше числа хранящихся значений.
Результаты замеров оказались неоднозначными. Где-то быстрее один метод, где-то другие. Вот табличка, время в миллисекундах. Там замеряны четыре реализации: Dивные ассоциативные массивы с chaining (связными списками для значений с одинаковой стартовой позицией), linear probing из vibe.d и два варианта моего Robin Hood: с хранением хэшей в отдельном массиве и с хранением их вместе с самими значениями. Хранить отдельно оказалось выгоднее в большинстве случаев. Для каждой пары типов ключ => значение там делались следующие замеры:
add_remove - составлялась программа действий, где чередовалось случайное количество добавлений одно за другим и случайное количество удалений случайных элементов, всего 400 000 действий, и эта программа действий исполнялась всеми реализациями хэшей. Т.е. они выполняли в точности одинаковые действия.
make_histo - для массива из 10 000 000 случайных элементов считалось число вхождений каждого значения, т.е. только добавления и обновления элементов, без удалений. Опять же, один и тот же массив для всех реализаций. Тип счетчика int.
read_histo - для того же массива из 10 000 000 элементов данные из посчитанной выше гистограммы извлекались для простой операции, т.е. тест чисто на чтение.
Каждый замер был сделан 10-20 раз, данные усреднены после выкидывания явно искаженных, где внезапно включался GC и лопатил большую кучу. Использованные для тестовых данных классы и структуры представлены в двух вариантах: с описанием своих ф-й toHash и сравнения, и без оных, с полаганием на дефолтные. Вот.
Когда таблица у нас большая, а значений мало, и хорошая хэш-функция их так хорошо рассредоточила, что каждое значение живет там, куда указывает хэш (на своей стартовой позиции), то все тривиально, и никакой разницы между этими алгоритмами не чувствуется. Интересные вещи начинаются, когда у нескольких разных значений стартовые позиции совпадают (а это начинает происходить очень быстро - см. birthday problem), тогда возникают кластеры - группы подряд идущих занятых ячеек в таблице. Для простоты возьмем утрированный случай, который однако позволяет получить нужную интуицию. Пусть при отображении хэшей на адреса в массиве у нас на отрезок от [0,100) приземлились 200 значений, а на [100,200) ни одного. Тогда в случае Linear Probing кластер будет выглядеть как-то так:
Тут немало значений, которым повезло оказаться на своей стартовой позиции, но хватает и таких, которые оказались очень далеко, к ним надо идти через весь кластер.
А в случае Robin Hood hashing будет выглядеть как-то так:
Богачей, сохранивших свое место, очень мало, но и через весь кластер ни к кому идти не придется, максимум половину кластера. Т.е. worst case тут получился в два раза лучше, а average - на четверть меньше. И тут видно главное свойство Robin Hood hashing, которое не сразу очевидно из типичного описания: все значения в таблице оказываются упорядочены по своим стартовым позициям. Ведь при вставке Робин Гуд всегда отдает место тому, кто беднее, т.е. значению, у которого путь от его стартовой позиции (PSL - path from starting location, он же DIB - distance from initial bucket, он же probe count) больше, т.е. значение с меньшей стартовой позицией вытесняет значение с большей, сдвигая его вправо. Такое понимание позволяет сделать оптимизацию: когда Робин Гуд выгоняет богача из его ячейки, у значений справа от него их стартовые позиции не меньше, чем у этого богача, поэтому вместо того, чтобы продолжать поэлементно сравнивать и совершать обмены-раскулачивания, можно просто сдвинуть вправо сразу весь остаток кластера. Смысл и результат тот же, действий меньше. Другая важная оптимизация, на которую обычно обращают внимание: при поиске значения нам не нужно идти от расчитанной стартовой позиции до конца кластера. Дойдя до значений, у которых стартовая позиция больше, чем у искомого, можно смело остановиться и сообщить о том, что требуемого значения в таблице нет. Это уменьшает среднее время поиска и делает поиск отсутствующих элементов значительно более быстрым.
Удаление. В варианте Linear Probing мы находим удаляемое значение и передвигаем на его место последнее значение из кластера, тем самым укорачивая его.
В варианте Robin Hood hashing делается иначе: найдя удаляемое значение, мы помечаем его ячейку как удаленную, но оставляем память о его хэше. Остается такой tombstone, где написано "здесь был Вася, его хэш был таким-то".
Делается это чтобы не нарушить упорядоченность стартовых позиций. Ведь если оставить ячейку, где было удаляемое значение, пустой, то там потом может оказаться значение, у которого стартовая позиция не меньше, чем у предшествующих, но больше, чем у значений справа от него, что сделает их ненаходимыми. И передвинуть на освободившееся место значение из конца кластера нельзя, опять нарушится упорядоченность. Можно, конечно, сдвинуть влево весь остаток кластера, и ряд блоггеров предлагали так делать, считая это "оптимизацией" (ведь это уменьшает среднее значение PSL и ускоряет поиск), но на практике от этого все делается только медленнее. Во-первых, само передвижение значений занимает порядочное время. А во-вторых, это сильно замедляет вставку. Ведь на самом деле при вставке мы сдвигаем вправо не весь остаток кластера, а лишь до первого могильного камня.
Каждый удаленный элемент с точки зрения вставки делит кластер на две части, делая его effectively вдвое меньше. Так что использование лишь пометок об удалении позволяет сделать и удаление и вставку существенно быстрее, чем при "่оптимизации" с backward shifting. Впрочем, это trade off между скоростью удаления/вставки и скоростью поиска, так что все зависит от сценариев использования.
Сделав свою реализацию и начав тестировать ее с разными типами и случайными значениями, обнаружил, что когда тип ключей - строка, все это работает чудовищно медленно. Сперва, конечно, подумал, что это вычисление хэша или сравнение строк тормозит, но нет, дело совсем в другом. На моих случайных строках использованная хэш-функция оказалась недостаточно равномерной, что привело к тому, что в таблице быстро образуются огромные кластеры. И поскольку сложность одной операции пропорциональна размеру кластера, то сложность n вставок росла как О(n^2). Для сравнения взял чужую готовую реализацию HashMap с Linear Probing (из проекта vibe.d), там эффект в точности тот же, на некоторых замерах выходит в 50 раз медленнее, чем вариант с separate chaining, используемый ассоциативными массивами в D. Для борьбы с этой бедой добавил у себя отслеживание максимального размера кластера при добавлении, и если он превосходит некоторый порог, то таблица удваивается, не дожидаясь, когда ее населенность достигнет обычного предела. Но много раз так удваивать тоже нельзя, а то всю память съест, поэтому еще один параметр ограничивает рост, чтобы размер таблицы был не больше чем во столько-то раз больше числа хранящихся значений.
Результаты замеров оказались неоднозначными. Где-то быстрее один метод, где-то другие. Вот табличка, время в миллисекундах. Там замеряны четыре реализации: Dивные ассоциативные массивы с chaining (связными списками для значений с одинаковой стартовой позицией), linear probing из vibe.d и два варианта моего Robin Hood: с хранением хэшей в отдельном массиве и с хранением их вместе с самими значениями. Хранить отдельно оказалось выгоднее в большинстве случаев. Для каждой пары типов ключ => значение там делались следующие замеры:
add_remove - составлялась программа действий, где чередовалось случайное количество добавлений одно за другим и случайное количество удалений случайных элементов, всего 400 000 действий, и эта программа действий исполнялась всеми реализациями хэшей. Т.е. они выполняли в точности одинаковые действия.
make_histo - для массива из 10 000 000 случайных элементов считалось число вхождений каждого значения, т.е. только добавления и обновления элементов, без удалений. Опять же, один и тот же массив для всех реализаций. Тип счетчика int.
read_histo - для того же массива из 10 000 000 элементов данные из посчитанной выше гистограммы извлекались для простой операции, т.е. тест чисто на чтение.
Каждый замер был сделан 10-20 раз, данные усреднены после выкидывания явно искаженных, где внезапно включался GC и лопатил большую кучу. Использованные для тестовых данных классы и структуры представлены в двух вариантах: с описанием своих ф-й toHash и сравнения, и без оных, с полаганием на дефолтные. Вот.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2014-06-25 02:47 pm (UTC)no subject
Date: 2014-06-25 03:32 pm (UTC)если элементы списков заранее выделены в виде пула
в том же куске памяти, где хэш живет?
Вроде и локальность сохраняется, и куску памяти
можно подрасти в случае необходимости, и вставка
всегда O(1). По памяти оверхед всего лишь
указатель на каждое значение.
no subject
Date: 2014-06-25 03:56 pm (UTC)no subject
Date: 2014-06-26 06:02 am (UTC)no subject
Date: 2014-06-25 04:42 pm (UTC)Я буду очень сильно удивлён, если хотя бы при некоторых параметрах этот робин будет быстрее.
Я бы и сам сделал, но высококвалифицированные open source разработчики, работающие над VisualD, не смогли даже написать тривиальную инструкцию "как это оп.сорсное говно установить на винду со всеми зависимостями, шоб заработало".
Да ещё требуют каких-то специальных привелегий, чтобы зарепортить им баг об этом.
Так что я только посмотрел на output "'dmd' is not recognized as an internal or external command, operable program or batch file. Building Release\robinhood.exe failed!", погуглил минут 15, и забил.
no subject
Date: 2014-06-25 04:48 pm (UTC)На CAtlMap посмотрю, только у меня из студий самая свежая - 2010, новее не стоит.
По-хорошему, сравнивать надо с плюсовыми реализациями Робин Гуда, их в интернетах имеется готовых.
http://sebastiansylvan.com/2013/05/08/robin-hood-hashing-should-be-your-default-hash-table-implementation/
http://codecapsule.com/2013/11/11/robin-hood-hashing/
Наверняка есть еще. Эти две страдают недо- и псевдо- оптимизациями.
no subject
Date: 2014-06-25 05:26 pm (UTC)Поставил dmd-2.063.2.exe - причём установщик VisualD даже у меня спрашивал, куда.
Не помогло.
Типичный open source подход к разработке: кто-то старался, пилил компилятор — а инсталлятор и интеграция в студию это же скучно и неинтересно.
Примерно поэтому в open source поделиях даже хорошие технические решения и неплохой по качеству код вполне может сочетаться с ужасающим качеством продуктом.
>На CAtlMap посмотрю
Это очень, очень эффективная реализация hash map. В разы быстрее тех stl, что мне попадались.
Там во-первых память локально выделяют, во-вторых ещё много трюков для оптимизации.
Например свойство "в большинстве случаев нахождение и извлечение значения требует загрузки ровно двух кэш-линий" тоже верно для CAtlMap, если нет злостных коллизий, и не запрещать автобалансироваться (первая линия элемент массива с корзинами, вторая линия нода с данными, там лежат и ключ и значение).
Единственный ньюанс — после добавления всех элементов желательно вызвать Rehash().
>самая свежая - 2010
Вполне OK: ATL-коллекции стали заруливать ещё в 2005-ой.
no subject
Date: 2014-06-25 05:40 pm (UTC)http://dlang.org/download.html
Когда DMD уже стоит, VisualD обычно сам его находит, у меня проблем с ним не было.
Про CAtlMap сейчас глянул в исходники, там separate chaining с кэшированием хэшей. Очень похоже на реализацию ассоц. массивов в D, с которой тут сравнивалось (только последняя вроде хэши не кэширует). Две кэш-линии в CAtlMap получится, если нужное значение было в его корзину положено последним. Если список длиннее 1 элемента и первый не искомый, то обращений к памяти уже больше нужно...
no subject
Date: 2014-06-25 07:14 pm (UTC)Так там ещё параметры по умолчанию правильно настроены.
Например если миллион элементов, то корзин у сбалансированного CAtlMap будет 1321139 штук (см.сорцы).
При таких условиях получается что пустых корзин в среднем 619756, остальные т.е. 701383 полные.
Вероятности разной наполняемости корзин мне пощитал какой-то калькулятор биномиального распределения в интернетах, вводил данные миллион trials, и 1/1321139 вероятность успеха.
То есть при условии годной хеш-функции, 70.13% всех элементов будут в своих корзинах или первыми в списке, или единственными.
no subject
Date: 2014-06-26 03:09 am (UTC)no subject
Date: 2014-06-26 09:19 am (UTC)Оказалось, в С++ я не могу просто написать
foreach(x; data) h[x]++;т.к. там при появлении нового значения оно не инициализируется нулем. Приходится возиться с Lookup и проверками.
Исходники:
https://gist.github.com/thedeemon/0c610024e2f04d5a7c24 - С++
https://gist.github.com/thedeemon/9fb6e9b29e5cd5bfd8b0 - D (сам тест)
С++ собрал в MSVC10 Release 32-bit, настройки дефолтные.
Убедился, что результаты совпадают.
Несколько раз позапускал, вариант с CAtlMap типично строит гистограмму за 2.19 с, читает за 1.19 с.
Вариант на D с Робин Гудом строит за 1.27 с, читает за 1.09 с.
Как минимум на этом тесте он быстрее. Но на строках или больших структурах наверняка будет медленнее.
no subject
Date: 2014-06-26 03:45 pm (UTC)В VS2012 можешь - раскомментированная строчка "h[ data[ i ] ]++;" компилируется и работает OK.
Странно что у тебя не так - документация про CAtlMap::operator [] для обоих версий гласит "If the key already exists, the element is replaced. If the key does not exist, a new element is added"
>Как минимум на этом тесте он быстрее
Ну конечно быстрее: ты забыл что я выше написал, после добавления всех элементов желательно вызвать Rehash()
Но если ты примерно знаешь сколько ожидается элементов, лучше сконструировать CAtlMap сразу нужного размера. Для этого замени строчку
CAtlMap<int, int> h;
например на
CAtlMap<int, int> h( 1664543, .75f, .25f, 2.25f, 1024 )
Ну как, кто теперь быстрее? :-)
no subject
Date: 2014-06-26 04:01 pm (UTC)С Rehash завтра попробую. Специально тюнить параметры не стану, интересно поведение структур как есть, без особых заточек на конкретные данные.
no subject
Date: 2014-06-26 04:45 pm (UTC)Да, точно - забыл уже, шо в С++ у интов конструкторов нет.
>Специально тюнить параметры не стану
Хотя бы последний параметр в конструкторе, nBlockSize, поменяй с 10 на что-то побольше, например 1024 - это число нод в одном куске памяти с данными который он выделяет когда растёт, для 10M твоих крошечных элементов с двумя интами в каждом значение по умолчанию "10" это неадекватно мало.
no subject
Date: 2014-06-27 05:53 am (UTC)CAtlMap: 2.37 построение, 0.92 чтение
После добавления указанных параметров в конструкторе:
1.76 построение, 0.92 чтение.
Робин Гуду сказал, чтобы сразу миллион элементов мог вместить (там в конструкторе есть опциональный параметр), время построения почему-то не изменилось, зато чтение чуть ускорилось до 1.06 с.
Итого, после настроек и рехеша CAtlMap ищет быстрее, но строится все еще медленнее.
no subject
Date: 2014-06-25 09:10 pm (UTC)На Робин Гуда есть похожая идея: Cookoo hashing.
no subject
Date: 2014-06-26 03:12 am (UTC)no subject
Date: 2014-06-26 04:04 am (UTC)no subject
Date: 2014-06-26 04:57 am (UTC)