Minimizing Cache Misses.

Most CPU's have first-level instruction and data caches on chip and many have second-level cache(s) 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 isn't in one of the caches, it gets a cache miss. This causes a block of consecutively addressed words, including the data that you 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 be constantly reading 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''.) However, if packing your data forces a big increase in the size of the data, it may not be the right optimization for your program.