Что это ещё за проприетарное ненужно? Где LICENSE файл?

PS: коль лицензия не указана, значит «ональная EULA».

лицензия не указана

Лицензия указана, zlib. Файл с кодом открой.

git clone https://github.com/leo-yuriev/t1ha.git
cd t1ha
git checkout smhasher-rurban.t1ha
cmake .

А где сам cmake?

И где main()?

git checkout smhasher-rurban.t1ha

http://wstaw.org/m/2016/11/18/Screenshot_20161118_071823.png

При запуске любых бенчмарков/тестов:

Program received signal SIGILL, Illegal instruction. 0x0000000000458aa8 in falkhash.continue ()

Чёт странно, судя по cat /proc/cpuinfo, sse4.2 у меня есть:

model name: Intel(R) Core(TM) i3 CPU       M 370  @ 2.40GHz
flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf pni dtes64 monitor ds_cpl vmx est tm2 ssse3 cx16 xtpr pdcm pcid sse4_1 sse4_2 popcnt lahf_lm arat dtherm tpr_shadow vnmi flexpriority ept vpid

При запуске любых бенчмарков/тестов:

Program received signal SIGILL, Illegal instruction. > 0x0000000000458aa8 in falkhash.continue ()

Чёт странно, судя по cat /proc/cpuinfo, sse4.2 у меня есть

cat /proc/cpuinfo | grep aes

?

давно не мерялись хэш-функциями

Ты давай равномерностью сперва померяйся.

В коде солянка из крестов и GNU99
Not suitable for cryptography

Но зачем тогда?

#if !defined(__GNUC__) || (__GNUC__ < 4)
#error Sorry, t1ha requires modern GCC compiler (gcc 4.2 or compatible).
#endif

gcc-only хэш-функция? гм

Или это из-за диапазонов в case?

case sizeof(uint64_t) * 3 + 1 ... sizeof(uint64_t) * 4 - 1:

Clang и ICC вроде уже это поддерживают

Ты давай равномерностью сперва померяйся.

А что, оно у вас уже выросло?

Not suitable for cryptography

Но зачем тогда?

Учите матчасть pls.

C++

Зачем?

#if !defined(__GNUC__) || (__GNUC__ < 4)

gcc-only хэш-функция? гм

Такая маскировка под gcc есть в clang, icc и где-то еще. Причем маскировка включает наличие всяческих __builtin_xyz() и т.д.

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

DJB2 все равно быстрее.

Я к чему это. Где доказателсьтва равномерности распределения коллизий?

Шланг определяет __GNUC__.

Я к чему это. Где доказателсьтва равномерности распределения коллизий?

Ну SMHasher же, RTFM.

А тесты от NIST мне лень прикручивать, ибо не известны случаи когда от них был толк после SMHasher (который из Diehard PRNG test suite).

Дайте тест, сравним результаты вашей реализации и моей.

И вообще я хочу constexpr от строки в компайл-тайме:
uint32_t hash = «some_useful_string»_hash;

А что, оно у вас уже выросло?

Да ты еще и хам.

Учите матчасть pls.

Вопрос был зачем очередной велосипед весьма сомнительной нужности.

Дайте тест, сравним результаты вашей реализации и моей.

Написано же, примерно буквами = https://github.com/leo-yuriev/t1ha/blob/master/README.md#benchmarking--testing

И вообще я хочу constexpr от строки в компайл-тайме:

А я хочу миллион, давайте хотеть вместе )

Покажи распределение на различных входных данных. Например, на случайных словах или лучше числах (телефоны, например).

Учите матчасть pls.

Вопрос был зачем очередной велосипед весьма сомнительной нужности.

Ваше мнение понято, но не интересно. Спасибо.

Покажи распределение на различных входных данных. Например, на случайных словах или лучше числах (телефоны, например).

Пожалуйста, ознакомтесь с матчастью = https://github.com/aappleby/smhasher/wiki

Написано же, примерно буквами = https://github.com/leo-yuriev/t1ha/blob/master/README.md#benchmarking--testing

Не нужно умничать, пальцем покажите, как мне в этот тест добавить свой хеш.

А я хочу миллион, давайте хотеть вместе )

Я вам про фому, а вы мне про ерему.

А вообще,

Small key speed test - 31-byte keys - 37.62 cycles/hash

Ключ-то короткий. У нас ключи бывают сильно длиннее 31 байта.

cat /proc/cpuinfo | grep aes

Ага, отсутствует. Прикрути в CMakeLists.txt тогда условие.

Ага, отсутствует. Прикрути в CMakeLists.txt тогда условие.

SMHasher - это отдельный проект, точнее несколько форков.

Поэтому все приктутки - pls к автору через добавление issue.
https://github.com/rurban/smhasher

Не нужно умничать, пальцем покажите, как мне в этот тест добавить свой хеш.

Гм, берете и добавляете = https://github.com/rurban/smhasher/blob/master/main.cpp#L67

> Small key speed test - 31-byte keys - 37.62 cycles/hash

Ключ-то короткий. У нас ключи бывают сильно длиннее 31 байта.

Вообще-то там для больших ключей отдельный тест и соответственно тогда t1ha_mux.

На ключах до 31 байта ваш хеш сильно круче используемого мною.

t1ha = Status Quo

1. По текущим тестам t1ha (aka Fast Positive Hash) является самой быстрой не-криптографической хэш-функцией, которая переносима (не использует специфический набор инструкций) и при этому проходит все тесты SMHasher. Проще говоря, быстрее только при использовании https://en.wikipedia.org/wiki/AES_instruction_set и/или crc32c из https://en.wikipedia.org/wiki/SSE4
2. t1ha импортирована в расширенный SMHasher = https://github.com/rurban/smhasher. В README есть таблица с результатами.
3. Выпущен релиз 1.0.0 = https://github.com/leo-yuriev/t1ha/tree/1.0.0

Всем спасибо.

Прогнал через несколько своих тестов, посмотрел распределения на различных «неудобных» входных данных. В общем, забираю свои слова про велосипед. Очень хорошая штука получилась, спасибо!

Быстрее

Что быстрее? Вставка ключа, удаление ключа, поиск ключа, создание таблицы?

И вообще, если сосредоточиться только на поиске ключа, то до оптимальности тут далеко.

посмотрел распределения на различных «неудобных» входных данных

А как ты смотрел? Я из любопытства построил карты типа таких как вот здесь: http://softwareengineering.stackexchange.com/a/145633 , только без радужной раскраски.

Получилось непонятно. На первый взгляд картинки довольно рандомные, но когда поскролил, там явно видно неслучайность

Вот случайная карта: http://storage1.static.itmages.com/i/16/1119/h_1479537485_1138560_3e674c71ac.png

А вот те же данные, но немного по-другому отмасштабированные: http://storage9.static.itmages.com/i/16/1119/h_1479537597_4689339_d10a0b1226.png

http://storage3.static.itmages.com/i/16/1119/h_1479537628_2184614_6c86368c03.png

http://storage6.static.itmages.com/i/16/1119/h_1479537676_6932060_35327b9341.png

Или это фича, так и должно быть? Может быть неправильно строил карту? Артефакты от rand() ? Вот код, который генерирует эти png:

https://gist.github.com/vmxdev/3f81581eea9add508d79c1f8fd16de5c

Щас посмотрел на эти же картинки в хроме, выглядят обычным шумом. Блин, это похоже просмотрщик картинок (точнее его масштабирование) жжот

Отбой тревоги

Я из любопытства построил карты

Тоже самое делал.

Вот код, который генерирует эти png

Я обычно двумя строчками в pbm вывожу :3

Что быстрее? Вставка ключа, удаление ключа, поиск ключа, создание таблицы?
И вообще, если сосредоточиться только на поиске ключа, то до оптимальности тут далеко.

Мы тут про хеш-функцию. А вы о чем?

Мы тут про хеш-функцию. А вы о чем?

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

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

Если сказать кратко - то идите в лес и учите матчасть )

Но давайте попробуем разобраться:

• Предположим у вас есть идеальная хэш-функция, выдающая результат шириной N бит.
• Тогда вероятность коллизии для нее 1/(2**(N/2)).
• Идеальная хеш-функция - это когда изменении одного бита в исходных данных, меняется половина битов результата, и это на любом наборе и размере исходных данных.

Что делаем SMHasher (https://github.com/rurban/smhasher) - он оценивает насколько поведение тестируемых хэш-функций близко к идеальному. Тесты разные, но во многих вычисляется некоторый % (упрощенно) отклонения от идеального поведения. И критерии отбраковки там достаточно жесткие (см Dieharder PRNG Test Suite).

Например:

Keyset 'TwoBytes' - up-to-12-byte keys, 18616785 total keys
Testing collisions   - Expected     0.00, actual     0.00 ( 0.00x)
Testing distribution - Worst bias is the  20-bit window at bit  18 - 0.054%

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

t1ha проходит все проверки SMHasher. Поэтому вероятность наткнуться на набор данных, при котором t1ha будет вести себя не как идеальная хэш-функция = «чуть меньше» чем выиграть в спортлото.

Если сказать кратко - то идите в лес и учите матчасть )

В Positive Technologies все такие хамы или ты такой особенный? Ты на форум пришел ЧСВ потешить?

Что быстрее? Вставка ключа, удаление ключа, поиск ключа, создание таблицы?

Вы хоть топик прочитали?

И вообще, если сосредоточиться только на поиске ключа, то до оптимальности тут далеко.

Вижу, что на это у вас времени не хватило.

Не понимаю, где вы видите хамство.

DJB2 все равно быстрее.

DJB2 также известна как «bernstein» (её автор Вan Bernstein).

В https://github.com/rurban/smhasher/blob/master/README.md есть таблица с результатами, в том числе для bernstein/DJB2.

Из этих результатов следует что t1ha примерно в 15 раз быстрее DJB2 для длинных ключей и примерно вдвое для коротких.

Я к чему это. Где доказателсьтва равномерности распределения коллизий?

Упомянутый smhasher является одним из общеизвестных тестов хеш-функций, и считается достаточно хорошим (лучше пока не сделали).

Соответственно, t1ha проходит все тесты без замечаний.

К слову, bernstein/DJB2 тесты smhasher-а не проходит, примерно совсем.

Судя по README.md, автор — выпускник МГИМО.