vendor/github.com/hashicorp/golang-lru/arc_test.go

   1 package lru
   2
   3 import (
   4         "math/rand"
   5         "testing"
   6         "time"
   7 )
   8
   9 func init() {
  10         rand.Seed(time.Now().Unix())
  11 }
  12
  13 func 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
  42 func 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
  74 func 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
 105 func 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
 151 func 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
 185 func 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
 294 func 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
 342 func 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
 361 func 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 }