3 ms·
> 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 implemen
by flgr 9y 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 9y 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.