Optimising 2D array indexing for cache line

This is probably not useful, but it may be interesting.

You could use Z-order addressing. It will map aligned 8x8 blocks to cache lines, so as long as you stay within one aligned 8x8 block you're always using the same cache line. But weird things sometimes happen when you cross from one block into the next.

Generating a Z-order address from an (x, y) pair is a little annoying:

static uint Interleave(uint x, uint y)
{
    y = (y | (y << 1)) & 0x00FF00FF;
    y = (y | (y << 2)) & 0x0F0F0F0F;
    y = (y | (y << 4)) & 0x33333333;
    y = (y | (y << 8)) & 0x55555555;

    x = (x | (x << 1)) & 0x00FF00FF;
    x = (x | (x << 2)) & 0x0F0F0F0F;
    x = (x | (x << 4)) & 0x33333333;
    x = (x | (x << 8)) & 0x55555555;

    return x | (y << 1);
}

(this is C#, should be easy to convert to C)

Less annoying if you have a CPU that supports PDEP, which is, so far, only Haswell.

But you probably don't need to do that often. You can directly increment or decrement the x or y part of a Z-order address (it's generalizable to adding any pair of constants (c1, c2) to a Z-address, if they are both nonzero it takes a little more code), like this: (those don't do any bounds checking)

static uint IncX(uint z)
{
    uint xsum = (z | 0xAAAAAAAA) + 1;
    return (xsum & 0x55555555) | (z & 0xAAAAAAAA);
}

static uint IncY(uint z)
{
    uint ysum = (z | 0x55555555) + 2;
    return (ysum & 0xAAAAAAAA) | (z & 0x55555555);
}

static uint DecX(uint z)
{
    uint xsum = (z & 0x55555555) - 1;
    return (xsum & 0x55555555) | (z & 0xAAAAAAAA);
}

static uint DecY(uint z)
{
    uint ysum = (z & 0xAAAAAAAA) - 2;
    return (ysum & 0xAAAAAAAA) | (z & 0x55555555);
}

You can even throw in some kinds of bounds-checking. I have routines for saturating increment/decrement, I'm only about 90% sure that they work though. Wrapping modulo a power of two is trivial, just do a binary AND on the result.

The addressing with the Z-coordinate is trivial, just add it to the base of the array. Moving is slightly more complicated than in (x, y) space, but if you combine this with the idea from your other post (looking up an area) you never even need to move (except in the computation of that lookup table, obviously). Packing a good surrounding area may be harder. But there is a less-good surrounding area that becomes trivial: offset the Z coordinate directly in Z-space in both directions and take everything in between (say, from Z-8 to Z+7). That will simulate fewer steps at once on average since it's not usually a square block and the current position is usually not in the middle, but the index into the lookup table would be easier to compute.

edit: it's probably better to take an aligned block instead of a range, because the ant can never walk from one of the "parts" of an unaligned range into an other "part" (the parts are, at best, diagonally connected, so it would have to step outside). That's also easy, just AND the least significant bits off of the Z-coordinate to get the start of the aligned block. The lookup table will need those least significant bits though so they have to become part of the index.

I don't expect this approach to win. But it's interesting, IMO.