Google выложил под свободной лицензией новое семейство хеш-функций CityHash для строк. Пока представлены функции CityHash64 и CityHash128 для получения 64- и 128-битных хеш-кодов.
Как сообщают разработчики, в реальных условиях CityHash64 превосходит по скорости аналогичные хеш-функции как минимум на 30%.
В силу своей простоты данные хеш-функции не подходят для криптографических применений, но теоретически это идеальный вариант для хеш-таблиц. Правда, код пока сыроват, недостаточно оттестирован (см. warning) и нуждается в некоторой доработке.
CityHash128 оптимизирован для строк хотя бы в несколько сотен байт и при достаточной длине строк обгоняет по скорости CityHash64. На малых строках он медленнее. Внутри Google его применяют в тех случаях, когда нужно минимизировать количество коллизий.
Хотя функции пытались оптимизировать для процессоров, которые стоят в дата-центрах Google, но оказалось, что они очень быстро работают на большинстве ПК и ноутбуков. Поддерживается работа с 64-битными регистрами, параллелизм на уровне инструкций и быстрый доступ к невыровненным данным в памяти.
Традиционно главное преимущество разработок Google — производительность. И здесь тоже это поставили первым приоритетом. Хеш-функция CityHash сделана на основе известных разработок, а основным образцом стала MurmurHash, созданная Остином Апплеби в 2008 году. Это простая и быстрая хэш-функция общего назначения, не являющаяся криптографически безопасной. Все её варианты находятся в свободном пользовании.
Главное достоинство подхода Google — большинство шагов содержат как минимум два независимых математических действия. Как выяснилось, современные CPU лучше справляются с кодом такого рода.
Обратная сторона медали — код становится сложнее, чем в других популярных хеш-функциях. Но разработчики решили оптимизировать его для производительности, а не для простоты, и даже добавили специальный варианты исполнения функции для коротких строк входных данных.
Странно, что разработчики не показали конкретных бенчмарков, если заявляют скорость главным преимуществом своей хеш-функции. Вот производительность некоторых популярных хеш-функций с сайта Остина Апплеби (он же разработал программу SMHasher для тестирования скорости хеш-функций):
Как сообщают разработчики, в реальных условиях 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