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
|
package clock //nolint:testpackage
import (
"sync/atomic"
"testing"
"lindenii.org/go/lgo/intconv"
)
func benchWeight(_, _ int) uint64 { return 1 }
// goroutineSeq hands each parallel worker a distinct starting offset
// so workers don't go in lockstep over identical keys.
//
//nolint:gochecknoglobals
var goroutineSeq atomic.Uint64
func workerOffset() int {
result, err := intconv.Uint64ToInt(goroutineSeq.Add(1) * 0x9E3779B1)
if err != nil {
panic(err)
}
return result
}
func BenchmarkReadHeavy(b *testing.B) {
// ≈95% Get hits, ≈5% Add, and fits budget.
const n = 100_000
clock := New(n, benchWeight)
for k := range n {
clock.Add(k, k)
}
b.ResetTimer()
b.RunParallel(func(pb *testing.PB) {
i := workerOffset()
for pb.Next() {
i++
key := i % n
if i%20 == 0 {
clock.Add(key, key)
} else {
_, _ = clock.Get(key)
}
}
})
}
func BenchmarkHotKey(b *testing.B) {
// Every worker does Get over a relatively small hot set.
const (
hot = 64
maxWeight = 4096
)
clock := New(maxWeight, benchWeight)
for k := range hot {
clock.Add(k, k)
}
b.ResetTimer()
b.RunParallel(func(pb *testing.PB) {
i := workerOffset()
for pb.Next() {
i++
_, _ = clock.Get(i % hot)
}
})
}
func BenchmarkMixed(b *testing.B) {
// Even split of Get and Add over a working set that fits.
const n = 100_000
clock := New(n, benchWeight)
for k := range n {
clock.Add(k, k)
}
b.ResetTimer()
b.RunParallel(func(pb *testing.PB) {
i := workerOffset()
for pb.Next() {
i++
key := i % n
if i%2 == 0 {
clock.Add(key, key)
} else {
_, _ = clock.Get(key)
}
}
})
}
func BenchmarkChurn(b *testing.B) {
// Every op inserts a fresh key into a small budget.
// I don't think this is likely to happen for git delta clocks,
// but this may matter if we use this for other workloads later.
const maxWeight = 4096
clock := New(maxWeight, benchWeight)
b.ResetTimer()
b.RunParallel(func(pb *testing.PB) {
base := workerOffset()
i := 0
for pb.Next() {
i++
clock.Add(base+i, i)
}
})
}
|
