4 ms·

> Anyone waiting for 10x improvements is likely to be disappointed. I don’t see that happening, except for the occasional unusual program (such as the chess eng

> Anyone waiting for 10x improvements is likely to be disappointed. I don’t see that happening, except for the occasional unusual program (such as the chess engine case mentioned above). > The compiler is a large, mature project. It’s well over 10 years old, and hundreds of thousands of lines. Projects like that tend to not get quantum leaps in performance. Many small improvements is more typical. And > And it’s hard to radically change the data structures used in a mature compiler. As the author describes, the compiler is likely fairly well optimized for its existing way of doing things. 10x improvements would come from architectural changes and it sounds like the compiler is so big now that this is difficult. The other piece that makes it difficult is that LLVM is a separate also large project. An example of an architectural change I think hasn’t been investigated enough is in the space of PGO. While compilers use PGO to choose better heuristics, they don’t use that to control optimization levels applied to various code. Most programs have performance critical compute paths, but the rest of the program is no where near that. I feel like dropping expensive optimization passes for “cold” code would provide significant savings and Rust already lets you annotate cold/hot functions. Would be nice if it combined it with call flow analysis to build something like audio ABR but for optimization. Anyway, such things are difficult research projects to attempt on existing large codebases. I believe the author that further meaningful performance wins are unlikely without deeper architectural changes. This is very similar to comments that Lemire makes in [1] and is well understood to be the same (often misunderstood) critique as Knuth made many decades ago about premature optimization. Architecture trumps code tuning. [1] https://lemire.me/blog/2023/04/27/hotspot-performance-engineering-fails/ https://lemire.me/blog/2023/04/27/hotspot-performance-engine...

glandium 3y ago
> they don’t use that to control optimization levels applied to various code. GCC does. I think LLVM does to some extent too.
- vlovich123 3y ago
  Where can I read up on this? AFAIK PGO is used in lieu of various heuristics within a pass, but is not used to remove optimization passes on “dead code”.
  - KMag 3y ago
    Dead code is a very specific term, meaning unreachable code paths that can be safely eliminated. You mean cold code paths, not dead code.
  - glandium 3y ago
    Good question, I unfortunately don't have a link to give you, or fine details, but GCC does hot/cold partitioning and applies different optimization level to hot and cold code blocks. IIRC, it uses the level given on the command line for hot code, and -Os for cold code.
    - vlovich123 3y ago
      I see nothing in the documentation to suggest that. The only thing I’m aware compilers do for hot/cold is partitioning to improve locality.
GeekyBear 3y ago
> The other piece that makes it difficult is that LLVM is a separate also large project. There is the Cranelift project which is intended to replace LLVM on the back end while you're coding, testing and debugging. > Cranelift focuses on just-in-time compilation with short compile time being an explicit goal of the project. https://en.wikipedia.org/wiki/Cranelift https://en.wikipedia.org/wiki/Cranelift
mamcx 3y ago
Exist many potential ways to speed up a compiler, than are proven (example: pascal), but the most nasty truth about that is that change the language. That is a reason for why will be impossible to fix Python (you can't assert that anything will keep their types) or in this case Rust (several features are "made" with the sole purpose to make the compiler pipeline SAD!). You need certain discipline to develop both the language/syntax/semantic so the compiler can exploit them for speed. --- However, I suspect it must be possible to speed up Rust and other langs massively, because you can chew gigabytes in a RDBMs in seconds. I now wonder if a "compiler database engine" could help, so you can store the lexemes, sources, inferences, etc and query them. Also, A LOT of the work of compiler is just repeat the same steps over and over, and exist some research about save pre-computed snippets to avoid that.
- estebank 3y ago
  > I now wonder if a "compiler database engine" could help, so you can store the lexemes, sources, inferences, etc and query them. rustc already does this https://rustc-dev-guide.rust-lang.org/queries/query-evaluation-model-in-detail.html https://rustc-dev-guide.rust-lang.org/queries/query-evaluati...
  - Rusky 3y ago
    This doesn't feel like the same thing. The performance benefits of an RDBMS come from the way its storage is organized and (at least in typical RDBMS scenarios) the way queries are dynamically optimized to traverse that storage, based on the data it contains. The thing rustc calls "queries" is more about incremental compilation- reusing work within and across compiler invocations, but without the sort of impact on memory layout and access patterns that you get from an RDBMS. The closest thing I've seen in a compiler is rather Zig's AST memory layout work: https://github.com/ziglang/zig/pull/7920 https://github.com/ziglang/zig/pull/7920. But this is a very "hand-crafted" version of what an RDBMS does.
    - nnethercote 3y ago
      I've tried AST memory layout work in the Zig style, look for "shrinkage" in these two posts: - https://nnethercote.github.io/2022/10/27/how-to-speed-up-the-rust-compiler-in-october-2022.html https://nnethercote.github.io/2022/10/27/how-to-speed-up-the... - https://nnethercote.github.io/2023/03/24/how-to-speed-up-the-rust-compiler-in-march-2023.html https://nnethercote.github.io/2023/03/24/how-to-speed-up-the... It's hard work. Small AST changes often require hundreds of changes to the code. The required changes usually make the AST less ergonomic to work with. And the perf benefits I obtained were very small. Even after shrinking `ast::Expr` (by far the most common AST node kind) from over 100 bytes to 64 bytes on 64-bit. The linked Zig PR has very impressive reductions in walltime/cycles/etc. but if you read closely it's restricted just to parsing, which is usually a very small slice of compile time, at least for rustc. My experience with these kinds of changes was disappointing. I concluded "I’d love to be proven wrong, but it doesn’t feel like this work is taking place in a good part of the effort/benefit curve."

glandium 3y ago

> they don’t use that to control optimization levels applied to various code. GCC does. I think LLVM does to some extent too.

vlovich123 3y ago
Where can I read up on this? AFAIK PGO is used in lieu of various heuristics within a pass, but is not used to remove optimization passes on “dead code”.
- KMag 3y ago
  Dead code is a very specific term, meaning unreachable code paths that can be safely eliminated. You mean cold code paths, not dead code.
- glandium 3y ago
  Good question, I unfortunately don't have a link to give you, or fine details, but GCC does hot/cold partitioning and applies different optimization level to hot and cold code blocks. IIRC, it uses the level given on the command line for hot code, and -Os for cold code.
  - vlovich123 3y ago
    I see nothing in the documentation to suggest that. The only thing I’m aware compilers do for hot/cold is partitioning to improve locality.

GeekyBear 3y ago

> The other piece that makes it difficult is that LLVM is a separate also large project. There is the Cranelift project which is intended to replace LLVM on the back end while you're coding, testing and debugging. > Cranelift focuses on just-in-time compilation with short compile time being an explicit goal of the project. https://en.wikipedia.org/wiki/Cranelift https://en.wikipedia.org/wiki/Cranelift

mamcx 3y ago

Exist many potential ways to speed up a compiler, than are proven (example: pascal), but the most nasty truth about that is that change the language. That is a reason for why will be impossible to fix Python (you can't assert that anything will keep their types) or in this case Rust (several features are "made" with the sole purpose to make the compiler pipeline SAD!). You need certain discipline to develop both the language/syntax/semantic so the compiler can exploit them for speed. --- However, I suspect it must be possible to speed up Rust and other langs massively, because you can chew gigabytes in a RDBMs in seconds. I now wonder if a "compiler database engine" could help, so you can store the lexemes, sources, inferences, etc and query them. Also, A LOT of the work of compiler is just repeat the same steps over and over, and exist some research about save pre-computed snippets to avoid that.

estebank 3y ago
> I now wonder if a "compiler database engine" could help, so you can store the lexemes, sources, inferences, etc and query them. rustc already does this https://rustc-dev-guide.rust-lang.org/queries/query-evaluation-model-in-detail.html https://rustc-dev-guide.rust-lang.org/queries/query-evaluati...
- Rusky 3y ago
  This doesn't feel like the same thing. The performance benefits of an RDBMS come from the way its storage is organized and (at least in typical RDBMS scenarios) the way queries are dynamically optimized to traverse that storage, based on the data it contains. The thing rustc calls "queries" is more about incremental compilation- reusing work within and across compiler invocations, but without the sort of impact on memory layout and access patterns that you get from an RDBMS. The closest thing I've seen in a compiler is rather Zig's AST memory layout work: https://github.com/ziglang/zig/pull/7920 https://github.com/ziglang/zig/pull/7920. But this is a very "hand-crafted" version of what an RDBMS does.
  - nnethercote 3y ago
    I've tried AST memory layout work in the Zig style, look for "shrinkage" in these two posts: - https://nnethercote.github.io/2022/10/27/how-to-speed-up-the-rust-compiler-in-october-2022.html https://nnethercote.github.io/2022/10/27/how-to-speed-up-the... - https://nnethercote.github.io/2023/03/24/how-to-speed-up-the-rust-compiler-in-march-2023.html https://nnethercote.github.io/2023/03/24/how-to-speed-up-the... It's hard work. Small AST changes often require hundreds of changes to the code. The required changes usually make the AST less ergonomic to work with. And the perf benefits I obtained were very small. Even after shrinking `ast::Expr` (by far the most common AST node kind) from over 100 bytes to 64 bytes on 64-bit. The linked Zig PR has very impressive reductions in walltime/cycles/etc. but if you read closely it's restricted just to parsing, which is usually a very small slice of compile time, at least for rustc. My experience with these kinds of changes was disappointing. I concluded "I’d love to be proven wrong, but it doesn’t feel like this work is taking place in a good part of the effort/benefit curve."