blob: e597eda3d0fd54909ea3e9d8fbb28dc02569e912 [file] [log] [blame]
package lru
import (
"math/rand"
"testing"
"time"
"google3/third_party/golang/cmp/cmp"
)
func init() {
rand.Seed(time.Now().Unix())
}
func BenchmarkARC_Rand(b *testing.B) {
l, err := NewARC(8192)
if err != nil {
b.Fatalf("err: %v", err)
}
trace := make([]int64, b.N*2)
for i := 0; i < b.N*2; i++ {
trace[i] = rand.Int63() % 32768
}
b.ResetTimer()
var hit, miss int
for i := 0; i < 2*b.N; i++ {
if i%2 == 0 {
l.Add(trace[i], trace[i])
} else {
_, ok := l.Get(trace[i])
if ok {
hit++
} else {
miss++
}
}
}
b.Logf("hit: %d miss: %d ratio: %f", hit, miss, float64(hit)/float64(miss))
}
func BenchmarkARC_Freq(b *testing.B) {
l, err := NewARC(8192)
if err != nil {
b.Fatalf("err: %v", err)
}
trace := make([]int64, b.N*2)
for i := 0; i < b.N*2; i++ {
if i%2 == 0 {
trace[i] = rand.Int63() % 16384
} else {
trace[i] = rand.Int63() % 32768
}
}
b.ResetTimer()
for i := 0; i < b.N; i++ {
l.Add(trace[i], trace[i])
}
var hit, miss int
for i := 0; i < b.N; i++ {
_, ok := l.Get(trace[i])
if ok {
hit++
} else {
miss++
}
}
b.Logf("hit: %d miss: %d ratio: %f", hit, miss, float64(hit)/float64(miss))
}
func TestARC_RandomOps(t *testing.T) {
size := 128
l, err := NewARC(128)
if err != nil {
t.Fatalf("err: %v", err)
}
n := 200000
for i := 0; i < n; i++ {
key := rand.Int63() % 512
r := rand.Int63()
switch r % 3 {
case 0:
l.Add(key, key)
case 1:
l.Get(key)
case 2:
l.Remove(key)
}
if l.t1.Len()+l.t2.Len() > size {
t.Fatalf("bad: t1: %d t2: %d b1: %d b2: %d p: %d",
l.t1.Len(), l.t2.Len(), l.b1.Len(), l.b2.Len(), l.p)
}
if l.b1.Len()+l.b2.Len() > size {
t.Fatalf("bad: t1: %d t2: %d b1: %d b2: %d p: %d",
l.t1.Len(), l.t2.Len(), l.b1.Len(), l.b2.Len(), l.p)
}
}
}
func TestARC_Get_RecentToFrequent(t *testing.T) {
l, err := NewARC(128)
if err != nil {
t.Fatalf("err: %v", err)
}
// Touch all the entries, should be in t1
for i := 0; i < 128; i++ {
l.Add(i, i)
}
if n := l.t1.Len(); n != 128 {
t.Fatalf("bad: %d", n)
}
if n := l.t2.Len(); n != 0 {
t.Fatalf("bad: %d", n)
}
// Get should upgrade to t2
for i := 0; i < 128; i++ {
_, ok := l.Get(i)
if !ok {
t.Fatalf("missing: %d", i)
}
}
if n := l.t1.Len(); n != 0 {
t.Fatalf("bad: %d", n)
}
if n := l.t2.Len(); n != 128 {
t.Fatalf("bad: %d", n)
}
// Get be from t2
for i := 0; i < 128; i++ {
_, ok := l.Get(i)
if !ok {
t.Fatalf("missing: %d", i)
}
}
if n := l.t1.Len(); n != 0 {
t.Fatalf("bad: %d", n)
}
if n := l.t2.Len(); n != 128 {
t.Fatalf("bad: %d", n)
}
}
func TestARC_Add_RecentToFrequent(t *testing.T) {
l, err := NewARC(128)
if err != nil {
t.Fatalf("err: %v", err)
}
// Add initially to t1
l.Add(1, 1)
if n := l.t1.Len(); n != 1 {
t.Fatalf("bad: %d", n)
}
if n := l.t2.Len(); n != 0 {
t.Fatalf("bad: %d", n)
}
// Add should upgrade to t2
l.Add(1, 1)
if n := l.t1.Len(); n != 0 {
t.Fatalf("bad: %d", n)
}
if n := l.t2.Len(); n != 1 {
t.Fatalf("bad: %d", n)
}
// Add should remain in t2
l.Add(1, 1)
if n := l.t1.Len(); n != 0 {
t.Fatalf("bad: %d", n)
}
if n := l.t2.Len(); n != 1 {
t.Fatalf("bad: %d", n)
}
}
func TestARC_Adaptive(t *testing.T) {
l, err := NewARC(4)
if err != nil {
t.Fatalf("err: %v", err)
}
// Fill t1
for i := 0; i < 4; i++ {
l.Add(i, i)
}
if n := l.t1.Len(); n != 4 {
t.Fatalf("bad: %d", n)
}
// Move to t2
l.Get(0)
l.Get(1)
if n := l.t2.Len(); n != 2 {
t.Fatalf("bad: %d", n)
}
// Evict from t1
l.Add(4, 4)
if n := l.b1.Len(); n != 1 {
t.Fatalf("bad: %d", n)
}
// Current state
// t1 : (MRU) [4, 3] (LRU)
// t2 : (MRU) [1, 0] (LRU)
// b1 : (MRU) [2] (LRU)
// b2 : (MRU) [] (LRU)
// Add 2, should cause hit on b1
l.Add(2, 2)
if n := l.b1.Len(); n != 1 {
t.Fatalf("bad: %d", n)
}
if l.p != 1 {
t.Fatalf("bad: %d", l.p)
}
if n := l.t2.Len(); n != 3 {
t.Fatalf("bad: %d", n)
}
// Current state
// t1 : (MRU) [4] (LRU)
// t2 : (MRU) [2, 1, 0] (LRU)
// b1 : (MRU) [3] (LRU)
// b2 : (MRU) [] (LRU)
// Add 4, should migrate to t2
l.Add(4, 4)
if n := l.t1.Len(); n != 0 {
t.Fatalf("bad: %d", n)
}
if n := l.t2.Len(); n != 4 {
t.Fatalf("bad: %d", n)
}
// Current state
// t1 : (MRU) [] (LRU)
// t2 : (MRU) [4, 2, 1, 0] (LRU)
// b1 : (MRU) [3] (LRU)
// b2 : (MRU) [] (LRU)
// Add 4, should evict to b2
l.Add(5, 5)
if n := l.t1.Len(); n != 1 {
t.Fatalf("bad: %d", n)
}
if n := l.t2.Len(); n != 3 {
t.Fatalf("bad: %d", n)
}
if n := l.b2.Len(); n != 1 {
t.Fatalf("bad: %d", n)
}
// Current state
// t1 : (MRU) [5] (LRU)
// t2 : (MRU) [4, 2, 1] (LRU)
// b1 : (MRU) [3] (LRU)
// b2 : (MRU) [0] (LRU)
// Add 0, should decrease p
l.Add(0, 0)
if n := l.t1.Len(); n != 0 {
t.Fatalf("bad: %d", n)
}
if n := l.t2.Len(); n != 4 {
t.Fatalf("bad: %d", n)
}
if n := l.b1.Len(); n != 2 {
t.Fatalf("bad: %d", n)
}
if n := l.b2.Len(); n != 0 {
t.Fatalf("bad: %d", n)
}
if l.p != 0 {
t.Fatalf("bad: %d", l.p)
}
// Current state
// t1 : (MRU) [] (LRU)
// t2 : (MRU) [0, 4, 2, 1] (LRU)
// b1 : (MRU) [5, 3] (LRU)
// b2 : (MRU) [0] (LRU)
}
func TestARC(t *testing.T) {
l, err := NewARC(128)
if err != nil {
t.Fatalf("err: %v", err)
}
for i := 0; i < 256; i++ {
l.Add(i, i)
}
if l.Len() != 128 {
t.Fatalf("bad len: %v", l.Len())
}
for i, k := range l.Keys() {
if v, ok := l.Get(k); !ok || v != k || v != i+128 {
t.Fatalf("bad key: %v", k)
}
}
for i := 0; i < 128; i++ {
_, ok := l.Get(i)
if ok {
t.Fatalf("should be evicted")
}
}
for i := 128; i < 256; i++ {
_, ok := l.Get(i)
if !ok {
t.Fatalf("should not be evicted")
}
}
for i := 128; i < 192; i++ {
l.Remove(i)
_, ok := l.Get(i)
if ok {
t.Fatalf("should be deleted")
}
}
l.Purge()
if l.Len() != 0 {
t.Fatalf("bad len: %v", l.Len())
}
if _, ok := l.Get(200); ok {
t.Fatalf("should contain nothing")
}
}
// Test that Contains doesn't update recent-ness
func TestARC_Contains(t *testing.T) {
l, err := NewARC(2)
if err != nil {
t.Fatalf("err: %v", err)
}
l.Add(1, 1)
l.Add(2, 2)
if !l.Contains(1) {
t.Errorf("1 should be contained")
}
l.Add(3, 3)
if l.Contains(1) {
t.Errorf("Contains should not have updated recent-ness of 1")
}
}
// Test that Peek doesn't update recent-ness
func TestARC_Peek(t *testing.T) {
l, err := NewARC(2)
if err != nil {
t.Fatalf("err: %v", err)
}
l.Add(1, 1)
l.Add(2, 2)
if v, ok := l.Peek(1); !ok || v != 1 {
t.Errorf("1 should be set to 1: %v, %v", v, ok)
}
l.Add(3, 3)
if l.Contains(1) {
t.Errorf("should not have updated recent-ness of 1")
}
}
func TestARC_OnEvictedCallback(t *testing.T) {
type testCase struct {
size int
data []int
evicted []int
}
testCases := map[string]testCase{
"basic-lru-like": {
size: 2,
data: []int{1, 2, 3, 4},
evicted: []int{1, 2},
},
"t1-to-t2-promotion-simple": {
size: 4,
data: []int{1, 2, 1, 2, 3, 4, 5, 6},
evicted: []int{3, 4},
},
"adaptive-replacement-simple": {
size: 4,
data: []int{1, 2, 3, 4, 5, 6, 1, 2, 7, 8},
evicted: []int{1, 2, 3, 4, 1, 5},
},
"MFU-not-evicted-by-new-entries": {
size: 4,
data: []int{4, 4, 1, 2, 3, 4, 5, 6, 7, 8},
evicted: []int{1, 2, 3, 5},
},
"t2-full-b2-empty-new-items": {
size: 4,
data: []int{
// fill t2, b2 should be empty since its target size is zero
1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8,
// insert "new" items
1, 2, 3, 4,
},
evicted: []int{1, 2, 3, 4, 5, 1, 2, 3},
},
}
runTest := func(t *testing.T, tc testCase) {
evicted := []int{}
c, err := NewARCWithEvict(tc.size, func(key interface{}, _ interface{}) {
evicted = append(evicted, key.(int))
})
if err != nil {
t.Fatal(err)
}
for _, val := range tc.data {
c.Add(val, val)
}
if !cmp.Equal(tc.evicted, evicted) {
t.Errorf("Expectations mismatch.\nWant: %+v\nGot: %+v", tc.evicted, evicted)
}
}
for name, tc := range testCases {
t.Run(name, func(t *testing.T) { runTest(t, tc) })
}
}