5 ms·

TL;DR "Optimizing compilers are still good to have because they are cheaper than programmer labour needed for hand optimization" The original DJB presentation,

by zurn 9y ago

TL;DR "Optimizing compilers are still good to have because they are cheaper than programmer labour needed for hand optimization" The original DJB presentation, which this is a response to, is very good and interesting. It would really be nice if the field of compiler engineering started to address the obvious neglected areas, like optimizing memory layout and data types/representations based on partial evaluation / profile feedback.

sanxiyn 9y ago
> It would really be nice if the field of compiler engineering started to address the obvious neglected areas, like optimizing memory layout Interesting tidbit: LLVM was developed by Chris Lattner for his PhD thesis. It was titled "Macroscopic Data Structure Analysis and Optimization" and about "Instead of analyzing individual load/store operations or structure definitions, this approach identifies, analyzes, and transforms entire memory structures as a unit", in his own words. Apparently, the world was more interested in a good compiler framework than specific memory layout optimization proposed. http://llvm.org/pubs/2005-05-04-LattnerPHDThesis.html http://llvm.org/pubs/2005-05-04-LattnerPHDThesis.html
DannyBee 9y ago
" like optimizing memory layout and data types/representations based on partial evaluation / profile feedback." They already can. The issue is usually one of what is allowable within language semantics, not of compiler optimization technology. One reason you may see this as neglected is that outside of, say, polyhedral loop optimizations, research in the 80's and 90's (and sometimes earlier) did a really really good job of exploring this area because fortran allowed so much freedom.
- zurn 9y ago
  Compilers and languages of course co-evolve. And we already have fairly widespread production use of invasive language extensions/dialects designed to enable use of parallelism, such as OpenMP and CUDA. And older language extensions that have ove time become everyday stuff, like SIMD intrinsics. So I don't think "languages don't support it" is a good excuse.
  - DannyBee 9y ago
    "And we already have fairly widespread production use of invasive language extensions/dialects designed to enable use of parallelism, such as OpenMP and CUDA" I'm not sure you are really saying anything that proves me wrong? Using those extensions, there are optimizing compilers that will perform very heavy memory layout optimization. Which does, in fact, go to show that it took "invasive language extensions" to make the original language able to be optimized in this fashion? IE you invasively changed the original semantics, and now it made these things possible. How does that not show that the original language semantics were not the problem, which is what i said?
    - zurn 9y ago
      Maybe OpenMP and CUDA do more optimizations than I thought they did. Do they perform AoS->SoA reorganizations, conversions from pointer members to inline members, or range analysis to choose smaller data types? Admittedly foremost I was thinking about entirely different kinds of data and layout optimizations: Herarchical data, pointer heavy structures, and potential compressed representations. Things like converting node pointers into 16-bit indices into a node array.
      - jlebar 9y ago
        > Maybe OpenMP and CUDA do more optimizations than I thought they did. Do they perform [...] range analysis to choose smaller data types? CUDA compiler developer here. We definitely perform range analysis on values stored in registers. This is an important optimization. Via scalar replacement of aggregates, we can sometimes also replace a struct with a set of scalars. Once we do that, we can again perform range analysis on those scalars. We can't change structs that don't get SROA'ed because of limitations of the language. For one thing, essentially any memory we write to the GPU's global memory can be read from the CPU side, and it's basically impossible to tell what is and isn't read, so we have to keep the memory layout the same.
        gcp 9y ago
        SROA'ed What does this mean? (Glad you're enjoying your time at Google, Justin!)
- moomin 9y ago
  Indeed. C# optimises struct memory layout unless told not to, C and C++ don't and can't.
  - kccqzy 9y ago
    I know C and C++ can't because the language standard forbids it. Anyone knows the reason why? It should be hard but doable. That's, of course, assuming everyone properly uses macros like offsetof instead of (shudder) hand-calculated offsets, does not use type punning to access the first members of structs, etc. The compiler will certainly need to store the memory layout to enable separate compilation of translation units so that's a complication. Any other issues I haven't thought of?
    - nhaehnle 9y ago
      Actually, the C (and I believe C++) language standards both allow reorganizing struct layouts, except for the first member which has to be in first place (for tagged unions). The struct layout is fixed by platform-specific ABI documents, which must specify the layout precisely so that structs can be passed between separately compiled code, e.g. between applications and dynamically linked libraries. Changing ABIs is virtually impossible, so... It would be nice to see opt-in optimizations of struct layouts, e.g. by annotating structs with a packing-style attribute. Though the best gains would probably be obtained from profile-guided optimizations for cache line optimizations, and those can only really be done with link-time optimizations for structs that are not passed outside the linker's scope.
      - gpderetta 9y ago
        The compiler is free to change the layout (even from AOS to SOA) as long as it can prove that the program can't tell the difference. Of course this is hard to prove in practice even with whole program optimization.
      - Sean1708 9y ago
        > It would be nice to see opt-in optimizations of struct layouts, e.g. by annotating structs with a packing-style attribute. Like __attribute__((packed))[0]? [0]: https://gcc.gnu.org/onlinedocs/gcc-3.3/gcc/Type-Attributes.html https://gcc.gnu.org/onlinedocs/gcc-3.3/gcc/Type-Attributes.h...
ttd 9y ago
Optimizing memory and cache use has been a primary focus of compiler research for a while now. I'm don't understand why you say partial evaluation w.r.t. optimizing memory use is a neglected area though: I think partial evaluation is orthogonal to this, and useful in other optimization types as well. For some recent compiler research with regards to optimizing memory and cache use, see e.g. "Optimizing Indirect Memory References with Milk", PACT 2016 [1]. [1] http://dl.acm.org/citation.cfm?doid=2967938.2967948 http://dl.acm.org/citation.cfm?doid=2967938.2967948
- zurn 9y ago
  The research side may not be the main culprit, hence I said "compiler engineering" - meaning usable tools delivered to the hands of developers. Though I think the research side has not focused on this enough either. Regarding the Milk paper specifically, it appears to be about reordering and clustering memory accesses without changes to data layout. This is a fine thing but I think it reinforces my point about lack of attention to memory/data layout optimizations.

by zurn 9y ago

sanxiyn 9y ago

> It would really be nice if the field of compiler engineering started to address the obvious neglected areas, like optimizing memory layout Interesting tidbit: LLVM was developed by Chris Lattner for his PhD thesis. It was titled "Macroscopic Data Structure Analysis and Optimization" and about "Instead of analyzing individual load/store operations or structure definitions, this approach identifies, analyzes, and transforms entire memory structures as a unit", in his own words. Apparently, the world was more interested in a good compiler framework than specific memory layout optimization proposed. http://llvm.org/pubs/2005-05-04-LattnerPHDThesis.html http://llvm.org/pubs/2005-05-04-LattnerPHDThesis.html

DannyBee 9y ago

" like optimizing memory layout and data types/representations based on partial evaluation / profile feedback." They already can. The issue is usually one of what is allowable within language semantics, not of compiler optimization technology. One reason you may see this as neglected is that outside of, say, polyhedral loop optimizations, research in the 80's and 90's (and sometimes earlier) did a really really good job of exploring this area because fortran allowed so much freedom.

zurn 9y ago
Compilers and languages of course co-evolve. And we already have fairly widespread production use of invasive language extensions/dialects designed to enable use of parallelism, such as OpenMP and CUDA. And older language extensions that have ove time become everyday stuff, like SIMD intrinsics. So I don't think "languages don't support it" is a good excuse.
- DannyBee 9y ago
  "And we already have fairly widespread production use of invasive language extensions/dialects designed to enable use of parallelism, such as OpenMP and CUDA" I'm not sure you are really saying anything that proves me wrong? Using those extensions, there are optimizing compilers that will perform very heavy memory layout optimization. Which does, in fact, go to show that it took "invasive language extensions" to make the original language able to be optimized in this fashion? IE you invasively changed the original semantics, and now it made these things possible. How does that not show that the original language semantics were not the problem, which is what i said?
  - zurn 9y ago
    Maybe OpenMP and CUDA do more optimizations than I thought they did. Do they perform AoS->SoA reorganizations, conversions from pointer members to inline members, or range analysis to choose smaller data types? Admittedly foremost I was thinking about entirely different kinds of data and layout optimizations: Herarchical data, pointer heavy structures, and potential compressed representations. Things like converting node pointers into 16-bit indices into a node array.
    - jlebar 9y ago
      > Maybe OpenMP and CUDA do more optimizations than I thought they did. Do they perform [...] range analysis to choose smaller data types? CUDA compiler developer here. We definitely perform range analysis on values stored in registers. This is an important optimization. Via scalar replacement of aggregates, we can sometimes also replace a struct with a set of scalars. Once we do that, we can again perform range analysis on those scalars. We can't change structs that don't get SROA'ed because of limitations of the language. For one thing, essentially any memory we write to the GPU's global memory can be read from the CPU side, and it's basically impossible to tell what is and isn't read, so we have to keep the memory layout the same.
      - gcp 9y ago
        SROA'ed What does this mean? (Glad you're enjoying your time at Google, Justin!)
moomin 9y ago
Indeed. C# optimises struct memory layout unless told not to, C and C++ don't and can't.
- kccqzy 9y ago
  I know C and C++ can't because the language standard forbids it. Anyone knows the reason why? It should be hard but doable. That's, of course, assuming everyone properly uses macros like offsetof instead of (shudder) hand-calculated offsets, does not use type punning to access the first members of structs, etc. The compiler will certainly need to store the memory layout to enable separate compilation of translation units so that's a complication. Any other issues I haven't thought of?
  - nhaehnle 9y ago
    Actually, the C (and I believe C++) language standards both allow reorganizing struct layouts, except for the first member which has to be in first place (for tagged unions). The struct layout is fixed by platform-specific ABI documents, which must specify the layout precisely so that structs can be passed between separately compiled code, e.g. between applications and dynamically linked libraries. Changing ABIs is virtually impossible, so... It would be nice to see opt-in optimizations of struct layouts, e.g. by annotating structs with a packing-style attribute. Though the best gains would probably be obtained from profile-guided optimizations for cache line optimizations, and those can only really be done with link-time optimizations for structs that are not passed outside the linker's scope.
    - gpderetta 9y ago
      The compiler is free to change the layout (even from AOS to SOA) as long as it can prove that the program can't tell the difference. Of course this is hard to prove in practice even with whole program optimization.
    - Sean1708 9y ago
      > It would be nice to see opt-in optimizations of struct layouts, e.g. by annotating structs with a packing-style attribute. Like __attribute__((packed))[0]? [0]: https://gcc.gnu.org/onlinedocs/gcc-3.3/gcc/Type-Attributes.html https://gcc.gnu.org/onlinedocs/gcc-3.3/gcc/Type-Attributes.h...

ttd 9y ago

Optimizing memory and cache use has been a primary focus of compiler research for a while now. I'm don't understand why you say partial evaluation w.r.t. optimizing memory use is a neglected area though: I think partial evaluation is orthogonal to this, and useful in other optimization types as well. For some recent compiler research with regards to optimizing memory and cache use, see e.g. "Optimizing Indirect Memory References with Milk", PACT 2016 [1]. [1] http://dl.acm.org/citation.cfm?doid=2967938.2967948 http://dl.acm.org/citation.cfm?doid=2967938.2967948

zurn 9y ago
The research side may not be the main culprit, hence I said "compiler engineering" - meaning usable tools delivered to the hands of developers. Though I think the research side has not focused on this enough either. Regarding the Milk paper specifically, it appears to be about reordering and clustering memory accesses without changes to data layout. This is a fine thing but I think it reinforces my point about lack of attention to memory/data layout optimizations.