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