?

Log in

No account? Create an account

elizarov


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


Previous Entry Share Next Entry
Пишем самый быстрый хеш для кэширования данных: Часть 2
elizarov

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

Про хеш-таблицы очень хорошо написано в третьем томе "Искусство программирования" Дональда Кнута. Секрет в том, что читая сравнения производительности различных методов надо обращать внимание на сравнения в случае реализации хеш-таблиц на внешней памяти, ибо память это новый диск. Все три самых быстрых реализации из протестированных мной (high-scale-lib, Trove, HPPC) не только работают с примитивным типом long, но и реализуют алгоритм хеш-таблиц с открытой адресацией. Он наиболее компактный по памяти. Однако, обогнать их всех не сложно, отказавшись от отдельного хранения ключа, а храня только массив объектов Order. Таким образом, я радикально снижаю потребление памяти, по сравнению со всеми остальными реализациями. Тем самым открывается путь к максимальной скорости с правильным алгоритмом.

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

    private int hash(long id) { 
        return (((int)id ^ (int)(id >>> 32)) * MAGIC) >>> shift; 
    } 

    public Order getById(long id) { 
        int index = hash(id); 
        Order obj; 
        while ((obj = a[index]) != null) { 
            if (obj.getId() == id) 
                return obj; 
            if (index == 0) 
                index = a.length; 
            index--; 
        } 
        return null; 
    } 

Результаты сравнения производительности (а заодно и объем занимаемой памяти, как бонус), указаны в таблице ниже:

Реализация Описание Скорость (нс на операцию) Занимая память
HashMapCache на основе java.util.HashMap из JDK 7 216 ± 30 46 MB
GuavaCache на основе com.google.common.cache.CacheBuilder из Google Guava версии 12 459 ± 37 68 MB
HighScaleCache на основе org.cliffc.high_scale_lib.NonBlockingHashMapLong из high-scale-lib Клифа Клика 143 ± 1 50 MB
TroveCache на основе gnu.trove.map.hash.TLongObjectHashMap из Trove версии 3.0.2 101 ± 1 43 MB
JavolutionCache на основе javolution.util.FastMap из Javolution версии 5.4.2 508 ± 26 67 MB
HppcCache на основе com.carrotsearch.hppc.LongObjectOpenHashMap из HPPC версии 0.4.1 156 ± 1 27 MB
FastCache один массив, открытая адресация, линейное исследование, хеш умножением 83 ± 1 8 MB

Неубедительный отрыв по скорости, несмотря на значительное преимущество по потребляемой памяти. Почему так и что с этим делать — я рассказал на конференции. Читателями моего блога я подробней расскажу об этом отдельно.

UPDATE: Более подробно про тонкости со скоростью работы я написал в следующей заметке.


  • 1
https://github.com/elizarov/fasthash/blob/master/src/fasthash/impl/FastCache.java#L43

Могу ошибаться, но в такой ситуации быстрее будет идти вверх и как index использовать выражение (index % size) или (index & (size - 1)) если size - степень двойки.

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

Измерить можно испортив хеш =)

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

Если нужна оптимизация на уровне отдельных тактов, то их можно грубо по ассемблерному коду посмотреть (мой варианты выглядит быстрей) а для пущей точности каким-нибудь VTune измерить такты потребляемые именно этими инструкциями кода.

А как лучше брать хеш, когда нужно использовать объекты в роли ключей ? В голову сразу лезет идея брать ключем Object#hashCode() и его хешировать, но есть ли более оптимальный способ ?

Object.hashCode для того и сделан, чтобы брать. Зачем что-то еще? Всё будет зависеть от качества реализации метода hashCode у вашего класса. Если вы используете свои классы, то всё в ваших руках.

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

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

Вы хотите увидеть код для удаления элемента?

Стоимость по времени и памяти в первую очередь

А какая вам разница какая скорость удаления? И как у него может быть эффект по памяти? Это же дополнительный метод на той же структуре данных.

Конечно речь идет про скорость поиска/добавления элементов.
Поясню на примере, в Трове поддержка удаления требует дополнительного массива состояний слотов, которые читаются при добавлении и поиске элементов => без поддержки удаления от него можно избавиться и добавление/поиск элементов (!) станет работать быстрее.

Edited at 2012-05-16 09:08 am (UTC)

Я могу предположить что в Трове массив состояний нужен для упрощения геренерации общего кода для всех пар типов по одному шаблону. Ведь в никакой конкретной реализации массив состояний слотов не нужен. Кроме Trove такой подход больше нигде не используется, ибо это лишний расход памяти. Я при линейном исследовании вообще удаление реализуется вообще без всяких специальных признаков. Я покажу оба способа удаления.

Массив состояний нужен для примитивных ключей / значений, для случая объектных значений без него можно обойтись tombstone.
С удовольствием посмотрю на новые способы :)

Да нет никаких новых способов. Всё давно избретено. Посмотрите как это делают другие. Всегда можно одно значение выделить в отдельную переменную, если нужно поддерживать всё множество примитивов. А для объектов естественно нужно использовать tombstone.

Нетривиальный случай это когда и ключ и значение примитивы и надо поддерживать всё множество значений. К счастью, такое на практике никому не нужно, но для поддержки такого случая Trove решил хранить массив состояний. Ну а дальше имея молоток, все проблемы кажутся гвоздями. Ради универсальности они так же делают и long-Object и Object-Object. А это уже далеко от наиболее эффективного подхода.

Да, эту "универсальную" особенность (для Object значений) Trove я открыл для себя в процессе обсуждения :).

  • 1