From b5fa10fd109e9118a5ad034b25305e16ebcb5d49 Mon Sep 17 00:00:00 2001 From: Runxi Yu Date: Thu, 11 Jun 2026 11:22:47 +0000 Subject: internal/cache/clock: Rename Cache to Clock --- internal/cache/clock/bench_test.go | 28 ++++----- internal/cache/clock/cache.go | 86 --------------------------- internal/cache/clock/cache_ops.go | 51 ---------------- internal/cache/clock/cache_test.go | 100 -------------------------------- internal/cache/clock/clock.go | 86 +++++++++++++++++++++++++++ internal/cache/clock/clock_ops.go | 51 ++++++++++++++++ internal/cache/clock/clock_test.go | 100 ++++++++++++++++++++++++++++++++ internal/cache/clock/concurrent_test.go | 24 ++++---- internal/cache/clock/invariant_test.go | 4 +- 9 files changed, 265 insertions(+), 265 deletions(-) delete mode 100644 internal/cache/clock/cache.go delete mode 100644 internal/cache/clock/cache_ops.go delete mode 100644 internal/cache/clock/cache_test.go create mode 100644 internal/cache/clock/clock.go create mode 100644 internal/cache/clock/clock_ops.go create mode 100644 internal/cache/clock/clock_test.go diff --git a/internal/cache/clock/bench_test.go b/internal/cache/clock/bench_test.go index 917aac3b..48bdff99 100644 --- a/internal/cache/clock/bench_test.go +++ b/internal/cache/clock/bench_test.go @@ -28,9 +28,9 @@ func BenchmarkReadHeavy(b *testing.B) { // ≈95% Get hits, ≈5% Add, and fits budget. const n = 100_000 - cache := New(n, benchWeight) + clock := New(n, benchWeight) for k := range n { - cache.Add(k, k) + clock.Add(k, k) } b.ResetTimer() @@ -41,9 +41,9 @@ func BenchmarkReadHeavy(b *testing.B) { key := i % n if i%20 == 0 { - cache.Add(key, key) + clock.Add(key, key) } else { - _, _ = cache.Get(key) + _, _ = clock.Get(key) } } }) @@ -56,9 +56,9 @@ func BenchmarkHotKey(b *testing.B) { maxWeight = 4096 ) - cache := New(maxWeight, benchWeight) + clock := New(maxWeight, benchWeight) for k := range hot { - cache.Add(k, k) + clock.Add(k, k) } b.ResetTimer() @@ -66,7 +66,7 @@ func BenchmarkHotKey(b *testing.B) { i := workerOffset() for pb.Next() { i++ - _, _ = cache.Get(i % hot) + _, _ = clock.Get(i % hot) } }) } @@ -75,9 +75,9 @@ func BenchmarkMixed(b *testing.B) { // Even split of Get and Add over a working set that fits. const n = 100_000 - cache := New(n, benchWeight) + clock := New(n, benchWeight) for k := range n { - cache.Add(k, k) + clock.Add(k, k) } b.ResetTimer() @@ -88,9 +88,9 @@ func BenchmarkMixed(b *testing.B) { key := i % n if i%2 == 0 { - cache.Add(key, key) + clock.Add(key, key) } else { - _, _ = cache.Get(key) + _, _ = clock.Get(key) } } }) @@ -98,11 +98,11 @@ func BenchmarkMixed(b *testing.B) { func BenchmarkChurn(b *testing.B) { // Every op inserts a fresh key into a small budget. - // I don't think this is likely to happen for git delta caches, + // I don't think this is likely to happen for git delta clocks, // but this may matter if we use this for other workloads later. const maxWeight = 4096 - cache := New(maxWeight, benchWeight) + clock := New(maxWeight, benchWeight) b.ResetTimer() b.RunParallel(func(pb *testing.PB) { @@ -111,7 +111,7 @@ func BenchmarkChurn(b *testing.B) { i := 0 for pb.Next() { i++ - cache.Add(base+i, i) + clock.Add(base+i, i) } }) } diff --git a/internal/cache/clock/cache.go b/internal/cache/clock/cache.go deleted file mode 100644 index 31d97082..00000000 --- a/internal/cache/clock/cache.go +++ /dev/null @@ -1,86 +0,0 @@ -package clock - -import ( - "hash/maphash" - "runtime" - - "lindenii.org/go/lgo/intconv" -) - -// maxShards bounds the shard count. -// -// Keep it relatively modest -// so the per-shard budget -// stays large enough to admit sizable values. -const maxShards = 16 - -// WeightFunc reports one entry's weight, used for eviction budgeting. -type WeightFunc[K comparable, V any] func(key K, value V) uint64 - -// Cache is a concurrent, weight-bounded cache -// with CLOCK eviction. -// -// Reads are lock-free; -// writes lock only the shard that owns the key. -// -// Labels: MT-Safe. -type Cache[K comparable, V any] struct { - shards []*shard[K, V] - seed maphash.Seed - mask uint64 - weightFn WeightFunc[K, V] -} - -// New returns a cache bounded to maxWeight total weight, -// weighing entries with weightFn. -// -// New panics if weightFn is nil. -func New[K comparable, V any](maxWeight uint64, weightFn WeightFunc[K, V]) *Cache[K, V] { - if weightFn == nil { - panic("internal/clock: nil weight function") - } - - count, mask := shardLayout(maxWeight) - perShard := maxWeight / (mask + 1) - - shards := make([]*shard[K, V], count) - for i := range shards { - shards[i] = newShard[K, V](perShard) - } - - return &Cache[K, V]{ - shards: shards, - seed: maphash.MakeSeed(), - mask: mask, - weightFn: weightFn, - } -} - -// shardLayout picks a power-of-two shard count and its address mask. -// -// Tracks GOMAXPROCS, capped at maxShards, -// and is shrunk so the per-shard budget -// stays at least one while maxWeight is nonzero. -func shardLayout(maxWeight uint64) (int, uint64) { - count := 1 - for count < runtime.GOMAXPROCS(0) && count < maxShards { - count *= 2 - } - - countU, err := intconv.IntToUint64(count) - if err != nil { - return 1, 0 - } - - for countU > maxWeight && countU > 1 { - count /= 2 - countU /= 2 - } - - return count, countU - 1 -} - -// shardFor returns the shard that owns key. -func (cache *Cache[K, V]) shardFor(key K) *shard[K, V] { - return cache.shards[maphash.Comparable(cache.seed, key)&cache.mask] -} diff --git a/internal/cache/clock/cache_ops.go b/internal/cache/clock/cache_ops.go deleted file mode 100644 index 18958202..00000000 --- a/internal/cache/clock/cache_ops.go +++ /dev/null @@ -1,51 +0,0 @@ -package clock - -// Add inserts or replaces key, marking it recently used. -// -// It reports whether the entry was admitted; -// an entry heavier than the per-shard budget is rejected -// and leaves the cache unchanged. -func (cache *Cache[K, V]) Add(key K, value V) bool { - return cache.shardFor(key).add(key, value, cache.weightFn(key, value)) -} - -// Get returns the value for key and marks it recently used. -// -//nolint:ireturn -func (cache *Cache[K, V]) Get(key K) (V, bool) { - return cache.shardFor(key).get(key) -} - -// Peek returns the value for key without changing its recency. -// -//nolint:ireturn -func (cache *Cache[K, V]) Peek(key K) (V, bool) { - return cache.shardFor(key).peek(key) -} - -// Len returns the number of cached entries. -func (cache *Cache[K, V]) Len() int { - total := 0 - for _, shard := range cache.shards { - total += shard.len() - } - - return total -} - -// Weight returns the current total weight across all shards. -func (cache *Cache[K, V]) Weight() uint64 { - var total uint64 - for _, shard := range cache.shards { - total += shard.loadWeight() - } - - return total -} - -// Clear removes all entries. -func (cache *Cache[K, V]) Clear() { - for _, shard := range cache.shards { - shard.clear() - } -} diff --git a/internal/cache/clock/cache_test.go b/internal/cache/clock/cache_test.go deleted file mode 100644 index 3d734b39..00000000 --- a/internal/cache/clock/cache_test.go +++ /dev/null @@ -1,100 +0,0 @@ -package clock_test - -import ( - "fmt" - "strings" - "testing" - - "lindenii.org/go/furgit/internal/cache/clock" - "lindenii.org/go/lgo/intconv" -) - -func byteWeight(_ string, value string) uint64 { - weight, err := intconv.IntToUint64(len(value)) - if err != nil { - return 0 - } - - return weight -} - -func TestCacheAddGetPeek(t *testing.T) { - t.Parallel() - - cache := clock.New(1<<20, byteWeight) - - if !cache.Add("a", "alpha") { - t.Fatalf("Add(a) should succeed") - } - - if got, ok := cache.Get("a"); !ok || got != "alpha" { - t.Fatalf("Get(a) = (%q, %v), want (alpha, true)", got, ok) - } - - if got, ok := cache.Peek("a"); !ok || got != "alpha" { - t.Fatalf("Peek(a) = (%q, %v), want (alpha, true)", got, ok) - } - - if _, ok := cache.Get("missing"); ok { - t.Fatalf("Get(missing) should miss") - } -} - -func TestCacheWeightStaysBounded(t *testing.T) { - t.Parallel() - - const maxWeight = 4096 - - cache := clock.New(maxWeight, byteWeight) - value := strings.Repeat("x", 64) - - for i := range 1000 { - cache.Add(fmt.Sprintf("key-%d", i), value) - } - - if got := cache.Weight(); got > maxWeight { - t.Fatalf("weight = %d, exceeds max %d", got, maxWeight) - } -} - -func TestCacheLenAndClear(t *testing.T) { - t.Parallel() - - cache := clock.New(1<<20, byteWeight) - - for i := range 10 { - cache.Add(fmt.Sprintf("key-%d", i), "v") - } - - if got := cache.Len(); got != 10 { - t.Fatalf("Len = %d, want 10", got) - } - - cache.Clear() - - if got := cache.Len(); got != 0 { - t.Fatalf("Len after Clear = %d, want 0", got) - } - - if got := cache.Weight(); got != 0 { - t.Fatalf("Weight after Clear = %d, want 0", got) - } -} - -func TestCacheRejectsOversized(t *testing.T) { - t.Parallel() - - cache := clock.New(4, byteWeight) - - if cache.Add("a", "xxxxx") { - t.Fatalf("oversized Add should report false") - } - - if _, ok := cache.Get("a"); ok { - t.Fatalf("oversized entry must not be cached") - } - - if got := cache.Weight(); got != 0 { - t.Fatalf("weight = %d, want 0", got) - } -} diff --git a/internal/cache/clock/clock.go b/internal/cache/clock/clock.go new file mode 100644 index 00000000..27d83c7b --- /dev/null +++ b/internal/cache/clock/clock.go @@ -0,0 +1,86 @@ +package clock + +import ( + "hash/maphash" + "runtime" + + "lindenii.org/go/lgo/intconv" +) + +// maxShards bounds the shard count. +// +// Keep it relatively modest +// so the per-shard budget +// stays large enough to admit sizable values. +const maxShards = 16 + +// WeightFunc reports one entry's weight, used for eviction budgeting. +type WeightFunc[K comparable, V any] func(key K, value V) uint64 + +// Clock is a concurrent, weight-bounded cache +// with CLOCK eviction. +// +// Reads are lock-free; +// writes lock only the shard that owns the key. +// +// Labels: MT-Safe. +type Clock[K comparable, V any] struct { + shards []*shard[K, V] + seed maphash.Seed + mask uint64 + weightFn WeightFunc[K, V] +} + +// New returns a cache bounded to maxWeight total weight, +// weighing entries with weightFn. +// +// New panics if weightFn is nil. +func New[K comparable, V any](maxWeight uint64, weightFn WeightFunc[K, V]) *Clock[K, V] { + if weightFn == nil { + panic("internal/clock: nil weight function") + } + + count, mask := shardLayout(maxWeight) + perShard := maxWeight / (mask + 1) + + shards := make([]*shard[K, V], count) + for i := range shards { + shards[i] = newShard[K, V](perShard) + } + + return &Clock[K, V]{ + shards: shards, + seed: maphash.MakeSeed(), + mask: mask, + weightFn: weightFn, + } +} + +// shardLayout picks a power-of-two shard count and its address mask. +// +// Tracks GOMAXPROCS, capped at maxShards, +// and is shrunk so the per-shard budget +// stays at least one while maxWeight is nonzero. +func shardLayout(maxWeight uint64) (int, uint64) { + count := 1 + for count < runtime.GOMAXPROCS(0) && count < maxShards { + count *= 2 + } + + countU, err := intconv.IntToUint64(count) + if err != nil { + return 1, 0 + } + + for countU > maxWeight && countU > 1 { + count /= 2 + countU /= 2 + } + + return count, countU - 1 +} + +// shardFor returns the shard that owns key. +func (clock *Clock[K, V]) shardFor(key K) *shard[K, V] { + return clock.shards[maphash.Comparable(clock.seed, key)&clock.mask] +} diff --git a/internal/cache/clock/clock_ops.go b/internal/cache/clock/clock_ops.go new file mode 100644 index 00000000..a21f44c3 --- /dev/null +++ b/internal/cache/clock/clock_ops.go @@ -0,0 +1,51 @@ +package clock + +// Add inserts or replaces key, marking it recently used. +// +// It reports whether the entry was admitted; +// an entry heavier than the per-shard budget is rejected +// and leaves the cache unchanged. +func (clock *Clock[K, V]) Add(key K, value V) bool { + return clock.shardFor(key).add(key, value, clock.weightFn(key, value)) +} + +// Get returns the value for key and marks it recently used. +// +//nolint:ireturn +func (clock *Clock[K, V]) Get(key K) (V, bool) { + return clock.shardFor(key).get(key) +} + +// Peek returns the value for key without changing its recency. +// +//nolint:ireturn +func (clock *Clock[K, V]) Peek(key K) (V, bool) { + return clock.shardFor(key).peek(key) +} + +// Len returns the number of cached entries. +func (clock *Clock[K, V]) Len() int { + total := 0 + for _, shard := range clock.shards { + total += shard.len() + } + + return total +} + +// Weight returns the current total weight across all shards. +func (clock *Clock[K, V]) Weight() uint64 { + var total uint64 + for _, shard := range clock.shards { + total += shard.loadWeight() + } + + return total +} + +// Clear removes all entries. +func (clock *Clock[K, V]) Clear() { + for _, shard := range clock.shards { + shard.clear() + } +} diff --git a/internal/cache/clock/clock_test.go b/internal/cache/clock/clock_test.go new file mode 100644 index 00000000..36622818 --- /dev/null +++ b/internal/cache/clock/clock_test.go @@ -0,0 +1,100 @@ +package clock_test + +import ( + "fmt" + "strings" + "testing" + + "lindenii.org/go/furgit/internal/cache/clock" + "lindenii.org/go/lgo/intconv" +) + +func byteWeight(_ string, value string) uint64 { + weight, err := intconv.IntToUint64(len(value)) + if err != nil { + return 0 + } + + return weight +} + +func TestCacheAddGetPeek(t *testing.T) { + t.Parallel() + + clock := clock.New(1<<20, byteWeight) + + if !clock.Add("a", "alpha") { + t.Fatalf("Add(a) should succeed") + } + + if got, ok := clock.Get("a"); !ok || got != "alpha" { + t.Fatalf("Get(a) = (%q, %v), want (alpha, true)", got, ok) + } + + if got, ok := clock.Peek("a"); !ok || got != "alpha" { + t.Fatalf("Peek(a) = (%q, %v), want (alpha, true)", got, ok) + } + + if _, ok := clock.Get("missing"); ok { + t.Fatalf("Get(missing) should miss") + } +} + +func TestCacheWeightStaysBounded(t *testing.T) { + t.Parallel() + + const maxWeight = 4096 + + clock := clock.New(maxWeight, byteWeight) + value := strings.Repeat("x", 64) + + for i := range 1000 { + clock.Add(fmt.Sprintf("key-%d", i), value) + } + + if got := clock.Weight(); got > maxWeight { + t.Fatalf("weight = %d, exceeds max %d", got, maxWeight) + } +} + +func TestCacheLenAndClear(t *testing.T) { + t.Parallel() + + clock := clock.New(1<<20, byteWeight) + + for i := range 10 { + clock.Add(fmt.Sprintf("key-%d", i), "v") + } + + if got := clock.Len(); got != 10 { + t.Fatalf("Len = %d, want 10", got) + } + + clock.Clear() + + if got := clock.Len(); got != 0 { + t.Fatalf("Len after Clear = %d, want 0", got) + } + + if got := clock.Weight(); got != 0 { + t.Fatalf("Weight after Clear = %d, want 0", got) + } +} + +func TestCacheRejectsOversized(t *testing.T) { + t.Parallel() + + clock := clock.New(4, byteWeight) + + if clock.Add("a", "xxxxx") { + t.Fatalf("oversized Add should report false") + } + + if _, ok := clock.Get("a"); ok { + t.Fatalf("oversized entry must not be clockd") + } + + if got := clock.Weight(); got != 0 { + t.Fatalf("weight = %d, want 0", got) + } +} diff --git a/internal/cache/clock/concurrent_test.go b/internal/cache/clock/concurrent_test.go index 86283a9b..4b7da162 100644 --- a/internal/cache/clock/concurrent_test.go +++ b/internal/cache/clock/concurrent_test.go @@ -19,7 +19,7 @@ func TestConcurrentStress(t *testing.T) { rounds = 5000 ) - cache := New(maxWeight, func(_ int, _ int) uint64 { return 1 }) + clock := New(maxWeight, func(_ int, _ int) uint64 { return 1 }) var wg sync.WaitGroup @@ -30,13 +30,13 @@ func TestConcurrentStress(t *testing.T) { switch i % 4 { case 0, 1: - cache.Add(key, keyValue(key)) + clock.Add(key, keyValue(key)) case 2: - if got, ok := cache.Get(key); ok && got != keyValue(key) { + if got, ok := clock.Get(key); ok && got != keyValue(key) { t.Errorf("Get(%d) = %d, want %d", key, got, keyValue(key)) } case 3: - if got, ok := cache.Peek(key); ok && got != keyValue(key) { + if got, ok := clock.Peek(key); ok && got != keyValue(key) { t.Errorf("Peek(%d) = %d, want %d", key, got, keyValue(key)) } } @@ -46,9 +46,9 @@ func TestConcurrentStress(t *testing.T) { wg.Wait() - checkCache(t, cache) + checkCache(t, clock) - if got := cache.Weight(); got > maxWeight { + if got := clock.Weight(); got > maxWeight { t.Fatalf("weight %d exceeds max %d", got, maxWeight) } } @@ -64,7 +64,7 @@ func TestReadDuringEviction(t *testing.T) { rounds = 20000 ) - cache := New(maxWeight, func(_ int, _ int) uint64 { return 1 }) + clock := New(maxWeight, func(_ int, _ int) uint64 { return 1 }) var wg sync.WaitGroup @@ -72,7 +72,7 @@ func TestReadDuringEviction(t *testing.T) { wg.Go(func() { for i := range rounds { key := i % hot - cache.Add(key, keyValue(key)) + clock.Add(key, keyValue(key)) } }) } @@ -82,11 +82,11 @@ func TestReadDuringEviction(t *testing.T) { for i := range rounds { key := i % hot - if got, ok := cache.Get(key); ok && got != keyValue(key) { + if got, ok := clock.Get(key); ok && got != keyValue(key) { t.Errorf("Get(%d) = %d, want %d", key, got, keyValue(key)) } - if got, ok := cache.Peek(key); ok && got != keyValue(key) { + if got, ok := clock.Peek(key); ok && got != keyValue(key) { t.Errorf("Peek(%d) = %d, want %d", key, got, keyValue(key)) } } @@ -95,9 +95,9 @@ func TestReadDuringEviction(t *testing.T) { wg.Wait() - checkCache(t, cache) + checkCache(t, clock) - if got := cache.Weight(); got > maxWeight { + if got := clock.Weight(); got > maxWeight { t.Fatalf("weight %d exceeds max %d", got, maxWeight) } } diff --git a/internal/cache/clock/invariant_test.go b/internal/cache/clock/invariant_test.go index 2efd7ff9..04896ca1 100644 --- a/internal/cache/clock/invariant_test.go +++ b/internal/cache/clock/invariant_test.go @@ -79,10 +79,10 @@ func checkShard[K comparable, V any](t *testing.T, shard *shard[K, V]) { } // checkCache verifies every shard's invariants. -func checkCache[K comparable, V any](t *testing.T, cache *Cache[K, V]) { +func checkCache[K comparable, V any](t *testing.T, clock *Clock[K, V]) { t.Helper() - for _, shard := range cache.shards { + for _, shard := range clock.shards { checkShard(t, shard) } } -- cgit v1.3.1-10-gc9f91