fxhash vs wyhash (uint64)

asm_amd64.s

#include "textflag.h"

TEXT ·memhash64(SB),NOSPLIT,$0-24
	// AX = data
	// BX = seed
	MOVQ    data+0(FP), AX
	MOVQ    seed+8(FP), BX
	MOVQ	BX, X0	// X0 = seed
	PINSRQ	$1, AX, X0	// data
	AESENC	runtime·aeskeysched+0(SB), X0
	AESENC	runtime·aeskeysched+16(SB), X0
	AESENC	runtime·aeskeysched+32(SB), X0
	MOVQ	X0, ret+16(FP)	// return X0
	RET

main.go

package main

import (
	"math/bits"
	_ "unsafe"
)

//go:linkname runtimefastrand runtime.fastrand
func runtimefastrand() uint32

func runtimefastrand64() uint64 {
	return (uint64(runtimefastrand()) << 32) | uint64(runtimefastrand())
}

var randseed uint64

func main() {
	var (
		testcount                        = 100
		badfxhash, badwyhash, badmemhash int
	)
	for i := 0; i < testcount; i++ {
		randseed = runtimefastrand64()
		badfxhash += hashBadCase1(fxhash)
	}
	for i := 0; i < testcount; i++ {
		randseed = runtimefastrand64()
		badwyhash += hashBadCase1(wyhash)
	}
	for i := 0; i < testcount; i++ {
		randseed = runtimefastrand64()
		badmemhash += hashBadCase1(memhash)
	}
	println("random inputs,", "fxhash:", badfxhash, "wyhash:", badwyhash, "memhash:", badmemhash)

	badfxhash, badwyhash = 0, 0
	for i := 0; i < testcount; i++ {
		randseed = runtimefastrand64()
		badfxhash += hashBadCase2(fxhash)
	}
	for i := 0; i < testcount; i++ {
		randseed = runtimefastrand64()
		badwyhash += hashBadCase2(wyhash)
	}
	for i := 0; i < testcount; i++ {
		randseed = runtimefastrand64()
		badmemhash += hashBadCase2(memhash)
	}
	println("linear inputs(1 .. N),", "fxhash:", badfxhash, "wyhash:", badwyhash, "memhash:", badmemhash)

	badfxhash, badwyhash = 0, 0
	for i := 0; i < testcount; i++ {
		randseed = runtimefastrand64()
		badfxhash += hashBadCase3(fxhash)
	}
	for i := 0; i < testcount; i++ {
		randseed = runtimefastrand64()
		badwyhash += hashBadCase3(wyhash)
	}
	for i := 0; i < testcount; i++ {
		randseed = runtimefastrand64()
		badmemhash += hashBadCase3(memhash)
	}
	println("shift inputs (1<<1 + 1 .. 1<<N + N),", "fxhash:", badfxhash, "wyhash:", badwyhash, "memhash:", badmemhash)
}

func fxhash(x uint64) uint64 {
	const K = 0x517cc1b727220a95
	return (bits.RotateLeft64(x, 5)^x)*K ^ randseed
}

func memhash64(x uint64, seed uint64) uint64

func memhash(x uint64) uint64 {
	return memhash64(x, randseed)
}

func wyhash(a uint64) uint64 {
	const (
		m1 = 0xa0761d6478bd642f
		m2 = 0xe7037ed1a0b428db
		m3 = 0x8ebc6af09c88c6e3
		m4 = 0x589965cc75374cc3
		m5 = 0x1d8e4e27c47d124f
	)
	return mix(m5^8, mix(a^m2, a^randseed^m1))
}

func mix(a, b uint64) uint64 {
	hi, lo := bits.Mul64(uint64(a), uint64(b))
	return uint64(hi ^ lo)
}

func hashBadCase1(hashf func(uint64) uint64) int {
	m := make(map[uint64]uint64, 0)
	for i := 0; i < 1<<16; i++ {
		v := hashf(runtimefastrand64()) % ((1 << 16) / 8)
		if pcount, ok := m[v]; ok {
			m[v] = pcount + 1
		} else {
			m[v] = 1
		}
	}
	var bad int
	for _, v := range m {
		if v > 8 {
			bad++
		}
	}
	return bad
}

func hashBadCase2(hashf func(uint64) uint64) int {
	m := make(map[uint64]uint64, 0)
	for i := 0; i < 1<<16; i++ {
		v := hashf(uint64(i)) % ((1 << 16) / 8)
		if pcount, ok := m[v]; ok {
			m[v] = pcount + 1
		} else {
			m[v] = 1
		}
	}
	var bad int
	for _, v := range m {
		if v > 8 {
			bad++
		}
	}
	return bad
}

func hashBadCase3(hashf func(uint64) uint64) int {
	m := make(map[uint64]uint64, 0)
	for i := 0; i < 1<<16; i++ {
		v := hashf(uint64((1<<i)+i)) % ((1 << 16) / 8)
		if pcount, ok := m[v]; ok {
			m[v] = pcount + 1
		} else {
			m[v] = 1
		}
	}
	var bad int
	for _, v := range m {
		if v > 8 {
			bad++
		}
	}
	return bad
}