1// Copyright 2017 The Bazel 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 5package starlark 6 7import ( 8 "fmt" 9 "math/rand" 10 "sync" 11 "testing" 12) 13 14func TestHashtable(t *testing.T) { 15 makeTestIntsOnce.Do(makeTestInts) 16 testHashtable(t, make(map[int]bool)) 17} 18 19func BenchmarkStringHash(b *testing.B) { 20 for len := 1; len <= 1024; len *= 2 { 21 buf := make([]byte, len) 22 rand.New(rand.NewSource(0)).Read(buf) 23 s := string(buf) 24 25 b.Run(fmt.Sprintf("hard-%d", len), func(b *testing.B) { 26 for i := 0; i < b.N; i++ { 27 hashString(s) 28 } 29 }) 30 b.Run(fmt.Sprintf("soft-%d", len), func(b *testing.B) { 31 for i := 0; i < b.N; i++ { 32 softHashString(s) 33 } 34 }) 35 } 36} 37 38func BenchmarkHashtable(b *testing.B) { 39 makeTestIntsOnce.Do(makeTestInts) 40 b.ResetTimer() 41 for i := 0; i < b.N; i++ { 42 testHashtable(b, nil) 43 } 44} 45 46const testIters = 10000 47 48var ( 49 // testInts is a zipf-distributed array of Ints and corresponding ints. 50 // This removes the cost of generating them on the fly during benchmarking. 51 // Without this, Zipf and MakeInt dominate CPU and memory costs, respectively. 52 makeTestIntsOnce sync.Once 53 testInts [3 * testIters]struct { 54 Int Int 55 goInt int 56 } 57) 58 59func makeTestInts() { 60 zipf := rand.NewZipf(rand.New(rand.NewSource(0)), 1.1, 1.0, 1000.0) 61 for i := range &testInts { 62 r := int(zipf.Uint64()) 63 testInts[i].goInt = r 64 testInts[i].Int = MakeInt(r) 65 } 66} 67 68// testHashtable is both a test and a benchmark of hashtable. 69// When sane != nil, it acts as a test against the semantics of Go's map. 70func testHashtable(tb testing.TB, sane map[int]bool) { 71 var i int // index into testInts 72 73 var ht hashtable 74 75 // Insert 10000 random ints into the map. 76 for j := 0; j < testIters; j++ { 77 k := testInts[i] 78 i++ 79 if err := ht.insert(k.Int, None); err != nil { 80 tb.Fatal(err) 81 } 82 if sane != nil { 83 sane[k.goInt] = true 84 } 85 } 86 87 // Do 10000 random lookups in the map. 88 for j := 0; j < testIters; j++ { 89 k := testInts[i] 90 i++ 91 _, found, err := ht.lookup(k.Int) 92 if err != nil { 93 tb.Fatal(err) 94 } 95 if sane != nil { 96 _, found2 := sane[k.goInt] 97 if found != found2 { 98 tb.Fatal("sanity check failed") 99 } 100 } 101 } 102 103 // Do 10000 random deletes from the map. 104 for j := 0; j < testIters; j++ { 105 k := testInts[i] 106 i++ 107 _, found, err := ht.delete(k.Int) 108 if err != nil { 109 tb.Fatal(err) 110 } 111 if sane != nil { 112 _, found2 := sane[k.goInt] 113 if found != found2 { 114 tb.Fatal("sanity check failed") 115 } 116 delete(sane, k.goInt) 117 } 118 } 119 120 if sane != nil { 121 if int(ht.len) != len(sane) { 122 tb.Fatal("sanity check failed") 123 } 124 } 125} 126