Pointer Alternatives

In the pointer chasing benchmark, for simplicity, we didn’t use actual pointers, but integer indices relative to a base address:

for (int i = 0; i < N; i++)
    k = q[k];

The memory addressing operator on x86 is fused with the address computation, so the k = q[k] line folds into just a single terse instruction that also does multiplication by 4 and addition under the hood:

mov rax, DWORD PTR q[0+rax*4]

Although fully fused, these additional computations add some delay to memory operations. The latency of an L1 fetch is either 4 or 5 cycles — the latter being the case if we need to perform a complex computation of the address. For this reason, the permutation benchmark measures 3ns or 6 cycles per jump: 4+1 for the read and address computation and another one to move the result to the right register.

Pointers

We can make our benchmark run slightly faster if we replace “fake pointers” — indices — with actual pointers.

There are some syntactical issues in getting “pointer to pointer to pointer…” constructions to work, so instead we will define a struct that just wraps a pointers to its own type — this is how most pointer chasing works anyway:

struct node { node* ptr; };

Now we randomly fill our array with pointers and chase them instead:

node* k = q + p[N - 1];

for (int i = 0; i < N; i++)
    k = k->ptr = q + p[i];

for (int i = 0; i < N; i++)
    k = k->ptr;

This code now runs in 2ns / 4 cycles for arrays that fit in the L1 cache. Why not 4+1=5? Because Zen 2 has an interesting feature that allows zero-latency reuse of data accessed just by address, so the “move” here is transparent, resulting in whole two cycles saved.

Unfortunately, there is a problem with it on 64-bit systems as the pointers become twice as large, making the array spill out of cache much sooner compared to using a 32-bit index. The latency-versus-size graph looks like if it was shifted by one power of two to the left — exactly like it should:

This problem is mitigated by switching to the 32-bit mode:

You need to go through some trouble getting 32-bit libs to get this running on a computer made in this century, but this shouldn’t pose other problems unless you need to interoperate with 64-bit software or access more than 4G of RAM

Bit Fields

The fact that on larger problem sizes the performance is bottlenecked by memory rather than CPU lets us try something even more strange: we can use less than 4 bytes for storing indices. This can be done with bit fields:

struct __attribute__ ((packed)) node { int idx : 24; };

You don’t need to do anything else other than defining a structure for the bit field — the compiler handles the 3-byte integer all by itself:

int k = p[N - 1];

for (int i = 0; i < N; i++) {
    k = q[k].idx = p[i];

for (int i = 0; i < N; i++) {
    k = q[k].idx;

This code measures at 6.5ns for the L1 cache. There is some room for improvement as the default conversion procedure chosen by the compiler is suboptimal. We could manually load a 4-byte integer and truncate it ourselves (we also need to add one more element to the q array to ensure we own that extra one byte of memory):

k = *((int*) (q + k));
k &= ((1<<24) - 1);

It now runs in 4ns, and produces the following graph:

If you zoom close enough (the graph is an svg), you’ll see that the pointers win on very small arrays, then starting from around the L2-L3 cache boundary our custom bit fields take over, and for very large arrays it doesn’t matter because we never hit cache anyway.

This isn’t a kind of optimization that can give you a 5x improvement, but it’s still something to try when all the other resources are exhausted.