From aaafafbdfe07754b771b824c71034f65c77cc76e Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Wed, 25 Jul 2018 09:18:08 +0200 Subject: add title caching --- vendor/github.com/hashicorp/golang-lru/2q_test.go | 306 ++++++++++++++++++++++ 1 file changed, 306 insertions(+) create mode 100644 vendor/github.com/hashicorp/golang-lru/2q_test.go (limited to 'vendor/github.com/hashicorp/golang-lru/2q_test.go') diff --git a/vendor/github.com/hashicorp/golang-lru/2q_test.go b/vendor/github.com/hashicorp/golang-lru/2q_test.go new file mode 100644 index 0000000..1b0f351 --- /dev/null +++ b/vendor/github.com/hashicorp/golang-lru/2q_test.go @@ -0,0 +1,306 @@ +package lru + +import ( + "math/rand" + "testing" +) + +func Benchmark2Q_Rand(b *testing.B) { + l, err := New2Q(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 Benchmark2Q_Freq(b *testing.B) { + l, err := New2Q(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 Test2Q_RandomOps(t *testing.T) { + size := 128 + l, err := New2Q(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.recent.Len()+l.frequent.Len() > size { + t.Fatalf("bad: recent: %d freq: %d", + l.recent.Len(), l.frequent.Len()) + } + } +} + +func Test2Q_Get_RecentToFrequent(t *testing.T) { + l, err := New2Q(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.recent.Len(); n != 128 { + t.Fatalf("bad: %d", n) + } + if n := l.frequent.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.recent.Len(); n != 0 { + t.Fatalf("bad: %d", n) + } + if n := l.frequent.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.recent.Len(); n != 0 { + t.Fatalf("bad: %d", n) + } + if n := l.frequent.Len(); n != 128 { + t.Fatalf("bad: %d", n) + } +} + +func Test2Q_Add_RecentToFrequent(t *testing.T) { + l, err := New2Q(128) + if err != nil { + t.Fatalf("err: %v", err) + } + + // Add initially to recent + l.Add(1, 1) + if n := l.recent.Len(); n != 1 { + t.Fatalf("bad: %d", n) + } + if n := l.frequent.Len(); n != 0 { + t.Fatalf("bad: %d", n) + } + + // Add should upgrade to frequent + l.Add(1, 1) + if n := l.recent.Len(); n != 0 { + t.Fatalf("bad: %d", n) + } + if n := l.frequent.Len(); n != 1 { + t.Fatalf("bad: %d", n) + } + + // Add should remain in frequent + l.Add(1, 1) + if n := l.recent.Len(); n != 0 { + t.Fatalf("bad: %d", n) + } + if n := l.frequent.Len(); n != 1 { + t.Fatalf("bad: %d", n) + } +} + +func Test2Q_Add_RecentEvict(t *testing.T) { + l, err := New2Q(4) + if err != nil { + t.Fatalf("err: %v", err) + } + + // Add 1,2,3,4,5 -> Evict 1 + l.Add(1, 1) + l.Add(2, 2) + l.Add(3, 3) + l.Add(4, 4) + l.Add(5, 5) + if n := l.recent.Len(); n != 4 { + t.Fatalf("bad: %d", n) + } + if n := l.recentEvict.Len(); n != 1 { + t.Fatalf("bad: %d", n) + } + if n := l.frequent.Len(); n != 0 { + t.Fatalf("bad: %d", n) + } + + // Pull in the recently evicted + l.Add(1, 1) + if n := l.recent.Len(); n != 3 { + t.Fatalf("bad: %d", n) + } + if n := l.recentEvict.Len(); n != 1 { + t.Fatalf("bad: %d", n) + } + if n := l.frequent.Len(); n != 1 { + t.Fatalf("bad: %d", n) + } + + // Add 6, should cause another recent evict + l.Add(6, 6) + if n := l.recent.Len(); n != 3 { + t.Fatalf("bad: %d", n) + } + if n := l.recentEvict.Len(); n != 2 { + t.Fatalf("bad: %d", n) + } + if n := l.frequent.Len(); n != 1 { + t.Fatalf("bad: %d", n) + } +} + +func Test2Q(t *testing.T) { + l, err := New2Q(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 Test2Q_Contains(t *testing.T) { + l, err := New2Q(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 Test2Q_Peek(t *testing.T) { + l, err := New2Q(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") + } +} -- cgit v1.2.3