A concrete explanation of how a cache works

Summary

A very concrete explanation of how a cache worksA hash table implemented in hardware 2019.03.30KO | ENAs 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 LocalityThe 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.Even within a single process, some parts are used often and others aren’t, so the operating system manages a process by dividing it into units called pages, and the figure above is a trace of page references. The horizontal axis is execution time, and the vertical axis is the memory address. A horizontal run of references means the same memory address was referenced over a long stretch of time, while a vertical run means closely spaced memory addresses were referenced at the same time. You can see that the principle of locality applies to page access too.CachesA CPU chip contains several caches, and each one has its own purpose and role.+-------------+------+------+ +---------------+ +--------+ | | I$...