Cache strategies, what reference article could I study?

Question

So as to optimize an application, I must implement data caching: not to recompute some data - those heavy on cpu but that don't change often.

When playing with the idea, I imagined something like the way win32/MFC manages the windows screen i.e.:

• While a part is valid, it is not repainted.
• When a rectangle or a region is invalidated, this part is repainted during the next painting session - launched by the OS.

I was imagining a way to validate and invalidate my cached value, so as to recompute only what is necessary when it is necessary.

Then I read this wikipedia page about Cache Algorithms, and none of the listed algorithm was using the technique I explained above. So I feel ill at ease, and I need to read some work about caching.

Do you know of some resources that I could rely on before I start implementing my own cache process ?

Answer 1

The best strategy to find the best suitable algorithms for caching is to read survey papers in this area. I recommend the paper A survey of Web cache replacement strategies by Podlipnig and Böszörmenyi (2003) which reviews many general techniques for caching.

Answer 2

The best overall view on optimization I've seen is Bentley's "Writing efficient programs" (sadly out of print), the medular part of its rules are in his "Programming pearls". For analysis of the algorithms I'd dig into Cormen et al "Introduction to Algorithms" (don't let the "introduction" fool you, it is more an encyclopaedia).