How to fetch a memory location in C++ without waiting for its retrieval?

user_2571490 0
Viewed 529

Suppose we want to fetch a value from an array.

In some cases, we know that the data is in data[i].

In other cases, we need to move the index by some offset: i += offset[i]

i = ....

FETCH data[i];         // The result could be here if the offset_shifts is 0 
                       // Or if i is very small (data[i] is in the same cache line & page)

i += offset_shifts[i];     // LLC cache miss (and most probably a TLB miss)

result = data[i];       // LLC cache miss (and most probably a TLB miss), 
                        // unless it is obtained by an earlier FETCH

The benefit that I expect from this trick is that if offset_shifts[i] is small, then it means that there will be no TLB & LLC cache misses, so that those lookups can be done with the overhead of ONE memory lookup (instead of two)

How can I fetch the value of data[i] at the same time that offset_shifts[i] is being fetched from memory? In other words, what is the proper way to implement such a "non-blocking fetch" in C++?

compiler-optimization latency caching optimization c++
2 Answers

The C++ language standard doesn't provide support for this, but some compilers do. For example, GCC provides __builtin_prefetch:

Built-in Function: void __builtin_prefetch (const void *addr, ...)

This function is used to minimize cache-miss latency by moving data into a
cache before it is accessed. You can insert calls to __builtin_prefetch into
code for which you know addresses of data in memory that is likely to be
accessed soon. If the target supports them, data prefetch instructions are 
generated. If the prefetch is done early enough before the access then the
data will be in the cache by the time it is accessed.

The value of addr is the address of the memory to prefetch. There are two
optional arguments, rw and locality. The value of rw is a compile-time
constant one or zero; one means that the prefetch is preparing for a write to
the memory address and zero, the default, means that the prefetch is preparing
for a read. The value locality must be a compile-time constant integer between
zero and three. A value of zero means that the data has no temporal locality,
so it need not be left in the cache after the access. A value of three means
that the data has a high degree of temporal locality and should be left in all
levels of cache possible. Values of one and two mean, respectively, a low or
moderate degree of temporal locality. The default is three.

for (i = 0; i < n; i++)
  {
    a[i] = a[i] + b[i];
    __builtin_prefetch (&a[i+j], 1, 1);
    __builtin_prefetch (&b[i+j], 0, 1);
    /* … */
  }

Data prefetch does not generate faults if addr is invalid, but the address
expression itself must be valid. For example, a prefetch of p->next does not
fault if p->next is not a valid address, but evaluation faults if p is not a
valid address.

If the target does not support data prefetch, the address expression is
evaluated if it includes side effects but no other code is generated and
GCC does not issue a warning.

I'd recommend taking some measurements afterwards to see if prefetching actually helps significantly - no point complicating your code with non-portable compiler features for nothing.

user_4107670

In portable C++, I'd solve it as follows:

result = data[i]; // Unconditional!
auto offset = offset_shifts[i];
if (offset)
   result = data[i+offset];

The rationale is that result is likely just a register, so result = data[i]; is effectively just a read. This will start the read, but not block the CPU pipeline for the next operation. offset_shifts[i] is effectively retrieved in parallel with the previous operation. (The optimizer may even swap the two operations - it knows more about CPU's than I do). If the branch is taken, you get the intended cache effect. If not taken, the operation is as effective as it can be.

MSalters_154160
Related