Comment by zelphirkalt

14 hours ago

I am rather thinking, if one is so much faster, and they are truly equal, why is the compiler too stupid to convert one into the other?

4 comments

zelphirkalt

Reply
br121  12 hours ago

It doesn't convert bogosort into heapsort either, despite the second being much faster than the first. I'm guessing that it's not that easy going from one to the other because the only thing they have in common is the output (and only after you have checked the last value), so if the transformation is not hard-coded into the compiler, the odds of it randomly discovering the optimization is close to zero

  • zelphirkalt  12 hours ago

    Yeah, I would expect such transformations to be implemented as optimizations. Just like maybe (the admitedly simpler):

        (+ ((lambda () 1)) ((lambda () 1))) -> (+ 1 1)

    A syntactical transformation, where it is possible as an equivalent transformation.

    I may be overlooking special cases, but I thought the compiler is smart enough to infer that the array elements are integers and that `<` will result in a boolean, which is just `0` and `1` and will understand that having only the `if` without `else` branch is equivalent in this case. Guess I was wrong and the compiler is not sophisticated in this specific way.

flohofwoe  13 hours ago

The two code snippets do different things, apples and oranges... e.g. the array modification in the second example needs to move in front of the if for the two snippets to behave identically. I bet then the compiler output is the same with -O1 or higher.

PS: e.g. note how bla() (first code snippet) and blob() (fixed second code snippet) have identical output (both are turned into the same 'branchless' code via a conditional 'setl' instruction), but the blub() function (original second code snippet) differs because that function has different behaviour:

https://www.godbolt.org/z/h9Kfbn5bc

TL;DR: most 'branchless advice' that only tinkers with language features (like "x = a ? b : c" instead of an if) is useless because to the optimizer passes both are the same thing (a condition).

When there's a difference in the generated code then it's usually a bug and the before-after code are not actually equivalent (like in the code examples above).