3 ms·

> 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

> 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 ago
Even 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 ago
  Requiring 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.

choudanu4 10y ago

Even 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 ago
Requiring 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.