Chapter 5. Memory Performance Problems and Solutions

Table of Contents

5.1. Data Layout Problems
5.1.1. Partially Used Structures
5.1.2. Too Large Data Types
5.1.3. Alignment Problems
5.1.4. Dynamic Memory Allocation
5.2. Data Access Pattern Problems
5.2.1. Inefficient Loop Nesting
5.2.2. Random Access Pattern
5.2.3. Unexploited Data Reuse Opportunities
5.3. Non-Temporal Data
5.3.1. Example of Non-Temporal Data Optimization
5.3.2. Singlethreaded Uses of Non-Temporal Hints
5.3.3. Multithreaded Uses of Non-Temporal Hints
5.3.4. Concurrent Uses of Non-Temporal Hints
5.3.5. Types of Non-Temporal Hint Instructions
5.3.6. Using Non-Temporal Hint Instructions
5.4. Multithreading Problems
5.4.1. False Sharing
5.4.2. Poor Communication Utilization
5.5. Common Data Structures
5.5.1. Arrays
5.5.2. Linked Lists
5.5.3. Trees
5.5.4. Hash Tables
5.6. Final Remedies

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:

Data Layout Example

Figure 5.1. Data Layout Example