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.

—Steven G. Johnson 16:10, 8 June 2007 (UTC)

cache-oblivious unrolled linked lists

"it is possible to design a variant of unrolled linked lists which is cache-oblivious" is false. The closest thing is the packed-memory array, but its append is slow. Normal and unrolled linked lists have constant time append. —Preceding unsigned comment added by 190.135.57.152 (talk) 00:10, 27 May 2010 (UTC)