0

I am new to dynamic programming and have come across the concept of cache misses when analyzing the efficiency of various dynamic programming algorithms.

Particularly, I have seen that optimizing code to avoid cache misses can help improve run-time.

What are cache misses, and how can I avoid them when writing dynamic programming algorithms?

coder_jam
  • 94
  • 12
  • 5
    If you are new to dynamic programming, optimizing caching strategies is not the best use of your time. In order to properly analyze caching behavior you will need a deep insight of the microarchitecture of the platform you are running on, some specialized software tools for profiling code in practice, etc. I would reserve investigation of caching behavior as a last resort for performance, after exhausting any easier optimizations that can potentially have bigger impact. – nanofarad Apr 26 '20 at 17:23
  • somewhat related: https://stackoverflow.com/questions/18559342/what-is-a-cache-hit-and-a-cache-miss-why-would-context-switching-cause-cache-mi – 463035818_is_not_an_ai Apr 26 '20 at 17:28
  • 3
    You are diving into the deep end of the pool without first learning to swim. Also; most code doesn't actually need to care about caching behaviour. There are usually 10-100 other things impacting performance that you should be fixing first. – Jesper Juhl Apr 26 '20 at 17:37
  • 1
    You avoid cache misses in dynamic programming pretty much the same way you avoid cache misses in all programming. Quoting Stroustrup: "don’t store data unnecessarily, keep data compact, and access memory in a predictable manner." – user4581301 Apr 26 '20 at 17:59
  • Just minimimize the number of cache lines accessed, understand how the memory of your program is laid out etc. – user997112 Apr 29 '20 at 05:50

0 Answers0