Why there are two type of hash function?

[zdyj3170101136]

i find there are two type of hash function.
one is https://github.com/minio/highwayhash for /proc/pid/mapping file.
the other is https://github.com/cespare/xxhash for debuginfo.

what is the difference?

[kakkoyun]

I think there are some performance differences. Kindly ping @brancz. Do you happen to remember the reason?

[brancz]

I think I benchmarked them against each other in parca-agent and highwayhash performed better. But I failed to keep the results around so we should repeat the experiment and document it this time.

[marselester]

In terms of speed they are similar.
Highwayhash requires 2 allocs per operation whereas xxhash requires 5.
Highwayhash allocates 88 bytes per operation more though: 33.0kB vs 32.9kB.

Details

$ go test -benchmem -count=10 -run=. -bench Hash ./pkg/debuginfo/ | tee bench.txt
goos: linux
goarch: amd64
pkg: github.com/parca-dev/parca-agent/pkg/debuginfo
cpu: Intel(R) Core(TM) i5-10600 CPU @ 3.30GHz
BenchmarkHash142mbXxhash-2        	   48273	     22215 ns/op	   32888 B/op	       5 allocs/op
BenchmarkHash142mbXxhash-2        	   53650	     21223 ns/op	   32888 B/op	       5 allocs/op
BenchmarkHash142mbXxhash-2        	   50102	     22062 ns/op	   32888 B/op	       5 allocs/op
BenchmarkHash142mbXxhash-2        	   66032	     19508 ns/op	   32888 B/op	       5 allocs/op
BenchmarkHash142mbXxhash-2        	   62894	     21680 ns/op	   32888 B/op	       5 allocs/op
BenchmarkHash142mbXxhash-2        	   69283	     23332 ns/op	   32888 B/op	       5 allocs/op
BenchmarkHash142mbXxhash-2        	   57036	     20587 ns/op	   32888 B/op	       5 allocs/op
BenchmarkHash142mbXxhash-2        	   69376	     25214 ns/op	   32888 B/op	       5 allocs/op
BenchmarkHash142mbXxhash-2        	   57848	     26335 ns/op	   32888 B/op	       5 allocs/op
BenchmarkHash142mbXxhash-2        	   51692	     25779 ns/op	   32888 B/op	       5 allocs/op
BenchmarkHash142mbHighwayhash-2   	   48436	     23156 ns/op	   32976 B/op	       2 allocs/op
BenchmarkHash142mbHighwayhash-2   	   70388	     20072 ns/op	   32976 B/op	       2 allocs/op
BenchmarkHash142mbHighwayhash-2   	   56131	     19872 ns/op	   32976 B/op	       2 allocs/op
BenchmarkHash142mbHighwayhash-2   	   67197	     22711 ns/op	   32976 B/op	       2 allocs/op
BenchmarkHash142mbHighwayhash-2   	   42259	     25584 ns/op	   32976 B/op	       2 allocs/op
BenchmarkHash142mbHighwayhash-2   	   65611	     23635 ns/op	   32976 B/op	       2 allocs/op
BenchmarkHash142mbHighwayhash-2   	   66428	     26096 ns/op	   32976 B/op	       2 allocs/op
BenchmarkHash142mbHighwayhash-2   	   52087	     21238 ns/op	   32976 B/op	       2 allocs/op
BenchmarkHash142mbHighwayhash-2   	   68560	     19946 ns/op	   32976 B/op	       2 allocs/op
BenchmarkHash142mbHighwayhash-2   	   46046	     22091 ns/op	   32976 B/op	       2 allocs/op
PASS
ok  	github.com/parca-dev/parca-agent/pkg/debuginfo	39.618s

$ grep Benchmark bench.txt | sed 's/Benchmark[A-z0-9]*/BenchmarkX/g' | split -l 10 -a 1 - bench_
$ benchstat bench_a bench_b
name  old time/op    new time/op    delta
X-2     22.8µs ±16%    22.4µs ±16%     ~     (p=0.853 n=10+10)

name  old alloc/op   new alloc/op   delta
X-2     32.9kB ± 0%    33.0kB ± 0%   +0.27%  (p=0.000 n=10+10)

name  old allocs/op  new allocs/op  delta
X-2       5.00 ± 0%      2.00 ± 0%  -60.00%  (p=0.000 n=10+10)

Details

import (
	// ...
	highwayhash "github.com/parca-dev/parca-agent/pkg/hash"
	xxhash "github.com/parca-dev/parca/pkg/hash"
)

var (
	hstr string
	hint uint64
)

func BenchmarkHash142mbXxhash(b *testing.B) {
	name := filepath.Join("../../dist", "parca")
	f, err := os.Open(name)
	if err != nil {
		b.Fatal(err)
	}
	b.Cleanup(func() {
		f.Close()
	})

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		hstr, err = xxhash.Reader(f)
		if err != nil {
			b.Fatal(err)
		}
	}
}

func BenchmarkHash142mbHighwayhash(b *testing.B) {
	name := filepath.Join("../../dist", "parca")
	f, err := os.Open(name)
	if err != nil {
		b.Fatal(err)
	}
	b.Cleanup(func() {
		f.Close()
	})

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		hint, err = highwayhash.Reader(f)
		if err != nil {
			b.Fatal(err)
		}
	}
}

[brancz]

I think it was initially for hashing the kallsyms file for resolving kernel symbols? Either way this is also awesome to have documented in this issue!