Source file src/runtime/hash_test.go

Documentation: runtime

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

View as plain text