Семейство хеш-функций CityHash от Google

    Google выложил под свободной лицензией новое семейство хеш-функций CityHash для строк. Пока представлены функции CityHash64 и CityHash128 для получения 64- и 128-битных хеш-кодов.

    Как сообщают разработчики, в реальных условиях CityHash64 превосходит по скорости аналогичные хеш-функции как минимум на 30%.

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

    CityHash128 оптимизирован для строк хотя бы в несколько сотен байт и при достаточной длине строк обгоняет по скорости CityHash64. На малых строках он медленнее. Внутри Google его применяют в тех случаях, когда нужно минимизировать количество коллизий.

    Хотя функции пытались оптимизировать для процессоров, которые стоят в дата-центрах Google, но оказалось, что они очень быстро работают на большинстве ПК и ноутбуков. Поддерживается работа с 64-битными регистрами, параллелизм на уровне инструкций и быстрый доступ к невыровненным данным в памяти.

    Традиционно главное преимущество разработок Google — производительность. И здесь тоже это поставили первым приоритетом. Хеш-функция CityHash сделана на основе известных разработок, а основным образцом стала MurmurHash, созданная Остином Апплеби в 2008 году. Это простая и быстрая хэш-функция общего назначения, не являющаяся криптографически безопасной. Все её варианты находятся в свободном пользовании.

    Главное достоинство подхода Google — большинство шагов содержат как минимум два независимых математических действия. Как выяснилось, современные CPU лучше справляются с кодом такого рода.

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

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

    OneAtATime - 354.163715 mb/sec
    FNV - 443.668038 mb/sec
    SuperFastHash - 985.335173 mb/sec
    lookup3 - 988.080652 mb/sec
    MurmurHash 1.0 - 1363.293480 mb/sec
    MurmurHash 2.0 - 2056.885653 mb/sec
    
    Поддержать автора
    Поделиться публикацией

    Комментарии 15

      +4
      А почему некриптографические хеш-функции находятся в разделе Криптография?
        +4
        Да, логично. Перенёс в «Алогритмы».
        +3
        Дополнительно нужно отметить, что в оригинальном (32-битном) алгоритме murmur2 есть слабые места, которые на некоторых специфичных тестовых наборах данных генерируют ~98% коллизий (!) Об этом я упоминал в Q&A — habrahabr.ru/qa/2148/
        Проверкой 64 битного алгоритма на наличие подобных артефактов, на моей памяти, никто не занимался.

        А так, конечно интересно посмотреть на живые тесты. Заявленные 30% форы звучат внушительно.
          +3
          MurmurHash3 еще быстрее, чем функция Google (проверил). Примерно в 2 раза на Core i7. Для 128-битной функции.
            +1
            Резалты в студию! (не то что бы не верю, но хочется внимательно посмотреть)
              0
              Проверял с помощью SMHasher, вот фрагмет лога для City128:

              Bulk speed test — 262144-byte keys
              Alignment 0 — 0.567 bytes/cycle — 1623.12 MiB/sec @ 3 ghz
              Alignment 1 — 0.560 bytes/cycle — 1600.99 MiB/sec @ 3 ghz
              Alignment 2 — 0.560 bytes/cycle — 1600.96 MiB/sec @ 3 ghz
              Alignment 3 — 0.560 bytes/cycle — 1600.96 MiB/sec @ 3 ghz
              Alignment 4 — 0.566 bytes/cycle — 1620.21 MiB/sec @ 3 ghz
              Alignment 5 — 0.555 bytes/cycle — 1587.87 MiB/sec @ 3 ghz
              Alignment 6 — 0.555 bytes/cycle — 1587.86 MiB/sec @ 3 ghz
              Alignment 7 — 0.555 bytes/cycle — 1587.87 MiB/sec @ 3 ghz

              А вот для Murmur 3 128-битного:

              Bulk speed test — 262144-byte keys
              Alignment 0 — 1.152 bytes/cycle — 3296.05 MiB/sec @ 3 ghz
              Alignment 1 — 1.133 bytes/cycle — 3242.34 MiB/sec @ 3 ghz
              Alignment 2 — 1.133 bytes/cycle — 3242.36 MiB/sec @ 3 ghz
              Alignment 3 — 1.117 bytes/cycle — 3197.15 MiB/sec @ 3 ghz
              Alignment 4 — 1.132 bytes/cycle — 3237.31 MiB/sec @ 3 ghz
              Alignment 5 — 1.114 bytes/cycle — 3187.78 MiB/sec @ 3 ghz
              Alignment 6 — 1.115 bytes/cycle — 3188.94 MiB/sec @ 3 ghz
              Alignment 7 — 1.131 bytes/cycle — 3234.62 MiB/sec @ 3 ghz

              Не исключаю, что дело в тесте от автора Murmur Hash, :) или в настройках компилятора, например — я просто собрал готовый проект в default настройках, ничего не трогая.
                0
                Это какая железка? Подозреваю на i7 разница была бы менее впечатляющей.
                  0
                  i7 950, 3.06 GHz, DDR3 (1600), собрал с помощью MSVC ничего не меняя в проекте (как скачал с сайта).
                    0
                    Хмм, а вот я протестировал на Core(TM) i5-750 @ 2.67GHz (linux 64 bit)
                    Сити64 (у 128 прмерно такиеже результаты), гораздо интереснее циферки:

                    Bulk speed test — 262144-byte keys
                    Alignment 0 — 3.903 bytes/cycle — 11165.29 MiB/sec @ 3 ghz
                    Alignment 1 — 3.846 bytes/cycle — 11002.34 MiB/sec @ 3 ghz
                    Alignment 2 — 3.845 bytes/cycle — 11001.87 MiB/sec @ 3 ghz
                    Alignment 3 — 3.845 bytes/cycle — 10999.91 MiB/sec @ 3 ghz
                    Alignment 4 — 3.845 bytes/cycle — 11000.40 MiB/sec @ 3 ghz
                    Alignment 5 — 3.846 bytes/cycle — 11003.00 MiB/sec @ 3 ghz
                    Alignment 6 — 3.845 bytes/cycle — 11001.09 MiB/sec @ 3 ghz
                    Alignment 7 — 3.845 bytes/cycle — 11001.91 MiB/sec @ 3 ghz

                    почти в 4 раза быстрее мурмура 32:
                    Bulk speed test — 262144-byte keys
                    Alignment 0 — 0.971 bytes/cycle — 2777.37 MiB/sec @ 3 ghz
                    Alignment 1 — 0.952 bytes/cycle — 2723.14 MiB/sec @ 3 ghz
                    Alignment 2 — 0.952 bytes/cycle — 2723.97 MiB/sec @ 3 ghz
                    Alignment 3 — 0.952 bytes/cycle — 2723.86 MiB/sec @ 3 ghz
                    Alignment 4 — 0.969 bytes/cycle — 2772.17 MiB/sec @ 3 ghz
                    Alignment 5 — 0.952 bytes/cycle — 2724.62 MiB/sec @ 3 ghz
                    Alignment 6 — 0.952 bytes/cycle — 2724.31 MiB/sec @ 3 ghz
                    Alignment 7 — 0.952 bytes/cycle — 2724.31 MiB/sec @ 3 ghz

                    и почти в двое быстрее мурмур 128 для 64битных платформ
                    Bulk speed test — 262144-byte keys
                    Alignment 0 — 2.483 bytes/cycle — 7104.41 MiB/sec @ 3 ghz
                    Alignment 1 — 2.453 bytes/cycle — 7018.73 MiB/sec @ 3 ghz
                    Alignment 2 — 2.453 bytes/cycle — 7019.24 MiB/sec @ 3 ghz
                    Alignment 3 — 2.453 bytes/cycle — 7018.96 MiB/sec @ 3 ghz
                    Alignment 4 — 2.454 bytes/cycle — 7019.90 MiB/sec @ 3 ghz
                    Alignment 5 — 2.454 bytes/cycle — 7020.06 MiB/sec @ 3 ghz
                    Alignment 6 — 2.454 bytes/cycle — 7020.17 MiB/sec @ 3 ghz
                    Alignment 7 — 2.454 bytes/cycle — 7020.13 MiB/sec @ 3 ghz

                      0
                      да, мурмур3 в обоих случаях.
                        0
                        Да, все еще интересней — я пересобрал тот же тест 64-битным копилятором поднастроив его:

                        City128:

                        Alignment 0 — 3.594 bytes/cycle — 10282.50 MiB/sec @ 3 ghz
                        Alignment 1 — 3.537 bytes/cycle — 10120.43 MiB/sec @ 3 ghz
                        Alignment 2 — 3.623 bytes/cycle — 10365.75 MiB/sec @ 3 ghz
                        Alignment 3 — 3.623 bytes/cycle — 10365.43 MiB/sec @ 3 ghz
                        Alignment 4 — 3.622 bytes/cycle — 10362.77 MiB/sec @ 3 ghz
                        Alignment 5 — 3.624 bytes/cycle — 10367.87 MiB/sec @ 3 ghz
                        Alignment 6 — 3.624 bytes/cycle — 10368.20 MiB/sec @ 3 ghz
                        Alignment 7 — 3.539 bytes/cycle — 10125.30 MiB/sec @ 3 ghz

                        Murmur 3 (128):

                        Alignment 0 — 2.281 bytes/cycle — 6525.46 MiB/sec @ 3 ghz
                        Alignment 1 — 2.262 bytes/cycle — 6470.77 MiB/sec @ 3 ghz
                        Alignment 2 — 2.262 bytes/cycle — 6470.83 MiB/sec @ 3 ghz
                        Alignment 3 — 2.215 bytes/cycle — 6337.93 MiB/sec @ 3 ghz
                        Alignment 4 — 2.184 bytes/cycle — 6247.14 MiB/sec @ 3 ghz
                        Alignment 5 — 2.208 bytes/cycle — 6318.09 MiB/sec @ 3 ghz
                        Alignment 6 — 2.261 bytes/cycle — 6470.01 MiB/sec @ 3 ghz
                        Alignment 7 — 2.262 bytes/cycle — 6470.33 MiB/sec @ 3 ghz

                        Но на коротких ключах все наоборот:

                        City128:

                        Small key speed test — 1-byte keys — 69.88 cycles/hash
                        Small key speed test — 2-byte keys — 69.83 cycles/hash
                        Small key speed test — 3-byte keys — 70.53 cycles/hash

                        Small key speed test — 30-byte keys — 89.85 cycles/hash
                        Small key speed test — 31-byte keys — 91.82 cycles/hash

                        Murmur 3 (128):

                        Small key speed test — 1-byte keys — 41.44 cycles/hash
                        Small key speed test — 2-byte keys — 41.15 cycles/hash
                        Small key speed test — 3-byte keys — 43.07 cycles/hash

                        Small key speed test — 30-byte keys — 60.53 cycles/hash
                        Small key speed test — 31-byte keys — 63.17 cycles/hash
                          0
                          почемуж наоборот, на коротких ключах сити во столько же раз быстрее :)
                            0
                            Там же чем меньше циклов, тем быстее — но видно, что с ростом длины преимущество снижается. Короче говоря функция Google заточена под большие блоки.
                              0
                              А, блин, в последнем бенчмарке самая правая колонка это циклы, а не мибы как в прошлых комментах
              +1
              >> Правда, код пока сыроват, недостаточно оттестирован
              А также собирает информацию о программистах, использующих его :)

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

              Самое читаемое