I've read in several places at this point that to get the most out of your CPU's cache, it's important to pack relevant data together, and access it in a linear fashion. That way the first access to that region of memory loads it into a cache line, and the remaining accesses will be much cheaper. One thing that isn't clear to me, however, is how many cache lines you can have "active" at once.

So for example, if you have a series of 3D vectors, and you lay them out like this:

[xxxx...]
[yyyy...]
[zzzz...]

And then you access your data as:

for (std::size_t i = 0; i < len; ++i) {
    auto x_i = x[i];
    auto y_i = y[i];
    auto z_i = z[i];

    // Do something with x, y, and z
}

Does each array get it's own cache line? Or does accessing the 'y' element push 'x' out of the cache, and then accessing the 'z' element push 'y' out of the cache? If you were to iterate backwards, would that cause more cache misses than iterating forwards?

On another note, while I try to follow best practices for this stuff where possible, I literally have zero idea how effective (or ineffective) it is, since I have no tools for profiling it, and I don't have time write one version of something and then test it against another. Are there any free (or free for students) tools for cache profiling on Windows? I'd love to use Valgrind, but I don't have anything that can run Linux that is also powerful enough to run my game.

Thanks!

The structure of arrays is ONE useful solution, but like every solution it can be misapplied.

The fundamental issue is how the data is accessed. The pattern matches one efficient way to access the data but it is not the only way, and if your access pattern doesn't match the data layout it will backfire.

Does each array get it's own cache line?

A cache line has been 64-bytes for many years now. It will likely eventually become 128 bytes.

Or does accessing the 'y' element push 'x' out of the cache, and then accessing the 'z' element push 'y' out of the cache?

Probably not. Modern processors have large caches, but the inner workings of how they load and evict contents is an implementation detail. There is no guarantee that they work any particular way.

There is a prediction system that can evaluate the current memory accesses and the memory addresses coming through the pipeline (about 30 instructions currently). It can start prefetching your data quite early.

Object sizes still play a role. If your data is not at a 64-byte stride or something easily predictable (96 bytes, 128 bytes, 160 bytes, etc) then it cannot be readily predicted. If it fits on the same cache line the processing is very nearly free. If it doesn't fit on the cache line but the prefetcher is able to predict it the cost is more than it being in L1 but far less than a full cache miss.

It is the cache prediction that gives the big speed advantage in this case. If it cannot predict what is next there will probably be a cache miss.

If you were to iterate backwards, would that cause more cache misses than iterating forwards?

Cache predictor is usually good about those things.

On another note, while I try to follow best practices for this stuff where possible, I literally have zero idea how effective (or ineffective) it is, since I have no tools for profiling it, and I don't have time write one version of something and then test it against another. Are there any free (or free for students) tools for cache profiling on Windows?

AMD's profiler CodeXL can do it. It was made open source, freely available on github. If you haven't used a profiler before you will likely have a bit of a learning curve, but there are many online guides.

Be aware that a structure of arrays really only helps when you are accessing your data sequentially as data streams. Having SoA doesn't provide any benefit if you are jumping around the array, or if you are using individual elements as objects, in which case the array of structures can be better because you're touching all those data members instead. The key detail is that whatever format you have for the data, it should be processed as a regular interval to enable prediction and tightly packed sequentially so multiple data read values span a single cache line.