Talk:Cache-oblivious algorithm
Latest comment: 14 years ago by 190.135.57.152 in topic cache-oblivious unrolled linked lists
![]() | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||
|
"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.
cache-oblivious unrolled linked lists
edit"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)