When should we use prefetch?

by

This question isn’t really about compilers as they’re just providing some hook to insert prefetch instructions into your assembly code / binary. Different compilers may provide different intrinsic formats but you can just ignore all these and (carefully) add it directly in assembly code.

Now the real question seems to be “when are prefetches useful”, and the answer is – in any scenario where youre bounded on memory latency, and the access pattern isn’t regular and distinguishable for the HW prefetch to capture (organized in a stream or strides), or when you suspect there are too many different streams for the HW to track simultaneously.
Most compilers would only very seldom insert their own prefetches for you, so it’s basically up to you to play with your code and benchmark how prefetches could be useful.

The link by @Mysticial shows a nice example, but here’s a more straight forward one that I think can’t be caught by HW:

#include "stdio.h"
#include "sys/timeb.h"
#include "emmintrin.h"

#define N 4096
#define REP 200
#define ELEM int

int main() {
    int i,j, k, b;
    const int blksize = 64 / sizeof(ELEM);
    ELEM __attribute ((aligned(4096))) a[N][N];
    for (i = 0; i < N; ++i) {
        for (j = 0; j < N; ++j) {
            a[i][j] = 1;
        }
    }
    unsigned long long int sum = 0;
    struct timeb start, end;
    unsigned long long delta;

    ftime(&start);
    for (k = 0; k < REP; ++k) {
        for (i = 0; i < N; ++i) {
            for (j = 0; j < N; j ++) {
                sum += a[i][j];
            }
        }
    }
    ftime(&end);
    delta = (end.time * 1000 + end.millitm) - (start.time * 1000 + start.millitm);
    printf ("Prefetching off: N=%d, sum=%lld, time=%lld\n", N, sum, delta); 

    ftime(&start);
    sum = 0;
    for (k = 0; k < REP; ++k) {
        for (i = 0; i < N; ++i) {
            for (j = 0; j < N; j += blksize) {
                for (b = 0; b < blksize; ++b) {
                    sum += a[i][j+b];
                }
                _mm_prefetch(&a[i+1][j], _MM_HINT_T2);
            }
        }
    }
    ftime(&end);
    delta = (end.time * 1000 + end.millitm) - (start.time * 1000 + start.millitm);
    printf ("Prefetching on:  N=%d, sum=%lld, time=%lld\n", N, sum, delta); 
}

What I do here is traverse each matrix line (enjoying the HW prefetcher help with the consecutive lines), but prefetch ahead the element with the same column index from the next line that resides in a different page (which the HW prefetch should be hard pressed to catch). I sum the data just so that it’s not optimized away, the important thing is that I basically just loop over a matrix, should have been pretty straightforward and simple to detect, and yet still get a speedup.

Built with gcc 4.8.1 -O3, it gives me an almost 20% boost on an Intel Xeon X5670:

Prefetching off: N=4096, sum=3355443200, time=1839
Prefetching on:  N=4096, sum=3355443200, time=1502

Note that the speedup is received even though I made the control flow more complicated (extra loop nesting level), the branch predictor should easily catch the pattern of that short block-size loop, and it saves execution of unneeded prefetches.

Note that Ivybridge and onward on should have a “next-page prefetcher”, so the HW may be able to mitigate that on these CPUs (if anyone has one available and cares to try i’ll be happy to know). In that case i’d modify the benchmark to sum every second line (and the prefetch would look ahead two lines everytime), that should confuse the hell out of the HW prefetchers.

Skylake results

Here are some results from a Skylake i7-6700-HQ, running at 2.6 GHz (no turbo) with gcc:

Compile flags: -O3 -march=native

Prefetching off: N=4096, sum=28147495993344000, time=896
Prefetching on:  N=4096, sum=28147495993344000, time=1222
Prefetching off: N=4096, sum=28147495993344000, time=886
Prefetching on:  N=4096, sum=28147495993344000, time=1291
Prefetching off: N=4096, sum=28147495993344000, time=890
Prefetching on:  N=4096, sum=28147495993344000, time=1234
Prefetching off: N=4096, sum=28147495993344000, time=848
Prefetching on:  N=4096, sum=28147495993344000, time=1220
Prefetching off: N=4096, sum=28147495993344000, time=852
Prefetching on:  N=4096, sum=28147495993344000, time=1253

Compile flags: -O2 -march=native

Prefetching off: N=4096, sum=28147495993344000, time=1955
Prefetching on:  N=4096, sum=28147495993344000, time=1813
Prefetching off: N=4096, sum=28147495993344000, time=1956
Prefetching on:  N=4096, sum=28147495993344000, time=1814
Prefetching off: N=4096, sum=28147495993344000, time=1955
Prefetching on:  N=4096, sum=28147495993344000, time=1811
Prefetching off: N=4096, sum=28147495993344000, time=1961
Prefetching on:  N=4096, sum=28147495993344000, time=1811
Prefetching off: N=4096, sum=28147495993344000, time=1965
Prefetching on:  N=4096, sum=28147495993344000, time=1814

So using prefetch is either about 40% slower, or 8% faster depending on if you use -O3 or -O2 respectively for this particular example. The big slowdown for -O3 is actually due to a code generation quirk: at -O3 the loop without prefetch is vectorized, but the extra complexity of the prefetch variant loop prevents vectorization on my version of gcc anyway.

So the -O2 results are probably more apples-to-apples, and the benefit is about half (8% speedup vs 16%) of what we saw on Leeor’s Westmere. Still it’s worth noting that you have to be careful not to change code generation such that you get a big slowdown.

This test probably isn’t ideal in that by going int by int implies a lot of CPU overhead rather than stressing the memory subsystem (that’s why vectorization helped so much).

More Related Contents:

  1. Are there any modern CPUs where a cached byte store is actually slower than a word store?
  2. Non-temporal loads and the hardware prefetcher, do they work together?
  3. What is the best way to set a register to zero in x86 assembly: xor, mov or and?
  4. Enhanced REP MOVSB for memcpy
  5. INC instruction vs ADD 1: Does it matter?
  6. Adding a redundant assignment speeds up code when compiled without optimization
  7. Why is Skylake so much better than Broadwell-E for single-threaded memory throughput?
  8. Why is this SSE code 6 times slower without VZEROUPPER on Skylake?
  9. Understanding the impact of lfence on a loop with two long dependency chains, for increasing lengths
  10. What are the latency and throughput costs of producer-consumer sharing of a memory location between hyper-siblings versus non-hyper siblings?
  11. Is there a penalty when base+offset is in a different page than the base?
  12. What happens after a L2 TLB miss?
  13. Branch alignment for loops involving micro-coded instructions on Intel SnB-family CPUs
  14. Why is XCHG reg, reg a 3 micro-op instruction on modern Intel architectures?
  15. What methods can be used to efficiently extend instruction length on modern x86?
  16. 32-byte aligned routine does not fit the uops cache
  17. Why is SSE scalar sqrt(x) slower than rsqrt(x) * x?
  18. Lost Cycles on Intel? An inconsistency between rdtsc and CPU_CLK_UNHALTED.REF_TSC
  19. Which Intel microarchitecture introduced the ADC reg,0 single-uop special case?
  20. Can modern x86 implementations store-forward from more than one prior store?
  21. What’s the actual effect of successful unaligned accesses on x86?
  22. Assembly – How to score a CPU instruction by latency and throughput
  23. Unexpectedly poor and weirdly bimodal performance for store loop on Intel Skylake
  24. Why can’t my ultraportable laptop CPU maintain peak performance in HPC
  25. How are cache memories shared in multicore Intel CPUs?
  26. Modern x86 cost model
  27. Cycles/cost for L1 Cache hit vs. Register on x86?
  28. Return address prediction stack buffer vs stack-stored return address?
  29. Relative performance of x86 inc vs. add instruction
  30. Efficient sse shuffle mask generation for left-packing byte elements

Leave a Comment