...
Run Format

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

View as plain text