elizarov


Блог Романа Елизарова


Previous Entry Share Next Entry
Распределение нагрузки имеет значение или быстрый хеш часть 3
elizarov

В предыдущей части я показал простейшую реализацию хеш-таблицы, которая занимает в разы меньше памяти, чем другие реализации, и обгоняет их по производительности. Отрыв в производительности заметный (20%), но не потрясающий воображение. Для того чтобы понять почему это происходит надо обратиться к исходной постановке задачи. Для максимально реалистичного моделирования нагрузки, запрашиваемые идентификаторы распределены геометрически так, что в определенном диапазоне целых чисел все они запрашиваются достаточно часто, а при удалении от него вероятность запроса уменьшается. Как я сейчас покажу, в этой задаче именно это распределение имеет существенное значение.

Дело в том, что Trove, который показал наибольшую производительность среди готовых решений, для первого места расположения элемента в таблице не применяет никакое дополнительное хеширование идентификатора, а просто берет его по модулю размера своей хеш-таблицы. Большая часть элементов располагается именно в том месте, которое выбрано первым (коллизии происходят не часто), а значит соседние идентификаторы с большой вероятностью будут располагаться в соседних элементах хеш-таблицы. В моей постановке задачи все наиболее часто запрашиваемые идентификаторы будут соседями в такой хеш-таблице. С большой вероятностью содержащие их страницы памяти будут в кэше процессора во время обработки всей последовательности обращений и именно они, наиболее часто запрашиваемые, будут обрабатываться быстрей всего.

Любопытно что high-scale-lib использует такую же стратегию для выбора первого места расположения элемента в своей таблице. Однако, high-scale-lib использует линейное исследование. Это серьезная ошибка. Линейное исследование можно использовать только если индексы очень хорошо размазаны по таблице, иначе наборы элементов с последовательными идентификаторами будут занимать соседние ячейки памяти и образовывать диапазон полностью занятых ячеек. Для любого другого элемента, случайно попавший в такой диапазон, придется очень долго подыскивать свободную ячейку с помощью линейного исследования. В своей реализации с линейным исследованием я избегаю такой проблемы размазывая элементы с помощью умножения на магическое число. high-scale-lib подсчитывает количество операций, которые требуется сделать при вставке элемента, и увеличивает размер таблицы если это число превосходит некий порог. Тем самым он потребляет больше памяти чем можно было бы и работает медленней. Линейное исследование можно использовать только если хеш-функция равномерно размазывает элементы по хеш-таблице.

При использовании двойного хеширования такой проблемы нет. Однако, нужно иметь вторую хеш-функцию, которая независима от первой, для определения шага с котором в таблице будет проводиться поиск свободной ячейки при коллизии. И шаг этого поиска должен быть взяимнопростым с размером таблицы. В общем, нужен набор специально подобранных простых чисел для использования их в качестве размера таблицы, да так, чтобы число на два меньшее размера таблицы тоже было простым. Тогда первая хеш-функция это идентификатор по модулю размера таблицы, а вторая — это один плюс идентификатор по модулю размера минус два (более подробно об этом также можно почитать у Кнута). В Trove реализовано двойное хеширование в котором это всё есть. Я сделал аналогичную реализацию в классе FastHash2 с таким вот методом поиска элемента:

    private int hash(long id) { 
        return ((int)id ^ (int)(id >>> 32)) & 0x7fffffff; 
    } 
 
    private int index0(int hash, int length) { 
        return hash % length; 
    } 
 
    private int step(int hash, int length) { 
        return 1 + (hash % (length - 2)); 
    } 
 
    public Order getById(long id) { 
        int hash = hash(id); 
        int index = index0(hash, a.length); 
        Order obj = a[index]; 
        if (obj == null || obj.getId() == id) 
            return obj; 
        int step = step(hash, a.length); 
        while ((obj = a[index = next(index, step, a.length)]) != null) { 
            if (obj.getId() == id) 
                return obj; 
        } 
        return null; 
    }

Для определения размеров таблицы я взял таблицу простых чисел из GNU Trove. В этом образовательном проекте GPL мне не помеха. Но даже при этом кода пришлось написать заметно больше.

Интересно посмотреть не только на скорость этого кода при таком же распределении идентификаторов. Интересно посмотреть что станет с производительностью, если перемешать идентификаторы заявок так, чтобы наиболее часто запрашиваемые идентификаторы были случайными. Такое происходит в реальности если с помощью хеш-таблицы кэшировать какие-нибудь словари. Например, наши торговые системы работают с большим количеством финансовых инструментов. Идентификаторы наиболее часто запрашиваемых инструментов не связанны между собой. Для тестирования такого распределения я добавил в тестовую программу параметр scramble, чтобы можно было указать в командной строке -Dscramble=true для перемешивания идентификаторов.

Сводная таблица результатов представлена ниже:

Реализация Описание Скорость (нс на операцию)
Исходная последовательность
Скорость (нс на операцию)
Перемешанные идентификаторы
HashMapCache на основе java.util.HashMap из JDK 7 216 ± 30 253 ± 25
GuavaCache на основе com.google.common.cache.CacheBuilder из Google Guava версии 12 459 ± 37 463 ± 37
HighScaleCache на основе org.cliffc.high_scale_lib.NonBlockingHashMapLong из high-scale-lib Клифа Клика 143 ± 1 163 ± 1
TroveCache на основе gnu.trove.map.hash.TLongObjectHashMap из Trove версии 3.0.2 101 ± 1 136 ± 1
JavolutionCache на основе javolution.util.FastMap из Javolution версии 5.4.2 508 ± 26 533 ± 24
HppcCache на основе com.carrotsearch.hppc.LongObjectOpenHashMap из HPPC версии 0.4.1 160 ± 3 158 ± 2
FastCache один массив, открытая адресация, линейное исследование, хеш умножением 83 ± 1 101 ± 1
FastCache2 один массив, открытая адресация, двойное хеширование, хеш делением 68 ± 1 113 ± 1

Как и ожидалось, двойное хеширование показывает небольшое преимущество в скорости из-за особенностей распределения запросов, которое пропадает при перемешивании.

UPDATE: Анализ эффекта перемешивания в следующей части.


  • 1
К слову код Trove (TLongHash) эквивалентен приведенному за вычетом массива состояний и массива ключей, без которых трудно использовать Trove as general purpose hash table.

Конечно. Дональд Кнут один на всех :) Я и не претендую на откытие нового алгоритма хеширования, а лишь показываю как правильно выбирать и реализовывать наиболее подходящий. Причем, двойное хеширование, как в Trove, дает преимущество только в специфических случаях, а кода сильно больше, чем в существенно более простой реализации с линейным исследованием.

Одна из ключевых мыслей моего доклада была в том, что general purpose всегда медленней чем специализированный код. Поэтому для написания быстрого кода надо хорошо ориентироваться в алгоритмах. В горячих точках кода всегда приходится писать специализированный код. А там где производительность не важна и какие-то особенные библиотеки типа Trove не нужны.

Да, но факт специализации посредством отрезания части функционала хэш таблиц требует упоминания. Или нужно сравнивать одинаковые по возможностям реализации.

Я так и не понял ваше замечание про "отрезанный функционал" (в этом весь и смысл специализированной реализации!), но раз вам интересно именно удаление (и лень самому прочитать Кнута ;), то в одной из ближайших заметок я покажу как просто и элегантно пишется метод для удаления элемента из хеш-таблицы с линейным исследованием. Это будет хорошей и наглядной иллюстрацией, которая дает дополнительное объяснение почему именно этот алгоритм является первым выбором программиста при реализации быстрых хеш-таблиц.

У меня сложилось впечатление от последних постов, что происходит специализация кода исключительно по типу элемента коллекции. Факт того, что в вашей задаче удаление в хэше не нужно (и его нет в коде) оказался несколько неочевиден, особенно на фоне сравнения с Trove, в котором реализация удаления небесплатна (http://elizarov.livejournal.com/25616.html?thread=271632#t271632).
ЗЫ И я часто смотрю на код Trove в районе добавления, поиска, удаления :)

Не смотрите на один Trove, если вам там что-то кажется не очевидным. Не надо слепо копировать их дизайн структур данных. Читайте Кнута. Там всё написано в том числе про удаление. Читайте high-scale-lib, java.util.IdentityHashMap и другие реализации. А главное - используйте свою собственную голову. Думайте, изучайте, выбирайте, применяйте. Это самое важное.

Рома, попробуй, пожалуйста, поменять в FastCache2
private Order[] a = new Order[7];
на
private Order[] a = new Order[13];


Edited at 2012-05-18 07:54 am (UTC)

Попробую. А на что это должно повлиять?

У тебя рабочий диапазон заполнения - 1/3-2/3.
При последовательности NextPrime(2*N), начинающейся с 7, ты имеешь дробную часть двоичного логарифма размера кеша 0.42. При 13 - 0.06. То есть, должно получится сравнение кешей FastCache и FastCache2 с близким размером и уровнем заполнения, а не "в противофазе", как у тебя сейчас. Собственно - речь о зависимости среднего времени доступа от уровня заполнения кеша. При его вариации от 1/3 до 2/3 (и исследовании отклонений по скорости ~20%) этим не стоит пренебрегать. Для чистоты эксперимента можно сделать NextPrime от степени двойки.

/add - и ты не думал о пресайзе для кешей?
У тебя при ресайзе - порядок, в котором элементы идут в новый массив - не зависит от их частоты. С другой стороны, наиболее частые элементы должны быть уже в старом массиве. Ну и ... 1/6 элементов старого массива, независимо от их частоты, не попадет в первую ячейку. Вместо пресайза можно заменить удвоение учетверением (и снизить коллизии до более приемлемого уровня 1/24). Ну или сменить рабочий диапазон заполненности с 1/3-2/3 на 1/6-1/3.

Edited at 2012-05-18 09:30 am (UTC)

Думал о пресайзе и пробовал с ним. Его включение существенно меняет статистику именно из-за описанного тобой эффекта. Например, FastHash написан именно так как написан (rehash идет в обратную сторону по массиву как и поиск элемента), чтобы максимально сохранять порядок. Даже изменение там порядка прохода заметно влияет на производительность. Я как-нибудь отдельно про это подрбобно напишу.

Однако, для большей честности я решил опубликовать сравнение разных реализаций без пресайза. Ну и еще из-за того, что на практике обычно они используются без пресайза, поэтому сравнение получается более приближенным к реальности.

Гм-м-м.

>Например, FastHash написан именно так как написан (rehash идет в обратную сторону по массиву как и поиск элемента), чтобы максимально сохранять порядок. Даже изменение там порядка прохода заметно влияет на производительность. Я как-нибудь отдельно про это подрбобно напишу.

И при этом скремблирование практически не влияет на скорость работы FastCache?
Не вяжется.

(сначала промазал мимо ветки)

А в нем есть встроенное скрэмблирование умножением. Внутри он всегда работает с достаточно равномерным распределением идентификаторов.

Нда... увидел, наконец. Я туплю, ты слегка мошенничаешь :)

Стабильность FastCache обеспечивается тем, что хеш-функция на размере N может быть вычислена на основании хеш-функции на размере 2N, и вследствие этого и порядка прохода ресайз гарантированно не увеличивает порядковый номер ячейки в списке попыток.

В свою очередь, хеш-функции FastCache2 не обладают подобным свойством, и при ресайзе происходят все те несчастья, о которых я писал.

Вывод: нужен FastCache3 - два хеша умножением, первый - длины P, второй - длины P-1, инкремент номера ячейки - (hash2<<1)+1. И, для иллюстрации, FastCache4 - хэш делением с линейным поиском :) Ну и это, вариации рабочего диапазона заполнения очень интересуют.

Edited at 2012-05-20 10:16 am (UTC)

Роман, добрый день.
Не очень ясна вот эта фраза

Большая часть элементов располагается именно в том месте, которое выбрано первым (коллизии происходят не часто), а значит соседние идентификаторы с большой вероятностью будут располагаться в соседних элементах хеш-таблицы. В моей постановке задачи все наиболее часто запрашиваемые идентификаторы будут соседями в такой хеш-таблице.

Получается, что и у Трове и у Вас элементы являются соседями, так в чем же разница? И все-таки не очень понятно, почему в вашей реализации наиболее запрашиваемые значения будут в кеше процессора, а у Трове - нет. Это как-то связано с open addressing реализацией, которую вы используете?

Edited at 2012-10-31 05:06 am (UTC)

В моей реализации используется линейное исследование. В случае коллизии мы смотрим в соседний элемент, который уже в кэше.

  • 1
?

Log in

No account? Create an account