Source file src/runtime/hash_test.go

     1  // Copyright 2013 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package runtime_test
     6  
     7  import (
     8  	"encoding/binary"
     9  	"fmt"
    10  	"internal/byteorder"
    11  	"internal/race"
    12  	"internal/testenv"
    13  	"math"
    14  	"math/rand"
    15  	"os"
    16  	. "runtime"
    17  	"slices"
    18  	"strings"
    19  	"testing"
    20  	"unsafe"
    21  )
    22  
    23  func TestMemHash32Equality(t *testing.T) {
    24  	if *UseAeshash {
    25  		t.Skip("skipping since AES hash implementation is used")
    26  	}
    27  	var b [4]byte
    28  	r := rand.New(rand.NewSource(1234))
    29  	seed := uintptr(r.Uint64())
    30  	for i := 0; i < 100; i++ {
    31  		randBytes(r, b[:])
    32  		got := MemHash32(unsafe.Pointer(&b), seed)
    33  		want := MemHash(unsafe.Pointer(&b), seed, 4)
    34  		if got != want {
    35  			t.Errorf("MemHash32(%x, %v) = %v; want %v", b, seed, got, want)
    36  		}
    37  	}
    38  }
    39  
    40  func TestMemHash64Equality(t *testing.T) {
    41  	if *UseAeshash {
    42  		t.Skip("skipping since AES hash implementation is used")
    43  	}
    44  	var b [8]byte
    45  	r := rand.New(rand.NewSource(1234))
    46  	seed := uintptr(r.Uint64())
    47  	for i := 0; i < 100; i++ {
    48  		randBytes(r, b[:])
    49  		got := MemHash64(unsafe.Pointer(&b), seed)
    50  		want := MemHash(unsafe.Pointer(&b), seed, 8)
    51  		if got != want {
    52  			t.Errorf("MemHash64(%x, %v) = %v; want %v", b, seed, got, want)
    53  		}
    54  	}
    55  }
    56  
    57  // Smhasher is a torture test for hash functions.
    58  // https://code.google.com/p/smhasher/
    59  // This code is a port of some of the Smhasher tests to Go.
    60  //
    61  // The current AES hash function passes Smhasher. Our fallback
    62  // hash functions don't, so we only enable the difficult tests when
    63  // we know the AES implementation is available.
    64  
    65  // Sanity checks.
    66  // hash should not depend on values outside key.
    67  // hash should not depend on alignment.
    68  func TestSmhasherSanity(t *testing.T) {
    69  	r := rand.New(rand.NewSource(1234))
    70  	const REP = 10
    71  	const KEYMAX = 128
    72  	const PAD = 16
    73  	const OFFMAX = 16
    74  	for k := 0; k < REP; k++ {
    75  		for n := 0; n < KEYMAX; n++ {
    76  			for i := 0; i < OFFMAX; i++ {
    77  				var b [KEYMAX + OFFMAX + 2*PAD]byte
    78  				var c [KEYMAX + OFFMAX + 2*PAD]byte
    79  				randBytes(r, b[:])
    80  				randBytes(r, c[:])
    81  				copy(c[PAD+i:PAD+i+n], b[PAD:PAD+n])
    82  				if BytesHash(b[PAD:PAD+n], 0) != BytesHash(c[PAD+i:PAD+i+n], 0) {
    83  					t.Errorf("hash depends on bytes outside key")
    84  				}
    85  			}
    86  		}
    87  	}
    88  }
    89  
    90  type HashSet struct {
    91  	list []uintptr // list of hashes added
    92  }
    93  
    94  func newHashSet() *HashSet {
    95  	return &HashSet{list: make([]uintptr, 0, 1024)}
    96  }
    97  func (s *HashSet) add(h uintptr) {
    98  	s.list = append(s.list, h)
    99  }
   100  func (s *HashSet) addS(x string) {
   101  	s.add(StringHash(x, 0))
   102  }
   103  func (s *HashSet) addB(x []byte) {
   104  	s.add(BytesHash(x, 0))
   105  }
   106  func (s *HashSet) addS_seed(x string, seed uintptr) {
   107  	s.add(StringHash(x, seed))
   108  }
   109  func (s *HashSet) check(t *testing.T) {
   110  	list := s.list
   111  	slices.Sort(list)
   112  
   113  	collisions := 0
   114  	for i := 1; i < len(list); i++ {
   115  		if list[i] == list[i-1] {
   116  			collisions++
   117  		}
   118  	}
   119  	n := len(list)
   120  
   121  	const SLOP = 50.0
   122  	pairs := int64(n) * int64(n-1) / 2
   123  	expected := float64(pairs) / math.Pow(2.0, float64(hashSize))
   124  	stddev := math.Sqrt(expected)
   125  	if float64(collisions) > expected+SLOP*(3*stddev+1) {
   126  		t.Errorf("unexpected number of collisions: got=%d mean=%f stddev=%f threshold=%f", collisions, expected, stddev, expected+SLOP*(3*stddev+1))
   127  	}
   128  	// Reset for reuse
   129  	s.list = s.list[:0]
   130  }
   131  
   132  // a string plus adding zeros must make distinct hashes
   133  func TestSmhasherAppendedZeros(t *testing.T) {
   134  	s := "hello" + strings.Repeat("\x00", 256)
   135  	h := newHashSet()
   136  	for i := 0; i <= len(s); i++ {
   137  		h.addS(s[:i])
   138  	}
   139  	h.check(t)
   140  }
   141  
   142  // All 0-3 byte strings have distinct hashes.
   143  func TestSmhasherSmallKeys(t *testing.T) {
   144  	if race.Enabled {
   145  		t.Skip("Too long for race mode")
   146  	}
   147  	testenv.ParallelOn64Bit(t)
   148  	h := newHashSet()
   149  	var b [3]byte
   150  	for i := 0; i < 256; i++ {
   151  		b[0] = byte(i)
   152  		h.addB(b[:1])
   153  		for j := 0; j < 256; j++ {
   154  			b[1] = byte(j)
   155  			h.addB(b[:2])
   156  			if !testing.Short() {
   157  				for k := 0; k < 256; k++ {
   158  					b[2] = byte(k)
   159  					h.addB(b[:3])
   160  				}
   161  			}
   162  		}
   163  	}
   164  	h.check(t)
   165  }
   166  
   167  // Different length strings of all zeros have distinct hashes.
   168  func TestSmhasherZeros(t *testing.T) {
   169  	t.Parallel()
   170  	N := 256 * 1024
   171  	if testing.Short() {
   172  		N = 1024
   173  	}
   174  	h := newHashSet()
   175  	b := make([]byte, N)
   176  	for i := 0; i <= N; i++ {
   177  		h.addB(b[:i])
   178  	}
   179  	h.check(t)
   180  }
   181  
   182  // Strings with up to two nonzero bytes all have distinct hashes.
   183  func TestSmhasherTwoNonzero(t *testing.T) {
   184  	if GOARCH == "wasm" {
   185  		t.Skip("Too slow on wasm")
   186  	}
   187  	if testing.Short() {
   188  		t.Skip("Skipping in short mode")
   189  	}
   190  	if race.Enabled {
   191  		t.Skip("Too long for race mode")
   192  	}
   193  	testenv.ParallelOn64Bit(t)
   194  	h := newHashSet()
   195  	for n := 2; n <= 16; n++ {
   196  		twoNonZero(h, n)
   197  	}
   198  	h.check(t)
   199  }
   200  func twoNonZero(h *HashSet, n int) {
   201  	b := make([]byte, n)
   202  
   203  	// all zero
   204  	h.addB(b)
   205  
   206  	// one non-zero byte
   207  	for i := 0; i < n; i++ {
   208  		for x := 1; x < 256; x++ {
   209  			b[i] = byte(x)
   210  			h.addB(b)
   211  			b[i] = 0
   212  		}
   213  	}
   214  
   215  	// two non-zero bytes
   216  	for i := 0; i < n; i++ {
   217  		for x := 1; x < 256; x++ {
   218  			b[i] = byte(x)
   219  			for j := i + 1; j < n; j++ {
   220  				for y := 1; y < 256; y++ {
   221  					b[j] = byte(y)
   222  					h.addB(b)
   223  					b[j] = 0
   224  				}
   225  			}
   226  			b[i] = 0
   227  		}
   228  	}
   229  }
   230  
   231  // Test strings with repeats, like "abcdabcdabcdabcd..."
   232  func TestSmhasherCyclic(t *testing.T) {
   233  	if testing.Short() {
   234  		t.Skip("Skipping in short mode")
   235  	}
   236  	if race.Enabled {
   237  		t.Skip("Too long for race mode")
   238  	}
   239  	t.Parallel()
   240  	r := rand.New(rand.NewSource(1234))
   241  	const REPEAT = 8
   242  	const N = 1000000
   243  	h := newHashSet()
   244  	for n := 4; n <= 12; n++ {
   245  		b := make([]byte, REPEAT*n)
   246  		for i := 0; i < N; i++ {
   247  			b[0] = byte(i * 79 % 97)
   248  			b[1] = byte(i * 43 % 137)
   249  			b[2] = byte(i * 151 % 197)
   250  			b[3] = byte(i * 199 % 251)
   251  			randBytes(r, b[4:n])
   252  			for j := n; j < n*REPEAT; j++ {
   253  				b[j] = b[j-n]
   254  			}
   255  			h.addB(b)
   256  		}
   257  		h.check(t)
   258  	}
   259  }
   260  
   261  // Test strings with only a few bits set
   262  func TestSmhasherSparse(t *testing.T) {
   263  	if GOARCH == "wasm" {
   264  		t.Skip("Too slow on wasm")
   265  	}
   266  	if testing.Short() {
   267  		t.Skip("Skipping in short mode")
   268  	}
   269  	t.Parallel()
   270  	h := newHashSet()
   271  	sparse(t, h, 32, 6)
   272  	sparse(t, h, 40, 6)
   273  	sparse(t, h, 48, 5)
   274  	sparse(t, h, 56, 5)
   275  	sparse(t, h, 64, 5)
   276  	sparse(t, h, 96, 4)
   277  	sparse(t, h, 256, 3)
   278  	sparse(t, h, 2048, 2)
   279  }
   280  func sparse(t *testing.T, h *HashSet, n int, k int) {
   281  	b := make([]byte, n/8)
   282  	setbits(h, b, 0, k)
   283  	h.check(t)
   284  }
   285  
   286  // set up to k bits at index i and greater
   287  func setbits(h *HashSet, b []byte, i int, k int) {
   288  	h.addB(b)
   289  	if k == 0 {
   290  		return
   291  	}
   292  	for j := i; j < len(b)*8; j++ {
   293  		b[j/8] |= byte(1 << uint(j&7))
   294  		setbits(h, b, j+1, k-1)
   295  		b[j/8] &= byte(^(1 << uint(j&7)))
   296  	}
   297  }
   298  
   299  // Test all possible combinations of n blocks from the set s.
   300  // "permutation" is a bad name here, but it is what Smhasher uses.
   301  func TestSmhasherPermutation(t *testing.T) {
   302  	if GOARCH == "wasm" {
   303  		t.Skip("Too slow on wasm")
   304  	}
   305  	if testing.Short() {
   306  		t.Skip("Skipping in short mode")
   307  	}
   308  	if race.Enabled {
   309  		t.Skip("Too long for race mode")
   310  	}
   311  	testenv.ParallelOn64Bit(t)
   312  	h := newHashSet()
   313  	permutation(t, h, []uint32{0, 1, 2, 3, 4, 5, 6, 7}, 8)
   314  	permutation(t, h, []uint32{0, 1 << 29, 2 << 29, 3 << 29, 4 << 29, 5 << 29, 6 << 29, 7 << 29}, 8)
   315  	permutation(t, h, []uint32{0, 1}, 20)
   316  	permutation(t, h, []uint32{0, 1 << 31}, 20)
   317  	permutation(t, h, []uint32{0, 1, 2, 3, 4, 5, 6, 7, 1 << 29, 2 << 29, 3 << 29, 4 << 29, 5 << 29, 6 << 29, 7 << 29}, 6)
   318  }
   319  func permutation(t *testing.T, h *HashSet, s []uint32, n int) {
   320  	b := make([]byte, n*4)
   321  	genPerm(h, b, s, 0)
   322  	h.check(t)
   323  }
   324  func genPerm(h *HashSet, b []byte, s []uint32, n int) {
   325  	h.addB(b[:n])
   326  	if n == len(b) {
   327  		return
   328  	}
   329  	for _, v := range s {
   330  		byteorder.LEPutUint32(b[n:], v)
   331  		genPerm(h, b, s, n+4)
   332  	}
   333  }
   334  
   335  type Key interface {
   336  	clear()              // set bits all to 0
   337  	random(r *rand.Rand) // set key to something random
   338  	bits() int           // how many bits key has
   339  	flipBit(i int)       // flip bit i of the key
   340  	hash() uintptr       // hash the key
   341  	name() string        // for error reporting
   342  }
   343  
   344  type BytesKey struct {
   345  	b []byte
   346  }
   347  
   348  func (k *BytesKey) clear() {
   349  	clear(k.b)
   350  }
   351  func (k *BytesKey) random(r *rand.Rand) {
   352  	randBytes(r, k.b)
   353  }
   354  func (k *BytesKey) bits() int {
   355  	return len(k.b) * 8
   356  }
   357  func (k *BytesKey) flipBit(i int) {
   358  	k.b[i>>3] ^= byte(1 << uint(i&7))
   359  }
   360  func (k *BytesKey) hash() uintptr {
   361  	return BytesHash(k.b, 0)
   362  }
   363  func (k *BytesKey) name() string {
   364  	return fmt.Sprintf("bytes%d", len(k.b))
   365  }
   366  
   367  type Int32Key struct {
   368  	i uint32
   369  }
   370  
   371  func (k *Int32Key) clear() {
   372  	k.i = 0
   373  }
   374  func (k *Int32Key) random(r *rand.Rand) {
   375  	k.i = r.Uint32()
   376  }
   377  func (k *Int32Key) bits() int {
   378  	return 32
   379  }
   380  func (k *Int32Key) flipBit(i int) {
   381  	k.i ^= 1 << uint(i)
   382  }
   383  func (k *Int32Key) hash() uintptr {
   384  	return Int32Hash(k.i, 0)
   385  }
   386  func (k *Int32Key) name() string {
   387  	return "int32"
   388  }
   389  
   390  type Int64Key struct {
   391  	i uint64
   392  }
   393  
   394  func (k *Int64Key) clear() {
   395  	k.i = 0
   396  }
   397  func (k *Int64Key) random(r *rand.Rand) {
   398  	k.i = uint64(r.Uint32()) + uint64(r.Uint32())<<32
   399  }
   400  func (k *Int64Key) bits() int {
   401  	return 64
   402  }
   403  func (k *Int64Key) flipBit(i int) {
   404  	k.i ^= 1 << uint(i)
   405  }
   406  func (k *Int64Key) hash() uintptr {
   407  	return Int64Hash(k.i, 0)
   408  }
   409  func (k *Int64Key) name() string {
   410  	return "int64"
   411  }
   412  
   413  type EfaceKey struct {
   414  	i any
   415  }
   416  
   417  func (k *EfaceKey) clear() {
   418  	k.i = nil
   419  }
   420  func (k *EfaceKey) random(r *rand.Rand) {
   421  	k.i = uint64(r.Int63())
   422  }
   423  func (k *EfaceKey) bits() int {
   424  	// use 64 bits. This tests inlined interfaces
   425  	// on 64-bit targets and indirect interfaces on
   426  	// 32-bit targets.
   427  	return 64
   428  }
   429  func (k *EfaceKey) flipBit(i int) {
   430  	k.i = k.i.(uint64) ^ uint64(1)<<uint(i)
   431  }
   432  func (k *EfaceKey) hash() uintptr {
   433  	return EfaceHash(k.i, 0)
   434  }
   435  func (k *EfaceKey) name() string {
   436  	return "Eface"
   437  }
   438  
   439  type IfaceKey struct {
   440  	i interface {
   441  		F()
   442  	}
   443  }
   444  type fInter uint64
   445  
   446  func (x fInter) F() {
   447  }
   448  
   449  func (k *IfaceKey) clear() {
   450  	k.i = nil
   451  }
   452  func (k *IfaceKey) random(r *rand.Rand) {
   453  	k.i = fInter(r.Int63())
   454  }
   455  func (k *IfaceKey) bits() int {
   456  	// use 64 bits. This tests inlined interfaces
   457  	// on 64-bit targets and indirect interfaces on
   458  	// 32-bit targets.
   459  	return 64
   460  }
   461  func (k *IfaceKey) flipBit(i int) {
   462  	k.i = k.i.(fInter) ^ fInter(1)<<uint(i)
   463  }
   464  func (k *IfaceKey) hash() uintptr {
   465  	return IfaceHash(k.i, 0)
   466  }
   467  func (k *IfaceKey) name() string {
   468  	return "Iface"
   469  }
   470  
   471  // Flipping a single bit of a key should flip each output bit with 50% probability.
   472  func TestSmhasherAvalanche(t *testing.T) {
   473  	if GOARCH == "wasm" {
   474  		t.Skip("Too slow on wasm")
   475  	}
   476  	if testing.Short() {
   477  		t.Skip("Skipping in short mode")
   478  	}
   479  	if race.Enabled {
   480  		t.Skip("Too long for race mode")
   481  	}
   482  	t.Parallel()
   483  	avalancheTest1(t, &BytesKey{make([]byte, 2)})
   484  	avalancheTest1(t, &BytesKey{make([]byte, 4)})
   485  	avalancheTest1(t, &BytesKey{make([]byte, 8)})
   486  	avalancheTest1(t, &BytesKey{make([]byte, 16)})
   487  	avalancheTest1(t, &BytesKey{make([]byte, 32)})
   488  	avalancheTest1(t, &BytesKey{make([]byte, 200)})
   489  	avalancheTest1(t, &Int32Key{})
   490  	avalancheTest1(t, &Int64Key{})
   491  	avalancheTest1(t, &EfaceKey{})
   492  	avalancheTest1(t, &IfaceKey{})
   493  }
   494  func avalancheTest1(t *testing.T, k Key) {
   495  	const REP = 100000
   496  	r := rand.New(rand.NewSource(1234))
   497  	n := k.bits()
   498  
   499  	// grid[i][j] is a count of whether flipping
   500  	// input bit i affects output bit j.
   501  	grid := make([][hashSize]int, n)
   502  
   503  	for z := 0; z < REP; z++ {
   504  		// pick a random key, hash it
   505  		k.random(r)
   506  		h := k.hash()
   507  
   508  		// flip each bit, hash & compare the results
   509  		for i := 0; i < n; i++ {
   510  			k.flipBit(i)
   511  			d := h ^ k.hash()
   512  			k.flipBit(i)
   513  
   514  			// record the effects of that bit flip
   515  			g := &grid[i]
   516  			for j := 0; j < hashSize; j++ {
   517  				g[j] += int(d & 1)
   518  				d >>= 1
   519  			}
   520  		}
   521  	}
   522  
   523  	// Each entry in the grid should be about REP/2.
   524  	// More precisely, we did N = k.bits() * hashSize experiments where
   525  	// each is the sum of REP coin flips. We want to find bounds on the
   526  	// sum of coin flips such that a truly random experiment would have
   527  	// all sums inside those bounds with 99% probability.
   528  	N := n * hashSize
   529  	var c float64
   530  	// find c such that Prob(mean-c*stddev < x < mean+c*stddev)^N > .9999
   531  	for c = 0.0; math.Pow(math.Erf(c/math.Sqrt(2)), float64(N)) < .9999; c += .1 {
   532  	}
   533  	c *= 11.0 // allowed slack: 40% to 60% - we don't need to be perfectly random
   534  	mean := .5 * REP
   535  	stddev := .5 * math.Sqrt(REP)
   536  	low := int(mean - c*stddev)
   537  	high := int(mean + c*stddev)
   538  	for i := 0; i < n; i++ {
   539  		for j := 0; j < hashSize; j++ {
   540  			x := grid[i][j]
   541  			if x < low || x > high {
   542  				t.Errorf("bad bias for %s bit %d -> bit %d: %d/%d\n", k.name(), i, j, x, REP)
   543  			}
   544  		}
   545  	}
   546  }
   547  
   548  // All bit rotations of a set of distinct keys
   549  func TestSmhasherWindowed(t *testing.T) {
   550  	if race.Enabled {
   551  		t.Skip("Too long for race mode")
   552  	}
   553  	t.Parallel()
   554  	h := newHashSet()
   555  	t.Logf("32 bit keys")
   556  	windowed(t, h, &Int32Key{})
   557  	t.Logf("64 bit keys")
   558  	windowed(t, h, &Int64Key{})
   559  	t.Logf("string keys")
   560  	windowed(t, h, &BytesKey{make([]byte, 128)})
   561  }
   562  func windowed(t *testing.T, h *HashSet, k Key) {
   563  	if GOARCH == "wasm" {
   564  		t.Skip("Too slow on wasm")
   565  	}
   566  	if PtrSize == 4 {
   567  		// This test tends to be flaky on 32-bit systems.
   568  		// There's not enough bits in the hash output, so we
   569  		// expect a nontrivial number of collisions, and it is
   570  		// often quite a bit higher than expected. See issue 43130.
   571  		t.Skip("Flaky on 32-bit systems")
   572  	}
   573  	if testing.Short() {
   574  		t.Skip("Skipping in short mode")
   575  	}
   576  	const BITS = 16
   577  
   578  	for r := 0; r < k.bits(); r++ {
   579  		for i := 0; i < 1<<BITS; i++ {
   580  			k.clear()
   581  			for j := 0; j < BITS; j++ {
   582  				if i>>uint(j)&1 != 0 {
   583  					k.flipBit((j + r) % k.bits())
   584  				}
   585  			}
   586  			h.add(k.hash())
   587  		}
   588  		h.check(t)
   589  	}
   590  }
   591  
   592  // All keys of the form prefix + [A-Za-z0-9]*N + suffix.
   593  func TestSmhasherText(t *testing.T) {
   594  	if testing.Short() {
   595  		t.Skip("Skipping in short mode")
   596  	}
   597  	t.Parallel()
   598  	h := newHashSet()
   599  	text(t, h, "Foo", "Bar")
   600  	text(t, h, "FooBar", "")
   601  	text(t, h, "", "FooBar")
   602  }
   603  func text(t *testing.T, h *HashSet, prefix, suffix string) {
   604  	const N = 4
   605  	const S = "ABCDEFGHIJKLMNOPQRSTabcdefghijklmnopqrst0123456789"
   606  	const L = len(S)
   607  	b := make([]byte, len(prefix)+N+len(suffix))
   608  	copy(b, prefix)
   609  	copy(b[len(prefix)+N:], suffix)
   610  	c := b[len(prefix):]
   611  	for i := 0; i < L; i++ {
   612  		c[0] = S[i]
   613  		for j := 0; j < L; j++ {
   614  			c[1] = S[j]
   615  			for k := 0; k < L; k++ {
   616  				c[2] = S[k]
   617  				for x := 0; x < L; x++ {
   618  					c[3] = S[x]
   619  					h.addB(b)
   620  				}
   621  			}
   622  		}
   623  	}
   624  	h.check(t)
   625  }
   626  
   627  // Make sure different seed values generate different hashes.
   628  func TestSmhasherSeed(t *testing.T) {
   629  	h := newHashSet()
   630  	const N = 100000
   631  	s := "hello"
   632  	for i := 0; i < N; i++ {
   633  		h.addS_seed(s, uintptr(i))
   634  	}
   635  	h.check(t)
   636  }
   637  
   638  func TestIssue66841(t *testing.T) {
   639  	if *UseAeshash && os.Getenv("TEST_ISSUE_66841") == "" {
   640  		// We want to test the backup hash, so if we're running on a machine
   641  		// that uses aeshash, exec ourselves while turning aes off.
   642  		cmd := testenv.CleanCmdEnv(testenv.Command(t, testenv.Executable(t), "-test.run=^TestIssue66841$"))
   643  		cmd.Env = append(cmd.Env, "GODEBUG=cpu.aes=off", "TEST_ISSUE_66841=1")
   644  		out, err := cmd.CombinedOutput()
   645  		if err != nil {
   646  			t.Errorf("%s", string(out))
   647  		}
   648  		// Fall through. Might as well run this test when aeshash is on also.
   649  	}
   650  	h := newHashSet()
   651  	var b [16]byte
   652  	binary.LittleEndian.PutUint64(b[:8], 0xe7037ed1a0b428db) // runtime.m2
   653  	for i := 0; i < 1000; i++ {
   654  		binary.LittleEndian.PutUint64(b[8:], uint64(i))
   655  		h.addB(b[:])
   656  	}
   657  	h.check(t)
   658  }
   659  
   660  // size of the hash output (32 or 64 bits)
   661  const hashSize = 32 + int(^uintptr(0)>>63<<5)
   662  
   663  func randBytes(r *rand.Rand, b []byte) {
   664  	for i := range b {
   665  		b[i] = byte(r.Uint32())
   666  	}
   667  }
   668  
   669  func benchmarkHash(b *testing.B, n int) {
   670  	s := strings.Repeat("A", n)
   671  
   672  	for i := 0; i < b.N; i++ {
   673  		StringHash(s, 0)
   674  	}
   675  	b.SetBytes(int64(n))
   676  }
   677  
   678  func BenchmarkHash5(b *testing.B)     { benchmarkHash(b, 5) }
   679  func BenchmarkHash16(b *testing.B)    { benchmarkHash(b, 16) }
   680  func BenchmarkHash64(b *testing.B)    { benchmarkHash(b, 64) }
   681  func BenchmarkHash1024(b *testing.B)  { benchmarkHash(b, 1024) }
   682  func BenchmarkHash65536(b *testing.B) { benchmarkHash(b, 65536) }
   683  
   684  func TestArrayHash(t *testing.T) {
   685  	// Make sure that "" in arrays hash correctly. The hash
   686  	// should at least scramble the input seed so that, e.g.,
   687  	// {"","foo"} and {"foo",""} have different hashes.
   688  
   689  	// If the hash is bad, then all (8 choose 4) = 70 keys
   690  	// have the same hash. If so, we allocate 70/8 = 8
   691  	// overflow buckets. If the hash is good we don't
   692  	// normally allocate any overflow buckets, and the
   693  	// probability of even one or two overflows goes down rapidly.
   694  	// (There is always 1 allocation of the bucket array. The map
   695  	// header is allocated on the stack.)
   696  	f := func() {
   697  		// Make the key type at most 128 bytes. Otherwise,
   698  		// we get an allocation per key.
   699  		type key [8]string
   700  		m := make(map[key]bool, 70)
   701  
   702  		// fill m with keys that have 4 "foo"s and 4 ""s.
   703  		for i := 0; i < 256; i++ {
   704  			var k key
   705  			cnt := 0
   706  			for j := uint(0); j < 8; j++ {
   707  				if i>>j&1 != 0 {
   708  					k[j] = "foo"
   709  					cnt++
   710  				}
   711  			}
   712  			if cnt == 4 {
   713  				m[k] = true
   714  			}
   715  		}
   716  		if len(m) != 70 {
   717  			t.Errorf("bad test: (8 choose 4) should be 70, not %d", len(m))
   718  		}
   719  	}
   720  	if n := testing.AllocsPerRun(10, f); n > 6 {
   721  		t.Errorf("too many allocs %f - hash not balanced", n)
   722  	}
   723  }
   724  func TestStructHash(t *testing.T) {
   725  	// See the comment in TestArrayHash.
   726  	f := func() {
   727  		type key struct {
   728  			a, b, c, d, e, f, g, h string
   729  		}
   730  		m := make(map[key]bool, 70)
   731  
   732  		// fill m with keys that have 4 "foo"s and 4 ""s.
   733  		for i := 0; i < 256; i++ {
   734  			var k key
   735  			cnt := 0
   736  			if i&1 != 0 {
   737  				k.a = "foo"
   738  				cnt++
   739  			}
   740  			if i&2 != 0 {
   741  				k.b = "foo"
   742  				cnt++
   743  			}
   744  			if i&4 != 0 {
   745  				k.c = "foo"
   746  				cnt++
   747  			}
   748  			if i&8 != 0 {
   749  				k.d = "foo"
   750  				cnt++
   751  			}
   752  			if i&16 != 0 {
   753  				k.e = "foo"
   754  				cnt++
   755  			}
   756  			if i&32 != 0 {
   757  				k.f = "foo"
   758  				cnt++
   759  			}
   760  			if i&64 != 0 {
   761  				k.g = "foo"
   762  				cnt++
   763  			}
   764  			if i&128 != 0 {
   765  				k.h = "foo"
   766  				cnt++
   767  			}
   768  			if cnt == 4 {
   769  				m[k] = true
   770  			}
   771  		}
   772  		if len(m) != 70 {
   773  			t.Errorf("bad test: (8 choose 4) should be 70, not %d", len(m))
   774  		}
   775  	}
   776  	if n := testing.AllocsPerRun(10, f); n > 6 {
   777  		t.Errorf("too many allocs %f - hash not balanced", n)
   778  	}
   779  }
   780  
   781  var sink uint64
   782  
   783  func BenchmarkAlignedLoad(b *testing.B) {
   784  	var buf [16]byte
   785  	p := unsafe.Pointer(&buf[0])
   786  	var s uint64
   787  	for i := 0; i < b.N; i++ {
   788  		s += ReadUnaligned64(p)
   789  	}
   790  	sink = s
   791  }
   792  
   793  func BenchmarkUnalignedLoad(b *testing.B) {
   794  	var buf [16]byte
   795  	p := unsafe.Pointer(&buf[1])
   796  	var s uint64
   797  	for i := 0; i < b.N; i++ {
   798  		s += ReadUnaligned64(p)
   799  	}
   800  	sink = s
   801  }
   802  
   803  func TestCollisions(t *testing.T) {
   804  	if testing.Short() {
   805  		t.Skip("Skipping in short mode")
   806  	}
   807  	t.Parallel()
   808  	for i := 0; i < 16; i++ {
   809  		for j := 0; j < 16; j++ {
   810  			if j == i {
   811  				continue
   812  			}
   813  			var a [16]byte
   814  			m := make(map[uint16]struct{}, 1<<16)
   815  			for n := 0; n < 1<<16; n++ {
   816  				a[i] = byte(n)
   817  				a[j] = byte(n >> 8)
   818  				m[uint16(BytesHash(a[:], 0))] = struct{}{}
   819  			}
   820  			// N balls in N bins, for N=65536
   821  			avg := 41427
   822  			stdDev := 123
   823  			if len(m) < avg-40*stdDev || len(m) > avg+40*stdDev {
   824  				t.Errorf("bad number of collisions i=%d j=%d outputs=%d out of 65536\n", i, j, len(m))
   825  			}
   826  		}
   827  	}
   828  }
   829  

View as plain text