A lesson from the Computer Memory module of the bootcamp. About a 13 minute read.
A cache is a small, fast memory that keeps copies of recently used data, and it is the reason two loops with the same Big-O can differ tenfold in speed. This lesson is how it decides what to keep, why arrays beat linked lists by more than any complexity table admits, and how to write code the cache is on the side of.
A CPU CACHE sits between the processor and DRAM and keeps copies of recently used data, so the next access to it takes about a nanosecond instead of about a hundred. It is a bet on LOCALITY, of which there are two kinds. TEMPORAL locality: data you just used, you are likely to use again, like a loop counter or a running total. SPATIAL locality: data near what you just used, you are likely to use next, like the next element of an array. Peter Denning's working set model of 1968 gave this its formal footing: at any moment a program is really using only a small subset of its memory, and if that subset fits in the fast level, the program runs at the fast level's speed. That is the whole idea. Everything else is detail about how the bet is placed.
The rest of this lesson continues with 6 further sections. See the full curriculum.
Browse all 546 practice puzzles