puzpuzpuz / xsync

Concurrent data structures for Go
Apache License 2.0
1.13k stars 40 forks source link

Fast zero-allocation universal hash function #107

Closed destel closed 1 year ago

destel commented 1 year ago

This pull request adds a fast generic hash functions that can be used in MapOf. This allowed to make two new constructors that do not require user to specify hash function manually

func NewUniversalMapOf[K comparable, V any]() *MapOf[K, V]
func NewUniversalMapOfPresized[K comparable, V any](sizeHint int) *MapOf[K, V]

The core idea behind is to create generic higher order function that can construct hash func for a specific comparable type.

hash := MakeHashFunc[string]()
seed := maphash.MakeSeed()
fmt.Println(hash(seed, "foo"), hash(seed, "bar"))

MakeHashFunc uses some reflection under the hood, but resulting function it produces is very fast zero-allocation hasher that's based on some unsafe magic (the same way as hashers that already exist in this package).

Below are the becnhmarks for different types

BenchmarkMakeHashFunc/int_hash-12                   1000000000           0.9810 ns/op          0 B/op          0 allocs/op
BenchmarkMakeHashFunc/string_hash-12                311438284            3.841 ns/op           0 B/op          0 allocs/op
BenchmarkMakeHashFunc/xsync_test.Point_hash-12      442970949            2.739 ns/op           0 B/op          0 allocs/op
BenchmarkMakeHashFunc/*xsync_test.Point_hash-12     1000000000           0.9841 ns/op          0 B/op          0 allocs/op
destel commented 1 year ago

Thank you very much for the feedback

puzpuzpuz commented 1 year ago

@destel many thanks on your contribution!