02.10.2017 14:35
yleo 25 13600 Источник

Чуть менее, чем самая быстрая, переносимая, 64-битная хеш-функция, с достойным качеством.
Да, вжух и в дамки, примерно так. Читаем дальше?


Вместо Disclaimer

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


Банальности

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


Ещё немного занудства

Для стройности изложения необходимо определить понятия «качества» хеш-функции и остальные требования чуть более детально:


  • Базовое качество: Изменение одного или более произвольных бит в произвольном наборе исходных данных, приводит к изменению каждого бита результата с вероятностью ?.
  • Необратимость (стойкость к восстановлению прообраза): Невозможность получения исходных данных или отдельных битов по результату хеширования.
  • Устойчивость к подбору под результат (стойкость к коллизиям первого рода): Сложность поиска/подбора исходного набора данных с целью получения заданного результата или даже отдельных его битов, в том числе когда известен исходный набора данных.
  • Устойчивость к подбору сообщений (стойкость к коллизиям второго рода): Сложность поиска/подбора двух разных наборов данных, которые давали бы одинаковый результат или совпадение отдельных битов.

Опуская цитирование доказательств и прочие выкладки можно констатировать:


  • Надлежащее выполнение всех пунктов, одновременно с обеспечением производительности, является достаточно трудной задачей, решение которой даёт хорошую криптографическую хеш-функцию. Но мы пока заниматься этим не будем.
  • Обеспечение базового качества требует достаточно большого количества операций АЛУ. Проще говоря, качество всегда конфликтует со скоростью.
  • Получение качественного результата с разрядностью больше разрядности операций АЛУ требует более, чем кратного увеличения количества перемешиваний, а следовательно базовых операций АЛУ.
  • В целом, создание быстрой хеш-функции предполагает достижения взвешенного компромисса между скоростью, качеством и разрядностью результата.

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


Базовый вариант t1ha является (самой) быстрой переносимой хеш-функцией для построения хеш-таблиц и других родственных применений. Поэтому базовый вариант t1ha ориентирован на 64-битные little-endian архитектуры, принимает 64-битное подсаливающее значение (seed) и выдает 64-битный результат, который включает усиление длиной ключа и seed-ом. Стоит отметить, t1ha намеренно сконструирована так, чтобы возвращать 0 при нулевых входных данных (ключ нулевого размера и нулевой seed).


Решил вынести из ответов на комментарии

64-битные операции: Возможно стоит пояснить, что именно 64-битные операции дают скорость и качество, не отбирая переносимости. Собственно, чем шире разрядность арифметических операций, тем больше они дают лавинного эффекта и лучше перемешивают данные. Ну и обрабатывать данные, при прочих равных, конечно быстрее по 8 байт, чем по 4. С другой стороны, именно 64-битные операции нативно доступны на многих современных процессорах, и более-менее сносно могут быть оттранслированы в 32-битные. Все прочие варианты, в том числе SIMD-операции, заставляют сильно жертвовать переносимостью и/или скоростью на "не родных" платформах.


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


Эта "магия" замены сравнений может быть непонятной и не востребованной, а может на порядок повысить скорость работы только за счет локальности, т.е. меньшего вымывания кэша CPU. Проще говоря, вы можете построить структуру хеш-таблицы так, чтобы вычисленные хеш-значения лежали рядом (паковались в кэш-линии). А за реальными данными процессору приходилось идти только при совпадении хеш-значений. И вот в этом случае 64-бита от t1ha позволяют получить предельный результат. Причем 128 бит уже не дадут выигрыша, а взять от 64 битов меньше — можно всегда.


Сравнение с HighwayHash: У меня двоякое отношение к этому неофициальному проекту сотрудников Google.


  1. Во-первых: С одной стороны, хороший код и отличное техническое воплощение. С другой стороны, HighwayHash позиционируется как возможно криптографический стойкий (как минимум равный SipHash). Хотя доказательство "стойкости" сводится к результатам статистических тестов, но без возможности их воспроизвести (как-то я даже позволил себе лишнее).
  2. Во-вторых: HighwayHash действительно быстр только на x86_64 c AVX2 или SSE41. Так не проще ли использовать AES-NI или акселерацию SHA?

Если всё будет хорошо, то в наборе t1ha появятся дополнительные варианты (прежде всего по ширине результата) и оптимизированные для E2K. На этом тему сравнения с HighwayHash я хотел-бы закрыть.



Качество


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


Напротив, для статистических испытаний легко получить прозрачные количественные оценки. При этом есть хорошо зарекомендовавшие себя тестовые пакеты, например SMHasher. Для t1ha результаты просты — все варианты t1ha проходят все тесты без каких-либо замечаний. С другой стороны, не следует считать, что у t1ha есть какие-либо свойства сверх тех, что необходимы для целевого применения (построение хеш-таблиц).


Читатели наверняка оценили бы тщательный и глубокий анализ качественности и/или стойкости t1ha. Однако, исходя из целевых областей применения t1ha это представляется излишним. Проще говоря, нам была важнее скорость, в том числе для коротких ключей. Поэтому много-раундовое перемешивание не рассматривалось. Представляемый вариант t1ha экономит на спичках тактах и выдает 64-битный результат — практически бессмысленно измерять найденный компромисс иначе, как статистически, а эти результаты просто хороши.


На самом деле

я просто беру пример в statistical prove с коллег из Google ;)



Бенчмарки


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


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


Кроме этого, на сайте проекта приведены таблицы с результатам замеров производительности посредством доработанной версии SMHasher от Reini Urban. Соответственно, все цифры можно перепроверить и/или получить результаты на конкретном процессоре при использовании конкретного компилятора.


Здесь же можно привести сопоставление с некоторыми ближайшими конкурентами t1ha.


Хеширование коротких ключей (среднее для 1..31 байта).
Смотрим на правую колонку «Cycles/Hash» (чем меньше значение, тем быстрее):


Function MiB/Second Cycles/Hash
t1ha 12228.80 35.55
FastHash64 5578.06 43.42
CityHash64 11041.72 51.77
xxHash64 11123.15 56.17
MetroHash 11808.92 46.33

Хеширование длинных ключей (256 Кб).
Смотрим на среднюю колонку «MiB/Second» (чем больше значение, тем быстрее):


Function MiB/Second Cycles/Hash
t1ha 12228.80 35.55
FarmHash64 12145.36 60.12
CityHash64 11041.72 51.77
xxHash64 11123.15 56.17
Spooky64 11820.20 60.39


Варианты t1ha


Разработка t1ha преследовала сугубо практические цели. Первой такой целью было получение быстрой переносимой и достаточно качественной функции для построения хеш-таблиц.


Затем потребовался максимально быстрый вариант хеш-функции, который давал-бы сравнимый по качеству результат, но был максимально адаптирован на целевую платформу. Например, базовый вариант t1ha работает с little-endian порядком байт, из-за чего на big-endian архитектурах требуется конвертация с неизбежной потерей производительности. Так почему-бы не избавиться от лишних операций на конкретной целевой платформе? Таким же образом было добавлено ещё несколько вариантов:


  • Упрощенный вариант для 32-битных платформ, как little, так и big-endian.
  • Вариант с использованием инструкций AES-NI для процессоров без AVX.
  • Два варианта с использованием инструкций AES-NI с использованием AVX.

Чуть позже стало понятно, что потребуются ещё варианты, сконструированные для различных применений, включая разную разрядность результата, требования к качеству и стойкости. Такое многообразие потребовало наведения порядка. Что выразилось в смене схемы именования, в которой цифровой суффикс обозначает «уровень» функции:


  • t1ha0() — максимально быстрый вариант для текущего процессора.
  • t1ha1() — базовый переносимый 64-битный вариант t1ha.
  • t1ha2() — переносимый 64-битный вариант с чуть большей заботой о качестве.
  • t1ha3() — быстрый переносимый 128-битный вариант для получения отпечатков.
  • и т.д.

В этой схеме предполагается, что t1ha0() является диспетчером, который реализует перенаправление в зависимости от платформы и возможностей текущего процессора. Кроме этого, не исключается использование суффиксов «_le» и «_be» для явного выбора между little-endian и big-endian вариантами. Таким образом, под «вывеской» t1ha сейчас находится несколько хеш-функций и это семейство будет пополняться, в том числе с прицелом на отечественный E2K «Эльбрус».


Представление о текущем наборе функций и их свойствах можно получить из вывода теста. Стоит лишь отметить, что все функции проходят все тесты SMHasher, а производительность вариантов AES-NI сильно варьируется в зависимости от модели процессора:


Simple bench for x86 (large keys, 262144 bytes):
              t1ha1_64le:   47151 ticks,  0.1799 clk/byte,  16.679 Gb/s @3GHz
              t1ha1_64be:   61602 ticks,  0.2350 clk/byte,  12.766 Gb/s @3GHz
              t1ha0_32le:   94101 ticks,  0.3590 clk/byte,   8.357 Gb/s @3GHz
              t1ha0_32be:   99804 ticks,  0.3807 clk/byte,   7.880 Gb/s @3GHz

Simple bench for x86 (small keys, 31 bytes):
              t1ha1_64le:      39 ticks,  1.2581 clk/byte,   2.385 Gb/s @3GHz
              t1ha1_64be:      42 ticks,  1.3548 clk/byte,   2.214 Gb/s @3GHz
              t1ha0_32le:      51 ticks,  1.6452 clk/byte,   1.824 Gb/s @3GHz
              t1ha0_32be:      54 ticks,  1.7419 clk/byte,   1.722 Gb/s @3GHz

Simple bench for AES-NI (medium keys, 127 bytes):
     t1ha0_ia32aes_noavx:      72 ticks,  0.5669 clk/byte,   5.292 Gb/s @3GHz
       t1ha0_ia32aes_avx:      78 ticks,  0.6142 clk/byte,   4.885 Gb/s @3GHz
      t1ha0_ia32aes_avx2:      78 ticks,  0.6142 clk/byte,   4.885 Gb/s @3GHz

Simple bench for AES-NI (large keys, 262144 bytes):
     t1ha0_ia32aes_noavx:   38607 ticks,  0.1473 clk/byte,  20.370 Gb/s @3GHz
       t1ha0_ia32aes_avx:   38595 ticks,  0.1472 clk/byte,  20.377 Gb/s @3GHz
      t1ha0_ia32aes_avx2:   19881 ticks,  0.0758 clk/byte,  39.557 Gb/s @3GHz


Немного о внутреннем устройстве

Если говорить чуть более детально, то t1ha построена по схеме Меркла-Дамгарда (в варианте «wipe-pipe») с упрочнением от размера данных и подсаливающего значения. Внутри основного сжимающего цикла используется 256-битное состояние, с аналогичным размером входного блока. Причем для каждого операнда данных реализуется две точки инъекции с перекрестным опылением. По завершению сжимающего цикла выполняется сжатие 256-битного состояния до 128 бит.


При выполнении описанных действий используются 64-битные операции, которые комбинируются в миксеры ARX (Add-Rotate-Xor) и MUX/MRX (Mul-Rotate-Xor). Немаловажно, что все эти вычисления выстроены так, чтобы обеспечить возможность параллельного выполнения большинства операций и плотной укладки u-ops как в конвейер, так и в исполняющие устройства x86_64. За счет этого достигается достаточно хорошее качество при практически предельной скорости хеширования длинных ключей.


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


Далее, оставшийся хвост данных порциями по 64 бита подмешивается попеременно к половинам 128-битного состояния. В заключении выполняется перемешивание состояния одновременно со сжатием до 64-битного результата. Немаловажной особенностью t1ha здесь является использование миксера на базе широкого умножения (128-битное произведение двух 64-битных множителей). Это позволяет реализовать качественно перемешивание с хорошим лавинным эффектом за меньшее количество операций. Несмотря на то, что широкое умножение относительно дорогая операция, меньшее количество операций позволяет t1ha обрабатывать короткие ключи за рекордно малое количество тактов процессора.


Следует отметить, что используемый миксер на основе широкого умножения и исключающего ИЛИ не идеален. Несмотря на то, что t1ha проходит все тесты SMHasher, у автора есть представление о последствиях неинъективности. Тем не менее, результирующее качество представляется рационально-достаточным, а в планах развития линейки t1ha уже отражено намерение предоставить чуть более качественный вариант.


Остальное здесь.


Спасибо за внимание. Всем добра.

Комментарии (25)


  1. Varim
    02.10.2017 18:01
    #10448028

    https://github.com/leo-yuriev/t1ha
    Там у вас в описании кажеться ошибка, в таблице «Implementation Platform/CPU»

    t1ha1_be() 32-bit big-endian
    возможно должно быть t1ha1_be() 64-bit big-endian


    1. yleo Автор
      02.10.2017 18:15
      #10448052

      Да, copy-paste…
      Спасибо.
      github.com/leo-yuriev/t1ha/commit/1bf59643b0bfe70e5160f10567ba5afa5e77bae2


  1. mwizard
    02.10.2017 18:04
    #10448032

    Интересно было бы сравнить производительность с 64-битной версией хэша Пирсона.


    1. yleo Автор
      02.10.2017 18:23
      #10448074

      Хеш Пирсона будет медленнее, плюс будут проблемы с качеством.
      При желании можете проверить добавить функцию в github.com/rurban/smhasher


  1. zuborg
    02.10.2017 18:33
    #10448086

    Неплохо, но ещё есть запас для улучшения. 35 циклов это не предел (например, операция взятия остатка от деления на простое число требует около 5 тактов на современном процессоре, а она перемешивает биты весьма непредсказуемым образом).

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


    1. yleo Автор
      02.10.2017 19:06
      #10448132
      +1

      С делением несколько печальнее.

      Во-первых делить придется число удвоенной ширины.
      Для 64-битного результата — 128 бит (например) на 18446744073709551557, а для 32-битного — 64-бита (например) на 4294967291.
      Такое деление выполняется медленнее, точнее говоря на многих CPU нет такой инструкции.

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

      При этом одна такая операция не даст хорошего качества, а две уже слишком сильно уронят производительность даже на x86_64.

      Но попробуйте, за каждый такт (на x86_64) готов что-нибудь презентовать.


      1. zuborg
        02.10.2017 20:34
        #10448238
        +1

        Для хеш-таблиц нет необходимости в таком большом количестве бит — там все равно используются только несколько десятков младших бит результата, в зависимости от размера таблицы.
        А для тех применений, где нужно все 64 бита, вполне достаточно генерировать старшую и младшую половину (32 бита) независимо — это в два раза больше работы, но все равно меньше, чем если реализовывать честное 128-бит деление. А суперскалярные процессоры могут обе половины хеша и вовсе одновременно обсчитывать )


        1. yleo Автор
          02.10.2017 22:15
          #10448324
          +2

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


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


          И вот в этом случае 64-бита от t1ha позволяют получить предельный результат.
          Причем 128 бит уже не дадут выигрыша, а сократить до 32 можно очень легко.



          Далее, считать два 32-битных результата конечно можно. Только на 64-битном CPU это достаточно нерационально.


          • во-первых, 64-битные операции, при правильном применении, дают гораздо больше выигрыша "количестве перемешивания" на такт.
          • во-вторых, обрабатывать хешируемые дынные так примерно в два раза быстрее.

          Т.е. если у вас есть более-менее приличное нативное 64-битное АЛУ, то нет смысла что-либо делать в 32-бита, при любой суперскалярности.



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


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


          • получаете более-менее качественный 64-битный суррогат результата.
          • вычисляете остаток от деления на простое число, но большее чем разрядность финального результата
          • обнуляете старшие биты результата до требуемой "ширины".

          Более того, можно даже добавить такой вариант в t1ha. Если это кому-нибудь требуется, ну или "интереса ради".


          1. Ivan_83
            03.10.2017 03:02
            #10448508

            Нубский вопрос: чем плохо взять и сделать XOR между двумя 32 бит числами образующими 64, когда нужно только 32?
            Ну и далее по нисходящей если нужно ещё меньше.

            PS: я бы в начале обозначил что функция не криптографическая, чтобы все сразу поняли.
            Для криптографической у вас битов маловато, и пруфов/анализов от специалистов нет что необходимые для криптографии свойства действительно соблюдены.


            1. yleo Автор
              03.10.2017 11:34
              #10448768
              +1

              Если исходная хэш-функция качественная, то XOR половинок безобиден, но и бесполезен. При хорошем перемешивании можно просто взять любую из половинок.

              Если же в исходной хеш-функции не всё хорошо, то такой XOR может внезапно ухудшить ситуацию, равно как и любые другие подобные манипуляции. Проще говоря, при плохой функции у вас есть шанс выявить/обострить корреляцию, статистическое смещение или даже частично обратить хеш-функцию.

              Про не-криптографию обозначено в самом начале (см. «замену дисклаймера»).


  1. masterspline
    02.10.2017 22:51
    #10448368

    Интересно сравнить скорость работы с xoroshiro.


    1. yleo Автор
      03.10.2017 00:35
      #10448440
      +1

      Не совсем понятно зачем сравнивать зеленое с горячим :)


      Xoroshiro — это PRNG, который можно отнести к ARX (add-rotate-xor). Соответственно, все его варианты будут очень быстро генерировать псевдо-случайные последовательности. Для 64 бит результата требуется всего 8 простых операций (но с зависимостями по данным и особо не параллелятся).


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


      Вот теперь представьте, что у вас всего 1 байт исходных данных, и вам нужно так "засунуть" его в PRNG, чтобы при изменении одного (любого) бита в этом байтике менялось половина битов результата.


      В SipHash для этого делается несколько раундов, т.е. для каждого вмешивания нужно несколько раз встряхнуть PRNG. В итоге производительность получается несколько иной.


      Кстати, если интересно, у меня есть старый PRNG-велосипед.


      1. masterspline
        03.10.2017 17:39
        #10449868

        Да, я глупость написал. xoroshiro — это быстрый генератор рандома, никакого отношения к хешам не имеет.


      1. Refridgerator
        04.10.2017 15:29
        #10452310

        А PRNG-велосипед проверялся на тесты типа diehard?


        1. yleo Автор
          04.10.2017 16:21
          #10452546

          Да, конечно.

          В gist не хватало функции инициализации/разогрева, добавил только-что по-памяти.
          Блин, почти пятнадцать лет уже прошло, стареем…


  1. firk
    03.10.2017 12:54
    #10448974
    +1

    Всё-таки непонятно предназначение этой штуки. С одной стороны заявляется простота, некриптографичность, скорость, с другой — алгоритм не выглядит тривиально простым.


    Для хеш-таблиц, да и для сравнений поиска тоже, никак не нужны честные 64 бита и не нужно даже это


    Базовое качество: Изменение одного или более произвольных бит в произвольном наборе исходных данных, приводит к изменению каждого бита результата с вероятностью ?.

    Достаточно "условно честных почти 64 бит" и одного (в конце вычисления хеша) вычисления остатка от деления на простое число где-нить например 50-битной разрядности, которое с достаточным для большинства бытовых применений качеством перемешает все биты и оставит ещё большую разрядность для сравнений.


    1. knstqq
      03.10.2017 13:19
      #10449064
      +2

      Условно честные + деление обычно дают такой результат: jsfiddle.net/fftzmha8 www.taygeta.com/rwalks/lcmbad.gif
      куча неслучайности, которую видно на последовательных или похожих значениях невооружённым глазом и производительность может сильно просесть


      1. firk
        03.10.2017 14:05
        #10449190

        И как эта неслучайность повредит хеш-таблице с 50-бит хешами?
        По первой ссылке брутфорс всего 17-битного пространства вариантов PRNG (причём пространство внутренних состояний у него такое же маленькое), естественно вы найдёте там коллизии при этом, а если PRNG не криптографический — то коллизии будут ещё и наглядно видны. Попробуйте сгенерировать там не всё пространство, а только 100 точек (из 131072) — никаких проблем не заметите. Аналогично, из 2^50 заполните "всего лишь" 2^40 (но даже такое количество данных в хеш-таблице очень мало у кого есть) — никаких проблем не будет.


      1. firk
        03.10.2017 16:31
        #10449624
        +1

        И кстати — если заменить % (1<<17) на % 96557 (простое число) то "видимые невооружённым глазом" проблемы исчезнут.
        96557 меньше чем исходное 131072 и разрядность PRNG становится ещё хуже где-то на полбита, но зато это простое число, а я писал именно про остаток от деления на простое.
        http://jsfiddle.net/bw4pzh4g/


    1. yleo Автор
      03.10.2017 14:09
      #10449208
      +1

      Криптографичность, э..., она разная. Но прежде всего нужна большая разрядность (256-512), а также много-раундовость для необратимости и сложности генерации коллизий. Если эти "пункта" влить в t1ha, то можно будет хотя-бы обсуждать "криптографичность". На этом предлагаю тему "криптографичности" закрыть.


      Далее, хеш-таблицы бывают разные, точнее сильно разные. И в конкретном случае вам вообще может не потребоваться какое-либо хеширование. Вот очень характерный пример. Но это может быть и терабайтный массив данных, уложенный в libfpta или Hyper100re. Тут конечно можно поспорить о терминологии (что такое хеш-таблица), но с точки зрения применения t1ha — это всё один сценарий.


      Так вот, собственно к чему я это всё = в каждом конкретном случае могут разные требования к качеству хеш-функции, или разное видение компромисса между скоростью и качеством. Обсуждаемый вариант t1ha_1() быстро выдает достаточно качественный 64-битный отпечаток/дайджест, притом с произвольным 64-битным с seed-значением. А стоит ли использовать t1ha или более простые миксеры (и породит ли это какие-либо риски) — решать вам.


  1. pftbest
    03.10.2017 13:22
    #10449074

    Можно ли заменить Fowler–Noll–Vo на вашу хеш функцию, и даст ли это какое либо преимущество? Как я понимаю они обе не криптографические, значит критериями будут только качество и скорость.


    1. yleo Автор
      03.10.2017 14:24
      #10449244

      Классический FNV имеет ряд проблем как с качеством, так и со скоростью. Вариант YoshimitsuTRIAD чуть быстрее t1ha, но имеет большие проблемы с качеством.


      Собственно в README есть таблица с цифрами и примечаниями — поищите там FNV и FNV1a_YoshimitsuTRIAD. Но на всякий хочу предупредить — прежде чем спрашивать о претензиях к качеству FNV следует понять что и как проверяет SMHasher, а также глянуть комментариии Reini Urban в README.


      1. pftbest
        03.10.2017 16:11
        #10449554

        Спасибо, посмотрю README.


  1. borisxm
    03.10.2017 18:58
    #10450108

    А вы не могли бы добавить табличку по коллизиям как здесь: softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed/145633#145633?


    1. yleo Автор
      03.10.2017 19:11
      #10450152

      В данный момент нет, просто некогда этим заниматься.
      Но если сделаете (тест и табличку), то обязательно добавлю.


      Собственно в моих планах сделать замену SMHasher...


      • С тем чтобы проверять тщательнее, в том числе выдавать удобный/понятный показатель качества.
      • Кроме этого в SMHasher исторически неудобный интерфейс добавления функций и тестов.
      • А также принципиальные сложности с возможностью менять набор тестируемых функций в зависимости от фичей CPU, т.е. для этого нужно править исходники и/или пересобирать SMHasher.