[flagged]
Seriously, spam at HN? That is pretty unusual to see.
https://news.ycombinator.com/item?id=10808926> (spam, trolls, same thing)
Cranelift code generation comes to Rust
101–110 of 117 posts
Re: Cranelift code generation comes to Rust
#102Tried 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…
cache on a nas would limit cache speed to network speed. 1gbit is just about 125 megabytes/sec, while you can get a nvme disc with 4000+ megabytes/sec speed. so consider running sccache locally or just disable it for better build performance
Re: Cranelift code generation comes to Rust
#103Earlier quoted context omitted.
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…
I found the video to be great! Informative and understandable even when I'm just casually interested in compilers, with not a lot of real world experience writing them.
Re: Cranelift code generation comes to Rust
#104Earlier 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?
Yes, it is weird.
One thing that would help is that if we explicitly reimagine programming is characterizing the search space for the compiler, just as the e-graphs stuff in the article talks about separating generating alternatives from finding the best alternative.
Re: Cranelift code generation comes to Rust
#105imo 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.
Re: Cranelift code generation comes to Rust
#106Earlier quoted context omitted.
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 you memoize across invocations so that the time spent optimizing is cumulative across all builds?
Speaking as an e-graph rookie - I believe so, with caveats.
You can certainly store the chosen extractions/optimizations and re-use any that don't change. For example, if a long chain of rewrites yields A ==> B ==> ... ==> Z, you could short-circuit that and assume that Z is still what you want to replace A with. Perhaps each time you compiled, you could only rewrite the 'changed' sections of the program, along with a randomly selected portion to explore for greater-optimization. (Although, you may just want to go all the way and write a tool that constantly adds to your equivalence DB in the background, with compilation just a matter of running your extraction heuristics.)
You probably wouldn't want to store every possible rewrite, though, as the space complexity or retrieval cost is likely a bigger deal than the time complexity (you wouldn't load 2+2=4 from a database, you'd just do the addition). But, if you restore only a subset of equivalencies that are known to be useful, there's not a simple way to keep the optimization from re-exploring the "rejected candidates" (without shutting off the eclass entirely) - and, it's even not clear to me that you'd want to, as changing program context may end up meaning that M becomes a better replacement candidate for A than Z.
(Boring prerequisites for this approach also include: consistent serialization of terms, avoiding storage of infinite equivalencies, like `A => A + 0 => A + 0 + 0 ==> ...` (and possibly of exponential equivalencies like the kind associativity rules can produce), and strong heuristics to capture "high-value" equivalencies that are both useful and cheaper to lookup than re-derive.)
Re: Cranelift code generation comes to Rust
#107FTA: “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 sequenc…
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,
Re: Cranelift code generation comes to Rust
#108Earlier 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?
I think the wide variety of hardware and complexities of running on a real system sometimes make this problem more difficult.
Even within a given processor microarchitecture (say, just Zen 2, or just Haswell), different CPUs will be running at different frequencies, have different cooling solutions, and be running different microcode releases, all of which will affect which program is the fastest. And this is without considering cache pressure or memory latency, which is also dependent on any other programs the user happens to be running.
Running a superoptimizer for your linear algebra program that runs on your Cray supercluster can give clear gains. Doing the same for every combination of user hardware seems less feasible - you may find output that is a clear win for the machines you tested on, but it's often possible that it will lose out on other machines.
Re: Cranelift code generation comes to Rust
#109Earlier quoted context omitted.
I'm not a compiler engineer, but I think it's a diminishing returns issue. Modern optimising compilers are already impressive, and they get more impressive year on year, but only quite slowly. We don't see compilers producing code that runs 30% faster than the code generated last year, for instance. Such improvements can happen with compiler updates, but not when the starting point is a compiler that's already of dec…
But maybe you can superoptimize some hot sections, and encode the superoptimizer findings somewhere. Then the compiler can validate the optimizations and apply them to the particular piece of code for the rest of the program life, untill the preconditions hold.
As I understand it they just aren't very practical. Perhaps you could use a superoptimizer in a targeted way, assuming that:
1. The codebase has hot loops of very short sequences (or can be automatically reshaped into this patten)
2. The superoptimising compiler can produce code that significantly outperforms the code generated by ordinary optimising compilers
3. A practical superoptimising compiler exists
I can imagine these assumptions may not hold in practice.
> the compiler can validate the optimizations
A compiler transforms code from one representation to another, it doesn't validate arbitrary transformations.
It's not easy to prove that a given fragment of source-code corresponds to some given assembly code. I've heard of only one instance of this being done. [0]
> untill the preconditions hold
I'm not sure what you mean by this.
Re: Cranelift code generation comes to Rust
#110Earlier quoted context omitted.
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?
I'm not a compiler engineer, but I think it's a diminishing returns issue. Modern optimising compilers are already impressive, and they get more impressive year on year, but only quite slowly. We don't see compilers producing code that runs 30% faster than the code generated last year, for instance. Such improvements can happen with compiler updates, but not when the starting point is a compiler that's already of dec…
Something I missed: compilers are a mix of clever theoretical work and hard graft in implementation. Even if you somehow implement a practical compiler that exhausts the state of the art in compiler theory (a multi-million-dollar project in itself), you might still not be where you want to be in terms of optimisation.