Fast Positive Hash, aka "Позитивный Хэш" by Positive Technologies.

The Future will Positive. Всё будет хорошо.

1. Intended for 64-bit little-endian platforms, predominantly for Elbrus and x86_64, but portable and without penalties it can run on any 64-bit CPU.
2. In most cases up to 15% faster than City, xxHash, mum-hash, metro-hash, etc. and all others portable hash-functions (which do not use specific hardware tricks).
3. Provides a set of terraced hash functions.
4. Currently not suitable for cryptography.
5. Licensed under Zlib License.

Also pay attention to Erlang and Golang implementations.

The t1ha library provides several terraced hash functions with the dissimilar properties and for a different cases. These functions briefly described below, see t1ha.h for more API details.

To use in your own project you may link with the t1ha-library, or just add to your project corresponding source files from /src directory.

Please, feel free to fill an issue or make pull request.

Provides fast-as-possible hashing for current CPU, including 32-bit systems and engaging the available hardware acceleration. You can rest assured that t1ha0 faster than all other fast hashes (with comparable quality) so, otherwise we will extend and refine it time-to-time.

On the other hand, without warranty that the hash result will be same for particular key on another machine or another version. Moreover, is deliberately known that the result will be different for systems with different bitness or endianness. Briefly, such hash-results and their derivatives, should be used only in runtime, but should not be persist or transferred over a network.

Also should be noted, the quality of t1ha0() hashing is a subject for tradeoffs with performance. Therefore the quality and strength of t1ha0() may be lower than t1ha1() and t1ha2(), especially on 32-bit targets, but then much faster. However, guaranteed that it passes all SMHasher tests.

Internally t1ha0() selects most faster implementation for current CPU, for now these are includes:

The first version of "Fast Positive Hash" with reasonable quality for checksum, hash tables and thin fingerprinting. It is stable, e.g. returns same result on all architectures and CPUs.

1. Speed with the reasonable quality of hashing.
2. Efficiency on modern 64-bit CPUs, but not in a hardware.
3. Strong as possible, until no penalties on performance.

Unfortunatelly, Yves Orton discovered that t1ha1() fails the strict avalanche criteria in some cases. This flaw is insignificant for the t1ha1() purposes and imperceptible from a practical point of view. However, nowadays this issue has resolved in the next t1ha2() function, that was initially planned to providing a bit more quality.

The basic version of t1ha1() intends for little-endian systems and will run slowly on big-endian. Therefore a dedicated big-endian version is also provided, but returns the different result than the basic version.

The recommended version of "Fast Positive Hash" with good quality for checksum, hash tables and fingerprinting. It is stable, e.g. returns same result on all architectures and CPUs.

1. Portable and extremely efficiency on modern 64-bit CPUs.
2. Great quality of hashing and still faster than other non-t1ha hashes.
3. Provides streaming mode and 128-bit result.

The t1ha2() is intended for little-endian systems and will run slightly slowly on big-endian systems.

The next-step version of "Fast Positive Hash", but not yet finished and therefore not available.

1. t1ha designed for modern 64-bit architectures. But on the other hand, t1ha doesn't require instructions specific to a particular architecture:
   • therefore t1ha could be used on any CPU for which compiler provides support 64-bit arithmetic.
   • but unfortunately t1ha could be dramatically slowly on architectures without native 64-bit operations.
2. This implementation of t1ha requires modern GNU C compatible compiler, including Clang/LLVM, or Visual Studio 2013/2015/2017. For proper performance please use one of: GNU C 5.5 or later, CLANG 5.0 or later, Microsoft Visual Studio 2017 15.6 or later.

The t1ha was originally developed by Leonid Yuriev (Леонид Юрьев) for The 1Hippeus project - zerocopy messaging in the spirit of Sparta!

Current version of t1ha library includes tool for basic testing and benchmarking. Just try make check from t1ha directory.

To comparison benchmark also includes 32- and 64-bit versions of xxhash() function. For example:

$ CC=gcc-7 CXX=g++-7 make all && sudo make check
...
Preparing to benchmarking...
 - suggest enable rdpmc for usermode (echo 2 | sudo tee /sys/devices/cpu/rdpmc)
 - running on CPU#3
 - use RDPMC_perf as clock source for benchmarking
 - assume it cheap and stable
 - measure granularity and overhead: 53 cycle, 0.0188679 iteration/cycle

Bench for tiny keys (7 bytes):
t1ha2_atonce            :     18.109 cycle/hash,  2.587 cycle/byte,  0.387 byte/cycle,  1.160 Gb/s @3GHz
t1ha2_atonce128*        :     36.406 cycle/hash,  5.201 cycle/byte,  0.192 byte/cycle,  0.577 Gb/s @3GHz
t1ha2_stream*           :     84.938 cycle/hash, 12.134 cycle/byte,  0.082 byte/cycle,  0.247 Gb/s @3GHz
t1ha2_stream128*        :    104.062 cycle/hash, 14.866 cycle/byte,  0.067 byte/cycle,  0.202 Gb/s @3GHz
t1ha1_64le              :     19.109 cycle/hash,  2.730 cycle/byte,  0.366 byte/cycle,  1.099 Gb/s @3GHz
t1ha0                   :     15.039 cycle/hash,  2.148 cycle/byte,  0.465 byte/cycle,  1.396 Gb/s @3GHz
xxhash32                :     18.016 cycle/hash,  2.574 cycle/byte,  0.389 byte/cycle,  1.166 Gb/s @3GHz
xxhash64                :     26.094 cycle/hash,  3.728 cycle/byte,  0.268 byte/cycle,  0.805 Gb/s @3GHz
HighwayHash64_pure_c    :    513.000 cycle/hash, 73.286 cycle/byte,  0.014 byte/cycle,  0.041 Gb/s @3GHz
HighwayHash64_portable  :    498.771 cycle/hash, 71.253 cycle/byte,  0.014 byte/cycle,  0.042 Gb/s @3GHz
HighwayHash64_sse41     :     67.062 cycle/hash,  9.580 cycle/byte,  0.104 byte/cycle,  0.313 Gb/s @3GHz
HighwayHash64_avx2      :     59.375 cycle/hash,  8.482 cycle/byte,  0.118 byte/cycle,  0.354 Gb/s @3GHz

Bench for large keys (16384 bytes):
t1ha2_atonce            :   3555.000 cycle/hash,  0.217 cycle/byte,  4.609 byte/cycle, 13.826 Gb/s @3GHz
t1ha2_atonce128*        :   3577.000 cycle/hash,  0.218 cycle/byte,  4.580 byte/cycle, 13.741 Gb/s @3GHz
t1ha2_stream*           :   3716.000 cycle/hash,  0.227 cycle/byte,  4.409 byte/cycle, 13.227 Gb/s @3GHz
t1ha2_stream128*        :   3731.000 cycle/hash,  0.228 cycle/byte,  4.391 byte/cycle, 13.174 Gb/s @3GHz
t1ha1_64le              :   3542.000 cycle/hash,  0.216 cycle/byte,  4.626 byte/cycle, 13.877 Gb/s @3GHz
t1ha0                   :   1306.000 cycle/hash,  0.080 cycle/byte, 12.545 byte/cycle, 37.636 Gb/s @3GHz
xxhash32                :   8201.000 cycle/hash,  0.501 cycle/byte,  1.998 byte/cycle,  5.993 Gb/s @3GHz
xxhash64                :   4118.000 cycle/hash,  0.251 cycle/byte,  3.979 byte/cycle, 11.936 Gb/s @3GHz
HighwayHash64_pure_c    :  49079.201 cycle/hash,  2.996 cycle/byte,  0.334 byte/cycle,  1.001 Gb/s @3GHz
HighwayHash64_portable  :  44486.000 cycle/hash,  2.715 cycle/byte,  0.368 byte/cycle,  1.105 Gb/s @3GHz
HighwayHash64_sse41     :   6419.000 cycle/hash,  0.392 cycle/byte,  2.552 byte/cycle,  7.657 Gb/s @3GHz
HighwayHash64_avx2      :   4265.000 cycle/hash,  0.260 cycle/byte,  3.842 byte/cycle, 11.525 Gb/s @3GHz

The test tool support a set of command line options to selecting functions and size of keys for benchmarking. For more info please run ./test --help.

One noteable option is --hash-stdin-strings, it intended to estimate hash collisions on your custom data. With this option test tool will hash each line from standard input and print its hash to standard output.

For instance, you could count collisions for lines from some words.list file by bash's command:

  ./t1ha/test --hash-stdin-strings < words.list | sort | uniq -c -d | wc -l

More complex example - count xxhash() collisions for lines from words.list and 0...10000 numbers, with distinction only in 32 bit of hash values:

  (cat words.list && seq 0 10000) | \
     ./t1ha/test --xxhash --hash-stdin-strings | \
     cut --bytes=-8 | sort | uniq -c -d | wc -l

SMHasher is a wellknown test suite designed to test the distribution, collision, and performance properties of non-cryptographic hash functions.

Reini Urban provides extended version/fork of SMHasher which integrates a lot of modern hash functions, including t1ha.

So, the quality and speed of t1ha can be easily checked with the following scenario:

git clone https://github.com/rurban/smhasher
cd smhasher
cmake .
make
./SMHasher City64
./SMHasher metrohash64_1
./SMHasher xxHash64
...
./SMHasher t1ha

For properly performance please use at least GCC 5.5, Clang 6.0 or Visual Studio 2017.

Please take in account that the results is significantly depend on actual CPU, compiler version and CFLAGS. The results below were obtained in 2016 on:

• CPU: Intel(R) Core(TM) i7-6700K CPU;
• Compiler: gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.4);
• CFLAGS: -march=native -O3 -fPIC;

Order by average Cycles per Hash for 1..31 bytes (less is better).

Order by hashing speed in Mi-bytes (2^20 = 1048576) per second for 262144-byte block (more is better).