MIT's Introduction to Algorithms, Lectures 22 and 23: Cache Oblivious Algorithms

You're viewing a comment by Wolter and its responses.

Wolter Permalink
July 14, 2009, 15:10

> You’d need to recompile the code to achieve best performance (treating the cache size as a constant and not something that varies at run time).

But how significant would the performance impact be? I'm wondering whether a dynamic cache-aware algorithm would give better performance than a cache-oblivious one. It would seem reasonable that a cache-aware algorithm would be capable of making more intelligent decisions.

> Because you can write a cache oblivious algorithm and have it perform best all the time without having to worry about that. The cache-aware-with-adjusting actually requires more complexity. The cache oblivious way “just works.”

But is that in fact true? Do cache-oblivious algorithms actually outperform cache-aware algorithms? Or are they just a compromise?

Reply to this comment

Reply To This Comment

(why do I need your e-mail?)

(Your twitter name, if you have one. (I'm @pkrumins, btw.))

Comment Help

Type first 3 letters of your name: (just to make sure you're a human)

Please preview the comment before submitting to make sure it's OK.