Sieve is simpler than LRU
A new cache eviction algorithm called SIEVE is presented as a simpler, higher-performing alternative to classic LRU, especially on modern web and CDN-like workloads. Commenters scrutinize its actual behavior, complexity, edge cases (such as scan resistance), and amortized performance, often contrasting academic benchmarks with real-world constraints like concurrency, CPU cache locality, and adversarial access patterns. The marketing-heavy blog style and an initially incorrect animation draw criticism, but the underlying research, open-source implementations, and author clarifications lead many to see SIEVE as a promising but workload-dependent addition to the cache design toolbox.
Writing style & communication
- Many readers dislike the blog’s hyped, “marketing” tone (e.g., “superstar”, “turbo boost”), describing it as off‑putting and ChatGPT‑like.
- Others are more tolerant, viewing it as outreach to non‑experts or a product of current “sell your research” culture.
- The authors state the post was “polished” by ChatGPT, accept the criticism, and commit to rewriting it in a more straightforward style.
Algorithm understanding & correctness
- Commenters relate SIEVE to classic CLOCK/NRU: a circular queue (or list), a “hand” pointer, and a 1‑bit visited flag meaning “touched since hand last passed”.
- On a miss, the hand scans forward, clearing visited bits until it finds an unvisited entry to evict.
- Several people found the prose and animation confusing. An inconsistency in the animation (not clearing a visited bit) was identified; the authors updated it.
Performance and workload suitability
- SIEVE is reported (per paper and additional plots) to beat strong baselines (e.g., LRU, TinyLFU) on many web and some multi‑tenant block‑I/O traces, but not all workloads.
- It is explicitly acknowledged to be not scan‑resistant and can degenerate toward MRU‑like behavior in some patterns.
- One metric claim (“best on ~45% of traces”) led to questions about the remaining 55%; the counterpoint is that those 55% are shared among many competing algorithms.
Design choices, complexity & implementation
- Worst‑case eviction cost is O(N), but commenters argue it is amortized O(1) because each scan clears visited bits that must be re‑set one by one.
- Implementations discussed: linked lists vs arrays/ring buffers vs ordered dicts; circular lists to avoid null checks; log‑structured/segment‑based designs like Segcache.
- Converting an existing LRU library to SIEVE required few code changes, which some see as evidence of implementation simplicity.
Critiques, alternatives & adversarial concerns
- One long subthread argues that inserting new items always at a fixed “head” while the hand roams a conceptual ring unfairly penalizes items depending on hand position; others respond that fairness to individual items is irrelevant if hit rate improves.
- Some suggest variants: inserting at the hand, keeping a fixed offset between insert and hand, adding randomness, or multi‑generational schemes.
- There is broader discussion that any deterministic policy has adversarial workloads, and production caches often inject randomness, sampling, or hybrid policies to avoid denial‑of‑service patterns.