arc_test.go

Documentation: github.com/hashicorp/golang-lru

     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] = getRand(b) % 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] = getRand(b) % 16384
    52  		} else {
    53  			trace[i] = getRand(b) % 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 := getRand(t) % 512
    84  		r := getRand(t)
    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  }
   378
View as plain text