Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Cranelift code generation comes to Rust

lwn.net

Post reply on HN
Print view View original

91–100 of 117 posts

Re: Cranelift code generation comes to Rust

#91

Post by sanxiyn »

posix_monad wrote: post #50
norman784 wrote: post #42

Earlier quoted context omitted.

> why those improvements can't also be applied to LLVM? 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.

X is too bloated! We need Y, which is leaner and more tailored to our use-case. (years pass...) Y is too bloated! We need Z...

After years of trying (IIRC there was funded effort from Intel), LLVM still can't parallelize code generation at function level. Cranelift had function level code generation parallelization from day 1.

Re: Cranelift code generation comes to Rust

#92

Post by kccqzy »

mort96 wrote: post #65
thesz wrote: post #22

Earlier quoted context omitted.

Superoptimizers: https://en.wikipedia.org/wiki/Superoptimization Also, program distillation: https://www.researchgate.net/publication/220989887_Distillat...

Isn't it a bit weird that this isn't just the standard? Like imagine if Chrome was optimized with such a superoptimizer; let the optimizer spend a couple hours every month or so when cutting a new release. Surely that has to be worth it?

Chrome already uses PGO: https://blog.chromium.org/2020/08/chrome-just-got-faster-wit...

Re: Cranelift code generation comes to Rust

#93

Post by cfallin »

Deukhoofd wrote: post #16

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.

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/

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)

Re: Cranelift code generation comes to Rust

#94

Post by cfallin »

Rusky wrote: post #56
Filligree wrote: post #36

Earlier quoted context omitted.

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.

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-grap…

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

Re: Cranelift code generation comes to Rust

#95

Post by cfallin »

weinzierl wrote: post #7
chrisaycock wrote: post #5

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 o…

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.

We actually take a fairly unconventional approach to e-graphs: we have a few linear passes and we do all rewrites eagerly, so we use them to provide a general framework for the fixpoint problem into which we plug in all our rewrites, but we don't have the usual "apply as much CPU time as you want to get better results" property of conventional equality saturation.

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)

Re: Cranelift code generation comes to Rust

#96

Post by Someone »

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?

Re: Cranelift code generation comes to Rust

#97

Post by cfallin »

convolvatron wrote: post #68
Ericson2314 wrote: post #24

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

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?

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

Re: Cranelift code generation comes to Rust

#98

Post by azakai »

sanxiyn wrote: post #91
posix_monad wrote: post #50

Earlier quoted context omitted.

X is too bloated! We need Y, which is leaner and more tailored to our use-case. (years pass...) Y is too bloated! We need Z...

After years of trying (IIRC there was funded effort from Intel), LLVM still can't parallelize code generation at function level. Cranelift had function level code generation parallelization from day 1.

I have always been told that LLVM doesn't parallelize codegen because the right place for that is in the build system: just do make -j N (or use ninja, which parallelizes automatically). And when you're building lots of source files in a normal project that's definitely true.

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

Re: Cranelift code generation comes to Rust

#99

Post by ecmascript »

orthecreedence wrote: post #48
ecmascript wrote: post #35

Earlier quoted context omitted.

Seriously, spam at HN? That is pretty unusual to see.

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.

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

Re: Cranelift code generation comes to Rust

#100

Post by PartiallyTyped »

loeg wrote: post #32
cube2222 wrote: post #17

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

I've seen it used for really simple JIT in Advent of Code puzzles.

Why am i not surprised and even find this amusing? :D
Post reply on HN