3 ms·

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 com

by ttd 1y ago

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/ https://halide-lang.org/

secondcoming 1y ago
gcc supports function multiversioning: https://gcc.gnu.org/onlinedocs/gcc/Function-Multiversioning.html https://gcc.gnu.org/onlinedocs/gcc/Function-Multiversioning....
- ttd 1y ago
  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.
almostgotcaught 1y ago
> 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...

by ttd 1y ago

secondcoming 1y ago

gcc supports function multiversioning: https://gcc.gnu.org/onlinedocs/gcc/Function-Multiversioning.html https://gcc.gnu.org/onlinedocs/gcc/Function-Multiversioning....

ttd 1y ago
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.

almostgotcaught 1y ago

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