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