Hardware and Software Prefetching in C++ Explained

The question

A loop walks a vector of order handles and, for each, reads the order from a pool. Walking the handles is fast, but reading the orders is slow. Would adding prefetch instructions help?

Hardware prefetchers

Cores watch the stream of memory accesses and fetch lines they expect to be needed before the program asks:

Next-line and adjacent-line prefetchers fetch the neighbour of a line that was just loaded.
Stride prefetchers notice that a load instruction moves by a constant step, forwards or backwards, and run ahead along that stride.
Streamers track several sequential streams at once.

When the next lines are requested ahead of use, the memory latency overlaps the work on the current line and only the first access waits.

Step 1 / 3

Both loops wait for the first cache line.
Step 2 / 3

With prefetching, the next lines are already in cache: the work runs back to back and the loop is finished.
Step 3 / 3

Without it, every new line is another full miss.

They make sequential and strided access almost as fast as cache hits for large arrays, which is a big part of why the vector beat the list in Module 1. They have limits:

They generally stop at 4 KB page boundaries, because the next physical page is unknown to them.
They cannot predict addresses that come from data: an index read from another array, a pointer in a node, a hash.
They can be overwhelmed by too many simultaneous streams.

The question's loop

Walking the handles is a sequential stream, which the hardware prefetches. Reading each order is an indirect access: the address comes from the handle's value, so no hardware prefetcher can predict it. Each order is a likely miss, and if the loop does little work per order, it runs at the speed of those misses (though the out-of-order core overlaps a few, since the misses do not depend on each other).

This is the case software prefetching is for: the program knows the future addresses because it can read them from the handle array ahead of time.

constexpr std::size_t AHEAD = 8;                     // tuned by measurement
for (std::size_t i = 0; i < handles.size(); ++i) {
    if (i + AHEAD < handles.size())
        __builtin_prefetch(&pool[handles[i + AHEAD]], 0 /*read*/, 3 /*keep in all levels*/);
    process(pool[handles[i]]);
}

The prefetch for element i + AHEAD is issued while element i is processed, so by the time the loop reaches it the line has arrived. AHEAD should cover the memory latency divided by the time per iteration; too short and the data has not arrived, too long and it may be evicted before use.

When software prefetching does not help

Sequential data: the hardware already does it; explicit prefetches only add instructions.
Data already in cache: the prefetch is wasted work.
Prefetching too far ahead or too much: lines evict each other, or the prefetches compete with real loads for memory bandwidth.
No independent work: if the address of the next element depends on the current one (a linked list), you cannot prefetch ahead without first walking the list, which is the original problem.

Prefetching must be measured: a change that helps on one machine can hurt on another with different latencies.

Writing without reading: non-temporal stores

Writing a line that is not in the cache first reads it (read for ownership), and then the written line occupies cache space. For large output that will not be read again soon, such as a recording buffer or a log, that is waste on both counts. Non-temporal (streaming) stores, through intrinsics like _mm_stream_si128, write combined lines directly to memory without reading them and without polluting the cache. They need a fence before another thread reads the data, and they are slow if the data is read back soon. Use them only for genuine write-once streams.

The structural fix

Prefetching hides latency; it does not remove it. Before adding prefetches, ask whether the indirection is necessary: if the loop only needs a few fields of each order, keeping those fields in an array parallel to the handles (a structure of arrays) makes the access sequential and lets the hardware do the work.

Check yourself

Question 1 of 3

Which access pattern can hardware prefetchers not predict?

Question 2 of 3

A software prefetch distance is set too large. What can happen?

Question 3 of 3

When are non-temporal stores appropriate?

In the interview

Say your own answer out loud first, then open the one we would give.

What do hardware prefetchers do?

They watch the access stream and fetch lines ahead of use for sequential and constant-stride patterns, within a page. They cannot predict data-dependent addresses such as indices read from another array or pointers in nodes.

When would you use __builtin_prefetch?

For indirect accesses whose future addresses the program can compute in advance, such as walking an array of handles into a pool. I would prefetch a measured distance ahead and check the gain with a benchmark and counters, because on sequential data or data already in cache it only adds overhead.

What are non-temporal stores?

Stores that write directly to memory through write-combining buffers without first reading the line and without keeping it in cache. They suit large write-once output and need a fence before other threads read the result.

Prefetching and streaming access