vendor/github.com/hashicorp/golang-lru/2q_test.go

   1 package lru
   2
   3 import (
   4         "math/rand"
   5         "testing"
   6 )
   7
   8 func 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
  37 func 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
  69 func 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
  96 func 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
 142 func 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
 176 func 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
 223 func 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
 271 func 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
 290 func 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 }