This chapter presents common causes for cache and memory related performance problems and solutions to these problems. The problems can be divided into two categories, data layout problems and data access pattern problems. We also present some common data structures and problems that they may cause.

This chapter uses some memory layout graphs to clarify what is happening in the cache. Cache lines are drawn with solid lines. Boundaries between data fields are drawn with thinner dashed lines. Used parts of a cache line are drawn in green, and unused parts of touched cache lines in red. Completely unused cache lines are drawn in white. For example, two cache lines where the first half of the first cache line is used and the second cache line is completely unused would look like this:

Figure 5.1. Data Layout Example