3 ms·
but they do, from the simplest automatic structure padding to the more complicated flow analysis and packing/vectorization
by HugoDaniel 5y ago
but they do, from the simplest automatic structure padding to the more complicated flow analysis and packing/vectorization
- cnity 5y agoHow could a compiler possibly optimize for cache hits in an array of structures? The only way it could do so is by disobeying the programmers intention with the described memory layout.
- HugoDaniel 5y agoHow can you? Do you know of a CPU that has specific instructions to handle cache allocations?
- cnity 5y agoYou simply take advantage of the fact that an entire cache line is fetched when reading from memory, and keep data that is frequently used together close to each other in memory.
- ratww 5y agoIf you have an array of small structures, all you have to do is access all of them in one go with a for() loop and you're already taking advantage of the cache. This is enforced in ECS frameworks, btw: it's how a "System" is implemented. However, if your code has random access, there's no point in using arrays of structures. The compiler would have to modify the order of execution of instructions inside your method to take advantage of how the data is laid out.
- HugoDaniel 5y agoSure there are great benefits in sequential access, some of these can even be calculated to some extent. However your reply does not answer the question. Do you know of any CPU that has specific instructions to handle cache? How can you be sure that you are gaming cache lines when even the mnemonics are mostly virtualised through all the pipeline and jump/memory pattern predictions?
- ratww 5y agoMy reply is answering the first question, How can you?. Not the second.
- DixieDev 5y agoThe compiler isn't even smart enough to switch for-loops that iterating over a grid when they would greatly improve cache usage. Swapping the lines `for (x=0; x<width; x++)` and `for (y=0; y<height; y++)` can give insane speedups on typical modern hardware.
- astrange 5y agoThey do have that optimization in some cases; it helps on SPECint. It often requires UB to optimize well, which many people aren't into letting it do.
- jcelerier 5y agoBoth GCC and clang are able to do some level of loop interchange optimization
- orwin 5y agoAre you sure about that? It must depend on the compiler.
- megameter 5y agoLast I checked, field declaration order still mattered to structure size and cache usage because the defacto packing and padding rules preserve the order. I admit that I haven't done any C optimization lately so I am curious. It is possible to make this optimization, but it may disrupt codebases that take shortcuts based on an assumed order. And it would be especially difficult to do the analysis of what should take precedence in the cache. Could you link an example of compilers accommodating these optimizations?
- HugoDaniel 5y agoThe clang documentation on vectorisation has a few examples https://llvm.org/docs/Vectorizers.html#slp-vectorizer https://llvm.org/docs/Vectorizers.html#slp-vectorizer Cache precedence and cache line optimisations are black magic, either you know specifically the cpu that you are targeting, or rely on hopium techniques like cache oblivious algorithms that try to reap some benefits. The baseline is to measure, always, before and after optimisation(s). These "Data oriented design" approaches are very hard to measure and change rapidly because they have a profound impact on a codebase, rarely ever change "just one thing" and they err to the less intuitive and less readable side.