Talk:Cache-oblivious algorithm
"This can be implemented in practice with the Least Recently Used policy, which is shown to be within a factor of 2 of the offline optimal replacement strategy."
I wrote this, but in hindsight I think it's wrong. The Move-To-Front heuristic is 2-optimal, but I'm not sure if that's equivalent to LRU. Seems not ...
Vecter 23:35, 7 June 2007 (UTC)
- No, it's basically correct. The following lemma is proved in the Frigo paper from the references:
- Lemma 12. Consider an algorithm that causes Q'(n;Z,L) cache misses on a problem of size n using a (Z, L) ideal cache. Then, the same algorithm incurs Q(n;Z,L) ≤ 2Q'(z;Z/2,L) cache misses on a (Z,L) cache that uses LRU replacement.
- Note that, technically, you need an LRU cache of twice the size of the optimal-replacement cache to simulate it within a factor of two.