6.4. Optimize Access Patterns

A program with poor access patterns exhibit some of the same traits as a program with inefficient memory layout, and it is not always obvious what the fundamental problem is. For instance, is using only one field from a record a memory layout problem or is the problem related to the access pattern?

By relating inefficient access patterns specifically to late spatial reuse, we can narrow the definition somewhat.

By addressing memory layout problems before access patterns, the analysis will produce more accurate estimates on the performance potential for fixing access pattern.

Generally, inefficient access patterns arise from:

[Tip]Tip
Organize data or change data access order to utilize all data in a cache line
[Tip]Tip
Avoid patterns or data structures that are random or non-deterministic in nature, or cause random access patterns.
[Tip]Tip
Consider building up local copies of data, where the local copy is transformed, filtered and sorted in an optimal way for the current algorithm.
[Tip]Tip
For data structures involving following pointers, such as linked lists, trees or hash table collision lists, consider collapsing several tree levels or ranges of nodes into densely packed vectors. This lowers the space overhead, while improving locality. The draw-back is more complex traversal logic.