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

[Ventura]

А почему некриптографические хеш-функции находятся в разделе Криптография?

[alizar]

Да, логично. Перенёс в «Алогритмы».

[Ghostwriter]

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

А так, конечно интересно посмотреть на живые тесты. Заявленные 30% форы звучат внушительно.

[sysprg]

MurmurHash3 еще быстрее, чем функция Google (проверил). Примерно в 2 раза на Core i7. Для 128-битной функции.

[xiWera]

Резалты в студию! (не то что бы не верю, но хочется внимательно посмотреть)

[sysprg]

Проверял с помощью 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 настройках, ничего не трогая.

[xiWera]

Это какая железка? Подозреваю на i7 разница была бы менее впечатляющей.

[sysprg]

i7 950, 3.06 GHz, DDR3 (1600), собрал с помощью MSVC ничего не меняя в проекте (как скачал с сайта).

[xiWera]

Хмм, а вот я протестировал на 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

[xiWera]

да, мурмур3 в обоих случаях.

[sysprg]

Да, все еще интересней — я пересобрал тот же тест 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

[xiWera]

почемуж наоборот, на коротких ключах сити во столько же раз быстрее :)

[sysprg]

Там же чем меньше циклов, тем быстее — но видно, что с ростом длины преимущество снижается. Короче говоря функция Google заточена под большие блоки.

[xiWera]

А, блин, в последнем бенчмарке самая правая колонка это циклы, а не мибы как в прошлых комментах

[afi]

>> Правда, код пока сыроват, недостаточно оттестирован
А также собирает информацию о программистах, использующих его :)