Computer Systems A Programmer's Perspective Second Edition
In Section 6.2, we introduced the idea of locality and talked in qualitative terms
about what constitutes good locality. Now that we understand how cache memo-
ries work, we can be more precise. Programs with better locality will tend to have
lower miss rates, and programs with lower miss rates will tend to run faster than
programs with higher miss rates. Thus, good programmers should always try to
write code that is
cache friendly
, in the sense that it has good locality. Here is the
basic approach we use to try to ensure that our code is cache friendly.
1.
Make the common case go fast.
Programs often spend most of their time in a
few core functions. These functions often spend most of their time in a few
loops. So focus on the inner loops of the core functions and ignore the rest.
2.
Minimize the number of cache misses in each inner loop.
All other things being
equal, such as the total number of loads and stores, loops with better miss rates
will run faster.