Branch Prediction & Loop Unrolling Awareness

## Why caches exist A CPU core can execute instructions far faster than **main memory (RAM)** can supply data — a fetch from RAM can cost on the order of **100+ cycles**, during which the core would otherwise sit idle. To hide this, CPUs have a **cache hierarchy**: small, very fast **L1** (per-core, tens of KB), larger/slower **L2**, and a big shared **L3**. Data the CPU needs is searched for in L1 first, then L2, then L3, then RAM — each level bigger but slower. A **cache hit** is finding the data in cache (fast); a **cache miss** is not finding it, forcing a fetch from a slower level (slow stall). ## Cache lines: memory moves in blocks Crucially, caches don't store individual bytes — they store **cache lines**, fixed-size blocks (**typically 64 bytes**). When you touch one byte, the whole 64-byte line containing it is loaded. For an `int[]` (4 bytes each), one line holds **16 consecutive ints**: touching `a[0]` brings `a[0..15]` along for free. ## Locality: the principle that makes caches pay off - **Spatial locality:** if you access an address, you're likely to access nearby addresses soon. Sequential array iteration is the ideal case — you walk straight through contiguous memory, so each loaded line is fully used before the next is needed. - **Temporal locality:** if you access something, you're likely to access it again soon, so keeping it cached pays off. ## Prefetching CPUs also have a **hardware prefetcher** that watches access patterns; when it detects a **regular stride** (e.g. +4 bytes each step through an `int[]`), it speculatively loads upcoming lines **before** you ask, so the data is already in cache when you reach it. Sequential access is exactly what the prefetcher loves; random addresses give it nothing to predict. ## Why sequential array access wins Put together: iterating `int[]` in order = full use of every cache line + accurate prefetch = nearly every access is an L1 hit. The loop runs at cache speed. ## Why random access / pointer chasing loses - **Random index access** into a large array jumps to addresses spread across many lines; each jump can be a cache miss, and there's no stride to prefetch — you repeatedly stall on slow memory. - **Pointer chasing** is worse: a `LinkedList`, tree, or graph of separately-allocated objects scatters nodes across the heap. Each step is `node = node.next`, and you can't even compute the next address until the current node arrives — a **dependent load**. So you wait for a (likely-missing) line, then wait for the next, serially. This is why a contiguous `int[]` typically **massively outperforms** a `LinkedList<Integer>` for traversal even though both are O(n): the array has spatial locality and prefetch; the list has neither, *and* boxing (`Integer` objects) adds another layer of indirection and scattering. ## Practical guidance (and what NOT to do) - **Prefer contiguous, primitive-backed structures** (`int[]`, `ArrayList`, arrays of values) over node-based ones (`LinkedList`, scattered object graphs) for hot iteration. - **Access in memory order.** For a 2D array stored **row-major** (Java's `int[][]` is an array of row arrays, each row contiguous), iterate **row by row, then column** — the cache-friendly order; iterating column-first jumps across rows and thrashes the cache. - Be aware of **false sharing** in concurrent code (two threads writing different variables on the *same* cache line ping-pong it between cores) — but that's an advanced concern. - **Don't** start hand-counting cache lines or padding structures speculatively. This is a **measure-first** concern: pick locality-friendly data structures and access patterns by default, and only do exotic layout tuning when a profiler (e.g. cache-miss counters) shows memory stalls dominate. ## Key terms recap - **Cache hierarchy (L1/L2/L3):** small-fast to large-slow on-chip memory between the core and RAM. - **Cache hit / miss:** found in cache (fast) vs. must fetch from a slower level (stall). - **Cache line (~64 bytes):** the block size memory is loaded/stored in; touching one byte loads the whole line. - **Spatial / temporal locality:** accessing nearby data soon / reusing the same data soon. - **Prefetcher:** hardware that loads upcoming lines when it detects a regular stride. - **Pointer chasing / dependent load:** following references where each address depends on the previous fetch — serial, miss-prone, no prefetch. - **Row-major:** consecutive elements of a row are contiguous; iterate rows-outer for locality.