GoKawiilA very concrete explanation of how a cache works
A hash table implemented in hardware 2019.03.30
KO | EN
As technology has advanced, processor speed has risen quickly, but memory speed hasn’t kept up. No matter how fast a processor is, if memory responds slowly the whole system ends up slow. The device that addresses this is the cache.
A cache is a small, fast memory that sits inside the CPU chip. (It’s also expensive.) Going to main memory for data every time is slow, so the cache holds frequently used data and lets the processor reach that data from the cache instead of main memory, which speeds things up.
Principle of Locality
The judgment about which data is “frequently used” follows the principle of locality, which can be split into temporal locality and spatial locality.
Temporal locality is the tendency to access recently accessed data again. For example, the variable i that serves as the index in a loop is accessed several times within a short span.
for (i = 0 ; i < 10 ; i += 1 ) { arr [i] = i; }
Spatial locality is the tendency to access the space near recently accessed data again. In the loop above, as it references each element of the array arr , it accesses nearby memory locations one after another. That’s because an array’s elements are allocated consecutively in memory.
... continue reading