4 ms·

The problem with doing this is that many other optimizations depend on inlining. So, if inlining is deferred until link time, thise optimizations will be far le

The problem with doing this is that many other optimizations depend on inlining. So, if inlining is deferred until link time, thise optimizations will be far less useful. Take for example auto-vecorization. If we have a loop that just calls a function which increments a value in an array, we may very well have a great candidate to vectorize. However, if the function isn't inlined, the auto vectorization optimization will just see a function call as opposed to an increment and won't be able to do anything with it.

vlovich123 8y ago
Why isn't optimization a repeated process? Apply some sequence of operations in a loop until diminishing gains are detected? So for example, run inlining again after the code has been lowered., I'm guessing it's actually really complex to try & implement & some optimizations can't run once the code has been lowered? Similarly, the article talks about how the LLVM inliner clearly is smarter since it seems likely they ask their built-in assembler to provide an estimate of the code size rather than using more coarse heuristics. It seems like there's clearly a better path forward for GCC.
- jcranmer 8y ago
  > Why isn't optimization a repeated process? Apply some sequence of operations in a loop until diminishing gains are detected? Compile time. Compiler optimizations are a tradeoff between code size, running time, and compile time, complicated by the fact that that sneezing at your code can change performance by 40% or more and the fact that correctness comes with steep performance costs and often isn't actually desired (until it really is). Of all the optimizations, inlining is probably the worst for the difficulty of balancing the triad of objectives and the black magic of its heuristics.
ken 8y ago
The part of this that I don't understand is: since we will always know more information later in time, why not defer such decisions until runtime? HP Labs' Dynamo project (~20 years ago) was a JIT for PA-RISC on PA-RISC, and it made most programs run faster, in large part by being able to inline functions at runtime even across library boundaries. Was there something impractical about this strategy that caused it to end up in the dustbin of computer science history?
- aw1621107 8y ago
  > The part of this that I don't understand is: since we will always know more information later in time, why not defer such decisions until runtime? I don't think I fully agree with this. The amount of information available to the JIT compared to an AoT compiler also depends on what input a JIT works on. In the case of Java, I'd imagine that the JVM has a strictly greater amount of information to work with than an AoT compiler because JVM bytecode carries basically all the information available in Java source code. However, a Rust JIT would have semantic information that a lower-level JIT like Dynamo wouldn't (assuming I'm understanding Dynamo right), like aliasing information. Dynamo could infer that a particular memory store probably doesn't affect a later memory load, and optimize based on that, but a Rust JIT could guarantee it, allowing for the same potential optimizations without having to insert deoptimization checks. This is where profile-guided optimization comes into play, I think. Assuming a representative profile (and that's admittedly a big if), you can get much of the same information that a JIT gets while also getting to work with a potentially semantically-richer source. > HP Labs' Dynamo project (~20 years ago) was a JIT for PA-RISC on PA-RISC, and it made most programs run faster, in large part by being able to inline functions at runtime even across library boundaries. I'm curious what kind of code Dynamo was tested on, as the effectiveness of a JIT depends on the particular code patterns of the software being run. For example, JITs can help a lot with code with lots of virtual function calls or indirections that traditional compilers tend to stumble on, but I don't think a JIT would help as much for something like a cache-optimized computational kernel. Admittedly, my point is weakened by the graph shown in an old Ars Technica article on Dynamo [0], where Dynamo showed significant improvements on the SPEC benchmark suite, which I assume doesn't rely on shared libraries. Now I'm curious whether similar differences can be shown given the nearly 20 years C/C++/Fortran compilers have had to improve. > Was there something impractical about this strategy that caused it to end up in the dustbin of computer science history? I'd hardly say that JITs ended up in the dustbin of computer science history; on the contrary, they're quite common. The JVM and the various Javascript JITs are probably the most well-known ones; you also have Pypy (and everything derived from RPython), LuaJIT, Julia, MATLAB, the new JITs showing up in Ruby and PostgreSQL, and the more recent push to develop new JITs (like Graal). The JVM got its JIT in 1998, and the JIT was made the default in 1.3 in 2000, so it's not like all these are recent developments. Now, between all that, I don't know why a low-level JIT like Dynamo (if I understood the article I found [1] right) didn't become more popular. It certainly seemed like promising technology at the time. I'd love to know why it seemed to die out and whether it's worth pursuing today. [0]: http://archive.arstechnica.com/reviews/1q00/dynamo/dynamo-3.html http://archive.arstechnica.com/reviews/1q00/dynamo/dynamo-3.... [1]: http://archive.arstechnica.com/reviews/1q00/dynamo/dynamo-1.html http://archive.arstechnica.com/reviews/1q00/dynamo/dynamo-1....

vlovich123 8y ago

Why isn't optimization a repeated process? Apply some sequence of operations in a loop until diminishing gains are detected? So for example, run inlining again after the code has been lowered., I'm guessing it's actually really complex to try & implement & some optimizations can't run once the code has been lowered? Similarly, the article talks about how the LLVM inliner clearly is smarter since it seems likely they ask their built-in assembler to provide an estimate of the code size rather than using more coarse heuristics. It seems like there's clearly a better path forward for GCC.

jcranmer 8y ago
> Why isn't optimization a repeated process? Apply some sequence of operations in a loop until diminishing gains are detected? Compile time. Compiler optimizations are a tradeoff between code size, running time, and compile time, complicated by the fact that that sneezing at your code can change performance by 40% or more and the fact that correctness comes with steep performance costs and often isn't actually desired (until it really is). Of all the optimizations, inlining is probably the worst for the difficulty of balancing the triad of objectives and the black magic of its heuristics.

ken 8y ago

The part of this that I don't understand is: since we will always know more information later in time, why not defer such decisions until runtime? HP Labs' Dynamo project (~20 years ago) was a JIT for PA-RISC on PA-RISC, and it made most programs run faster, in large part by being able to inline functions at runtime even across library boundaries. Was there something impractical about this strategy that caused it to end up in the dustbin of computer science history?

aw1621107 8y ago
> The part of this that I don't understand is: since we will always know more information later in time, why not defer such decisions until runtime? I don't think I fully agree with this. The amount of information available to the JIT compared to an AoT compiler also depends on what input a JIT works on. In the case of Java, I'd imagine that the JVM has a strictly greater amount of information to work with than an AoT compiler because JVM bytecode carries basically all the information available in Java source code. However, a Rust JIT would have semantic information that a lower-level JIT like Dynamo wouldn't (assuming I'm understanding Dynamo right), like aliasing information. Dynamo could infer that a particular memory store probably doesn't affect a later memory load, and optimize based on that, but a Rust JIT could guarantee it, allowing for the same potential optimizations without having to insert deoptimization checks. This is where profile-guided optimization comes into play, I think. Assuming a representative profile (and that's admittedly a big if), you can get much of the same information that a JIT gets while also getting to work with a potentially semantically-richer source. > HP Labs' Dynamo project (~20 years ago) was a JIT for PA-RISC on PA-RISC, and it made most programs run faster, in large part by being able to inline functions at runtime even across library boundaries. I'm curious what kind of code Dynamo was tested on, as the effectiveness of a JIT depends on the particular code patterns of the software being run. For example, JITs can help a lot with code with lots of virtual function calls or indirections that traditional compilers tend to stumble on, but I don't think a JIT would help as much for something like a cache-optimized computational kernel. Admittedly, my point is weakened by the graph shown in an old Ars Technica article on Dynamo [0], where Dynamo showed significant improvements on the SPEC benchmark suite, which I assume doesn't rely on shared libraries. Now I'm curious whether similar differences can be shown given the nearly 20 years C/C++/Fortran compilers have had to improve. > Was there something impractical about this strategy that caused it to end up in the dustbin of computer science history? I'd hardly say that JITs ended up in the dustbin of computer science history; on the contrary, they're quite common. The JVM and the various Javascript JITs are probably the most well-known ones; you also have Pypy (and everything derived from RPython), LuaJIT, Julia, MATLAB, the new JITs showing up in Ruby and PostgreSQL, and the more recent push to develop new JITs (like Graal). The JVM got its JIT in 1998, and the JIT was made the default in 1.3 in 2000, so it's not like all these are recent developments. Now, between all that, I don't know why a low-level JIT like Dynamo (if I understood the article I found [1] right) didn't become more popular. It certainly seemed like promising technology at the time. I'd love to know why it seemed to die out and whether it's worth pursuing today. [0]: http://archive.arstechnica.com/reviews/1q00/dynamo/dynamo-3.html http://archive.arstechnica.com/reviews/1q00/dynamo/dynamo-3.... [1]: http://archive.arstechnica.com/reviews/1q00/dynamo/dynamo-1.html http://archive.arstechnica.com/reviews/1q00/dynamo/dynamo-1....