Debian Codegraph @

arc/arc_test.go

raw
1 // Copyright (c) HashiCorp, Inc.
2 // SPDX-License-Identifier: MPL-2.0
3
4 package arc
5
6 import (
7 "crypto/rand"
8 "math"
9 "math/big"
10 mathrand "math/rand"
11 "testing"
12 "time"
13 )
14
15 func getRand(tb testing.TB) int64 {
16 out, err := rand.Int(rand.Reader, big.NewInt(math.MaxInt64))
17 if err != nil {
18 tb.Fatal(err)
19 }
20 return out.Int64()
21 }
22
23 func init() {
24 mathrand.Seed(time.Now().Unix())
25 }
26
27 func BenchmarkARC_Rand(b *testing.B) {
28 l, err := NewARC[int64, int64](8192)
29 if err != nil {
30 b.Fatalf("err: %v", err)
31 }
32
33 trace := make([]int64, b.N*2)
34 for i := 0; i < b.N*2; i++ {
35 trace[i] = getRand(b) % 32768
36 }
37
38 b.ResetTimer()
39
40 var hit, miss int
41 for i := 0; i < 2*b.N; i++ {
42 if i%2 == 0 {
43 l.Add(trace[i], trace[i])
44 } else {
45 if _, ok := l.Get(trace[i]); ok {
46 hit++
47 } else {
48 miss++
49 }
50 }
51 }
52 b.Logf("hit: %d miss: %d ratio: %f", hit, miss, float64(hit)/float64(hit+miss))
53 }
54
55 func BenchmarkARC_Freq(b *testing.B) {
56 l, err := NewARC[int64, int64](8192)
57 if err != nil {
58 b.Fatalf("err: %v", err)
59 }
60
61 trace := make([]int64, b.N*2)
62 for i := 0; i < b.N*2; i++ {
63 if i%2 == 0 {
64 trace[i] = getRand(b) % 16384
65 } else {
66 trace[i] = getRand(b) % 32768
67 }
68 }
69
70 b.ResetTimer()
71
72 for i := 0; i < b.N; i++ {
73 l.Add(trace[i], trace[i])
74 }
75 var hit, miss int
76 for i := 0; i < b.N; i++ {
77 if _, ok := l.Get(trace[i]); ok {
78 hit++
79 } else {
80 miss++
81 }
82 }
83 b.Logf("hit: %d miss: %d ratio: %f", hit, miss, float64(hit)/float64(hit+miss))
84 }
85
86 func TestARC_RandomOps(t *testing.T) {
87 size := 128
88 l, err := NewARC[int64, int64](128)
89 if err != nil {
90 t.Fatalf("err: %v", err)
91 }
92
93 n := 200000
94 for i := 0; i < n; i++ {
95 key := getRand(t) % 512
96 r := getRand(t)
97 switch r % 3 {
98 case 0:
99 l.Add(key, key)
100 case 1:
101 l.Get(key)
102 case 2:
103 l.Remove(key)
104 }
105
106 if l.t1.Len()+l.t2.Len() > size {
107 t.Fatalf("bad: t1: %d t2: %d b1: %d b2: %d p: %d",
108 l.t1.Len(), l.t2.Len(), l.b1.Len(), l.b2.Len(), l.p)
109 }
110 if l.b1.Len()+l.b2.Len() > size {
111 t.Fatalf("bad: t1: %d t2: %d b1: %d b2: %d p: %d",
112 l.t1.Len(), l.t2.Len(), l.b1.Len(), l.b2.Len(), l.p)
113 }
114 }
115 }
116
117 func TestARC_Get_RecentToFrequent(t *testing.T) {
118 l, err := NewARC[int, int](128)
119 if err != nil {
120 t.Fatalf("err: %v", err)
121 }
122
123 // Touch all the entries, should be in t1
124 for i := 0; i < 128; i++ {
125 l.Add(i, i)
126 }
127 if n := l.t1.Len(); n != 128 {
128 t.Fatalf("bad: %d", n)
129 }
130 if n := l.t2.Len(); n != 0 {
131 t.Fatalf("bad: %d", n)
132 }
133
134 // Get should upgrade to t2
135 for i := 0; i < 128; i++ {
136 if _, ok := l.Get(i); !ok {
137 t.Fatalf("missing: %d", i)
138 }
139 }
140 if n := l.t1.Len(); n != 0 {
141 t.Fatalf("bad: %d", n)
142 }
143 if n := l.t2.Len(); n != 128 {
144 t.Fatalf("bad: %d", n)
145 }
146
147 // Get be from t2
148 for i := 0; i < 128; i++ {
149 if _, ok := l.Get(i); !ok {
150 t.Fatalf("missing: %d", i)
151 }
152 }
153 if n := l.t1.Len(); n != 0 {
154 t.Fatalf("bad: %d", n)
155 }
156 if n := l.t2.Len(); n != 128 {
157 t.Fatalf("bad: %d", n)
158 }
159 }
160
161 func TestARC_Add_RecentToFrequent(t *testing.T) {
162 l, err := NewARC[int, int](128)
163 if err != nil {
164 t.Fatalf("err: %v", err)
165 }
166
167 // Add initially to t1
168 l.Add(1, 1)
169 if n := l.t1.Len(); n != 1 {
170 t.Fatalf("bad: %d", n)
171 }
172 if n := l.t2.Len(); n != 0 {
173 t.Fatalf("bad: %d", n)
174 }
175
176 // Add should upgrade to t2
177 l.Add(1, 1)
178 if n := l.t1.Len(); n != 0 {
179 t.Fatalf("bad: %d", n)
180 }
181 if n := l.t2.Len(); n != 1 {
182 t.Fatalf("bad: %d", n)
183 }
184
185 // Add should remain in t2
186 l.Add(1, 1)
187 if n := l.t1.Len(); n != 0 {
188 t.Fatalf("bad: %d", n)
189 }
190 if n := l.t2.Len(); n != 1 {
191 t.Fatalf("bad: %d", n)
192 }
193 }
194
195 func TestARC_Adaptive(t *testing.T) {
196 l, err := NewARC[int, int](4)
197 if err != nil {
198 t.Fatalf("err: %v", err)
199 }
200
201 // Fill t1
202 for i := 0; i < 4; i++ {
203 l.Add(i, i)
204 }
205 if n := l.t1.Len(); n != 4 {
206 t.Fatalf("bad: %d", n)
207 }
208
209 // Move to t2
210 l.Get(0)
211 l.Get(1)
212 if n := l.t2.Len(); n != 2 {
213 t.Fatalf("bad: %d", n)
214 }
215
216 // Evict from t1
217 l.Add(4, 4)
218 if n := l.b1.Len(); n != 1 {
219 t.Fatalf("bad: %d", n)
220 }
221
222 // Current state
223 // t1 : (MRU) [4, 3] (LRU)
224 // t2 : (MRU) [1, 0] (LRU)
225 // b1 : (MRU) [2] (LRU)
226 // b2 : (MRU) [] (LRU)
227
228 // Add 2, should cause hit on b1
229 l.Add(2, 2)
230 if n := l.b1.Len(); n != 1 {
231 t.Fatalf("bad: %d", n)
232 }
233 if l.p != 1 {
234 t.Fatalf("bad: %d", l.p)
235 }
236 if n := l.t2.Len(); n != 3 {
237 t.Fatalf("bad: %d", n)
238 }
239
240 // Current state
241 // t1 : (MRU) [4] (LRU)
242 // t2 : (MRU) [2, 1, 0] (LRU)
243 // b1 : (MRU) [3] (LRU)
244 // b2 : (MRU) [] (LRU)
245
246 // Add 4, should migrate to t2
247 l.Add(4, 4)
248 if n := l.t1.Len(); n != 0 {
249 t.Fatalf("bad: %d", n)
250 }
251 if n := l.t2.Len(); n != 4 {
252 t.Fatalf("bad: %d", n)
253 }
254
255 // Current state
256 // t1 : (MRU) [] (LRU)
257 // t2 : (MRU) [4, 2, 1, 0] (LRU)
258 // b1 : (MRU) [3] (LRU)
259 // b2 : (MRU) [] (LRU)
260
261 // Add 4, should evict to b2
262 l.Add(5, 5)
263 if n := l.t1.Len(); n != 1 {
264 t.Fatalf("bad: %d", n)
265 }
266 if n := l.t2.Len(); n != 3 {
267 t.Fatalf("bad: %d", n)
268 }
269 if n := l.b2.Len(); n != 1 {
270 t.Fatalf("bad: %d", n)
271 }
272
273 // Current state
274 // t1 : (MRU) [5] (LRU)
275 // t2 : (MRU) [4, 2, 1] (LRU)
276 // b1 : (MRU) [3] (LRU)
277 // b2 : (MRU) [0] (LRU)
278
279 // Add 0, should decrease p
280 l.Add(0, 0)
281 if n := l.t1.Len(); n != 0 {
282 t.Fatalf("bad: %d", n)
283 }
284 if n := l.t2.Len(); n != 4 {
285 t.Fatalf("bad: %d", n)
286 }
287 if n := l.b1.Len(); n != 2 {
288 t.Fatalf("bad: %d", n)
289 }
290 if n := l.b2.Len(); n != 0 {
291 t.Fatalf("bad: %d", n)
292 }
293 if l.p != 0 {
294 t.Fatalf("bad: %d", l.p)
295 }
296
297 // Current state
298 // t1 : (MRU) [] (LRU)
299 // t2 : (MRU) [0, 4, 2, 1] (LRU)
300 // b1 : (MRU) [5, 3] (LRU)
301 // b2 : (MRU) [0] (LRU)
302 }
303
304 func TestARC(t *testing.T) {
305 l, err := NewARC[int, int](128)
306 if err != nil {
307 t.Fatalf("err: %v", err)
308 }
309
310 for i := 0; i < 256; i++ {
311 l.Add(i, i)
312 }
313 if l.Len() != 128 {
314 t.Fatalf("bad len: %v", l.Len())
315 }
316
317 for i, k := range l.Keys() {
318 if v, ok := l.Get(k); !ok || v != k || v != i+128 {
319 t.Fatalf("bad key: %v", k)
320 }
321 }
322 for i, v := range l.Values() {
323 if v != i+128 {
324 t.Fatalf("bad value: %v", v)
325 }
326 }
327 for i := 0; i < 128; i++ {
328 if _, ok := l.Get(i); ok {
329 t.Fatalf("should be evicted")
330 }
331 }
332 for i := 128; i < 256; i++ {
333 if _, ok := l.Get(i); !ok {
334 t.Fatalf("should not be evicted")
335 }
336 }
337 for i := 128; i < 192; i++ {
338 l.Remove(i)
339 if _, ok := l.Get(i); ok {
340 t.Fatalf("should be deleted")
341 }
342 }
343
344 l.Purge()
345 if l.Len() != 0 {
346 t.Fatalf("bad len: %v", l.Len())
347 }
348 if _, ok := l.Get(200); ok {
349 t.Fatalf("should contain nothing")
350 }
351 }
352
353 // Test that Contains doesn't update recent-ness
354 func TestARC_Contains(t *testing.T) {
355 l, err := NewARC[int, int](2)
356 if err != nil {
357 t.Fatalf("err: %v", err)
358 }
359
360 l.Add(1, 1)
361 l.Add(2, 2)
362 if !l.Contains(1) {
363 t.Errorf("1 should be contained")
364 }
365
366 l.Add(3, 3)
367 if l.Contains(1) {
368 t.Errorf("Contains should not have updated recent-ness of 1")
369 }
370 }
371
372 // Test that Peek doesn't update recent-ness
373 func TestARC_Peek(t *testing.T) {
374 l, err := NewARC[int, int](2)
375 if err != nil {
376 t.Fatalf("err: %v", err)
377 }
378
379 l.Add(1, 1)
380 l.Add(2, 2)
381 if v, ok := l.Peek(1); !ok || v != 1 {
382 t.Errorf("1 should be set to 1: %v, %v", v, ok)
383 }
384
385 l.Add(3, 3)
386 if l.Contains(1) {
387 t.Errorf("should not have updated recent-ness of 1")
388 }
389 }