7 ms·
Cache eviction: when are randomized algorithms better than LRU? (2014)
- ordinaryperson 10y agoRelated: the author, Dan Luu has, IMHO, one of the best IT-related Twitter feeds out there: https://twitter.com/danluu https://twitter.com/danluu Highly recommended.
- PaulHoule 10y agoOften you can get away with dumping the whole cache when it fills up and starting fresh.
- Coding_Cat 10y agothat's a horrible pattern. As soon as you go 1 bit over your cache size in a hot loop you'll have a 100% miss rate. (assuming each element is loaded once in the hot loop).
- jandrese 10y agoStrict LRU has the exact same problem. That's one reason the article was advocating for 2-Random, since it has more gradual performance degradation when the data set gets too large.
- rspeer 10y agoYou don't use this pattern while looping. You use it while memoizing results that you don't want to compute again. Here's an example, in the Python package wordfreq [1]. When you look up word frequencies, there's some normalization it has to do to your text. Some words are very common, and it would be silly to normalize them repeatedly. So frequency lookups are cached. The cache dictionary has a maximum size of 100,000, so that exceptional or malicious cases don't use up all your memory. It is extremely rare for text to contain 100,000 distinct words, but if that happens, the cache gets full and the entire thing is dropped. It will quickly be re-populated with common words, of course. Yes, you can make this perform horribly by looking up frequencies of ["zero", "one", "two", "three", "four", ..., "one hundred thousand"] in a loop. That's not realistic data. Do you actually have a suggestion for how to do this faster? We benchmarked this against other cache strategies (with smaller cache sizes so it would drop sometimes) on realistic data. It's much faster than Python's LRU decorator, for example. [1] https://github.com/LuminosoInsight/wordfreq/blob/master/wordfreq/__init__.py https://github.com/LuminosoInsight/wordfreq/blob/master/word...
- ghshephard 10y agoCurious - why wouldn't your CPU L1/L2/L3 caches always be "full?" What does it even mean to have a "full" cache in that context? Wouldn't they, under normal operations, typically fill up in a few seconds? (If not milliseconds?)
- AstralStorm 10y agoThey will, but not with the data of the currently running process.
- rspeer 10y agoSad to see this downvoted. There is definitely a case where this applies, which is the case where going over your cache size is an exceptional circumstance that you don't expect to reach very often. In that case, all the bookkeeping for determining what to evict is wasted effort.
- kabdib 10y agoOuch. At 600+ clock cycles for a cache line fill (more if you're doing NUMA) this doesn't sound even remotely okay.
- nsebban 10y agoWhen the cost of retrieving an item from your slower storage is pretty much the same for every item, may it be old or new, small or big, popular or not.
- falcolas 10y agoOne thing I've seen is that a weighted LRU is usually slightly better for unpredictable workloads. i.e. it will never evict high use cache data when there's a flurry of one-off traffic that would normally start evicting a normal LRU cache, and even a 2 random LRU scheme. This is particularly relevant for databases and keeping rows in memory. The algorithm is something like "add two weight when an item is used, and decay one from every item every second, evict items under pressure from the lowest weight to the highest."
- rozim 10y agoWell, once you go down this path you gotta consider ARC: https://en.wikipedia.org/wiki/Adaptive_replacement_cache https://en.wikipedia.org/wiki/Adaptive_replacement_cache as I believe it is designed to be scan-resistant.
- logophobia 10y agoWhich is, unfortunately, patented: http://patft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=6996676.PN.&OS=PN/6996676&RS=PN/6996676 http://patft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=....
- takeda 10y agoHmm given that patents span for 20 years, and that's essentially forever in computer world, once this patent expires it probably will be worthless. In a world where advances are built on top of other advancements, patents just stifle innovation.
- noonewhocounts 10y agoAnd yet innovation proceeds at a pace unmatched in history, and is so commonplace it gets dismissed as not counting when it's not a revolutionary breakthrough.
- mapgrep 10y agoDumb question, what is "2-random"?
- sethammons 10y agoFrom the article: ...on real workloads, random tends to do worse than other algorithms. But what if we take two random choices and just use LRU between those two choices? "2-random" is his short hand for the above scenario. [edit: formatting, I have no idea how to signify a quote; I don't want preformatted because it makes a scroll box.]
- mapgrep 10y agoThanks! Sorry, I missed that.
- AnimalMuppet 10y agoOn HN, typically a quote is done like this: > This is a quote. It won't become a scroll box, no matter how long it gets. It will just wrap to the next line. True, the next line won't begin with a ">" character, but the convention is that the whole paragraph is a quote if the first line begins with a ">".
- mnarayan01 10y agoPick two entries at random, and then choose the least recently used one.
- plandis 10y agohttp://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf http://www.eecs.harvard.edu/~michaelm/postscripts/handbook20... Basically pick-2 allows you to make a mixture of a totally random and optimal choice in cases where you have imperfect information that is much more resilient to the staleness of data than either a random choice or the globally optimum choice.
- pacificleo11 10y agoAjax made predictive (random)prefetching mainstream .its only natural that random eviction algorithm are coming along . when you pick one end of stick you pick another too
- jandrese 10y agoAre there any languages that allow you to give the compiler a hint that you're about to grind over a gigantic dataset so don't bother to cache any of this data because it won't be accessed again for a long time? It seems like it could be helpful in keeping a big crunch from obliterating the cache constantly. You might also be able to apply other optimizations, like preloading the next data blocks so they're ready when the CPU rolls around. Maybe compilers already do this behind the scenes?
- JoshTriplett 10y agoLanguages, no, but the madvise syscall has flags for that kind of pattern.
- deleted 10y ago[deleted]
- jnordwick 10y agoWhat level of cache? For memory mapped regions there is madvise() DONT_NEED to tell the kernel to that you won't need this data again so don't bother with the disk cache. For the CPU cache the non-temporal instructions MOVNTI that tells the CPU to not bother caching the move to prevent cache pollution.
- jamesfmilne 10y agoSSE allows you to do non-temporal loads & stores, within certain constraints. "A case for the non-temporal store" https://blogs.fau.de/hager/archives/2103 https://blogs.fau.de/hager/archives/2103
- openasocket 10y agoThe short answer is no, because the machine language doesn't allow general manipulation of the cache. So the cache is pretty strictly controlled by the hardware. In general the hardware works very well for a wide variety of different workloads. It can often work better than a compiler can, because it works at runtime, and is thus flexible to changes in workloads. The preloading optimization you mentioned is sort of done already: it's called prefetching. The idea is a cache will automatically cache memory near where you just accessed, because for a lot of memory intensive operations you are linearly scanning a specific section of memory.
- krallja 10y agoRedis supports LRU and random eviction: https://support.redislabs.com/hc/en-us/articles/203290657-What-eviction-policies-do-you-support- https://support.redislabs.com/hc/en-us/articles/203290657-Wh... I wonder if it would be worth adding a k-random eviction strategy, for a balance between the two.
- BillinghamJ 10y agoRedis's LRU eviction is actually 3-random by default. It does not support true/full LRU. Edit: this is clearer - https://redis.io/topics/lru-cache#approximated-lru-algorithm https://redis.io/topics/lru-cache#approximated-lru-algorithm Excerpt from https://raw.githubusercontent.com/antirez/redis/2.8/redis.conf https://raw.githubusercontent.com/antirez/redis/2.8/redis.co... # LRU and minimal TTL algorithms are not precise algorithms but approximated # algorithms (in order to save memory), so you can select as well the sample # size to check. For instance for default Redis will check three keys and # pick the one that was used less recently, you can change the sample size # using the following configuration directive. # # maxmemory-samples 3
- antirez 10y agoRedis does a much better thing in recent versions: it uses a few samples per iteration, but instead of discarding the accumulated data, it takes a pool of good candidates to re-check in the next iteration, so the approximation to LRU is very close compared to vanilla "among 3" algorithms. Moreover since the performance was improved, now the default is to look at 5 items making the algorithm better. More than the precision of LRU itself, I'm more intrigued with the potential improvements that LFU (Redis >= 4.0) can provide, but being 4.0 just in RC state, most users are currently just using LRU.
- BillinghamJ 10y agoNice! Thanks for the in-depth explanation :)
- antirez 10y agoHello, now Redis (4.0, still in release candidate) supports LFU (Least Frequently Used) which should work better in most cases since LRU also is also just a way to approximate LFU, since the most frequently used items are often the last recently used ones.
- danbruc 10y ago[...] choosing the least recently used (LRU) is an obvious choice, since you’re more likely to use something if you’ve used it recently. There are many other cache replacement policies [1] and they can outperform LRU especially if the quoted assumption is not true. It is for example quite common to have two types of data, one is frequently reused over very long periods, the other is reused over short periods after the first use. In those cases a more complex policy like ARC or CAR can provide noticeable improvements. [1] https://en.wikipedia.org/wiki/Cache_replacement_policies https://en.wikipedia.org/wiki/Cache_replacement_policies
- bnegreve 10y ago> There are many other cache replacement policies [1] and they can outperform LRU especially The article is about CPU caches so speed and memory usage are very critical. One of the main benefit of LRU is that it only needs one extra bit per cache line.
- choudanu4 10y agoEven when discussing CPU caches, there are policies that can severely outperform LRU, specifically at the Last-Level Cache (LLC). LLCs often are exposed to access streams where the temporal locality (which is the assumption that makes LRU good) has been filtered out by earlier caches. For that reason, newer cache replacement policies such as RRIP, SHiP, and Hawkeye have significant headroom to improve upon LRU (and PseudoLRU).
- flgr 10y ago> One of the main benefit of LRU is that it only needs one extra bit per cache line. This might be well known, but why's that? I've recently seen a Go implementation of LRU and it uses a lot of memory. Maybe this would allow us to save some of that in a better implementation.
- danbruc 10y agoRequiring only a single bit is only true for a two-way set associative cache, i.e. the content stored at every memory address may only be cached in two different cache slots. In this case you can simply flag the other corresponding cache entry you did not access as least recently uses every time you access a cache entry. The implementation in software was probably fully associative, i.e. every item can be cached in every slot. This requires a lot more memory and it is the same for caches in processors, they require more additional bits and logic the more freedom they have where to cache the content of every address. To be more precise, you have to keep track of the order all cache entries were accessed which requires at least about n * log(n) bits unless you only implicitly store the access order by using something like move to front.
- SomewhatLikely 10y agoThis 2 random cache scheme reminds me a lot of the 2 random load balancing scheme laid out in "The Power of Two Choices in Randomized Load Balancing" https://www.eecs.harvard.edu/~michaelm/postscripts/mythesis.pdf https://www.eecs.harvard.edu/~michaelm/postscripts/mythesis.... Which shows an exponential improvement in choosing the less loaded of two randomly chosen servers over just random.
- colonelxc 10y agoIt is indirectly referenced near the bottom of the page, with a pointer to http://brooker.co.za/blog/2012/01/17/two-random.html http://brooker.co.za/blog/2012/01/17/two-random.html, which references http://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf http://www.eecs.harvard.edu/~michaelm/postscripts/handbook20...
- SomewhatLikely 10y agoAnother characteristic of the data which would make random particularly bad is if reloading/recomputing the most popular items took significantly longer than reloading unpopular items. This could be the case for instance if item data size grew in proportion to popularity.
- j2kun 10y agoThe "2 random choices" idea also shows up as a good idea in other settings, such as load balancing for hashing. I wrote a writeup[1], but if you google "power of two random choices" you'll see a lot of literature on it. [1]: https://jeremykun.com/2015/12/28/load-balancing-and-the-power-of-hashing/ https://jeremykun.com/2015/12/28/load-balancing-and-the-powe...
- kazinator 10y agoLRU is predicated on locality of reference. Ideally we could peer into a crystal ball and know which items are going to be accessed in the near future and keep those in the cache at all costs. Since we don't know that, we use a predictor based on past behavior. If past behavior is random, then prediction is for shit. So we assume that behavior has locality: something referenced recently is more likely to be referenced again than something not referenced recently. Based on that guess, we sort things from least recently used to most recently (or approximately sort, using aging tricks to avoid actually sorting), and boot out the least recently used entries. If accesses are completely random, then the LRU selection is pure overhead. Or worse; some patterns, like repeated sequential accesses of something large through a small cache, are anti-locality. If we are accessing a big buffer in a circle, then the next thing we are accessing at all times is precisely the least-recently used item that LRU wants to boot out. For situations like that, caching mechanisms sometimes support some API for providing a hint. "These memory locations are going to be needed soon". "This memory mapped file is being sequentially accessed". And such.