4 ms·

If you don't want to think about it, use LRU. The optimal algorithm can at best be twice as good as LRU using half the memory. And yes that includes an algorit

If you don't want to think about it, use LRU. 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.

jonstewart 3y ago
Twice as good meaning that the cache miss rate is halved? 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.
- marcosdumay 3y ago
  Oh, "cache" means a huge amount of functionality, on both hardware and software, with a huge amount of dissimilarity. 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.
taneq 3y ago
I tend to think similarly about most optimisation things. Sure, sometimes in niche cases (embedded, or sometimes gaming, are good examples) doubling performance takes it from a no-go to a go, so it's definitely worth knowing things like this. Usually though we're looking for more than 50% scalability, and if you're within 50% of max capacity you need to re-think things on a much higher level.
- contravariant 3y ago
  And as far as optimising things go this is a bit of a special case. Often you can make something several orders of magnitude faster or efficient, but when it comes to LRU you know you're already quite close to the optimal algorithm (in logarithmic terms). 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.

jonstewart 3y ago

Twice as good meaning that the cache miss rate is halved? 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.

marcosdumay 3y ago
Oh, "cache" means a huge amount of functionality, on both hardware and software, with a huge amount of dissimilarity. 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.

taneq 3y ago

I tend to think similarly about most optimisation things. Sure, sometimes in niche cases (embedded, or sometimes gaming, are good examples) doubling performance takes it from a no-go to a go, so it's definitely worth knowing things like this. Usually though we're looking for more than 50% scalability, and if you're within 50% of max capacity you need to re-think things on a much higher level.

contravariant 3y ago
And as far as optimising things go this is a bit of a special case. Often you can make something several orders of magnitude faster or efficient, but when it comes to LRU you know you're already quite close to the optimal algorithm (in logarithmic terms). 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.