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