Comment by ttd | Hacker News Reader

Comment by ttd | Hacker News Reader

Good article that I agree with mostly. One interesting note is this:

> There is no way to provide both optimized assembly and equivalent C code and let the compiler use the former in the general case and the latter in special cases.

This is true, but can be seen as a failure of language and tooling. For example, Halide [1] pioneered (AFAIK) the concept of separating algorithm from implementation at the language level. This separation lets you express the algorithm once, and then "schedule" it by specifying parallelism, vectorization, etc. You can provide multiple schedules for one algorithm, which allows you to specialize / make different choices depending on varying factors.

It's a really interesting concept, though maybe limited in practice to DSLs. I'm not sure a general purpose language would be a good fit for this model, but then, for general purpose programs written in general purpose languages, perf optimization at the level TFA discusses is frequently limited to just specific hot sections. Those hot sections could be extracted out into specialized components written in such a DSL.

1 - https://halide-lang.org/

> Halide [1] pioneered (AFAIK) the concept of separating algorithm from implementation at the language level.

you don't need to go all the way to Halide to do what the article is claiming isn't possible - you can do it just by including a "micro-kernel" in your library and have the code branch to that impl (depending on something at runtime) instead of whatever the C code compiled down to. this is done every single day in every single GPU lib (famously cublas ships with hundreds/thousands of these of such ukernels for gemms depending on shapes).

Ah ok, I see what you mean (and likely sibling comment too w.r.t. gcc feature). Yes that is a fair point - though still has the substantial downfall of maintaining many different implementation of any given algorithm.

I was going for something different: I don't want to choose a different implementation in runtime, I want the compiler to see through my code and apply constant propagation -- not just for constant inputs, but inputs with known properties, like `n < 1000` or `(n & 7) == 0`. I want it to also learn facts about the output values, e.g. that my `isqrt(n) -> m` function always returns `m` such that `m^2 <= n`. None of this is possible with runtime selection because runtime selection was never the point.

i have no idea what that has to do with what op quoted from your article:

> There is no way to provide both optimized assembly and equivalent C code and let the compiler use the former in the general case and the latter in special cases.

this is manifestly obviously possible (as i've said).

what you're talking about is something completely different goes by many names and uses many techniques (symbex, conex, sccp, scev, blah blah blah). many of these things are implemented in eg LLVM.

A lot of people have ways of accomplishing this, but my way is using compile-time execution in Zig (I know at least D, C++, and Terra have their own versions of this feature). You can specify a parameter as `comptime` and then do different things based on whatever conditions you want. You can also execute a lot of code at compile-time, including your sqrt check.

E.g. I wrote a `pextComptime` function, which will compile to just a `pext` instruction on machines that have a fast implementation, otherwise it will try to figure out if it can use a few clever tricks to emit just a couple of instructions, but if those aren't applicable it will fallback on a naïve technique.

https://github.com/Validark/Accelerated-Zig-Parser/blob/8782...

I think we're all talking past each other here.

Your suggestions introduce, in effect, a hypothetical `if` statement, only one branch of which is taken. I can change the condition arbitrarily, but ultimately it's still going to be either one or the other.

I want the `if` to take both branches at once. I want the compiler to assume that both branches trigger the exact same side effects and return the same results. I want it to try both approaches and determine the better one depending on the environment, e.g. the number of free registers, (lack of) inlining, facts statically known about the input -- all those things that you can't write a condition for on the source level.

Think about it this way. A standard compiler like LLVM contains passes which rewrite the program in order. If something has been rewritten, it will never be rolled back, except it another pass performs a separate rewrite that explicitly does that. In contrast, e-graphs-based compilers like Cranelift maintain an equivalence graph that represents all possible lowerings, and after the whole graph is built, an algorithm finds a single optimal lowering.

Existing solutions make me choose immediately without knowing all the context. The solution I'd like to see would delay the choice until lowering.

> e-graphs-based compilers like Cranelift maintain an equivalence graph that represents all possible lowerings, and after the whole graph is built, an algorithm finds a single optimal lowering

Do you have a good entrypoint reference for learning about how this works? This (and the associated mention in the article) is the first time I've heard of this approach.

@thrtythreeforty I think this RFC is a good start: https://github.com/bytecodealliance/rfcs/blob/main/accepted/.... Then read through these docs: https://docs.rs/egg/latest/egg/tutorials/. They document the behavior of a particular crate, but they also act as a very accessible high-level overview.

Oh, yes, I understand now. I've thought to myself before it would be nice if I could have implementation 1 go into variable x. And implementation 2 go into variable y. Then I do `assert(x == y)` and a compiler like Cranelift should know it only needs to pick one of them.

I'm glad to know that's the design of Cranelift, since that's how I would think it should be done, although I haven't written a middle or backend for a compiler yet.

> I want the `if` to take both branches at once.

this is called symbolic execution - as i have already told you, many compilers do this in the form sccp and scev. you don't need silly things like egraphs for this.

> If something has been rewritten, it will never be rolled back

this is patently false - not only do passes get rolled back to catch/correct errors but there is a fixed-point iteration system (at least in MLIR) that will apply passes as long as they are "profitable".

I don't see how symbolic execution is relevant to this. Yes, symbolic execution does "check both paths" for some definition of "check", but ultimately I as a programmer still need to write a condition, and that condition is on the source level, so it can't access information on e.g. register pressure, which is what I would like to comptime-branch on.

> not only do passes get rolled back to catch/correct errors but there is a fixed-point iteration system (at least in MLIR) that will apply passes as long as they are "profitable"

Huh? I'm not arguing against fixed-point iteration, that's perfectly fine because it's still a unidirectional process. What do you mean by "passes get rolled back to catch/correct errors" though? Certain rewrites can certainly be not performed in the first place if they pessimize the code, but that's not what I'm talking about.

If there's pass 1 that chooses between rewrite A and B, pass 2 that chooses between rewrite C or D, and pass 3 choosing between E or F, in a typical compiler, this choices would be made one by one mostly greedily. An e-graph style approach allows all of those eight combinations to be tried out without necessarily leading to a combinatorial explosion.

Another cool thing you could do is fuzz test a version of the code that actually does take both branches (in separate runs with fresh memory etc.) and aborts if they give different results.

I recently ran down approximately the same rabbit hole when trying to figure out what to do about x86 treating addition and bitwise OR differently. There's https://llvm.org/docs/LangRef.html#id171, but it can't generally be synthesized in Rust. So I went on a short-lived quest:

- https://internals.rust-lang.org/t/expose-llvms-or-disjoint-i...

- https://github.com/rust-lang/libs-team/issues/373

- https://github.com/rust-lang/rust/pull/124601

Which ultimately culminated in an opinion that should sound familiar - https://github.com/rust-lang/rust/pull/124601#issuecomment-2....

gcc supports function multiversioning:

https://gcc.gnu.org/onlinedocs/gcc/Function-Multiversioning....

This is useful but not equivalent. Using this type of tooling you still have to write the algorithm itself in N versions. Changing the algorithm then requires changing all N implementations. This contrasts with the Halide approach where the algorithm is written once, and then schedules can be modified without worrying that you are changing the algorithm itself.

Reply on news.ycombinator.com