WyHash 1.0.0

wyhash-dotnet

Zero-allocation C# implementation of Wang Yi's 64-bit wyhash hash algorithm and wyrand PRNG.

wyhash is an extremely fast, portable hashing algorithm, and passes all of the SMHasher tests (which evaluates collision, dispersion and randomness qualities of hash functions).

Getting Started

Install the WyHash package from NuGet:

Install-Package WyHash

WyHash implements HashAlgorithm, so can be integrated into existing projects easily:

var seed = 42;
var hasher = WyHash64.Create(seed);

var result = hasher.ComputeHash(myData);

A common use case is getting the resulting hash as a 64-bit unsigned integer (ulong), so a static convenience method is also provided:

// Note that if no seed is specified, it default to 0
var seed = 42;
var result = WyHash64.ComputeHash64(myData, seed);

The wyrand PRNG is also implemented:

var rng = new WyRng(42);

// Generate pseudorandom values
ulong a64BitVal = rng.NextLong();
uint a32BitVal = rng.Next();

// Fill a buffer with pseudorandom bytes
var buffer = new byte[256];
rng.NextBytes(buffer);

// Span is also supported
Span<byte> spanBuffer = stackalloc byte[128];
rng.NextBytes(spanBuffer);

Performance & Future Work

At present (April 2019), wyhash is the fastest algorithm in the SMHasher benchmark.

On a dev laptop with 64GB RAM and an Intel Xeon CPU E3-1545M v5 2.90GHz CPU, this implementation can process data at a rate of around 3GB/s, which is very fast.

Note that PInvokeing into a native DLL built using the reference C code (see the WyHash.Native project) achieves around 10.8GB/s, so there is still work to do to bridge the performance gap.

The bottleneck is 64-bit integer multiplication, as .NET doesn't yet support intrinsics, which would allow performing 64x64 multiplication in a single instruction on supported platforms. Work on this is ongoing by the .NET team, and is expected to land in .NET Core 3.0 - support is unlikely to make it into the .NET Framework though. I expected that using instructions such as BMI2 MULX or SSE4.1 PMULLD will get this implementation running at roughly the same speeds as the C reference code (that is, more or less RAM SPEED)

Latest benchmarks (DataSize is the size of data hashed, in bytes):

BenchmarkDotNet=v0.11.5, OS=Windows 7 SP1 (6.1.7601.0)
Intel Xeon CPU E3-1545M v5 2.90GHz, 1 CPU, 8 logical and 4 physical cores
Frequency=2836132 Hz, Resolution=352.5929 ns, Timer=TSC
.NET Core SDK=2.2.105
  [Host] : .NET Core 2.2.3 (CoreCLR 4.6.27414.05, CoreFX 4.6.27414.05), 64bit RyuJIT
  Core   : .NET Core 2.2.3 (CoreCLR 4.6.27414.05, CoreFX 4.6.27414.05), 64bit RyuJIT

Job=Core  Runtime=Core