6 ms·

One of the cool things in C is the space it leaves for the compiler to perform optimisations. Beyond what is observable, C compilers have almost free reins to

One of the cool things in C is the space it leaves for the compiler to perform optimisations. Beyond what is observable, C compilers have almost free reins to do whatever they want, so long as the observable things are kept the same (output/memory address values, etc...). Data oriented design was a smart-kid anti-pattern thing back then, but I wonder if compilers have evolved enough so that it is useless nowadays? It is by all measures a useless optimization, since it can be placed hidden from the observable object properties. (i.e. who cares if it is an array of structs or a struct of arrays, so long as the vec3 is still a { x, y, z }?)

hsn915 5y ago
One of the core principles (truths?) behind data oriented design is that compilers can never and will never be able to compensate for unoptimized data layouts.
- HugoDaniel 5y ago
  but they do, from the simplest automatic structure padding to the more complicated flow analysis and packing/vectorization
  - cnity 5y ago
    How 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 ago
      How can you? Do you know of a CPU that has specific instructions to handle cache allocations?
      - cnity 5y ago
        You 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 ago
        If 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 ago
        Sure 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 ago
        My reply is answering the first question, How can you?. Not the second.
  - DixieDev 5y ago
    The 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 ago
      They 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 ago
      Both GCC and clang are able to do some level of loop interchange optimization
    - orwin 5y ago
      Are you sure about that? It must depend on the compiler.
  - megameter 5y ago
    Last 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 ago
      The 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.
- MaxBarraclough 5y ago
  This is true today, but I don't see that it must always be so. I'm not a compiler researcher, but isn't there a realistic chance that good things could happen if this became a major research focus? Somewhat related: I believe Jonathan Blow's currently unreleased Jai programming language is meant to do some interesting new things in this area, enabling (or rather, greatly simplifying) automatic transformations relating to memory layouts.
  - garethrowlands 5y ago
    It's not going to happen for C.
  - username90 5y ago
    > But isn't there a realistic chance that good things could happen if this became a major research focus? It has already been a major research focus the past 50 years or so. We have made great strides, yes, but we are still very far from where it needs to be to compete with lower level languages.
  - gnuvince 5y ago
    The compiler can automate some things (take a look at Zig's MultiArrayList for example), but ultimately the programmer must understand the data in their application, how it needs to be transformed, and how to lay it out to be processed efficiently by the hardware. The compiler is a tool, you can set the field to help it do its job, but it's no magic wand, it cannot think and understand your application: only you can do that.
    - MaxBarraclough 5y ago
      > take a look at Zig's MultiArrayList for example Thanks, I'd not seen that before, very neat. [0] I thought it was just going to be an option to be row-major or column-major, but no: Instead of storing a single list of items, MultiArrayList stores separate lists for each field of the struct. Could this be done in C++, perhaps with template metaprogramming? > The compiler is a tool, you can set the field to help it do its job, but it's no magic wand A paraphrasing of a familiar Mike Acton quote. Fittingly it was mentioned in a blog post that mentions the Jai language. [1][2] I find it frustratingly insubstantial. Given we all presumably accept Rice's theorem and how it applies to compiler optimization, it's a rather empty quip, especially considering we're discussing future possibilities. Today's compilers are capable of some impressive optimizations. It doesn't do to just dismiss the idea that tomorrow's compilers might be able to do significantly more with memory layouts. Consider if, decades ago, a sceptic of optimizing compilers had said: Compilers are useful tools, but they are not magic wands, and cannot achieve highly optimized instruction-selection and register-allocation. It cannot think and understand your application: only you can do that. The baseless suggestion that efficient register-allocation is impossible in the absence of a strong AI, would seem laughable today. > it cannot think and understand your application: only you can do that. Today's compilers are not strong AIs, sure enough, but that doesn't speak to the point here. Optimizers and static-analysis tools are capable of reasoning about program behaviour. Again, you haven't justified dismissing the suggestion that future optimizing compilers might be much more sophisticated at this kind of transformation. Perhaps I'm an optimist for arguing for the sufficiently smart compiler, but it doesn't strike me as beyond the realm of possibility. Perhaps the closer answer is to adjust (or indeed replace) our languages to be more amenable to memory layout transformations than C/C++. This would presumably be comparatively easy to implement. [0] https://ziglang.org/documentation/master/std/#std;MultiArrayList https://ziglang.org/documentation/master/std/#std;MultiArray... [1] https://blog.royalsloth.eu/posts/the-compiler-will-optimize-that-away/ https://blog.royalsloth.eu/posts/the-compiler-will-optimize-... [2] https://news.ycombinator.com/item?id=27010965 https://news.ycombinator.com/item?id=27010965
cjfd 5y ago
No, compilers cannot do that. Who says that it is not the case that in one cpp file the data access pattern is completely different than in another cpp file? Hence, it may be that for one ccp file the most efficient way would be to have an array of structs and for another cpp file the most efficient way would be a struct of arrays. The compiler cannot possibly know this so it has to follow the data layout that the programmer has specified.
ratww 5y ago
It's not that simple. Like I said in another comment, organising the data is only half the battle. This optimisation also depends on your code accessing the data in an optimal way. If the code itself is not organised for DOD, then the "optimal" organisation is what we currently have. A per-entity Update method that's accessing different "kinds of data" will perform worse with DOD-organised data. This is why we have an architectural pattern that automates all that, called ECS.
TheCoelacanth 5y ago
What optimizations would hypothetically be allowed and what optimizations the compiler actually has enough information to be allowed to perform are very different. A compiler is hypothetically allowed to convert array-of-struct into struct-of-array, but to actually be allowed to do that it would need to understand every single use of pointers in the entire program. That is extremely challenging, if not impossible.

hsn915 5y ago

One of the core principles (truths?) behind data oriented design is that compilers can never and will never be able to compensate for unoptimized data layouts.

HugoDaniel 5y ago
but they do, from the simplest automatic structure padding to the more complicated flow analysis and packing/vectorization
- cnity 5y ago
  How 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 ago
    How can you? Do you know of a CPU that has specific instructions to handle cache allocations?
    - cnity 5y ago
      You 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 ago
      If 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 ago
        Sure 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 ago
        My reply is answering the first question, How can you?. Not the second.
- DixieDev 5y ago
  The 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 ago
    They 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 ago
    Both GCC and clang are able to do some level of loop interchange optimization
  - orwin 5y ago
    Are you sure about that? It must depend on the compiler.
- megameter 5y ago
  Last 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 ago
    The 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.
MaxBarraclough 5y ago
This is true today, but I don't see that it must always be so. I'm not a compiler researcher, but isn't there a realistic chance that good things could happen if this became a major research focus? Somewhat related: I believe Jonathan Blow's currently unreleased Jai programming language is meant to do some interesting new things in this area, enabling (or rather, greatly simplifying) automatic transformations relating to memory layouts.
- garethrowlands 5y ago
  It's not going to happen for C.
- username90 5y ago
  > But isn't there a realistic chance that good things could happen if this became a major research focus? It has already been a major research focus the past 50 years or so. We have made great strides, yes, but we are still very far from where it needs to be to compete with lower level languages.
- gnuvince 5y ago
  The compiler can automate some things (take a look at Zig's MultiArrayList for example), but ultimately the programmer must understand the data in their application, how it needs to be transformed, and how to lay it out to be processed efficiently by the hardware. The compiler is a tool, you can set the field to help it do its job, but it's no magic wand, it cannot think and understand your application: only you can do that.
  - MaxBarraclough 5y ago
    > take a look at Zig's MultiArrayList for example Thanks, I'd not seen that before, very neat. [0] I thought it was just going to be an option to be row-major or column-major, but no: Instead of storing a single list of items, MultiArrayList stores separate lists for each field of the struct. Could this be done in C++, perhaps with template metaprogramming? > The compiler is a tool, you can set the field to help it do its job, but it's no magic wand A paraphrasing of a familiar Mike Acton quote. Fittingly it was mentioned in a blog post that mentions the Jai language. [1][2] I find it frustratingly insubstantial. Given we all presumably accept Rice's theorem and how it applies to compiler optimization, it's a rather empty quip, especially considering we're discussing future possibilities. Today's compilers are capable of some impressive optimizations. It doesn't do to just dismiss the idea that tomorrow's compilers might be able to do significantly more with memory layouts. Consider if, decades ago, a sceptic of optimizing compilers had said: Compilers are useful tools, but they are not magic wands, and cannot achieve highly optimized instruction-selection and register-allocation. It cannot think and understand your application: only you can do that. The baseless suggestion that efficient register-allocation is impossible in the absence of a strong AI, would seem laughable today. > it cannot think and understand your application: only you can do that. Today's compilers are not strong AIs, sure enough, but that doesn't speak to the point here. Optimizers and static-analysis tools are capable of reasoning about program behaviour. Again, you haven't justified dismissing the suggestion that future optimizing compilers might be much more sophisticated at this kind of transformation. Perhaps I'm an optimist for arguing for the sufficiently smart compiler, but it doesn't strike me as beyond the realm of possibility. Perhaps the closer answer is to adjust (or indeed replace) our languages to be more amenable to memory layout transformations than C/C++. This would presumably be comparatively easy to implement. [0] https://ziglang.org/documentation/master/std/#std;MultiArrayList https://ziglang.org/documentation/master/std/#std;MultiArray... [1] https://blog.royalsloth.eu/posts/the-compiler-will-optimize-that-away/ https://blog.royalsloth.eu/posts/the-compiler-will-optimize-... [2] https://news.ycombinator.com/item?id=27010965 https://news.ycombinator.com/item?id=27010965

cjfd 5y ago

No, compilers cannot do that. Who says that it is not the case that in one cpp file the data access pattern is completely different than in another cpp file? Hence, it may be that for one ccp file the most efficient way would be to have an array of structs and for another cpp file the most efficient way would be a struct of arrays. The compiler cannot possibly know this so it has to follow the data layout that the programmer has specified.

ratww 5y ago

It's not that simple. Like I said in another comment, organising the data is only half the battle. This optimisation also depends on your code accessing the data in an optimal way. If the code itself is not organised for DOD, then the "optimal" organisation is what we currently have. A per-entity Update method that's accessing different "kinds of data" will perform worse with DOD-organised data. This is why we have an architectural pattern that automates all that, called ECS.

TheCoelacanth 5y ago

What optimizations would hypothetically be allowed and what optimizations the compiler actually has enough information to be allowed to perform are very different. A compiler is hypothetically allowed to convert array-of-struct into struct-of-array, but to actually be allowed to do that it would need to understand every single use of pointers in the entire program. That is extremely challenging, if not impossible.