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.

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.

I gave a talk about this approach, aegraphs (acyclic e-graphs), here: slides (https://cfallin.org/pubs/egraphs2023_aegraphs_slides.pdf), video (https://vimeo.com/843540328)

(disclosure: Cranelift tech lead 2020-2022 and main author of the e-graphs mid-end, as well as regalloc, isel and its custom DSL, and other bits, along with the excellent team)

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.

Also, program distillation: https://www.researchgate.net/publication/220989887_Distillat...

Such improvements can happen with compiler updates, but not when the starting point is a compiler that's already of decent quality. I recall some GPU driver updates from ATi (years ago) delivered pretty drastic performance improvements, but I believe that's because the original drivers were rather primitive.

(Perhaps a drastic improvement to autovectorisation could give a 30% boost, or better, but this would apply only to certain programs.)

You could grant a compute budget 100x the typical build set-up, but no one has built a production-ready compiler to take advantage of that, and if they did I suspect the improvements would be unimpressive. They may also run into a 'complexity ceiling' issue, as the compiler would presumably be even more complex than today's ordinary optimising compilers, which are already enormous.

As Filligree says, superoptimisers tend to only be practical for very short programs. They can't be applied to monstrous codebases like Chromium.

[1] https://proebsting.cs.arizona.edu/law.html

This might seem discouraging, but it is not - one can still reap the benefits of code optimization twelve times as long after Moore's law stops working.

https://unison-code.github.io/

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

  $ time go build
  go build  3.62s user 0.76s system 171% cpu 2.545 total

[0] https://github.com/rust-lang/rust-analyzer

[1] https://github.com/gleam-lang/gleam

[2] https://github.com/hashicorp/terraform

[3] https://blog.rust-lang.org/2023/11/09/parallel-rustc.html

*edit: code-comments & links + making it easier to see the differences

    $ 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://docs.rs/cranelift-frontend/0.105.3/cranelift_fronten...

> 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!

https://news.ycombinator.com/item?id=39721922

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.

Isn't incremental compilation already like that?

See https://www.reddit.com/r/rust/comments/1bhpfeb/vastly_improv...

I'd expect the generic code to lower the function parameters to primitive types (pointers, ints, floats, etc.), but the backend would then distribute those over registers and/or stack. Keeping that compatible would still require an (unstable) specification implemented by all compatible backends.

Unwinding might be tricky as well.

Not sure about that. Calling conventions are defined by the platform ABI which is what the backend implements, so any conforming backend should still be mutually invokable. That's why a Rust program can emit an ABI-stable C API and why you can call GCC built libraries from an LLVM built executable. The lowering of parameters to registers is constrained by this because the intermediate representation understands that what are parameters to functions & then follows the platform ABI to lower it to function calls.

What is left is to account for the ABI in any monomorphizations that occur at the boundary, i.e. when your own structures monomorphize generic functions in the dependency.

When the compiler creates this monomorphic variant, and lowers down, it can provide the necessary details of the ABI.

[0] https://en.wikipedia.org/wiki/E-graph

[1] https://en.wikipedia.org/wiki/ESC/Java

[2] https://www.kindsoftware.com/products/opensource/escjava2/

Sadly, it does not yet support ARM macOS, so us M1-3 users will have to wait a bit :/

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)

So, in practice, the order of optimizations can change the result? How easy is it to hit that limit?

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...

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.

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.

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/). 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)

LLVM is a huge and bloated ecosystem (it has tons of tools and millions of LoC), also the code base itself is pretty old or rather the project has his age, so there's a lot of legacy code, other aspect is that is hard to try new/radical things because how big the project itself is.

(years pass...)

Y is too bloated! We need Z...

It's different when you're a wasm VM that receives big chunk of wasm that contains many source files, and you get it all at once. And for that reason pretty much every wasm compiler parallelizes codegen: Cranelift as you said, and also V8, SpiderMonkey, JSC, and not just VMs but also optimizers like Binaryen. It's a crucial part of their design.

For LLVM, the right design may be what it has today: single-core codegen. (LTO is the main issue there, but that's what thin LTO is for.)

> 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).

- 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...

[2] - https://nnethercote.github.io/2024/03/06/how-to-speed-up-the...

[3] - https://blog.rust-lang.org/2023/11/09/parallel-rustc.html

[4] - https://github.com/rust-lang/rust/issues/39915

> 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.

> 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

Don't have numbers handy, so hard to say how much faster Cranelift is making the codegen portion, but gets into Amdahl's Law

…why is it still the default?

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")

I wish them every success, but i hope for a more balanced overview of pros and cons rather than gushing praise at every step...