69 ms·

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)
norman784 3y ago
> 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.
- papruapap 3y ago
  iirc Zig want to replace LLVM for similar reasons, also hard to debug.
- posix_monad 3y ago
  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...
  - dymk 3y ago
    I don't get it. Is your point that new software shouldn't be written to fulfill new usecases? We should always bolt new patterns and architecture onto existing codebases?
  - alserio 3y ago
    Yes. But in the meantime one can experiment with new things, void some assumptions. And I don't know about the LLVM project, but its quite more difficult to try different ideas in a big and old organization and codebase than it is in a greenfield project. Maybe they won't be successful, maybe they will move the whole field ahead.
  - sanxiyn 3y ago
    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.
    - azakai 3y ago
mort96 3y ago
I've heard compiler writers complain that LLVM's API is inherently slow. Something about using runtime polymorphism everywhere. I don't know how much there is to this though, I haven't investigated it myself.

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)

norman784 3y ago

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

papruapap 3y ago
iirc Zig want to replace LLVM for similar reasons, also hard to debug.
posix_monad 3y ago
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...
- dymk 3y ago
  I don't get it. Is your point that new software shouldn't be written to fulfill new usecases? We should always bolt new patterns and architecture onto existing codebases?
- alserio 3y ago
  Yes. But in the meantime one can experiment with new things, void some assumptions. And I don't know about the LLVM project, but its quite more difficult to try different ideas in a big and old organization and codebase than it is in a greenfield project. Maybe they won't be successful, maybe they will move the whole field ahead.
- sanxiyn 3y ago
  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.
  - azakai 3y ago

mort96 3y ago

I've heard compiler writers complain that LLVM's API is inherently slow. Something about using runtime polymorphism everywhere. I don't know how much there is to this though, I haven't investigated it myself.