Programming with Judy

Caching and Memory Management
Appendix B 61
B Caching and Memory
Management
Why use caching? Cache is a small, fast memory holding recently accessed data. The
purpose of caching is to avoid unnecessary reloads of hot data that is
likely to be used soon or frequently. CPU caching is usually used to
access processor memory but other types of caching can also be used for a
local copy of data accessible over a network (such as web browser caching
or disk buffer caching).
CPU “cache lines” exist because CPUs are becoming so much faster than
RAM. When a computer must fill a cache line by accessing RAM (cache
line fill), it can cause a 30-150 instruction delay (freeze) during which the
CPU has to wait. Detailed profiles reveal that many programs spend a
lot of time waiting for load and store instructions.
The caching curve The figure below shows the knee in the caching curve that often occurs
when the population (the number of valid keys or indexes) grows beyond
a certain point. Note that as the population increases, the time to access
any index in the population also increases exponentially showing a
strong upward trend in the graph at a certain point.
Figure B-1 The caching curve
average
access time
population
“knee” in
caching curve