Why Aren't We Sieve-Ing?
brooker.co.za
brooker.co.za
Ultimately, the right eviction policy depends on the application behavior, and you'll only find the right answer through profiling against actual data from service logs... and the difference between miss rates isn't large so I really don't think it should even be the first thing that gets profiled.. use LRU or LFU (based on intuition about usage) and move on. But I do love to see newly proposed algorithms, more tools for the bag.
But I think this might also not be too helpful overall. I think in many cases there is an obvious choice depending on how and for what the cache is used. And then there are caches that have more unpredictable access patterns, a file system cache might be a good candidate, experiencing the access patterns of all the different applications.
In that case there is probably no best choice as several applications with different access patterns concurrently hit the cache. Or if there is a best choice, it might change very quickly as different applications or components of applications execute. In such a scenario it seems more promising to me to try to categorize the access patterns on a per source basis and treating them accordingly instead of trying to find one best policy for all sources combined.
On the other hand something like this might quickly become prohibitively expensive.
For the general case the ideal is an eviction policy that adapts to fit the given workload. Unfortunately adaptivity is not a very well explored area so most policies have heuristic settings that default to work well in a target range of workloads, but this has to be tuned for others. In this and the author's other paper, S3-FIFO, their lower hit rates with TinyLFU turned out to be due to the implementation. When running it with Caffeine, a productionized version that adds hill climbing and jitter, it had equivalent hit rates [1]. That cache is pretty robust across a wide range of workloads, but also much more complicated to implement. I'd really like to see more research on adaptivity because I think all policies are converging on similar structures and goals, but self-tuning is still an error prone art.
[1] https://github.com/Yiling-J/theine/issues/21#issuecomment-18...
It is promising to see more experimenting with these algorithms.
The optimal algorithm can at best be twice as good as LRU using half the memory. And yes that includes an algorithm that knows exactly which memory is going to be requested. If LRU is not enough you need to be clever or use more memory.
Something like LFU has no such guarantees. Just read a big block of data 10 times and you can get close to 100% cache misses just by continuing to read random bits of data 10 times after each other. LRU would only have 10%, and I think that's optimal.
A standard homework problem in a computer architecture class is to work through the math on how marginal improvements to cache rates can provide dramatic performance improvements, due to the disparity in times of providing data from cache and from the source. Small improvements to caching are a big deal. I hadn’t heard of SIEVE but I’ve had to work more with traditional block cache strategies, where scans are intermixed with random access. LIRS works pretty well.
People are talking like of the one cache thing they are thinking about is the end-all be-all instance of "cache" and nothing can differ. Even the article's author, that really should know better.
Anyway, you seem to be talking about a basically free network (probably a bus), with huge throughput and relatively short latency. The article seems to be about a more limited network, with comparatively lower throughput and larger latency. The same algorithm won't work for both cases.
Basically there's very little speed-up you can achieve with a smarter algorithm that you couldn't achieve with a simple increase in cache.
It's so great to see that this area is subject if theoretical and empirical work and in fact my default view is likely wrong in most cases.
It appears evident that there is no single approach that will work for all workloads (i.e. combinations of access patterns, read/write ratios, scans, processor/cache parameters, etc.). Perhaps I am wrong, and there's a holy grail out there, but...
If there is no single approach, shouldn't the focus be on matching algorithms to workloads? Better selection approaches would seem to yield far more value than yet another boutique algorithm.
Cache replacement algorithms are in the family of universal sequence prediction problems. These problems are unfortunately related to the problem of generally optimal AI/learning algorithms, which gives you a sense of why the task is so difficult.
No but it's easily findable. If you have a group of say 10 cache machines, you can set each one to a different eviction algorithm, and then track misses, hits, and eviction rates. You can even use a one-arm bandit algo for the algos if you want to be really thorough.
But the main question would be why? In 99.9% of cases, the cache eviction algorithm is not going to be your bottleneck. So might as well just use LRU and move on to more important problems.
Insertion sort is heuristically good in many practical circumstances. You wouldn't call it optimal, nor choose to use it as your general-purpose sorting algorithm.
Or if you're implementing a feature in the standard library of a widely used language, the effects of your choice may be enormous.
Sure, and that would be the 0.1% of the time where it make sense.
> if you're implementing a feature in the standard library of a widely used language
I would contend that unless your library is very opinionated on exactly how data will be accessed, you can't possibly optimize cache access in a way that makes sense for every user.
It really isn't. This has been known for things like silicon design since at least the 1980s, and there are a few different seemingly basic properties that make an otherwise simple data model have intrinsically poor cache characteristics. One of the best known is the use of high-dimensionality access methods (e.g. graphics, spatial, graph, etc processing).
The traditional solution to cache replacement intractability is latency hiding architectures (e.g. GPUs, barrel processors, etc) for applications that are mostly about throughput. In fact, this is a reasonable working definition of the difference between latency-oriented and throughput-oriented design (caching versus latency hiding).
> In 99.9% of cases, the cache eviction algorithm is not going to be your bottleneck.
What types of cases are we talking about here? For data intensive applications like database engines, using a naive algorithm like LRU will definitely show up in the profiler unless the rest of your code is similarly naive. You don't notice it for high-throughput workhorse systems because someone else has already spent a lot of time tweaking and optimizing this, using some combination of caching and latency hiding.
Next I thought it might be an algorithm for managing the CPU caches, Wrong again (I think.)
I think it's a discussion of managing application caches or perhaps things like disk caches. Not sure if I'm right.
> The new algorithm is called SIEVE: a simple and efficient turn-key cache eviction policy
According to the footnote in the paper where the name is first mentioned, "SIEVE sifts out unpopular objects from cache over time".
...but a good part of what this article is discussing is why you don't know what it is; why it hasn't been in textbooks for 40+ years:
> if it’s so effective, and so simple, and so closely related to an algorithm that’s been around forever, why has nobody discovered it already?
https://gist.github.com/vidarh/b72615c16673cb38630cab5148190...
Implementing it using arrays isn't hard. You have two obvious options:
One is to still use a linked ring. In that case your array just saves you dynamic allocations and allocator overhead (and if in a gc'd language, gc pressure).
The other is to copy to compact the right on eviction. Whether that is a horrible idea or might work will depend a great deal on your performance characteristics and the number of entries in your cache.
Personally I think the "linked ring in an array" approach is a nice middle ground - you're likely to get better (CPU) cache locality than a naive linked list (whether enough to matter really depends on your implementation languages underlying allocator - and the singly linked version has quite low extra overhead (and it can be made smaller if size is a concern - e.g. it doesn't need to be a pointer but can be an array index) vs. just an array.
The elements which are between 'hand' and 'tail' are going to stay there for a long time, until the hand pointer cycles. If there are lots of elements which get put in the cache but don't really deserve it, that could take a long time. But that's exactly the case where you wouldn't want to keep the elements behind the hand around for a long time. Remember, they got 'promoted' for appearing twice in around the cache size records. Not a great indication that they should be kept for a long time. On the other hand, when the pointer cycles, they could get thrown away quite easily.
On the other hand CLOCK converges to a situation where elements which have appeared a lot are at the front. They are much less likely to be thrown out even if they have a temporary run of scarcity. The elements which don't appear much quickly bubble to the back and become much more likely to be thrown out in the next few evictions. This is accentuated if there are lots of elements which are getting hit relatively more frequently.
After a long time of running SIEVE, there's not really anything about the state which will improve future performance compared to when it starts cold. In many cases it seems it will be locked in to a suboptimal state by overadapting to past observations.
I'm thinking something like this:
Every entry has two values "solidity" and "time since last seen". When an entry is accessed solidity increases based on time since last seen - if it was a short while ago it increases just a little, longer means bigger increase. This is to ensure that solidity will correspond roughly to the long term need for the entry and doesn't go up too much if something is accessed a lot of times in quick succession.
Entries with low solidity and long time-since-last-seen are evicted.
[1] https://www.usenix.org/system/files/conference/atc17/atc17-b...
https://github.com/1a1a11a/libCacheSim/blob/develop/libCache...
If I understand you correctly, you're asking if this is different because an external process is involved. I don't see a use in drawing a distinction, and as far as I know, there's no special term for that pattern.
Update: after looking into it, it looks like this cache/architecture pattern is called "refresh-ahead"
In some ways, caching can be seen a prediction problem. And the cache hit rate is the error as we lag the previous history at time T. Blending load over time is effectively what these various cache algorithms do to avoid overfitting.
Tho potentially just refreshing out of date data in the cache could increase effectiveness given that general assumption of the cache is whats in the cache will probably be used again.
I called it a periodically refreshing cache when I wrote one. Not sure if there is a more formal name.
I wonder how messing of the order of items between hand and tail influences the benchmarks.
You can still get closer to what an array would buy you. E.g. the example code in the paper uses a doubly linked list and there's reason to, so you can reduce overhead right away there. One of the other benefits of an array is you can wrap around just by using a modulo of an index, but you can avoid the conditionals for their list implementation by linking the list together into a ring instead. Those bits I've implemented in a quick and dirty Ruby version (the singly linked ring is last here: https://gist.github.com/vidarh/b72615c16673cb38630cab5148190... ).
You can then also do a "linked ring in array" version, and use that to both reduce the memory overhead (both from individual node allocations and from the size of the pointers in the linked list) by placing linked list/ring nodes in a statically sized array. You just need to relink the node you evict into where you want to insert. You can save on pointer size if that matters to you as well by using array indices instead of pointers in that case.
Whether any of these matters is something you really should measure in your preferred implementation language.
Putting author names but no date at the top seems to be some sort of standard template or convention that every single paper author or institution everywhere uses since forever, since I never see dates at tops of papers.
Why is date not part of the standard template? Knowing the date is so incredibly important to know the paper in context, and in relation to other science. Especially for science I just don't understand why they don't have a convention to date their stuff.
---
Anyway, why I was interested in the date was because the article said "Why aren’t we all SIEVE-ing?". Well turns out the paper is from 2023 or newer, so that could explain why.
Just looking at NSDI ‘23, I can see the first published paper in the Spring: https://www.usenix.org/conference/nsdi23/presentation/liu-ti...
Looking at the BibTex metadata can give you a better idea of how recent/relevant the paper is:
year = {2023}, … month = apr
But since this is not yet published (to appear in 2024 of NSDI), I use a similar method you describe. Most of the time, can also infer from the paper itself (sometimes in the abstract or the discussion)
TFA and the paper both wonder why this extremely simple algorithm was not discovered sooner. Both posit that no paper should be prerequisite to applying this modification.
The question in TFA is less about the paper and more about the concept -- is there some reason why this has evaded us? Is it too good to be true?
The article does a better job than the paper digging in to the details IMO.
The answer to all these questions is that having the prerequisites for inventing something doesn't mean we instantly invent that thing, a la Sid Meier's Civilization. The expectation that we would is actually what's kind of odd here. Humans doesn't even all share the same info, much less automatically know all the possibilities of all combinations of all humanity's knowledge.
Another factor might be that Yet Another Eviction Algorithm isn't necessarily one of humanity's top focuses for inventions at the moment. We could ask any of us here on HN, for example, why we didn't think of it, and sooner. The answer is likely that we were all working on something else we found more important than YAEA.
The article's question "why aren't we SIEVE-ing?" follows this theme.
No one is asking the equivalent of "why didn't we invent cars sooner?" here.
Many inventions in humanity were "simple modifications" of other things. Why didn't we invent them sooner? The answer is in the post you replied to: because it's totally normal for "obvious" inventions to not be invented for a long time, even when somebody thinks, after the fact, that it's a "simple modification". Indeed, what percentage of humanity is currently searching for Yet Another Eviction Algorithm, and what percentage of that percentage is looking in this direction, instead of one of the hundreds of other directions?
So yes, the question is indeed equivalent to "why didn't we invent [X] sooner", replacing X with any invention that at least 1 person out of billions in the world finds "obvious" or a "simple modification".
Do you have any routines that you've refined over the years? Is every step you take in a routine something you were taught or learned elsewhere? Or did you "invent" part of it yourself?
I know how to make tea or coffee. Should someone take the credit for the fact that I know to start boiling water first, while I get everything else together, because this results in the most efficient use of my time?
My perception of the paper is this analogy isn't too far off. It's not an invention, it's a discovery.
The points therein still stand: [inventions/discoveries] which at least 1 person in the world thinks (after the fact) are obvious and just a "small modification" of other [inventions/discoveries], usually go [uninvented/undiscovered] for quite some time.
The paper and TFA asks, "why?" But the better question is, "why wouldn't they?" There's no reason to think they would be be immediately [invented/discovered] as soon as all the prerequisites are [invented/discovered] (again, even if someone thinks they're similar), for the reasons described in my above posts.
The fax machine and the electric car come to mind.
The electric printing telegraph in 1848 though, that's amazing!
Usually the final paper PDF, from the conference proceedings, contains the publication information.
Wouldn't the target audience of a preprint also benefit from knowing a rough date?
The year usually appears in the bottom left of the first page, and in the header or footer of subsequent pages.
The first linked PDF [1] says only "14th USENIX Symposium on Operating Systems Design and Implementation" (without the year), but does have the year on an initial cover page. The second [2] says "HotOS ’23, June 22–24, 2023, Providence, RI, USA". The third [3] says "SOSP ’23, October 23–26, 2023, Koblenz, Germany" in the bottom-left of the first page.
However, this information may be missing from an author produced files/preprints, as it may be inserted along with page numbers when the conference proceedings or journal issue gets created. This seems to be the case for the fourth linked PDF [4].
[1]: https://www.usenix.org/system/files/osdi20-yang.pdf
[2]: https://jasony.me/publication/hotos23-qdlp.pdf
I noticed that arxiv at least puts the dates in vertical on the left side of the PDFs there, but it seems that too is something arxiv puts there, not the paper itself.
If it's about subtleties like "what is exact publication date", at least put some date, at least let us know it's from the 2020's or the 2000's, it's not guaranteed to be easy to tell. It should be possible to put a year during which the text is being typed there.
The title is more raising the question of why an algorithm that performs this decently and is so simply doesn't seem to have been invented earlier.