Most efficient data layout for a symmetrical 3d mesh when interpolating nearest 8 vertices to random sampled point on Intel CPU
<p>I have a lookup table of 3d data (a 3D RGB lookup table) where I have preset values of f(r,g,b) for each ri, gi, bi (r, g and b not necessarily evenly spaced). n happens to be the same for r g and b in this case.</p>

<p>r1,r2, ...., rn
g1,g2, ...., gn
b1,b2, ...., bn</p>

<p>I need to calculate and store many millions of estimated f(r,g,b) values from any input (r,g,b) image by interpolating between the the f() values of the nearest 8 vertices surrounding r,g,b. The successive input r,g,b values are RGB video pixels and are not particularly predictable. They may be similar but not identical for a few dozen values then change rapidly. Values of R,G,B near the midpoint will typically be more common than very extreme values though. The table of f() values is preset and doesn't change - I can't make assumptions about f() other than the sampling intervals of f() are sufficiently fine that interpolating vertices is a reasonable estimate. I'm targetting higher end Intel CPUs using C++. </p>

<p>Given that the entire table could be large (several MB) and may not fit in the L1 or L2 cache, is there a cache-efficient layout which isn't very expensive to index and keeps 8 neighbouring vertices nearer to each other in memory to make cache misses less likely? Is it likely to perform badly if I'm using the same f() table from multiple threads to increase speed?</p>

<p>My first thought is to use a simple linear C array and calculate an index into it - ftable[r + n <em>(g + n</em>b)] </p>

<p>One alternative is to use C style 3d arrays with their multiple lookups - ftable[r][g][b] but it seems likely to perform worse given the relative cheapness of a couple of additions and multiplies for indexing versus the expense of lookups and potential L1/L2 cache misses. Alternatively is there a cunning method of laying out a C style 3D array that improves cache hit rate for looking up 8 neighbouring vertices of an essentially random input value?</p>