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 ?

  • $\begingroup$ Are you interested in something like a programming tutorial or best practice, or do you want sciencey answers? $\endgroup$ – Raphael Jan 28 '13 at 10:11
  • $\begingroup$ @Raphael I have started to read the article that Reza's answer is pointing to. It's pretty much what I expected/wanted: Theoretical critiques and point of view over real life application of cache algorithms. However, if you have other ressources that you might find helpful, don't hesitate: I love having several learning and knowledge sources. $\endgroup$ – Stephane Rolland Jan 28 '13 at 10:16
  • $\begingroup$ I don't have references handy; it's just that in the first case, your question would be offtopic here. :) $\endgroup$ – Raphael Jan 28 '13 at 10:17

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.

| cite | improve this answer | |

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).

| cite | improve this answer | |
  • $\begingroup$ Aren't those a bit too general? $\endgroup$ – Raphael Jan 28 '13 at 10:18
  • $\begingroup$ @Raphael, can't give a specific answer to a general question... $\endgroup$ – vonbrand Jan 28 '13 at 10:29
  • $\begingroup$ Well, the question is focused on caching (if very general otherwise), so general program optimisation references seem to be too general. YMMV. $\endgroup$ – Raphael Jan 28 '13 at 10:31
  • $\begingroup$ It asked specifically on optimizing performance by caching... and that may well be the wrong strategy. $\endgroup$ – vonbrand Jan 28 '13 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.