5 ms·

Why can't a compiler optimize that? Perhaps I'm naive, but it seems totally possible for a compiler to have some sort of heuristic that allows it to do this tra

Why can't a compiler optimize that? Perhaps I'm naive, but it seems totally possible for a compiler to have some sort of heuristic that allows it to do this transformation behind-the-scenes when it makes sense

Blikkentrekker 5y ago
The ironic part is that the compiler can't because the languages are fairly low level for performance's sake. C and Rust make various guarantees about data layout which programmers rely upon. C compilers cannot turn an array of structs into a struct of arrays because the layout of arrays is guaranteed, and needed to make common and trivial C accesses work which work by pointer arithmetic. Turning an array of structs into a struct of arrays is indeed an optimization that would be possible in a language that did not make such guarantees about data layout. Perhaps it would be interesting to have a data structure that provides less guarantees on lower level access that in turn could be more aggressively optimized.
- gpderetta 5y ago
  It is technically also possible in C as long as the program can't tell the difference (thanks to the as-if rule). This is hard to prove though and in practice requires whole program compilation.
  - Blikkentrekker 5y ago
    The C standard provides guarantees about data layout even if the compiler can prove it will never be used internally, for the sake of, say, external debugging.
    - gpderetta 5y ago
      And C compilers routinely optimize structures in such a way that they are impossible to inspect in a debugger. Because of SRA, non escaping aggregates might even not be allocated on a memory location at all.
      - Blikkentrekker 5y ago
        What is an "escaping aggregate"?; this term has 80 hits on Google, none of which seem to be related to programming. Looking it up “aggregate” is a C++ term for which the standard indeed does explicitly allow various optimizations and guarantees about data layout are weakened; this is not the case with C arrays. Do you have any practical evidence to C compilers altering the data layout of an array in any way?
        throwaway17_17 5y ago
        GP’s comment is referring to Scalar Replacement of Aggregates on the one hand. This is an optimization where by the compiler will, for a function with a Struct argument, only pass in a pointer to / copy of the actual element of the struct used inside a function. Hence the name, the compiler is replacing the aggregate struct by one or more of the individual values it contains. The reference to non-escaping aggregates, describes the compiler optimizing a local only struct by keeping the individual elements in registers during usage, and because the struct as a whole does not leave the local scope, these elements are just discarded when that scope closes. Both of these transformations/optimizations are performed by all three industrial C and C++ compilers (gcc/llvm/msvc).
        gpderetta 5y ago
        Exactly. Thanks.
    - astrange 5y ago
      It doesn't require this as long as the program has the same side effects - the contents of memory are not a side effect necessarily. The problem is that there are lots of operations which imply the existence of part of an object, like passing around pointers or allocating single objects at a time, and that would disable these layout optimizations. An optimization that's easy to break isn't useful even if it would help a lot; you want them to be predictable more than anything.
    - lostmsu 5y ago
      Which sections of the standard are you referring to?

Blikkentrekker 5y ago

The ironic part is that the compiler can't because the languages are fairly low level for performance's sake. C and Rust make various guarantees about data layout which programmers rely upon. C compilers cannot turn an array of structs into a struct of arrays because the layout of arrays is guaranteed, and needed to make common and trivial C accesses work which work by pointer arithmetic. Turning an array of structs into a struct of arrays is indeed an optimization that would be possible in a language that did not make such guarantees about data layout. Perhaps it would be interesting to have a data structure that provides less guarantees on lower level access that in turn could be more aggressively optimized.

gpderetta 5y ago
It is technically also possible in C as long as the program can't tell the difference (thanks to the as-if rule). This is hard to prove though and in practice requires whole program compilation.
- Blikkentrekker 5y ago
  The C standard provides guarantees about data layout even if the compiler can prove it will never be used internally, for the sake of, say, external debugging.
  - gpderetta 5y ago
    And C compilers routinely optimize structures in such a way that they are impossible to inspect in a debugger. Because of SRA, non escaping aggregates might even not be allocated on a memory location at all.
    - Blikkentrekker 5y ago
      What is an "escaping aggregate"?; this term has 80 hits on Google, none of which seem to be related to programming. Looking it up “aggregate” is a C++ term for which the standard indeed does explicitly allow various optimizations and guarantees about data layout are weakened; this is not the case with C arrays. Do you have any practical evidence to C compilers altering the data layout of an array in any way?
      - throwaway17_17 5y ago
        GP’s comment is referring to Scalar Replacement of Aggregates on the one hand. This is an optimization where by the compiler will, for a function with a Struct argument, only pass in a pointer to / copy of the actual element of the struct used inside a function. Hence the name, the compiler is replacing the aggregate struct by one or more of the individual values it contains. The reference to non-escaping aggregates, describes the compiler optimizing a local only struct by keeping the individual elements in registers during usage, and because the struct as a whole does not leave the local scope, these elements are just discarded when that scope closes. Both of these transformations/optimizations are performed by all three industrial C and C++ compilers (gcc/llvm/msvc).
        gpderetta 5y ago
        Exactly. Thanks.
  - astrange 5y ago
    It doesn't require this as long as the program has the same side effects - the contents of memory are not a side effect necessarily. The problem is that there are lots of operations which imply the existence of part of an object, like passing around pointers or allocating single objects at a time, and that would disable these layout optimizations. An optimization that's easy to break isn't useful even if it would help a lot; you want them to be predictable more than anything.
  - lostmsu 5y ago
    Which sections of the standard are you referring to?