Expert · Module 23 · Lesson 1 of 4
Cache lines and prefetching
Memory moves in 64-byte lines, not four-byte integers. Count the lines a sequential walk, a stride-3 walk and a linked-list walk each touch, and see why the processor can hide some of those waits but not others.
By the end you can
- Count the cache lines two access patterns touch over the same number of reads
- Explain why a hardware prefetcher follows a fixed stride but not a pointer chase
- Rank L1, L3 and DRAM hits by cost and connect the gap to the price of a miss
Builds on Caches: why neighbors are fast, Arrays vs linked lists on real hardware.
01 · A question first
Two loops add up the same million integers: one reads a[0], a[1], a[2] in order, the other reads a[0], a[3], a[6]. Both do a million additions, yet the strided loop can make about three times as many trips to memory. Big-O calls them both O(n). Where does the extra time come from?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Two loops, one array
- Memory moves in lines
- Counting lines instead of elements
- The cost ladder
- What the prefetcher can follow
- Three walks compared
- Where this shows up
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
03 · Practice
Something wrong with this lesson? Report a problem