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