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