Back to 20 Concepts
memory • Intermediate
CPU Cache Lines (64-Byte) & Spatial Locality of Reference
CPUs fetch memory in 64-byte chunks called Cache Lines into ultra-fast L1/L2/L3 caches. Traversing arrays sequentially triggers automatic hardware prefetching, achieving 100x faster execution than random pointer chasing.
Intuitive Mental Model
The Egg Carton in the Kitchen: When you cook breakfast, you do not walk to the grocery store for 1 egg; you bring home a 12-egg carton to the kitchen counter. Accessing the next 11 eggs takes zero travel time.
C / TypeScript ImplementationHardware & Algorithmic Standard
// Row-Major (Cache-Friendly - Fast Sequential 64-byte prefetch):
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
sum += matrix[i][j]; // 1 Cache Miss every 16 integers!
}
}
// Column-Major (Cache-Catastrophic - 100x slower strided access):
for (int j = 0; j < COLS; j++) {
for (int i = 0; i < ROWS; i++) {
sum += matrix[i][j]; // Cache Miss on EVERY single iteration!
}
}Key Architectural Takeaways
- •Spatial Locality: If memory address X is accessed, addresses X+1 through X+15 are preloaded into L1 cache for free.
- •64-Byte Cache Line: Holds 16 32-bit integers or 8 64-bit pointers.
- •Sequential iteration over arrays is one of the fastest operations modern CPUs can perform.
Common Coding Mistake
Iterating 2D arrays in column-major order (matrix[i][j] where outer loop is j), destroying CPU cache hit ratios.
Optimal Solution
Always loop over the innermost contiguous dimension first (row-major order in C/C++/Java/JS).