Gregg: CPU Utilization is Wrong

I think your randomisation isn't going to work properly - it'll produce lots of small cycles, and the 'for' loop will get stuck in one and won't access the whole NELEMs, so you're only really testing the L2 latency. RAM latency should be maybe 10x-20x slower. (Rather than an array of random numbers, maybe use an array of consecutive numbers then randomly shuffle it. And use a decent RNG, not rand().)

To increase latency further you should try a stride of 4096 bytes (1 page), so that every memory access is a TLB miss and requires a page table walk.

The page table walk has to go through four levels of page tables (on x86_64). Apparently they're usually accessed via the data cache to reduce the cost; but if you access widely-separated pages, the cached page table entries won't be much use. One cache line fits 8 page table entries, so a stride of 8 pages should be more expensive. If you use even larger strides (like, say, 2^21 bytes or 2^30 bytes) then you'll get cache misses in the earlier levels of page table too.

Unfortunately you can't reserve more than about 2^46 bytes of virtual memory, and very large strides means you can't fit many elements into that space, and small numbers of elements are too easily cached. On my particular CPU, a decent tradeoff seemed to be looping over an array of 2^12 elements with a stride of 2^34 bytes.

Randomising the pointer chasing can help defeat any cache prefetching logic, but for me it doesn't seem to make a significant difference with strides >= 1 page. (Most of Intel's prefetchers simply never cross page boundaries. Apparently Ivy Bridge has a "next-page prefetcher" but I guess that only works in very specific situations.)

It can also be helpful to misalign your data so that each read straddles two pages. Modern Intel CPUs can do most misaligned accesses just as fast as aligned ones, but if crossing cache lines or pages increases the number of cache/TLB misses then it will still add some cost.

Also you need to unroll the pointer-chasing loop and remove the arithmetic, so it ideally does about 1 instruction per memory read.

With that approach, I can get down to an IPC of roughly 0.001:

#include <algorithm>
#include <sys/mman.h>

#define ELEMENTS (1 << 12)
#define STRIDE (1ull << 34)
#define ITERS (1024*1024*64)
#define OFFSET (STRIDE - 4)
#define UNROLL 16

#define ALIGN_UP(x, a) (((x) + (a) - 1) / (a)) * (a)

int main() {
  void *m = mmap(nullptr,
    STRIDE * ELEMENTS + STRIDE + OFFSET,
    PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS|MAP_NORESERVE, -1, 0);

  uintptr_t base = ALIGN_UP((uintptr_t)m, STRIDE) + OFFSET;

  std::vector<int> indexes(ELEMENTS);
  std::iota(indexes.begin(), indexes.end(), 0);
//  std::shuffle(indexes.begin(), indexes.end(), std::mt19937(0));

  for (int i = 0; i < ELEMENTS; ++i)
    *(uintptr_t *)(base + STRIDE * indexes[i]) = base + STRIDE * indexes[(i+1) % ELEMENTS];

  printf("==================== Setup done ====================\n");

  uintptr_t p = base;
  for (int i = 0; i < ITERS; i += UNROLL)
    for (int j = 0; j < UNROLL; ++j)
      p = *(uintptr_t *)p;

  printf("Result: %p\n", (void *)p);
}

Measuring with "perf stat -e task-clock,cycles,instructions,LLC-load-misses,dTLB-load-misses -I 1000", looking at the stats a few seconds after the "Setup done" message (the setup is very expensive because it's creating lots of page tables):

    1000.220203      task-clock (msec)        
  3,955,098,490      cycles                   
      4,358,278      instructions             
     14,094,438      LLC-load-misses          
      5,215,481      dTLB-load-misses    

(on Core i7-4790, "gcc -O3"). Each instruction takes >1 TLB miss, >3 cache misses, and >900 cycles.

Alternatively you could simply call an instruction like "rep stosb" with a very large repetition count. On my CPU the performance counters seem to count it as 1 instruction per 64KB or thereabouts, and it gives an IPC of around 0.0004.