segmentio/fasthash

Go package porting the standard hashing algorithms to a more efficient implementation.

fasthash

Go package porting the standard hashing algorithms to a more efficient implementation.

Note
Segment has paused maintenance on this project, but may return it to an active status in the future. Issues and pull requests from external contributors are not being considered, although internal contributions may appear from time to time. The project remains available under its open source license for anyone to use.

Motivations

Go has great support for hashing algorithms in the standard library, but the APIs are all exposed as interfaces, which means passing strings or byte slices to those require dynamic memory allocations. Hashing a string typically requires 2 allocations, one for the Hash value, and one to covert the string to a byte slice.

This package attempts to solve this issue by exposing functions that implement string hashing algorithms and don't require dynamic memory alloations.

Testing

To ensure consistency between the fasthash package and the standard library, all tests must be implemented to run against the standard hash functions and validate that both packages produced the same results.

Benchmarks

The implementations also have to prove that they are more efficient in terms of CPU and memory usage than the functions found in the standard library.
Here's an example with fnv-1a:

BenchmarkHash64/standard_hash_function 20000000   105.0 ns/op   342.31 MB/s   56 B/op   2 allocs/op
BenchmarkHash64/hash_function          50000000    38.6 ns/op   932.35 MB/s    0 B/op   0 allocs/op

Usage Example: FNV-1a

package main

import (
    "fmt"

    "github.com/segmentio/fasthash/fnv1a"
)

func main() {
    // Hash a single string.
    h1 := fnv1a.HashString64("Hello World!")
    fmt.Println("FNV-1a hash of 'Hello World!':", h1)

    // Incrementally compute a hash value from a sequence of strings.
    h2 := fnv1a.Init64
    h2 = fnv1a.AddString64(h2, "A")
    h2 = fnv1a.AddString64(h2, "B")
    h2 = fnv1a.AddString64(h2, "C")
    fmt.Println("FNV-1a hash of 'ABC':", h2)
}

fasthash's Issues

add murmur3?

Move testutils into a subpackage

The public API currently looks like this:

package fasthash 

func BenchmarkHashString32(b *testing.B, name string, reference func(string) uint32, algorithm func(string) uint32)
func BenchmarkHashString64(b *testing.B, name string, reference func(string) uint64, algorithm func(string) uint64)
func HashString32(f func() hash.Hash32) func(string) uint32
func HashString64(f func() hash.Hash64) func(string) uint64
func HashUint32(f func() hash.Hash32) func(uint32) uint32
func HashUint64(f func() hash.Hash64) func(uint64) uint64
func TestHashString32(t *testing.T, name string, reference func(string) uint32, algorithm func(string) uint32)
func TestHashString64(t *testing.T, name string, reference func(string) uint64, algorithm func(string) uint64)
func TestHashUint32(t *testing.T, name string, reference func(uint32) uint32, algorithm func(uint32) uint32)
func TestHashUint64(t *testing.T, name string, reference func(uint64) uint64, algorithm func(uint64) uint64)

I think we should split the testing ones into a subpackage (like nettest) and simplify the core package a bit.

package fasthash

func HashString32(f func() hash.Hash32) func(string) uint32
func HashString64(f func() hash.Hash64) func(string) uint64
func HashUint32(f func() hash.Hash32) func(uint32) uint32
func HashUint64(f func() hash.Hash64) func(uint64) uint64

package fasthashtest

func BenchmarkHashString32(b *testing.B, name string, reference func(string) uint32, algorithm func(string) uint32)
func BenchmarkHashString64(b *testing.B, name string, reference func(string) uint64, algorithm func(string) uint64)
func TestHashString32(t *testing.T, name string, reference func(string) uint32, algorithm func(string) uint32)
func TestHashString64(t *testing.T, name string, reference func(string) uint64, algorithm func(string) uint64)
func TestHashUint32(t *testing.T, name string, reference func(uint32) uint32, algorithm func(uint32) uint32)
func TestHashUint64(t *testing.T, name string, reference func(uint64) uint64, algorithm func(uint64) uint64)

Port more algorithms

• FNV-1 (64 bits)
• FNV-1 (32 bits)
• FNV-1a (32 bits)

panic in fasthash/jody when race detector is enabled

I consistently get a panic in AddString64, but only when the race detector is enabled.

fatal error: checkptr: pointer arithmetic result points to invalid allocation

 goroutine 129 [running]:
 runtime.throw(0x11204c7, 0x40)
 	/usr/local/go/src/runtime/panic.go:1116 +0x72 fp=0xc00046b340 sp=0xc00046b310 pc=0x46a4d2
 runtime.checkptrArithmetic(0xc000402df0, 0xc00046b3f0, 0x1, 0x1)
 	/usr/local/go/src/runtime/checkptr.go:43 +0xbe fp=0xc00046b370 sp=0xc00046b340 pc=0x4397be
 github.com/segmentio/fasthash/jody.AddString64(0x1c26a908921dd5e0, 0xc000402dec, 0x4, 0x1c26a908921dd5e0)
 	/build/vendor/github.com/segmentio/fasthash/jody/hash.go:111 +0x3f0 fp=0xc00046b410 sp=0xc00046b370 pc=0xf42850