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

View as plain text