KOMIHASH - Very Fast Hash Function (in C/C++)

Introduction

The komihash() function available in the komihash.h file implements a very fast 64-bit hash function, mainly designed for hash-table, hash-map, and bloom-filter uses; produces identical hashes on both big- and little-endian systems. Suitable for file and large data hashing (checksums). Function's code is portable, cross-platform, scalar, zero-allocation, header-only, inlinable C (compatible with C++).

This function features both a high large-block hashing performance (27 GB/s on Ryzen 3700X) and a high hashing throughput for small strings/messages (about 8 cycles/hash for 0-15-byte strings, if hashed repeatedly). Performance on 32-bit systems is, however, quite low. Also, large-block hashing performance on big-endian systems may be 20% lower due to the need of byte-swapping (can be switched off with a define).

Technically, komihash is close to the class of hash functions like wyhash and CircleHash, which are, in turn, close to the lehmer64 PRNG. However, komihash is structurally different to them in that it accumulates the full 128-bit multiplication result, without folding into a single 64-bit state variable. Thus komihash does not lose differentiation between consecutive states while others may.

Another important difference in komihash is that it parses the input message without overlaps. While overlaps allow a function to have fewer code branches, they are considered "non-ideal", potentially causing collisions and seed value flaws. Beside that, komihash features superior seed value handling and Perlin Noise hashing.

An aspect worth noting, important to some users, is that komihash at its base uses a simple mathematical construct, and uses no author-intended nor author-fabricated information. The base state of the function is equal to the first mantissa bits of PI, and can be changed to any uniformly random values. This means that statistical properties (collision resistance) of komihash are not based on manual fine-tuning, but are a product of the mathematical construct.

Note that this function is not cryptographically secure: in open systems, and within any server-side internal structures, it should only be used with a secret seed, to minimize the chance of a collision attack (hash flooding). However, when the default seed is used (0), this further reduces function's overhead by 1-2 cycles/hash (compiler-dependent).

This function passes all SMHasher and SMHasher3 tests. The function was also tested with the xxHash collision tester at various settings, with the collision statistics satisfying the expectations. The performance (expressed in cycles/byte) of this hash function on various platforms is best evaluated at the ECRYPT/eBASH project. Thanks to Daniel J. Bernstein for maintaining the benchmark.

This function and the source code (which conforms to ISO C99) were quality-tested on: Clang, GCC, MSVC, and Intel C++ compilers; x86, x86-64 (Intel, AMD), and AArch64 (Apple Silicon) architectures; Windows 10, AlmaLinux 9.3, and macOS 13.3. Full C++ compliance is enabled conditionally and automatically when the source code is compiled with a C++ compiler.

Usage

#include <stdio.h>
#include "komihash.h"

int main(void)
{
    const char s1[] = "This is a test of komihash.";
    const char s2[] = "7 chars";

    printf( "%016llx\n", komihash( s1, strlen( s1 ), 0 )); // 5b13177fc68b4f96
    printf( "%016llx\n", komihash( s2, strlen( s2 ), 0 )); // 2c514f6e5dcb11cb
}

Discrete-Incremental Hashing

A correct way to hash an array of independent values, and which does not require pre-buffering, is to pass previous hash value as a seed value. This method may be as fast or faster than pre-buffering, especially if lengths of values in the array are not small. An additional 1-2 cycles/hash advantage is obtained if fixed-size values are being hashed incrementally (due to compiler's branching optimization). In most cases, incremental hashing of even a few 2-8-byte values may be faster than using pre-buffering if the overall input length is not known in advance.

uint64_t HashVal = komihash( &val1, sizeof( val1 ), Seed );
HashVal = komihash( &val2, sizeof( val2 ), HashVal );
...
HashVal = komihash( &valN, sizeof( valN ), HashVal );

Note that this approach is not the same as "streamed" hashing since this approach implicitly encodes the length of each independent value. Such kind of hashing can be beneficial when a database record is being hashed, when it is necessary to separate fields by means of encoding their lengths.

Discrete-incremental hashing of nested structures requires a "hash value stack" where the current hash value is pushed into it upon each nesting, the nested level starts at hash value 0, and the resulting value is hashed with a popped previous hash value upon exiting the nesting level.

Streamed Hashing

The komihash.h file also features a fast continuously-streamed implementation of the komihash hash function. Streamed hashing expects any number of update calls inbetween the init and final calls:

komihash_stream_t ctx;
komihash_stream_init( &ctx, UseSeed );

komihash_stream_update( &ctx, &val1, sizeof( val1 ));
komihash_stream_update( &ctx, &val2, sizeof( val2 ));
...
komihash_stream_update( &ctx, &valN, sizeof( valN ));

uint64_t Hash = komihash_stream_final( &ctx );

Since the final function is non-destructive to the context structure, the function can be used to obtain intermediate "incremental" hashes of the data stream being hashed, and the hashing can then be resumed.

The hash value produced via streamed hashing can be used in the discrete-incremental hashing outlined above (e.g., for files and blobs).

You may also consider using PRVHASH64S which provides 8.5 GB/s hashing throughput on Ryzen 3700X, and is able to produce a hash value of any required bit-size.

Ports

• C++, vcpkg
• C3, by NotsoanoNimus
• Crystal, by Coral Pink
• Java, by Dynatrace
• LUA, by rangercyh
• .NET, by TommasoBelluzzo
• Perl, by scottchiefbaker
• Rust, by thynson

Customizing C++ namespace

In C++ environments where it is undesirable to export komihash symbols into the global namespace, the KOMIHASH_NS_CUSTOM macro can be defined externally:

#define KOMIHASH_NS_CUSTOM komihash
#include "komihash.h"

Similarly, komihash symbols can be placed into any other custom namespace (e.g., a namespace with hash functions):

#define KOMIHASH_NS_CUSTOM my_hashes
#include "komihash.h"

This way, komihash functions can be referenced like my_hashes::komihash(...). Note that since all komihash functions have the static specifier, there can be no ABI conflicts, even if the komihash.h header is included in unrelated, mixed C/C++, compilation units.

Comparisons

These are the performance comparisons made and used by the author during the development of komihash, on different compilers and platforms.

1. LLVM clang-cl 18.1.8 x86-64, Windows 10, Ryzen 3700X (Zen2), 4.2 GHz. Compiler options: /Ox -msse2.
2. LLVM clang-cl 18.1.8 x86-64, Windows 10, Ryzen 3700X (Zen2), 4.2 GHz. Compiler options: /Ox -mavx2.
3. ICC 19.0 x86-64, Windows 10, Ryzen 3700X (Zen2), 4.2 GHz. Compiler options: /O3 /QxSSE2.
4. LLVM clang 18.1.8 x86-64, AlmaLinux 9.3, Xeon E-2386G (RocketLake), 5.1 GHz. Compiler options: -O3 -mavx2.
5. GCC 11.4.1 x86-64, AlmaLinux 9.3, Xeon E-2386G (RocketLake), 5.1 GHz. Compiler options: -O3 -msse2.
6. GCC 11.4.1 x86-64, AlmaLinux 9.3, Xeon E-2386G (RocketLake), 5.1 GHz. Compiler options: -O3 -mavx2.
7. LLVM clang-cl 18.1.8 x86-64, Windows 10, Core i7-7700K (KabyLake), 4.5 GHz. Compiler options: /Ox -mavx2.
8. ICC 19.0 x86-64, Windows 10, Core i7-7700K (KabyLake), 4.5 GHz. Compiler options: /O3 /QxSSE2.
9. Apple clang 15.0.0 arm64, macOS 13.3.2, Apple M1, 3.5 GHz. Compiler options: -O3.
10. LLVM clang-cl 18.1.8 x86-64, Windows 11, Ryzen 9950X (Zen5), 5.7 GHz. Compiler options: /Ox -msse2.

|Platform |1 |1 |1 |2 |2 |2 |3 |3 |3 |4 |4 |4 |5 |5 |5 |6 |6 |6 |7 |7 |7 |8 |8 |8 |9 |9 |9 |10 |10 |10 | |-----------------|-----------------|---------------|---------------|-------|-----|----|-------|-----|----|-------|-----|----|-------|-----|----|-------|-----|----|-------|-----|----|-------|-----|----|-------|-----|----|-------|-----|----| |Hash function |0-15b, cycles/h|8-28b, cycles/h|bulk, GB/s |0-15b|8-28b|bulk|0-15b|8-28b|bulk|0-15b|8-28b|bulk|0-15b|8-28b|bulk|0-15b|8-28b|bulk|0-15b|8-28b|bulk|0-15b|8-28b|bulk|0-15b|8-28b|bulk|0-15b|8-28b|bulk| |komihash 5.28|9.7 |11.2 |27.1 |9.7 |11.2 |27.1|11.8 |13.9 |23.2|9.7 |11.3 |31.7|10.0 |11.4 |31.0|10.0 |11.4 |31.0|12.0 |13.2 |22.8|15.0 |18.0 |19.4|8.1 |7.9 |23.6|7.0 |8.0 |42.7| |wyhash_final4 |14.5 |18.2 |29.3 |14.7 |18.2 |29.3|25.9 |32.9 |12.5|16.8 |21.6 |34.6|17.2 |23.1 |35.3|17.3 |23.2 |35.5|15.5 |20.4 |29.8|21.1 |26.1 |19.4|7.9 |8.1 |26.1|13.9 |18.5 |41.7| |XXH3_64 0.8.0 |15.5 |28.8 |30.0