Pre-allocation and Pre-fetching

Memory hierarchy

From fastest to slowest:

• Registers (1 CPU cycle, a few bytes per register)
• L0 cache (around 16 KB)
• L1 cache (128 KB; 0.5 ns for the data cache, 5 ns for a branch misprediction on the instruction cache)
• L2 cache (instruction and data, shared; 256 KB to 8 MB; access around 5-7 ns)
• L3 cache (shared; 32 to 64 MB; around 12 ns). L1 and L2 sit per core; L3 can live on the CPU itself and is the shared cache for all cores
• L4 cache (shared; 64 to 128 MB; around 40 ns)
• Main memory (16 to 256 GB; around 60 ns). NUMA machines experience non-uniform access times
• Disk storage (terabytes; 100 microseconds)

Pre-fetching

Pre-fetching also happens as part of branch prediction (instruction pre-fetching).

Data is not loaded a few bytes at a time, but one or a few pages (a few kilobytes) at a time. Subsequent references to the same data lead to cache hits and experience lower access latencies.

Locality

The principle of locality: related datasets placed near each other in memory allow for more efficient caching. You must know how big each cache is, how much data fits in a cache line, and the cache access times, for the specific architecture.