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