11 ms·

Cranelift code generation comes to Rust

444 points by ridruejo 3y ago

k_bx 3y ago
Any fresh compilation time benchmarks and comparisons to LLVM?
- zokier 3y ago
  From the article: > A full debug build of Cranelift itself using the Cranelift backend took 29.6 seconds on my computer, compared to 37.5 with LLVM (a reduction in wall-clock time of 20%) That seems much smaller difference than what I would have expected
  - __s 3y ago
    Those numbers are the entire compile time, parsing/typecheck/MIR+MIR optimization/linking Don't have numbers handy, so hard to say how much faster Cranelift is making the codegen portion, but gets into Amdahl's Law
    - Filligree 3y ago
      And there are faster linkers than the default. …why is it still the default?
      - 3836293648 3y ago
        Compatibility with niche usecases
        Filligree 3y ago
        That sounds like a good reason to keep the existing one as an opt-in possibility.
      - kibwen 3y ago
        Because the linker provided by the system itself is the one that's guaranteed to be the most broadly compatible. For a toolchain to begin distributing an alternative linker is a lot of work on every supported platform (future versions of Rust may sidestep this issue by making LLD the default on certain platforms, which they get "for free" by dint of shipping alongside LLVM). But also, because there are about ten people on planet Earth qualified to write a production-grade linker, which is why LLD still isn't broadly recommended yet.
- boxed 3y ago
  The very last paragraph: > A full debug build of Cranelift itself using the Cranelift backend took 29.6 seconds on my computer, compared to 37.5 with LLVM (a reduction in wall-clock time of 20%). Those wall-clock times don't tell the full story, however, because of parallelism in the build system. Compiling with Cranelift took 125 CPU-seconds, whereas LLVM took 211 CPU-seconds, a difference of 40%. Incremental builds — rebuilding only Cranelift itself, and none of its dependencies — were faster with both backends. 66ms of CPU time compared to 90ms.
- AlexErrant 3y ago
  Not quite fresh, but > A paper from 2020 [0] showed that Cranelift was an order of magnitude faster than LLVM, while producing code that was approximately twice as slow on some benchmarks. [0] https://arxiv.org/pdf/2011.13127.pdf https://arxiv.org/pdf/2011.13127.pdf
  - Findecanor 3y ago
    The changes in Cranelift since 2020 have been quite significant so I would not put any trust in those benchmarks.
- nindalf 3y ago
  Few reports comparing Cranelift to LLVM from this day old reddit thread [1] - 29.52s -> 24.47s (17.1%) - 27s -> 19s (29.6%) - 11.5s -> 8.4s (26.9%) - 37.5s -> 29.6s (28.7%) - this measurement from TFA. To put these numbers in context, all the perf improvements over the last 4 years have helped the compiler become faster on a variety of workloads by 7%, 17%, 13% and 15%, for an overall speed gain of 37% over 4 years. [2] So one large change providing a 20-30% improvement is very impressive. When you add that to the parallel frontend [3] and support for linking with LLD [4], Rust compilation could be substantially faster by this time next year. [1] - https://old.reddit.com/r/rust/comments/1bgyo8a/try_cranelift_codegen_backend_for_faster_compile/ https://old.reddit.com/r/rust/comments/1bgyo8a/try_cranelift... [2] - https://nnethercote.github.io/2024/03/06/how-to-speed-up-the-rust-compiler-in-march-2024.html https://nnethercote.github.io/2024/03/06/how-to-speed-up-the... [3] - https://blog.rust-lang.org/2023/11/09/parallel-rustc.html https://blog.rust-lang.org/2023/11/09/parallel-rustc.html [4] - https://github.com/rust-lang/rust/issues/39915 https://github.com/rust-lang/rust/issues/39915
  - k_bx 3y ago
    Thanks, that's really great news. The only thing I wish for now is aarch64 support on Apple Silicon
chrisaycock 3y ago
This article provides an excellent overview of the latest in speed of optimizer vs quality of optimization. In particular, copy-and-patch compilation is still the fastest approach because it uses pre-compiled code, though leaves little room for optimization. Cranelift uses e-graphs to represent equivalence on the IR. This allows for more optimizations than the copy-and-patch approach. Of course, the most optimized output is going to come from a more traditional compiler toolchain like LLVM or GCC. But for users who want to get "fast enough" output as quickly as possible, newer compiler techniques provide a promising alternative.
- weinzierl 3y ago
  From what I understand, the big advantage of the e-graphs approach is, that the quality of the output is (within limits) a function the time and memory given. The more memory, the more nodes can be generated in the e-graph and the more time for search, the better the selected node. It might never be as fast as copy-and-patch or as good as LLVM or GCC, but this flexibility is a value in itself.
  - thechao 3y ago
    When we first reviewed the equality saturation paper, we thought there was one major pro, and one major con: [pro] phase-ordering invariant; [con] at the time there was no (believable) way to extract the transformed graph in a non-hand-wavy-way. Personally, I think e-graphs should be combined with Massalin superoptimization — they're natural "duals" — and just turn the whole exercise into a hill-climbing process. You can tune the total effort by the set of passes used, the amount of time to drive the graph to saturation, and the method (and time) for graph extraction.
    - vlovich123 3y ago
      Can you memoize across invocations so that the time spent optimizing is cumulative across all builds?
      - 3y ago
diggan 3y ago
Tried out the instructions from the article on a tiny Bevy project, and compared it to a "normal" build: > cargo build --release 23.93s user 22.85s system 66% cpu 1:09.88 total > cargo +nightly build -Zcodegen-backend 23.52s user 21.98s system 68% cpu 1:06.86 total Seems just marginally faster than a normal release build. Wonder if there is something particular with Bevy that makes this so? The author of the article mentions 40% difference in build speed, but I'm not seeing anything near that. Edit: just realized I'm caching my release builds with sccache and a local NAS, hence the release builds being as fast as Cranelift+debug builds. Trying it again with just debug builds and without any caching: > cargo +nightly build 1997.35s user 200.38s system 1878% cpu 1:57.02 total > cargo +nightly build -Zcodegen-backend 280.96s user 73.06s system 657% cpu 53.850 total Definitely an improvement once I realized what I did wrong, about half the time spent compiling now :) Neat!
- naasking 3y ago
  Maybe your build is not limited by code generation, which seems like the only thing that changed here. There was a good thread recently about the variation in what slows down compilation: https://news.ycombinator.com/item?id=39721922 https://news.ycombinator.com/item?id=39721922
  - diggan 3y ago
    Edited my comment now, forgot I was caching the release builds with sccache so wasn't actually compiling all the units, but fetching a lot of them instead :/
    - vlovich123 3y ago
      Which speaks to maybe that cargo should just ship with sccache turned on by default so that the “normal” experience for developing Rust has this seamless experience. Intelligent caching should always win. I’d like to see rustc get sccache integration that works at the MIR level too so that changing something that doesn’t change the code gen meaningfully still gets a cached response (e.g. changing some comments/whitespace, moving functions around, etc). Even cooler would be if LLVM itself could also cache internal expensive parts of compilation and optimization across process instances. That would make a huge impact in cutting down incremental builds.
pjmlp 3y ago
Finally, looking forward for wider adoption.
Dowwie 3y ago
Would it be naive to assume a general compile-time reduction of 20% for all Rust projects by swapping llvm with cranelift?
- mrklol 3y ago
  There are still projects out there which won’t hit 20% or even some %, if the bottleneck isn’t code gen (for example). So the part with"all" can be wrong, but beside that 20% is a good number.
Deukhoofd 3y ago
Does anyone by chance have benchmarks of runtime (so not the compile time) when using Cranelift? I'm seeing a mention of "twice as slow" in the article, but that's based on data from 2020. Wondering if it has substantially improved since then.
- cfallin 3y ago
  There are some benchmarks of Cranelift-based Wasm VMs (Wasmtime) vs. LLVM-based Wasm VMs here: https://00f.net/2023/01/04/webassembly-benchmark-2023/ https://00f.net/2023/01/04/webassembly-benchmark-2023/ The (perhaps slightly exaggerated but encouraging to me at least!) money quote there is: > That’s right. The cranelift code generator has become as fast as LLVM. This is extremely impressive considering the fact that cranelift is a relatively young project, written from scratch by a very small (but obviously very talented) team. In practice anywhere from 10%-30% slower maybe is reasonable to expect. Compiler microbenchmarks are interesting because they're very "quantized": for any particular benchmark, often either you get the right transforms and achieve the correct optimized inner loop, or you don't. So the game is about getting more and more cases right and we're slowly getting there. (disclosure: I was tech lead of Cranelift in 2020-2022)
cube2222 3y ago
Slightly off-topic, but if you fancy writing compilers in your free time, Cranelift has a great Rust library[0] for doing code generation - it’s a pleasure to use! [0]: https://docs.rs/cranelift-frontend/0.105.3/cranelift_frontend/index.html https://docs.rs/cranelift-frontend/0.105.3/cranelift_fronten...
- loeg 3y ago
  I've seen it used for really simple JIT in Advent of Code puzzles.
  - PartiallyTyped 3y ago
    Why am i not surprised and even find this amusing? :D
Tehnix 3y ago
Very excited for Cranelift for debug builds to speed up development iteration - in particular for WASM/Frontend Rust where iteration speed is competing with the new era of Rust tooling for JS which lands in the sub 1 second builds sometimes (iteration speed in Frontend is crucial). Sadly, it does not yet support ARM macOS, so us M1-3 users will have to wait a bit :/
- kapilsinha 3y ago
  But usually, at least I don't build an executable while iterating. And if I do, I try to set up the feature flags so the build is minimal for the tests I am running
- heavyset_go 3y ago
  As someone who doesn't work in the frontend much, what tools are you talking about?
  - Tehnix 3y ago
    There’s been a recent trend of rewriting tools in Rust with insanes speed gains - Rspack (webpack compatible) - Rolldown (rollup compatible) - Turbopack - Oxc (linter) - Biome (linter and more) - Bun (writing in Zig, does crazy fast bundling) There’s several parts here that are crucial to Frontend development For production you need: - Minificion of source code - Bundling of modules and source code into either one JS file or split into multiple for lazy loading only the parts you need - Transforming various unsupported high-level constructs into something older target browsers support - Typechecking/compiling, or stripping TypeScript if that’s in use Build times could easily go to 10-20 minutes with older tools. The development loop also gets hurt, here you’d want the loop from saving your change to seeing it in the UI to be almost instant. Anything else means you’ll have to develop crutch methods to workaround this (imagine moving and styling components only to need to sit and wait during each small incremental change).
    - heavyset_go 3y ago
      Thanks for your informative post!
Ericson2314 3y ago
Really looking forward to the death of non-e-graph-based compilation :)
- convolvatron 3y ago
  I've tried to look into this a couple times, including today. To me this looks alot like unification? but I don't really understand how operationally one gets from equivalence classes to instructions. is there an e-graphs for dummies writeup?
  - tekknolagi 3y ago
    If by instructions you mean machine instructions, you don't; it's used for internal optimization passes only.
    - convolvatron 3y ago
      that helps, so this is really an alternative to pushing analysis attributes aronud a dataflow graph
  - cfallin 3y ago
    The approach that Cranelift uses is what we call the "aegraph" (talk I gave about it: slides https://cfallin.org/pubs/egraphs2023_aegraphs_slides.pdf https://cfallin.org/pubs/egraphs2023_aegraphs_slides.pdf, video https://vimeo.com/843540328 https://vimeo.com/843540328). The basic idea is that eclasses hold sets of operator expressions (think sea-of-node IR), and we keep that alongside the CFG with a "skeleton" of side-effecting ops. We build that, do rewrites, then extract out of it back to a conventional CFG-of-basic-blocks for lowering. The "equivalence" part comes in when doing rewrites: the main difference between an egraph and a conventional sea-of-nodes IR with rewrite rules is that one keeps all representations in the equivalence class around, then chooses the best one later. We had to solve a few novel problems in working out how to handle control flow, and we're still polishing off some rough edges (search recent issues in the repo for egraphs); but we're mostly happy how it turned out! (Disclosure: tech lead of CL for a while; the e-graphs optimizer is "my fault")
CodesInChaos 3y ago
You can use different backends and optimization for different crates. It often makes sense to use optimized LLVM builds for dependencies, and debug LLVM or even Cranelift for your own code. See https://www.reddit.com/r/rust/comments/1bhpfeb/vastly_improved_recompile_times_in_rust_with/ https://www.reddit.com/r/rust/comments/1bhpfeb/vastly_improv...
- zozbot234 3y ago
  I would not expect this to work without issues, as Rust does not support a stable binary ABI across different compiler versions. How can we be sure that the two "codegen backends" will always be implementing the same binary ABI?
  - Ar-Curunir 3y ago
    This is for local work, so you use the same compiler for your dependencies and for your own code. Only the codegen backend differs.
  - sanxiyn 3y ago
    In theory yes, this could be problematic with alternative Rust implementations, but it works fine and many people are using it in this case. We can be sure LLVM and Cranelift codegen backends will be implementing the same binary ABI, because binary ABI decisions are made in the shared code.
  - aw1621107 3y ago
    I suppose that might depend on how the ABI is represented internally. If the ABI is fully described by (one of?) the lowered IR the backends consume (e.g., does MIR fully describe struct layouts/etc.) then I wouldn't expect there to be any issues outside "regular" bugs since all the relevant information would be contained in the inputs.
    - sanxiyn 3y ago
      It is done in the shared code, see https://rustc-dev-guide.rust-lang.org/backend/backend-agnostic.html https://rustc-dev-guide.rust-lang.org/backend/backend-agnost... for details.
metadat 3y ago
The Equality Graphs link [0] led me to discover ESC/Java [1] [2]. Has anyone actually tried or had any success with ESC/Java? It's piqued my curiosity to compare with Spot bugs (formerly known as Findbugs). [0] https://en.wikipedia.org/wiki/E-graph https://en.wikipedia.org/wiki/E-graph [1] https://en.wikipedia.org/wiki/ESC/Java https://en.wikipedia.org/wiki/ESC/Java [2] https://www.kindsoftware.com/products/opensource/escjava2/ https://www.kindsoftware.com/products/opensource/escjava2/
ad-ops 3y ago
I see that there are many comments on full debug builds, but for me the most important difference are incremental build times when making minor changes. In my opinion this is what speeds up the development iterations. Here are my build times when making a trivial change to a print-statment in a root function, comparing nightly dev vs adding cranelift + mold for rust-analyzer[0] (347_290 LoC) and gleam[1] (76_335 LoC): $ time cargo build Compiling rust-analyzer v0.0.0 (/home/user/repos/rust-analyzer/crates/rust-analyzer) # nightly Finished `dev` profile [unoptimized] target(s) in 6.60s cargo build 4.18s user 2.51s system 100% cpu 6.650 total # cranelift+mold Finished `dev` profile [unoptimized] target(s) in 2.25s cargo build 1.77s user 0.36s system 92% cpu 2.305 total Compiling gleam v1.0.0 (/home/user/repos/gleam/compiler-cli) # nightly Finished `dev` profile [unoptimized + debuginfo] target(s) in 4.69s cargo build --bin gleam 3.02s user 1.74s system 100% cpu 4.743 total # cranelift+mold Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.99s cargo build --bin gleam 0.71s user 0.20s system 88% cpu 1.033 total For me this is the most important metric and it shows a huge improvement. If I compare it to Go building Terraform[2] (371_594 LoC) it is looking promising. This is a bit unfair since it is the release build for Go and this is really nice in the CI/CD. Love Go compilation times and I thought it would be nice to compare with another language to show the huge improvements that Rust has made. $ time go build go build 3.62s user 0.76s system 171% cpu 2.545 total I was looking forward to parallel front-end[3], but I have not seen any improvement for these small changes. [0] https://github.com/rust-lang/rust-analyzer https://github.com/rust-lang/rust-analyzer [1] https://github.com/gleam-lang/gleam https://github.com/gleam-lang/gleam [2] https://github.com/hashicorp/terraform https://github.com/hashicorp/terraform [3] https://blog.rust-lang.org/2023/11/09/parallel-rustc.html https://blog.rust-lang.org/2023/11/09/parallel-rustc.html *edit: code-comments & links + making it easier to see the differences
- deleted 3y ago
  [deleted]
- ad-ops 3y ago
  For completion here is the compilation time for a small project from the axum/examples[0] (125 LoC), also comparing nightly dev vs adding cranelift + mold: $ time cargo build Compiling example-todos v0.1.0 (/home/user/ws/rust/example-todos) Finished `dev` profile [unoptimized + debuginfo] target(s) in 1.65s cargo build 1.49s user 0.58s system 123% cpu 1.685 total Compiling example-todos v0.1.0 (/home/user/ws/rust/example-todos) Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.55s cargo build 0.47s user 0.13s system 102% cpu 0.590 total [0] https://github.com/tokio-rs/axum/tree/main/examples/todos https://github.com/tokio-rs/axum/tree/main/examples/todos
rishav_sharan 3y ago
It sucks that there is no way to use cranelift from outside of rust to create your own toy language. I would have loved to use cranelift in a toy compiler, but I am not ready to pay the Rust price of complexity.
- sigsev_251 3y ago
  There is always qbe if you need something simpler
- kibwen 3y ago
  As far as I know, you should be able to generate textual CLIF files and feed them to Cranelift: https://github.com/bytecodealliance/wasmtime/blob/main/cranelift/docs/ir.md https://github.com/bytecodealliance/wasmtime/blob/main/crane...
- littlestymaar 3y ago
  Would using cranelift frontend[1] with PyO3[2] be an option for you? [1]: https://docs.rs/cranelift-frontend/0.105.3/cranelift_frontend/index.html https://docs.rs/cranelift-frontend/0.105.3/cranelift_fronten... [2]: https://pyo3.rs/v0.15.1/ https://pyo3.rs/v0.15.1/
posix_monad 3y ago
Can anyone explain why Cranelift is expected to be faster than LLVM? And why those improvements can't also be applied to LLVM?
- Filligree 3y ago
  It uses E-graphs, as explained in the article. That’s a completely different approach to compilation, and to use it in LLVM you’d have to rewrite LLVM. It’s also unlikely that the resulting code will ever be as fast as a traditional compiler’s output. It’s great for development, but I wouldn’t use it in a release build.
  - Rusky 3y ago
    I don't believe the performance difference between Cranelift and LLVM really has much to do with E-graphs. Cranelift had this same performance profile (faster than LLVM but generating slower output) before they switched to E-graphs. Rather it's about how much effort Cranelift puts toward optimizing its output- it has fewer, less involved passes (regardless of whether those "passes" are expressed as part of the E-graph framework). More subtly, this means it is also written to generate "okay" code without as much reliance on those passes- while LLVM on the other hand generates a lot of naive code at -O0 which contributes to its slower compile times in that mode.
    - cfallin 3y ago
      Right, it's about algorithmic tradeoffs throughout. A good example I wrote about is here: https://cfallin.org/blog/2021/01/22/cranelift-isel-2/ https://cfallin.org/blog/2021/01/22/cranelift-isel-2/ where we use a single-pass algorithm to solve a problem that LLVM has a multi-part fixpoint loop to solve. Most CPU time during compile is in the register allocator and I took a really careful approach to optimization when I rewrote it a few years ago (more details https://cfallin.org/blog/2022/06/09/cranelift-regalloc2/ https://cfallin.org/blog/2022/06/09/cranelift-regalloc2/). We generally try to pay close attention to algorithmic efficiency and avoid altogether the fixpoint loops, etc that one often finds elsewhere. (RA2 does backtrack and have a worklist loop, though it's pretty minimal, and also we're planning to add a single-pass mode.) (disclosure: I was Cranelift tech lead in 2020-2022)
tsegratis 3y ago
I feel like im reading advertising blurb reading that article I wish them every success, but i hope for a more balanced overview of pros and cons rather than gushing praise at every step...
Monalisa12 3y ago
[flagged]
- ecmascript 3y ago
  Seriously, spam at HN? That is pretty unusual to see.
  - orthecreedence 3y ago
    If you have showdead set to "yes" in your settings, you'll see a lot more spam like this. You also get to see comments that add to discussion but were downvoted to oblivion because people don't like certain things being questioned.
    - ecmascript 3y ago
      It wasn't dead when I replied. I know this, I show dead since I often find my comments to be flagged or killed since I have some unpopular opinions. Just watch the my history and view the sea of down votes I've collected. ;)
  - dredmorbius 3y ago
    <https://news.ycombinator.com/item?id=10808926 https://news.ycombinator.com/item?id=10808926> (spam, trolls, same thing)
rayiner 3y ago
Very interesting article. I had not heard of equality graphs before. Here's some pretty good background reading on the subject: https://inst.eecs.berkeley.edu/~cs294-260/sp24/2024-03-04-eqsat-paper https://inst.eecs.berkeley.edu/~cs294-260/sp24/2024-03-04-eq...
mmoskal 3y ago
> JIT compilers often use techniques, such as speculative optimizations, that make it difficult to reuse the compiler outside its original context, since they encode so many assumptions about the specific language for which they were designed. > The developers of Cranelift chose to use a more generic architecture, which means that Cranelift is usable outside of the confines of WebAssembly. One would think this has more to do with Wasm being the source language, as it's fairly generic (compared to JS or Python), so there are no specific assumptions to encode. Great article though. It's quite interesting to see E-matching used in compilers, took me down a memory lane (and found myself cited on Wikipedia page for e-graphs).
namuol 3y ago
Is there no native support for M1-M3 Macs currently, and no Windows support either? Unclear what the roadmap is there, as this update from the most active contributor is inconclusive: > Windows support has been omitted for now. And for macOS currently on supports x86_64 as Apple invented their own calling convention for arm64 for which variadic functions can’t easily be implemented as hack. If you are using an M1 processor, you could try installing the x86_64 version of rustc and then using Rosetta 2. Rosetta 2 will hurt performance though, so you will need to try if it is faster than the LLVM backend with arm64 rustc. Source is from Oct 2023 so this could easily be outdated, but I found nothing in the original article: https://bjorn3.github.io/2023/10/31/progress-report-oct-2023.html https://bjorn3.github.io/2023/10/31/progress-report-oct-2023...
- bhaney 3y ago
  https://github.com/rust-lang/rustc_codegen_cranelift#platform-support https://github.com/rust-lang/rustc_codegen_cranelift#platfor...
- sanxiyn 3y ago
  Windows is supported. See https://github.com/rust-lang/rustc_codegen_cranelift/issues/977 https://github.com/rust-lang/rustc_codegen_cranelift/issues/....
Someone 3y ago
FTA: “Because optimizations run on an E-graph only add information in the form of new annotations, the order of the optimizations does not change the result. As long as the compiler continues running optimizations until they no longer have any new matches (a process known as equality saturation), the E-graph will contain the representation that would have been produced by the optimal ordering of an equivalent sequence of traditional optimization passes […] In practice, Cranelift sets a limit on how many operations are performed on the graph to prevent it from becoming too large.” So, in practice, the order of optimizations can change the result? How easy is it to hit that limit?
- HelloNurse 3y ago
  For example, simplification of arithmetic expressions and propagating constants need to be combined (discovery of constants can allow further simplification, simplification can reach constant results). With destructive updates you have to decide what variant has the last word (e.g. 2*a or a+a or a<<1), while an equality graph collects progress without heuristic and imprecise choices allowing equality saturation,
makemake_kbo 3y ago
imo rust debug builds are fast enough, but its nice to see things are going to get even faster! hopefully this will eventually make `rust-analyzer` faster and more efficient.
deleted 3y ago
[deleted]

444 points by ridruejo 3y ago

k_bx 3y ago

Any fresh compilation time benchmarks and comparisons to LLVM?

zokier 3y ago
From the article: > A full debug build of Cranelift itself using the Cranelift backend took 29.6 seconds on my computer, compared to 37.5 with LLVM (a reduction in wall-clock time of 20%) That seems much smaller difference than what I would have expected
- __s 3y ago
  Those numbers are the entire compile time, parsing/typecheck/MIR+MIR optimization/linking Don't have numbers handy, so hard to say how much faster Cranelift is making the codegen portion, but gets into Amdahl's Law
  - Filligree 3y ago
    And there are faster linkers than the default. …why is it still the default?
    - 3836293648 3y ago
      Compatibility with niche usecases
      - Filligree 3y ago
        That sounds like a good reason to keep the existing one as an opt-in possibility.
    - kibwen 3y ago
      Because the linker provided by the system itself is the one that's guaranteed to be the most broadly compatible. For a toolchain to begin distributing an alternative linker is a lot of work on every supported platform (future versions of Rust may sidestep this issue by making LLD the default on certain platforms, which they get "for free" by dint of shipping alongside LLVM). But also, because there are about ten people on planet Earth qualified to write a production-grade linker, which is why LLD still isn't broadly recommended yet.
boxed 3y ago
The very last paragraph: > A full debug build of Cranelift itself using the Cranelift backend took 29.6 seconds on my computer, compared to 37.5 with LLVM (a reduction in wall-clock time of 20%). Those wall-clock times don't tell the full story, however, because of parallelism in the build system. Compiling with Cranelift took 125 CPU-seconds, whereas LLVM took 211 CPU-seconds, a difference of 40%. Incremental builds — rebuilding only Cranelift itself, and none of its dependencies — were faster with both backends. 66ms of CPU time compared to 90ms.
AlexErrant 3y ago
Not quite fresh, but > A paper from 2020 [0] showed that Cranelift was an order of magnitude faster than LLVM, while producing code that was approximately twice as slow on some benchmarks. [0] https://arxiv.org/pdf/2011.13127.pdf https://arxiv.org/pdf/2011.13127.pdf
- Findecanor 3y ago
  The changes in Cranelift since 2020 have been quite significant so I would not put any trust in those benchmarks.
nindalf 3y ago
Few reports comparing Cranelift to LLVM from this day old reddit thread [1] - 29.52s -> 24.47s (17.1%) - 27s -> 19s (29.6%) - 11.5s -> 8.4s (26.9%) - 37.5s -> 29.6s (28.7%) - this measurement from TFA. To put these numbers in context, all the perf improvements over the last 4 years have helped the compiler become faster on a variety of workloads by 7%, 17%, 13% and 15%, for an overall speed gain of 37% over 4 years. [2] So one large change providing a 20-30% improvement is very impressive. When you add that to the parallel frontend [3] and support for linking with LLD [4], Rust compilation could be substantially faster by this time next year. [1] - https://old.reddit.com/r/rust/comments/1bgyo8a/try_cranelift_codegen_backend_for_faster_compile/ https://old.reddit.com/r/rust/comments/1bgyo8a/try_cranelift... [2] - https://nnethercote.github.io/2024/03/06/how-to-speed-up-the-rust-compiler-in-march-2024.html https://nnethercote.github.io/2024/03/06/how-to-speed-up-the... [3] - https://blog.rust-lang.org/2023/11/09/parallel-rustc.html https://blog.rust-lang.org/2023/11/09/parallel-rustc.html [4] - https://github.com/rust-lang/rust/issues/39915 https://github.com/rust-lang/rust/issues/39915
- k_bx 3y ago
  Thanks, that's really great news. The only thing I wish for now is aarch64 support on Apple Silicon

chrisaycock 3y ago

This article provides an excellent overview of the latest in speed of optimizer vs quality of optimization. In particular, copy-and-patch compilation is still the fastest approach because it uses pre-compiled code, though leaves little room for optimization. Cranelift uses e-graphs to represent equivalence on the IR. This allows for more optimizations than the copy-and-patch approach. Of course, the most optimized output is going to come from a more traditional compiler toolchain like LLVM or GCC. But for users who want to get "fast enough" output as quickly as possible, newer compiler techniques provide a promising alternative.

weinzierl 3y ago
From what I understand, the big advantage of the e-graphs approach is, that the quality of the output is (within limits) a function the time and memory given. The more memory, the more nodes can be generated in the e-graph and the more time for search, the better the selected node. It might never be as fast as copy-and-patch or as good as LLVM or GCC, but this flexibility is a value in itself.
- thechao 3y ago
  When we first reviewed the equality saturation paper, we thought there was one major pro, and one major con: [pro] phase-ordering invariant; [con] at the time there was no (believable) way to extract the transformed graph in a non-hand-wavy-way. Personally, I think e-graphs should be combined with Massalin superoptimization — they're natural "duals" — and just turn the whole exercise into a hill-climbing process. You can tune the total effort by the set of passes used, the amount of time to drive the graph to saturation, and the method (and time) for graph extraction.
  - vlovich123 3y ago
    Can you memoize across invocations so that the time spent optimizing is cumulative across all builds?
    - 3y ago

diggan 3y ago

Tried out the instructions from the article on a tiny Bevy project, and compared it to a "normal" build: > cargo build --release 23.93s user 22.85s system 66% cpu 1:09.88 total > cargo +nightly build -Zcodegen-backend 23.52s user 21.98s system 68% cpu 1:06.86 total Seems just marginally faster than a normal release build. Wonder if there is something particular with Bevy that makes this so? The author of the article mentions 40% difference in build speed, but I'm not seeing anything near that. Edit: just realized I'm caching my release builds with sccache and a local NAS, hence the release builds being as fast as Cranelift+debug builds. Trying it again with just debug builds and without any caching: > cargo +nightly build 1997.35s user 200.38s system 1878% cpu 1:57.02 total > cargo +nightly build -Zcodegen-backend 280.96s user 73.06s system 657% cpu 53.850 total Definitely an improvement once I realized what I did wrong, about half the time spent compiling now :) Neat!

naasking 3y ago
Maybe your build is not limited by code generation, which seems like the only thing that changed here. There was a good thread recently about the variation in what slows down compilation: https://news.ycombinator.com/item?id=39721922 https://news.ycombinator.com/item?id=39721922
- diggan 3y ago
  Edited my comment now, forgot I was caching the release builds with sccache so wasn't actually compiling all the units, but fetching a lot of them instead :/
  - vlovich123 3y ago
    Which speaks to maybe that cargo should just ship with sccache turned on by default so that the “normal” experience for developing Rust has this seamless experience. Intelligent caching should always win. I’d like to see rustc get sccache integration that works at the MIR level too so that changing something that doesn’t change the code gen meaningfully still gets a cached response (e.g. changing some comments/whitespace, moving functions around, etc). Even cooler would be if LLVM itself could also cache internal expensive parts of compilation and optimization across process instances. That would make a huge impact in cutting down incremental builds.

pjmlp 3y ago

Finally, looking forward for wider adoption.

Dowwie 3y ago

Would it be naive to assume a general compile-time reduction of 20% for all Rust projects by swapping llvm with cranelift?

mrklol 3y ago
There are still projects out there which won’t hit 20% or even some %, if the bottleneck isn’t code gen (for example). So the part with"all" can be wrong, but beside that 20% is a good number.

Deukhoofd 3y ago

Does anyone by chance have benchmarks of runtime (so not the compile time) when using Cranelift? I'm seeing a mention of "twice as slow" in the article, but that's based on data from 2020. Wondering if it has substantially improved since then.

cfallin 3y ago
There are some benchmarks of Cranelift-based Wasm VMs (Wasmtime) vs. LLVM-based Wasm VMs here: https://00f.net/2023/01/04/webassembly-benchmark-2023/ https://00f.net/2023/01/04/webassembly-benchmark-2023/ The (perhaps slightly exaggerated but encouraging to me at least!) money quote there is: > That’s right. The cranelift code generator has become as fast as LLVM. This is extremely impressive considering the fact that cranelift is a relatively young project, written from scratch by a very small (but obviously very talented) team. In practice anywhere from 10%-30% slower maybe is reasonable to expect. Compiler microbenchmarks are interesting because they're very "quantized": for any particular benchmark, often either you get the right transforms and achieve the correct optimized inner loop, or you don't. So the game is about getting more and more cases right and we're slowly getting there. (disclosure: I was tech lead of Cranelift in 2020-2022)

cube2222 3y ago

Slightly off-topic, but if you fancy writing compilers in your free time, Cranelift has a great Rust library[0] for doing code generation - it’s a pleasure to use! [0]: https://docs.rs/cranelift-frontend/0.105.3/cranelift_frontend/index.html https://docs.rs/cranelift-frontend/0.105.3/cranelift_fronten...

loeg 3y ago
I've seen it used for really simple JIT in Advent of Code puzzles.
- PartiallyTyped 3y ago
  Why am i not surprised and even find this amusing? :D

Tehnix 3y ago

Very excited for Cranelift for debug builds to speed up development iteration - in particular for WASM/Frontend Rust where iteration speed is competing with the new era of Rust tooling for JS which lands in the sub 1 second builds sometimes (iteration speed in Frontend is crucial). Sadly, it does not yet support ARM macOS, so us M1-3 users will have to wait a bit :/

kapilsinha 3y ago
But usually, at least I don't build an executable while iterating. And if I do, I try to set up the feature flags so the build is minimal for the tests I am running
heavyset_go 3y ago
As someone who doesn't work in the frontend much, what tools are you talking about?
- Tehnix 3y ago
  There’s been a recent trend of rewriting tools in Rust with insanes speed gains - Rspack (webpack compatible) - Rolldown (rollup compatible) - Turbopack - Oxc (linter) - Biome (linter and more) - Bun (writing in Zig, does crazy fast bundling) There’s several parts here that are crucial to Frontend development For production you need: - Minificion of source code - Bundling of modules and source code into either one JS file or split into multiple for lazy loading only the parts you need - Transforming various unsupported high-level constructs into something older target browsers support - Typechecking/compiling, or stripping TypeScript if that’s in use Build times could easily go to 10-20 minutes with older tools. The development loop also gets hurt, here you’d want the loop from saving your change to seeing it in the UI to be almost instant. Anything else means you’ll have to develop crutch methods to workaround this (imagine moving and styling components only to need to sit and wait during each small incremental change).
  - heavyset_go 3y ago
    Thanks for your informative post!

Ericson2314 3y ago

Really looking forward to the death of non-e-graph-based compilation :)

convolvatron 3y ago
I've tried to look into this a couple times, including today. To me this looks alot like unification? but I don't really understand how operationally one gets from equivalence classes to instructions. is there an e-graphs for dummies writeup?
- tekknolagi 3y ago
  If by instructions you mean machine instructions, you don't; it's used for internal optimization passes only.
  - convolvatron 3y ago
    that helps, so this is really an alternative to pushing analysis attributes aronud a dataflow graph
- cfallin 3y ago
  The approach that Cranelift uses is what we call the "aegraph" (talk I gave about it: slides https://cfallin.org/pubs/egraphs2023_aegraphs_slides.pdf https://cfallin.org/pubs/egraphs2023_aegraphs_slides.pdf, video https://vimeo.com/843540328 https://vimeo.com/843540328). The basic idea is that eclasses hold sets of operator expressions (think sea-of-node IR), and we keep that alongside the CFG with a "skeleton" of side-effecting ops. We build that, do rewrites, then extract out of it back to a conventional CFG-of-basic-blocks for lowering. The "equivalence" part comes in when doing rewrites: the main difference between an egraph and a conventional sea-of-nodes IR with rewrite rules is that one keeps all representations in the equivalence class around, then chooses the best one later. We had to solve a few novel problems in working out how to handle control flow, and we're still polishing off some rough edges (search recent issues in the repo for egraphs); but we're mostly happy how it turned out! (Disclosure: tech lead of CL for a while; the e-graphs optimizer is "my fault")

CodesInChaos 3y ago

You can use different backends and optimization for different crates. It often makes sense to use optimized LLVM builds for dependencies, and debug LLVM or even Cranelift for your own code. See https://www.reddit.com/r/rust/comments/1bhpfeb/vastly_improved_recompile_times_in_rust_with/ https://www.reddit.com/r/rust/comments/1bhpfeb/vastly_improv...

zozbot234 3y ago
I would not expect this to work without issues, as Rust does not support a stable binary ABI across different compiler versions. How can we be sure that the two "codegen backends" will always be implementing the same binary ABI?
- Ar-Curunir 3y ago
  This is for local work, so you use the same compiler for your dependencies and for your own code. Only the codegen backend differs.
- sanxiyn 3y ago
  In theory yes, this could be problematic with alternative Rust implementations, but it works fine and many people are using it in this case. We can be sure LLVM and Cranelift codegen backends will be implementing the same binary ABI, because binary ABI decisions are made in the shared code.
- aw1621107 3y ago
  I suppose that might depend on how the ABI is represented internally. If the ABI is fully described by (one of?) the lowered IR the backends consume (e.g., does MIR fully describe struct layouts/etc.) then I wouldn't expect there to be any issues outside "regular" bugs since all the relevant information would be contained in the inputs.
  - sanxiyn 3y ago
    It is done in the shared code, see https://rustc-dev-guide.rust-lang.org/backend/backend-agnostic.html https://rustc-dev-guide.rust-lang.org/backend/backend-agnost... for details.

metadat 3y ago

The Equality Graphs link [0] led me to discover ESC/Java [1] [2]. Has anyone actually tried or had any success with ESC/Java? It's piqued my curiosity to compare with Spot bugs (formerly known as Findbugs). [0] https://en.wikipedia.org/wiki/E-graph https://en.wikipedia.org/wiki/E-graph [1] https://en.wikipedia.org/wiki/ESC/Java https://en.wikipedia.org/wiki/ESC/Java [2] https://www.kindsoftware.com/products/opensource/escjava2/ https://www.kindsoftware.com/products/opensource/escjava2/

ad-ops 3y ago

I see that there are many comments on full debug builds, but for me the most important difference are incremental build times when making minor changes. In my opinion this is what speeds up the development iterations. Here are my build times when making a trivial change to a print-statment in a root function, comparing nightly dev vs adding cranelift + mold for rust-analyzer[0] (347_290 LoC) and gleam[1] (76_335 LoC): $ time cargo build Compiling rust-analyzer v0.0.0 (/home/user/repos/rust-analyzer/crates/rust-analyzer) # nightly Finished `dev` profile [unoptimized] target(s) in 6.60s cargo build 4.18s user 2.51s system 100% cpu 6.650 total # cranelift+mold Finished `dev` profile [unoptimized] target(s) in 2.25s cargo build 1.77s user 0.36s system 92% cpu 2.305 total Compiling gleam v1.0.0 (/home/user/repos/gleam/compiler-cli) # nightly Finished `dev` profile [unoptimized + debuginfo] target(s) in 4.69s cargo build --bin gleam 3.02s user 1.74s system 100% cpu 4.743 total # cranelift+mold Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.99s cargo build --bin gleam 0.71s user 0.20s system 88% cpu 1.033 total For me this is the most important metric and it shows a huge improvement. If I compare it to Go building Terraform[2] (371_594 LoC) it is looking promising. This is a bit unfair since it is the release build for Go and this is really nice in the CI/CD. Love Go compilation times and I thought it would be nice to compare with another language to show the huge improvements that Rust has made. $ time go build go build 3.62s user 0.76s system 171% cpu 2.545 total I was looking forward to parallel front-end[3], but I have not seen any improvement for these small changes. [0] https://github.com/rust-lang/rust-analyzer https://github.com/rust-lang/rust-analyzer [1] https://github.com/gleam-lang/gleam https://github.com/gleam-lang/gleam [2] https://github.com/hashicorp/terraform https://github.com/hashicorp/terraform [3] https://blog.rust-lang.org/2023/11/09/parallel-rustc.html https://blog.rust-lang.org/2023/11/09/parallel-rustc.html *edit: code-comments & links + making it easier to see the differences

deleted 3y ago
[deleted]
ad-ops 3y ago
For completion here is the compilation time for a small project from the axum/examples[0] (125 LoC), also comparing nightly dev vs adding cranelift + mold: $ time cargo build Compiling example-todos v0.1.0 (/home/user/ws/rust/example-todos) Finished `dev` profile [unoptimized + debuginfo] target(s) in 1.65s cargo build 1.49s user 0.58s system 123% cpu 1.685 total Compiling example-todos v0.1.0 (/home/user/ws/rust/example-todos) Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.55s cargo build 0.47s user 0.13s system 102% cpu 0.590 total [0] https://github.com/tokio-rs/axum/tree/main/examples/todos https://github.com/tokio-rs/axum/tree/main/examples/todos

rishav_sharan 3y ago

It sucks that there is no way to use cranelift from outside of rust to create your own toy language. I would have loved to use cranelift in a toy compiler, but I am not ready to pay the Rust price of complexity.

sigsev_251 3y ago
There is always qbe if you need something simpler
kibwen 3y ago
As far as I know, you should be able to generate textual CLIF files and feed them to Cranelift: https://github.com/bytecodealliance/wasmtime/blob/main/cranelift/docs/ir.md https://github.com/bytecodealliance/wasmtime/blob/main/crane...
littlestymaar 3y ago
Would using cranelift frontend[1] with PyO3[2] be an option for you? [1]: https://docs.rs/cranelift-frontend/0.105.3/cranelift_frontend/index.html https://docs.rs/cranelift-frontend/0.105.3/cranelift_fronten... [2]: https://pyo3.rs/v0.15.1/ https://pyo3.rs/v0.15.1/

posix_monad 3y ago

Can anyone explain why Cranelift is expected to be faster than LLVM? And why those improvements can't also be applied to LLVM?

Filligree 3y ago
It uses E-graphs, as explained in the article. That’s a completely different approach to compilation, and to use it in LLVM you’d have to rewrite LLVM. It’s also unlikely that the resulting code will ever be as fast as a traditional compiler’s output. It’s great for development, but I wouldn’t use it in a release build.
- Rusky 3y ago
  I don't believe the performance difference between Cranelift and LLVM really has much to do with E-graphs. Cranelift had this same performance profile (faster than LLVM but generating slower output) before they switched to E-graphs. Rather it's about how much effort Cranelift puts toward optimizing its output- it has fewer, less involved passes (regardless of whether those "passes" are expressed as part of the E-graph framework). More subtly, this means it is also written to generate "okay" code without as much reliance on those passes- while LLVM on the other hand generates a lot of naive code at -O0 which contributes to its slower compile times in that mode.
  - cfallin 3y ago
    Right, it's about algorithmic tradeoffs throughout. A good example I wrote about is here: https://cfallin.org/blog/2021/01/22/cranelift-isel-2/ https://cfallin.org/blog/2021/01/22/cranelift-isel-2/ where we use a single-pass algorithm to solve a problem that LLVM has a multi-part fixpoint loop to solve. Most CPU time during compile is in the register allocator and I took a really careful approach to optimization when I rewrote it a few years ago (more details https://cfallin.org/blog/2022/06/09/cranelift-regalloc2/ https://cfallin.org/blog/2022/06/09/cranelift-regalloc2/). We generally try to pay close attention to algorithmic efficiency and avoid altogether the fixpoint loops, etc that one often finds elsewhere. (RA2 does backtrack and have a worklist loop, though it's pretty minimal, and also we're planning to add a single-pass mode.) (disclosure: I was Cranelift tech lead in 2020-2022)

tsegratis 3y ago

I feel like im reading advertising blurb reading that article I wish them every success, but i hope for a more balanced overview of pros and cons rather than gushing praise at every step...

Monalisa12 3y ago

[flagged]

ecmascript 3y ago
Seriously, spam at HN? That is pretty unusual to see.
- orthecreedence 3y ago
  If you have showdead set to "yes" in your settings, you'll see a lot more spam like this. You also get to see comments that add to discussion but were downvoted to oblivion because people don't like certain things being questioned.
  - ecmascript 3y ago
    It wasn't dead when I replied. I know this, I show dead since I often find my comments to be flagged or killed since I have some unpopular opinions. Just watch the my history and view the sea of down votes I've collected. ;)
- dredmorbius 3y ago
  <https://news.ycombinator.com/item?id=10808926 https://news.ycombinator.com/item?id=10808926> (spam, trolls, same thing)

rayiner 3y ago

Very interesting article. I had not heard of equality graphs before. Here's some pretty good background reading on the subject: https://inst.eecs.berkeley.edu/~cs294-260/sp24/2024-03-04-eqsat-paper https://inst.eecs.berkeley.edu/~cs294-260/sp24/2024-03-04-eq...

mmoskal 3y ago

> JIT compilers often use techniques, such as speculative optimizations, that make it difficult to reuse the compiler outside its original context, since they encode so many assumptions about the specific language for which they were designed. > The developers of Cranelift chose to use a more generic architecture, which means that Cranelift is usable outside of the confines of WebAssembly. One would think this has more to do with Wasm being the source language, as it's fairly generic (compared to JS or Python), so there are no specific assumptions to encode. Great article though. It's quite interesting to see E-matching used in compilers, took me down a memory lane (and found myself cited on Wikipedia page for e-graphs).

namuol 3y ago

Is there no native support for M1-M3 Macs currently, and no Windows support either? Unclear what the roadmap is there, as this update from the most active contributor is inconclusive: > Windows support has been omitted for now. And for macOS currently on supports x86_64 as Apple invented their own calling convention for arm64 for which variadic functions can’t easily be implemented as hack. If you are using an M1 processor, you could try installing the x86_64 version of rustc and then using Rosetta 2. Rosetta 2 will hurt performance though, so you will need to try if it is faster than the LLVM backend with arm64 rustc. Source is from Oct 2023 so this could easily be outdated, but I found nothing in the original article: https://bjorn3.github.io/2023/10/31/progress-report-oct-2023.html https://bjorn3.github.io/2023/10/31/progress-report-oct-2023...

bhaney 3y ago
https://github.com/rust-lang/rustc_codegen_cranelift#platform-support https://github.com/rust-lang/rustc_codegen_cranelift#platfor...
sanxiyn 3y ago
Windows is supported. See https://github.com/rust-lang/rustc_codegen_cranelift/issues/977 https://github.com/rust-lang/rustc_codegen_cranelift/issues/....

Someone 3y ago

FTA: “Because optimizations run on an E-graph only add information in the form of new annotations, the order of the optimizations does not change the result. As long as the compiler continues running optimizations until they no longer have any new matches (a process known as equality saturation), the E-graph will contain the representation that would have been produced by the optimal ordering of an equivalent sequence of traditional optimization passes […] In practice, Cranelift sets a limit on how many operations are performed on the graph to prevent it from becoming too large.” So, in practice, the order of optimizations can change the result? How easy is it to hit that limit?

HelloNurse 3y ago
For example, simplification of arithmetic expressions and propagating constants need to be combined (discovery of constants can allow further simplification, simplification can reach constant results). With destructive updates you have to decide what variant has the last word (e.g. 2*a or a+a or a<<1), while an equality graph collects progress without heuristic and imprecise choices allowing equality saturation,

makemake_kbo 3y ago

imo rust debug builds are fast enough, but its nice to see things are going to get even faster! hopefully this will eventually make `rust-analyzer` faster and more efficient.

deleted 3y ago

[deleted]