software and hardware prefetching
A cache miss is expensive because the CPU only discovers it needs data at the moment it asks for it, then must wait out the full DRAM latency. Prefetching attacks this by fetching data into cache BEFORE it is actually needed, so that by the time the program reaches the access, the data has already arrived and the miss is hidden. It is the difference between ordering your ingredients only when you start cooking versus having them delivered ahead of time.
There are two kinds. Hardware prefetching is done automatically by a unit in the CPU called the prefetcher, which watches your memory access pattern and, when it detects a regular stride (such as a sequential walk a[0], a[1], a[2], or a fixed-stride march), starts fetching the next lines ahead of demand. This is why a simple sequential scan of a huge array runs near memory bandwidth instead of paying a miss on every line — the prefetcher saw the pattern and ran ahead. Software prefetching is an explicit instruction you (or the compiler) issue, such as the __builtin_prefetch hint in gcc/clang, telling the CPU to start loading an address you know you will need soon but the hardware cannot predict — typically the next node in a linked structure, computed before you actually dereference it.
Be candid about the limits. The hardware prefetcher is very good at regular strides but blind to irregular, data-dependent access like pointer chasing or hashed lookups — exactly the patterns that hurt most — which is where software prefetch can help by issuing the load far enough ahead. But software prefetch is a sharp and easily-misused tool: prefetch too late and the data has not arrived; prefetch too early and it may be evicted before use; prefetch wastefully and you pollute the cache and waste bandwidth, making things slower. It does not change the total data you must move, only when you move it. Treat manual prefetch as a last-resort optimization to apply and measure on a specific hot loop, never a default.
Walking a linked list, dereference node->next blindly and each node is a fresh cache miss the prefetcher cannot foresee. Prefetching one node ahead — __builtin_prefetch(node->next) before processing node — can overlap the next miss with the current node's work, IF the work per node is large enough to hide the latency.
Where the hardware prefetcher is blind (pointer chasing), a manual prefetch may help — but only if timed right.
Manual prefetch is easy to get wrong and often a net loss — wrong distance wastes bandwidth and pollutes cache. The hardware prefetcher already handles regular strides for free, so reach for software prefetch only on irregular hot paths, and always benchmark.