10 ms·

What Is the Minimal Set of Optimizations Needed for Zero-Cost Abstraction?

109 points by matt_d 6y ago

andoma 6y ago
gcc have -Og which turns on optimization steps that can be enabled without sacrificing debugability.
- slavik81 6y ago
  In practice, I find I usually have to switch to -O0, as nearly all my variables are <optimized out> with -Og.
  - pm215 6y ago
    That's been my experience too. Unfortunately the gcc devs essentially poisoned their own well there -- I'm now much less likely to want to go back and try -Og because of my initial bad experience. If they'd started with "always good debug and very few optimisations" and only added in optimisations when they didn't break the debug illusion then the user-experience would have been much better (always at least as good as -O0 when debugging, and gradually gets faster as you use newer gcc versions).
blaisio 6y ago
Looking at it from this angle is a very interesting idea. Languages like Go have to avoid a lot of abstractions to avoid increasing compile time. If we can narrow down the specific optimizations required, we can make better decisions about the abstractions that could be supported.
fanf2 6y ago
My list would be: - Inlining - Common subexpression elimination - Dead code elimination - Monomorphization I get the impression that 2 and 3 come out of an SSA middle end fairly straightforwardly, along with the article’s copy propagation and dead store elimination. The biggie is monomorphization, which is part of the language in C++. The alternative is uniform representation of generic values, which implies boxing and indirection instead. I understand Rust does not hide representations enough for the compiler to be able to choose whether or not to monomorphize. Interestingly, the Go generics discussion seems to be heading towards a design where the compiler does have this option.
- davidcuddeback 6y ago
  > I understand Rust does not hide representations enough for the compiler to be able to choose whether or not to monomorphize. Any chance you could expand on that?
  - fanf2 6y ago
    I don't know enough Rust to explain clearly or give examples :-) But like C++, Rust makes it explicit whether an object is boxed or not and the compiler doesn't get a choice about the memory layout, so it can't switch between monomorphization or uniform representation depending on the optimization level.
    - davidcuddeback 6y ago
      I'm so used to choosing between monomorphization and dynamic dispatch myself that I never thought of the possibility of a compiler being able to choose. Is the point to avoid monomorphization during dev to have faster compile times, and then enable monomorphization for release builds? That's a neat idea. That makes me wonder what Java does these days. I haven't used Java much since about v1.6. Java took a different approach than C++ and Rust. I remember when generics were introduced, they were basically syntactic sugar for type casts (for backwards compatibility). That implies that Java at the time didn't monomorphize generics. I think the language has evolved a lot since those days, so I wonder if it does any monomorphization today.
      - kjeetgill 6y ago
        Java is slightly more complicated. It can make assumptions about the code (even if it can't prove they always hold!) and specialize some things but not others. Generally, the jit can specialize the code making assumptions about the real type under interfaces/polymorphism, which types the generic parameters will be, or even which target virtual dispatch will always hit. But for the objects themselves, it never specializes layout in any way (short of removing an allocation entirely). ... I think. I'm no expert in this, ask chrisseaton.
Kinrany 6y ago
Aggressive inlining keeps coming up. There's Spiral [0]: a language where inlining is the default and also a first-class concept, much like immutability in new popular languages like Rust. As a bonus, the commit messages contain a whole journal worth of notes. [0]: https://github.com/mrakgr/The-Spiral-Language https://github.com/mrakgr/The-Spiral-Language
toolslive 6y ago
- Should there be a reference to C++/Rust in the title ? > Tail calls: I can't think of a Rust or C++ abstraction that relies on TCO to be zero-cost. This is an interesting one. Doesn't the absence of TCO mean that there are a lot of (recursive) abstractions that cannot ever be zero cost ? First thing that comes to mind is processing of composites (for example serialization of a protobuf type definition). There are others.
- nicoburns 6y ago
  Yeah, I thought this was a bizarre one to exclude. Especially as I can't imagine it has a particularly large effect on compile time. At least not if it's enabled by a keyword.
  - toolslive 6y ago
    What I think happened is rationalization: the early versions of the rust compiler omitted TCO. "It doesn't fit with the rest of it. We might revisit this later". Later, it turned out too difficult to retrofit, and now the stance is "you don't need it". https://dev.to/seanchen1991/the-story-of-tail-call-optimizations-in-rust-35hf https://dev.to/seanchen1991/the-story-of-tail-call-optimizat...
- swsieber 6y ago
  Can't one fake TCO by hoisting things out into a loop? > Tail calls: I can't think of a Rust or C++ abstraction that relies on TCO to be zero-cost. Rust doesn't have TCO, so it's hard to rely on something that doesn't exist (unless it's on nightly and I missed it).
  - steveklabnik 6y ago
    Rust doesn't guarantee TCO, but LLVM may decide to do it if it wishes.
    - Gibbon1 6y ago
      Lack of a guarantee says you should use explicit loops.
proverbialbunny 6y ago
Speaking of zero-cost abstractions. How many languages have this feature? Do only C++ and Rust support zero-cost abstractions?
- benrbray 6y ago
  I don't know how truly "zero-cost" the compiler implementations are, but the premise of functional programming languages like Haskell seems to be that programmers should be able to freely think in abstractions like map, fold, monads, etc.. without worrying about performance.
  - proverbialbunny 6y ago
    The benefit of zero cost is creating types that are not native, yet have the speed of native types. Eg, I do a lot of financial programming, so I need a decimal type, which is like a float, but base 10 so math with no floating point errors. When I turn on compiler optimizations on zero cost languages, I get roughly a 15-20x speedup, depending on what it is. Interestingly, languages without zero cost abstractions, but are still quite fast, eg Java, run at the speed of the zero cost languages with optimizations turned off. Zero cost is not helpful in most use cases, but in my situation it gives quite a large speed boost. Sadly, I feel like I'm locked in to using Rust (or C++) and don't have much of a choice. I suspect Haskell is going to be quite a bit slower for creating custom types unfortunately.
    - benrbray 6y ago
      Interesting, thanks for your perspective! Regarding speed, I suspect there might be more to the story since so many finance firms [1] are known to use Haskell internally. Perhaps they're not using it for anything speed-critical, though. [1] https://wiki.haskell.org/Haskell_in_industry https://wiki.haskell.org/Haskell_in_industry
      - proverbialbunny 6y ago
        Keep in mind finance is not quantitative finance. (edit: I just realized I didn't specify above. I'm doing quant work.) In finance (and quant work) you don't want a mistake. You want what you code to have provability, so you know what you write is what you get. This is super important. Speed in pure finance is not important. In quantitative finance the common practice today is companies roll out their own programming language that has provability like Haskell, but is closer to the speed of C++. These languages tend to be a big closer to lisp than Haskell, but it depends from company to company.
modeless 6y ago
The reason compilation time is a problem is that compiler architecture is stuck in the 1970s, at least for systems programming languages. Compilers make you wait while they repeat the same work over and over again, thousands of times. Trillions, if you count the work globally. How many times has <vector> been parsed over the years? In a world where compiler architecture had actually advanced, you would download a precompiled binary alongside the source, identical to what you would have produced with a clean build, and that binary would be updated incrementally as you type code. If you made a change affecting a large part of the binary that couldn't be applied immediately, JIT techniques would be used to allow you to run and test the program anyway before it finished compiling. There is no fundamental reason why anyone should ever have to wait for a compiler. And if you didn't have to wait, then it would free the compiler to spend potentially much more time doing optimizations, actually improving the final binary. The zapcc project shows a bit of the potential for improvement in build times, though it's just scratching the surface. https://github.com/yrnkrn/zapcc https://github.com/yrnkrn/zapcc
- greggman3 6y ago
  You lost me.... <vector> isn't executable code. It's generic instructions for how to generate new code given a type and at least in C++ that code is not and can not be shared because what is generated depends on the type itself.
  - geocar 6y ago
    When a C++ compiler sees a statement like template<class T>... it updates its internal state to be able to recognise the constructions this statement is intended to enable. If you are able (somehow) to encapsulate this state, and save and load it faster than you can regenerate it, that’s a win. You can call it caching or memoisation or “incremental compilation” if you really enjoy that sort of thing, but this is such a basic concept that if you cannot understand it, you are going to have a lot of other problems.
    - msla 6y ago
      > If you are able (somehow) to encapsulate this state, and save and load it faster than you can regenerate it, that’s a win. You can call it caching or memoisation or “incremental compilation” if you really enjoy that sort of thing, but this is such a basic concept that if you cannot understand it, you are going to have a lot of other problems. If you're going to be condescending like that, it would be nice if you could provide a concrete example of how to incrementally compile vector<T> in the general case in such a way that it's useful and reasonable to redistribute (that is, not tied to a specific architecture or compiler) instead of just waving your hands.
ndesaulniers 6y ago
> actually configure the Rust compiler with a promising set of optimizations and evaluate the results. LLVM lets you configure an optimization pipeline of passes. I'd hack up my own -O flag and pipeline. It would be cool to see these suggestions tested out.
- steveklabnik 6y ago
  You don't need code changes to try this out, see * https://doc.rust-lang.org/stable/rustc/codegen-options/index.html#passes https://doc.rust-lang.org/stable/rustc/codegen-options/index... * https://doc.rust-lang.org/stable/rustc/codegen-options/index.html#no-prepopulate-passes https://doc.rust-lang.org/stable/rustc/codegen-options/index...
  - ndesaulniers 6y ago
    Oh cool! Happy to see you land on your feet btw, new gig looks cool!
    - steveklabnik 6y ago
      Thank you! It's been really really great :)
ncmncm 6y ago
I think common sub-expression elimination is a part of hoisting out of loops, which seems pretty important. I have seen Gcc dismantle one loop into two adjacent loops, the first to pre-compute a table for the second loop. My jaw was on the floor.
- roca 6y ago
  Can you give an example where CSE/hoisting is necessary to make an abstraction zero-cost? I mean: give an example of a zero-cost abstraction that takes some hand-written code and packages it up nicely, and then show that the compiler can't compile it back down to the hand-written code without CSE/hoisting.
  - fanf2 6y ago
    The usual example is something like a safe array where the bounds are checked on every access. The bounds check is a common subexpression in code that accesses the array more than once. If the abstraction includes a safety check on access that doesn’t depend on the loop variable (eg if empty arrays are NULL) then that can be hoisted.
brandmeyer 6y ago
"copy propagation" sounds like he's got two things mixed up: Copy elision and constant propagation. Each one of these are important for zero-cost abstractions, IMO.
- roca 6y ago
  I mean this: https://en.wikipedia.org/wiki/Copy_propagation https://en.wikipedia.org/wiki/Copy_propagation
  - brandmeyer 6y ago
    With respect to zero-cost abstractions, its copy elision that matters. operator= is just another function in C++, for example. Only in a handful of specific circumstances is the compiler allowed to elide calls to operator=.
Animats 6y ago
The expensive optimizations are the ones that require non-local analysis. Register allocation is classically a win for compile speed. It takes less compiler work to put values in registers than to emit all the loads and stores and pushes and pops for putting them on the stack.

109 points by matt_d 6y ago

andoma 6y ago

gcc have -Og which turns on optimization steps that can be enabled without sacrificing debugability.

slavik81 6y ago
In practice, I find I usually have to switch to -O0, as nearly all my variables are <optimized out> with -Og.
- pm215 6y ago
  That's been my experience too. Unfortunately the gcc devs essentially poisoned their own well there -- I'm now much less likely to want to go back and try -Og because of my initial bad experience. If they'd started with "always good debug and very few optimisations" and only added in optimisations when they didn't break the debug illusion then the user-experience would have been much better (always at least as good as -O0 when debugging, and gradually gets faster as you use newer gcc versions).

blaisio 6y ago

Looking at it from this angle is a very interesting idea. Languages like Go have to avoid a lot of abstractions to avoid increasing compile time. If we can narrow down the specific optimizations required, we can make better decisions about the abstractions that could be supported.

fanf2 6y ago

My list would be: - Inlining - Common subexpression elimination - Dead code elimination - Monomorphization I get the impression that 2 and 3 come out of an SSA middle end fairly straightforwardly, along with the article’s copy propagation and dead store elimination. The biggie is monomorphization, which is part of the language in C++. The alternative is uniform representation of generic values, which implies boxing and indirection instead. I understand Rust does not hide representations enough for the compiler to be able to choose whether or not to monomorphize. Interestingly, the Go generics discussion seems to be heading towards a design where the compiler does have this option.

davidcuddeback 6y ago
> I understand Rust does not hide representations enough for the compiler to be able to choose whether or not to monomorphize. Any chance you could expand on that?
- fanf2 6y ago
  I don't know enough Rust to explain clearly or give examples :-) But like C++, Rust makes it explicit whether an object is boxed or not and the compiler doesn't get a choice about the memory layout, so it can't switch between monomorphization or uniform representation depending on the optimization level.
  - davidcuddeback 6y ago
    I'm so used to choosing between monomorphization and dynamic dispatch myself that I never thought of the possibility of a compiler being able to choose. Is the point to avoid monomorphization during dev to have faster compile times, and then enable monomorphization for release builds? That's a neat idea. That makes me wonder what Java does these days. I haven't used Java much since about v1.6. Java took a different approach than C++ and Rust. I remember when generics were introduced, they were basically syntactic sugar for type casts (for backwards compatibility). That implies that Java at the time didn't monomorphize generics. I think the language has evolved a lot since those days, so I wonder if it does any monomorphization today.
    - kjeetgill 6y ago
      Java is slightly more complicated. It can make assumptions about the code (even if it can't prove they always hold!) and specialize some things but not others. Generally, the jit can specialize the code making assumptions about the real type under interfaces/polymorphism, which types the generic parameters will be, or even which target virtual dispatch will always hit. But for the objects themselves, it never specializes layout in any way (short of removing an allocation entirely). ... I think. I'm no expert in this, ask chrisseaton.

Kinrany 6y ago

Aggressive inlining keeps coming up. There's Spiral [0]: a language where inlining is the default and also a first-class concept, much like immutability in new popular languages like Rust. As a bonus, the commit messages contain a whole journal worth of notes. [0]: https://github.com/mrakgr/The-Spiral-Language https://github.com/mrakgr/The-Spiral-Language

toolslive 6y ago

- Should there be a reference to C++/Rust in the title ? > Tail calls: I can't think of a Rust or C++ abstraction that relies on TCO to be zero-cost. This is an interesting one. Doesn't the absence of TCO mean that there are a lot of (recursive) abstractions that cannot ever be zero cost ? First thing that comes to mind is processing of composites (for example serialization of a protobuf type definition). There are others.

nicoburns 6y ago
Yeah, I thought this was a bizarre one to exclude. Especially as I can't imagine it has a particularly large effect on compile time. At least not if it's enabled by a keyword.
- toolslive 6y ago
  What I think happened is rationalization: the early versions of the rust compiler omitted TCO. "It doesn't fit with the rest of it. We might revisit this later". Later, it turned out too difficult to retrofit, and now the stance is "you don't need it". https://dev.to/seanchen1991/the-story-of-tail-call-optimizations-in-rust-35hf https://dev.to/seanchen1991/the-story-of-tail-call-optimizat...
swsieber 6y ago
Can't one fake TCO by hoisting things out into a loop? > Tail calls: I can't think of a Rust or C++ abstraction that relies on TCO to be zero-cost. Rust doesn't have TCO, so it's hard to rely on something that doesn't exist (unless it's on nightly and I missed it).
- steveklabnik 6y ago
  Rust doesn't guarantee TCO, but LLVM may decide to do it if it wishes.
  - Gibbon1 6y ago
    Lack of a guarantee says you should use explicit loops.

proverbialbunny 6y ago

Speaking of zero-cost abstractions. How many languages have this feature? Do only C++ and Rust support zero-cost abstractions?

benrbray 6y ago
I don't know how truly "zero-cost" the compiler implementations are, but the premise of functional programming languages like Haskell seems to be that programmers should be able to freely think in abstractions like map, fold, monads, etc.. without worrying about performance.
- proverbialbunny 6y ago
  The benefit of zero cost is creating types that are not native, yet have the speed of native types. Eg, I do a lot of financial programming, so I need a decimal type, which is like a float, but base 10 so math with no floating point errors. When I turn on compiler optimizations on zero cost languages, I get roughly a 15-20x speedup, depending on what it is. Interestingly, languages without zero cost abstractions, but are still quite fast, eg Java, run at the speed of the zero cost languages with optimizations turned off. Zero cost is not helpful in most use cases, but in my situation it gives quite a large speed boost. Sadly, I feel like I'm locked in to using Rust (or C++) and don't have much of a choice. I suspect Haskell is going to be quite a bit slower for creating custom types unfortunately.
  - benrbray 6y ago
    Interesting, thanks for your perspective! Regarding speed, I suspect there might be more to the story since so many finance firms [1] are known to use Haskell internally. Perhaps they're not using it for anything speed-critical, though. [1] https://wiki.haskell.org/Haskell_in_industry https://wiki.haskell.org/Haskell_in_industry
    - proverbialbunny 6y ago
      Keep in mind finance is not quantitative finance. (edit: I just realized I didn't specify above. I'm doing quant work.) In finance (and quant work) you don't want a mistake. You want what you code to have provability, so you know what you write is what you get. This is super important. Speed in pure finance is not important. In quantitative finance the common practice today is companies roll out their own programming language that has provability like Haskell, but is closer to the speed of C++. These languages tend to be a big closer to lisp than Haskell, but it depends from company to company.

modeless 6y ago

The reason compilation time is a problem is that compiler architecture is stuck in the 1970s, at least for systems programming languages. Compilers make you wait while they repeat the same work over and over again, thousands of times. Trillions, if you count the work globally. How many times has <vector> been parsed over the years? In a world where compiler architecture had actually advanced, you would download a precompiled binary alongside the source, identical to what you would have produced with a clean build, and that binary would be updated incrementally as you type code. If you made a change affecting a large part of the binary that couldn't be applied immediately, JIT techniques would be used to allow you to run and test the program anyway before it finished compiling. There is no fundamental reason why anyone should ever have to wait for a compiler. And if you didn't have to wait, then it would free the compiler to spend potentially much more time doing optimizations, actually improving the final binary. The zapcc project shows a bit of the potential for improvement in build times, though it's just scratching the surface. https://github.com/yrnkrn/zapcc https://github.com/yrnkrn/zapcc

greggman3 6y ago
You lost me.... <vector> isn't executable code. It's generic instructions for how to generate new code given a type and at least in C++ that code is not and can not be shared because what is generated depends on the type itself.
- geocar 6y ago
  When a C++ compiler sees a statement like template<class T>... it updates its internal state to be able to recognise the constructions this statement is intended to enable. If you are able (somehow) to encapsulate this state, and save and load it faster than you can regenerate it, that’s a win. You can call it caching or memoisation or “incremental compilation” if you really enjoy that sort of thing, but this is such a basic concept that if you cannot understand it, you are going to have a lot of other problems.
  - msla 6y ago
    > If you are able (somehow) to encapsulate this state, and save and load it faster than you can regenerate it, that’s a win. You can call it caching or memoisation or “incremental compilation” if you really enjoy that sort of thing, but this is such a basic concept that if you cannot understand it, you are going to have a lot of other problems. If you're going to be condescending like that, it would be nice if you could provide a concrete example of how to incrementally compile vector<T> in the general case in such a way that it's useful and reasonable to redistribute (that is, not tied to a specific architecture or compiler) instead of just waving your hands.

ndesaulniers 6y ago

> actually configure the Rust compiler with a promising set of optimizations and evaluate the results. LLVM lets you configure an optimization pipeline of passes. I'd hack up my own -O flag and pipeline. It would be cool to see these suggestions tested out.

steveklabnik 6y ago
You don't need code changes to try this out, see * https://doc.rust-lang.org/stable/rustc/codegen-options/index.html#passes https://doc.rust-lang.org/stable/rustc/codegen-options/index... * https://doc.rust-lang.org/stable/rustc/codegen-options/index.html#no-prepopulate-passes https://doc.rust-lang.org/stable/rustc/codegen-options/index...
- ndesaulniers 6y ago
  Oh cool! Happy to see you land on your feet btw, new gig looks cool!
  - steveklabnik 6y ago
    Thank you! It's been really really great :)

ncmncm 6y ago

I think common sub-expression elimination is a part of hoisting out of loops, which seems pretty important. I have seen Gcc dismantle one loop into two adjacent loops, the first to pre-compute a table for the second loop. My jaw was on the floor.

roca 6y ago
Can you give an example where CSE/hoisting is necessary to make an abstraction zero-cost? I mean: give an example of a zero-cost abstraction that takes some hand-written code and packages it up nicely, and then show that the compiler can't compile it back down to the hand-written code without CSE/hoisting.
- fanf2 6y ago
  The usual example is something like a safe array where the bounds are checked on every access. The bounds check is a common subexpression in code that accesses the array more than once. If the abstraction includes a safety check on access that doesn’t depend on the loop variable (eg if empty arrays are NULL) then that can be hoisted.

brandmeyer 6y ago

"copy propagation" sounds like he's got two things mixed up: Copy elision and constant propagation. Each one of these are important for zero-cost abstractions, IMO.

roca 6y ago
I mean this: https://en.wikipedia.org/wiki/Copy_propagation https://en.wikipedia.org/wiki/Copy_propagation
- brandmeyer 6y ago
  With respect to zero-cost abstractions, its copy elision that matters. operator= is just another function in C++, for example. Only in a handful of specific circumstances is the compiler allowed to elide calls to operator=.

Animats 6y ago

The expensive optimizations are the ones that require non-local analysis. Register allocation is classically a win for compile speed. It takes less compiler work to put values in registers than to emit all the loads and stores and pushes and pops for putting them on the stack.