First release of the .NET implementation of the SIEVE cache eviction algorithm (lazy promotion + quick demotion, see the NSDI'24 paper).
Install
dotnet add package PatrikSima.SieveCache --version 0.1.0
The .nupkg and .snupkg are attached to this release. The package is not yet on nuget.org.
What's inside
All caches target .NET 9 and share ICache<TKey, TValue> (Get, Put, Contains, Clear, Count).
SieveCache<TKey, TValue>– reference implementation: dictionary + doubly-linked node list. Single-threaded.OptimizedSieveCache<TKey, TValue>– allocation-free variant with pooled struct nodes and an index-based list. Single-threaded,IDisposable.ShardedSieveCache<TKey, TValue>– thread-safe and scalable: lock-striped shards, lock-freeGet, per-shard lock only for structural mutation. Recommended for concurrent use; ~3.3× faster than a globally locked SIEVE cache at 8 threads on an 8-core box.SieveCacheCore– string-keyed, globally locked thread-safe variant with hit/miss statistics. Kept as a baseline; preferShardedSieveCache.SieveCacheActor<TKey, TValue>– experimental async facade (IAsyncCache) that serializes operations through a channel. Slow, included for comparison only.LruCache,FifoCache– baselines used by the benchmarks.
Tests and benchmarks
- 96 xUnit tests: shared contract tests for every implementation, SIEVE list-order/eviction assertions, barrier-synchronized race tests for the concurrent caches, and a Zipf hit-ratio guard that keeps every implementation within 10 % of the reference cache.
- BenchmarkDotNet suites (
SieveCache.Benchmark) for sequential and multi-threaded Zipf workloads; results are in the README.
Known limitations
- API is not yet stable (hence 0.x).
SieveCacheCoreis string-only andSieveCacheActoris a proof of concept. SieveCacheandOptimizedSieveCacheare deliberately not thread-safe.