What is a cache line?
A cache line is the fixed-size block of bytes that a CPU cache always moves as a single unit between main memory and the cache — typically 64 bytes on common processors — so asking for one value always brings its neighboring bytes along for the ride.
Why does the cache transfer whole blocks instead of individual bytes?
Moving data between main memory and the CPU is expensive in latency, so hardware designers amortize that cost by transferring a whole contiguous block whenever any byte inside it is needed. That block is the cache line: once it arrives, every value sitting inside those same 64 bytes (or whatever the line size is on that chip) becomes available at cache speed without another trip to RAM. The design assumes that programs often use nearby data soon after touching one address — a property called spatial locality — and packing transfers into fixed lines is how the hardware bets on that assumption. The flip side is that a program which needs only four bytes still pays for the full line, and a program that scatters its accesses across many distant addresses will pull in entire lines that it barely uses.
That block-transfer rule is the concrete reason memory layout choices change HNSW‘s measured speed even when the algorithm itself stays fixed.
How does a cache line interact with the vectors HNSW compares?
A high-dimensional vector is a long sequence of numbers stored one after another. When a distance calculation starts reading that vector from the beginning, the first access pulls in one cache line covering the opening dimensions, and as the loop continues it naturally walks into the next lines in order. Because those lines are contiguous, sequential vector arithmetic tends to get good mileage out of each transfer: most of the bytes that arrived with the line are actually consumed by the distance loop. Shorter vectors may even fit in a handful of lines; longer ones spill across many, but the accesses remain sequential, so the hardware’s prefetchers can often start fetching the next line before the loop explicitly asks for it. This is why contiguous vector storage and aligned layouts matter — they turn the cache line’s all-or-nothing transfer into an advantage rather than wasted bandwidth.
Neighbor lists and graph hops tell a different story, because the unit of useful work is often much smaller than a full line and the next useful address is rarely the next one in memory.
Why do HNSW’s graph hops waste so much of each cache line?
Following a neighbor edge typically means reading a compact node ID, then jumping to that node’s vector and its own neighbor list somewhere else in the index. The ID itself may be only four or eight bytes, yet fetching it still brings an entire cache line of surrounding bytes that the hop may never touch. The next hop then jumps to a different region entirely, so the leftover bytes from the previous line sit unused while a fresh miss pulls another mostly-unrelated line. Over hundreds of hops in a single search, that pattern multiplies: the processor spends bandwidth and latency moving whole lines whose useful payload is a tiny fraction of their size. Packing neighbor IDs tightly into contiguous arrays, keeping a node’s hot metadata together, and avoiding pointer-chasing layouts that scatter related fields are all ways of putting more useful bytes inside each line the search is forced to pay for.
False sharing is the concurrent cousin of the same line-sized unit, and it shows up once multiple threads update data that happens to share a line.
How can two threads fight over a cache line they are not even sharing logically?
Because ownership and coherence work at line granularity, two threads writing different fields that happen to live inside the same cache line still force the hardware to bounce that line back and forth between cores. Neither thread is sharing a variable on purpose, but they are sharing a line, and the coherence traffic looks almost as expensive as true sharing. In a multithreaded HNSW build or a concurrent query path that updates per-thread statistics packed too tightly, this false sharing can quietly inflate latency even though the algorithm’s locks look correct. Aligning hot per-thread counters or per-node write targets onto separate lines is the usual fix — another reminder that the cache line, not the logical field, is the unit the hardware actually cares about.
A cache line is the hardware’s transfer quantum, and every HNSW layout decision either packs useful work into those blocks or pays for bytes the search never reads. From here, the glossary page on cache misses covers what happens when the needed line is absent, the page on false sharing goes deeper into the concurrent case, locality of reference explains the access-pattern assumption behind line-sized transfers, and the chapter on laying out HNSW’s data structures in memory shows how to design neighbor lists and vectors so each line earns its keep.