18.2.1.1 Minimizing Cache Misses

Most CPUs have first-level instruction and data caches on chip and many have second-level caches that are bigger but somewhat slower. Memory accesses are much faster if the data is already loaded into the first-level cache. When your program accesses data that is not in one of the caches, a cache miss occurs. This causes a block of consecutively addressed words, including the data that your program just accessed, to be loaded into the cache. Since cache misses are costly, you should try to minimize them, using these tips:

• Keep frequently accessed data together. Store and access frequently used data in flat, sequential data structures and avoid pointer indirection. This way, the most frequently accessed data remains in the first-level cache as much as possible.

• Access data sequentially. Each cache miss brings in a block of consecutively addressed words of needed data. If you are accessing data sequentially then each cache miss will bring in $n$ words (where $n$ is system dependent); if you are accessing only every nth word, then you will constantly be bringing in unneeded data, degrading performance.

• Avoid simultaneously traversing several large buffers of data, such as an array of vertex coordinates and an array of colors within a loop since there can be cache conflicts between the buffers. Instead, pack the contents into one buffer whenever possible. If you are using vertex arrays, try to use interleaved arrays. (For more information on vertex arrays see ``Rendering Geometry Efficiently.'')

Some framebuffers have cache-like behaviors as well. It is a good idea to group geometry so that the drawing is done to one part of the screen at a time. Using triangle strips and polylines tends to do this while simultaneously offering other performance advantages as well.