Cache-friendly multi-dimensional array iteration in D

caching, d, multidimensional-array

Solution

The outer loop should be `DEPTH` as evidenced by the following program:

import std.stdio;

void main() {
  enum X = 6, Y = 4, Z = 2;
  ubyte[X][Y][Z] root;

  foreach (i, ref level3; root) {
    foreach (j, ref level2; level3) {
      foreach (k, ref level1; level2) {
        writefln("%s %s %s: 0x%x", i, j, k, &level1);
      }
    }
  }   
}

This prints:

0 0 0: 0x7fbfc8b9f0
0 0 1: 0x7fbfc8b9f1
0 0 2: 0x7fbfc8b9f2
0 0 3: 0x7fbfc8b9f3
0 0 4: 0x7fbfc8b9f4
0 0 5: 0x7fbfc8b9f5
0 1 0: 0x7fbfc8b9f6
0 1 1: 0x7fbfc8b9f7
0 1 2: 0x7fbfc8b9f8
0 1 3: 0x7fbfc8b9f9
0 1 4: 0x7fbfc8b9fa
0 1 5: 0x7fbfc8b9fb
0 2 0: 0x7fbfc8b9fc
0 2 1: 0x7fbfc8b9fd
0 2 2: 0x7fbfc8b9fe
0 2 3: 0x7fbfc8b9ff
0 2 4: 0x7fbfc8ba00
0 2 5: 0x7fbfc8ba01
0 3 0: 0x7fbfc8ba02
0 3 1: 0x7fbfc8ba03
0 3 2: 0x7fbfc8ba04
0 3 3: 0x7fbfc8ba05
0 3 4: 0x7fbfc8ba06
0 3 5: 0x7fbfc8ba07
1 0 0: 0x7fbfc8ba08
1 0 1: 0x7fbfc8ba09
1 0 2: 0x7fbfc8ba0a
1 0 3: 0x7fbfc8ba0b
1 0 4: 0x7fbfc8ba0c
1 0 5: 0x7fbfc8ba0d
1 1 0: 0x7fbfc8ba0e
1 1 1: 0x7fbfc8ba0f
1 1 2: 0x7fbfc8ba10
1 1 3: 0x7fbfc8ba11
1 1 4: 0x7fbfc8ba12
1 1 5: 0x7fbfc8ba13
1 2 0: 0x7fbfc8ba14
1 2 1: 0x7fbfc8ba15
1 2 2: 0x7fbfc8ba16
1 2 3: 0x7fbfc8ba17
1 2 4: 0x7fbfc8ba18
1 2 5: 0x7fbfc8ba19
1 3 0: 0x7fbfc8ba1a
1 3 1: 0x7fbfc8ba1b
1 3 2: 0x7fbfc8ba1c
1 3 3: 0x7fbfc8ba1d
1 3 4: 0x7fbfc8ba1e
1 3 5: 0x7fbfc8ba1f

Notice that the addresses are increasing in a linear fashion and that the fastest changing index is `X`. So the inner loop represents `X` and the outer loop represents `Z`.

Problem

I have a static 3-dimensional array in D, generally ``` Struct[WIDTH][HEIGHT][DEPTH] values; ``` with two of these dimensions going into thousands. If I want to iterate over this array accessing memory locations linearly, over which dimension should iterate in the outer loop? `WIDTH` or `DEPTH`?

Original source