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