3 ms·

> 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

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

ttd 1y ago
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.
purplesyringa 1y ago
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.
- almostgotcaught 1y ago
  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.
- Validark 1y ago
  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/8782a1924573641dc1f4a146afd530bf47838987/src/main.zig#L4533 https://github.com/Validark/Accelerated-Zig-Parser/blob/8782...
  - purplesyringa 1y ago
    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.
    - thrtythreeforty 1y ago
      > 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.

ttd 1y ago

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.

purplesyringa 1y ago

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.

almostgotcaught 1y ago
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.
Validark 1y ago
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/8782a1924573641dc1f4a146afd530bf47838987/src/main.zig#L4533 https://github.com/Validark/Accelerated-Zig-Parser/blob/8782...
- purplesyringa 1y ago
  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.
  - thrtythreeforty 1y ago
    > 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.