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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
// 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")
}
}
}
func TestHashtableCount(t *testing.T) {
const count = 1000
ht := new(hashtable)
for i := 0; i < count; i++ {
ht.insert(MakeInt(i), None)
}
if c, err := ht.count(rangeValue{0, count, 1, count}.Iterate()); err != nil {
t.Error(err)
} else if c != count {
t.Errorf("count doesn't match: expected %d got %d", count, c)
}
}
|
