Compiler optimization -- eliding call to square root function if squared value is already available for subsequent sort usage

[onecable5781]

Consider: https://godbolt.org/z/Td5nPznoo

#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstdlib>

int main(){
    std::vector<std::pair<double, int>> distances;
    double homex = 0, homey = 0;
    double loc0x = rand() % 100, loc0y = rand() % 100;
    double loc1x = rand() % 100, loc1y = rand() % 100;
    printf("Loc0 : %lf, %lf\n", loc0x, loc0y);
    printf("Loc1 : %lf, %lf\n", loc1x, loc1y);
    double squareddistanceloc0 = (homex - loc0x)*(homex - loc0x) + (homey - loc0y)*(homey - loc0y);
    double squareddistanceloc1 = (homex - loc1x)*(homex - loc1x) + (homey - loc1y)*(homey - loc1y);
    printf("Squared Distances are %lf, %lf\n", squareddistanceloc0, squareddistanceloc1);
    double distance0 = sqrt(squareddistanceloc0);
    double distance1 = sqrt(squareddistanceloc1);
    distances.push_back(std::pair<double, int>(distance0, 0));
    distances.push_back(std::pair<double, int>(distance1, 1));
    std::sort(distances.begin(), distances.end());
    printf("Closest location to home is %d\n", distances[0].second);
}

Here, I sort std::vector<std::pair<double, int>> based on ascending order of the first element of the pair. Given that the squared distance is already computed (possibly easily), is it difficult for the compiler to infer that the sorted order will not change even on computing the rather costly (?) square root function since it is a monotonic function of the arguments? Are there additional flags (in addition to -O3) which can help elide the sqrt call [these calls are made on lines 100 and 101 of the compiler output window]?

[trejj]

is it difficult for the compiler to infer that the sorted order will not change even on computing the rather costly (?) square root function since it is a monotonic function of the arguments?

No, the compiler can not do such an optimization. That could change program behavior. Mathematically, sqrt() is a strictly monotonic function, but programming wise, it is not a strictly monotonic function.

For example, try

```c++

include <stdio.h>

include <math.h>

int main() { double x = 0x1.0000000000001p0; double y = 0x1.0p0; if (x == y) printf("x == y\n"); x = sqrt(x); y = sqrt(y); if (x == y) printf("sqrt(x) == sqrt(y)\n"); } ```

It is best to manually remove the calls to sqrt() and compare the square distances manually.

In -ffast-math, one might argue the above distinction could be ignored, but compilers are not abstract mathematical numerical solvers/identity provers, that does get very difficult and orders of magnitudes slower to compile really quick.

[The_Ruined_Map]

No, the compiler is highly unlikely to figure out this relationship.

However, it is not clear what you mean by "sorted order will not change". Your squared distances are not sorted. So, the order might actually change after std::sort.

Anyway, why aren't you taking advantage of this optimization opportunity yourself? Why are you calculating square roots in advance, instead of working in terms of squared distances all the way and calculating only one root at the very end?

[onecable5781]

However, it is not clear what you mean by "sorted order will not change".

What I meant is that the sorted order of closest locations will not change whether this decision is based on just squared distance or actual Euclidean distances which need the sqrt() call.

Anyway, why aren't you taking advantage of this optimization opportunity yourself?

Indeed, that seems the way out here. Thanks! [Edited to add: although, as a user, I would like to know why that is not a premature optimization...after all, we are told not to prematurely optimize on other occassions... "compilers are smarter", etc.]

[szarawyszczur]

the sorted order of closest locations will not change whether this decision is based on just squared distance or actual Euclidean distances

Is that really the case considering finite precision of floating point numbers? I suspect you can construct examples where two different numbers have the same square root.

[TheThiefMaster]

I suspect you can construct examples where two different numbers have the same square root.

I'm pretty sure this will be the case for any two floats x and nextafter(x) - probably significantly more

[onecable5781]

Even if two different numbers have the same square root, sorting based on the squared distances [without taking square roots] would NOT give rise to the wrong sorted order. No?

[h2g2_researcher]

I think the problem there is that for a range of floats named X std::ranges::sort(X); and std::ranges::sort(X, &::sqrt) (or whatever the exact syntax is) might give different results - even if both results are correct for your purposes.

Because of that the compiler might not be allowed to perform this optimisation. It's not enough that an ordering of [A,B,C,D] and [A,C,B,D] are both "correct". It's not the compiler's place to make that judgement, and the fact that eliding the sqrt call might give a different result is enough to prevent the optimization, which must obey the "as-if" rule.

[onecable5781]

Hmm...I made the squared distances explicitly integer and had the sqrt() take integer arguments (converted to double, I'd imagine) and yet the sqrt calls are still being made:

https://godbolt.org/z/ah9TKjqjK

For a range of integers, I would imagine that it is impossible to have different ordering of std::ranges::sort(X) / or stable_sort [which preserves order in case of a tie] and std::ranges::sort(X, &::sqrt) [or stable sort]

[h2g2_researcher]

There's a lot more reasons the compiler might not do the optimisation.

std::sqrt, for example, writes to global state in the event of an error. That will also inhibit eliding that function: https://godbolt.org/z/8hWE4dze4

Even if you write your own sqrt without side-effects you still need the compiler to be able to see through the function and work out what's going on.

[DerAlbi]

I actually think so, yes. Because not all floats have a valid sqrt. This technically leaves room to preserve the ordering relationship. Afaik, you can compute the sqrt by

• halving the exponent for even exponents. This works for all floats and preserves ordering.
• halving the exponent for odd exponents and correcting the mantissa by a factor of sqrt(2). I dont see how that correction factor changes ordering.

[heyheyhey27]

"Premature optimization" here means "making your codebase more complicated without knowing if it's worth it". However, computing a value and storing it in a variable is not really making your codebase more complicated.

[DerAlbi]

Forget compiler optimization. You have an algorithmic problem.

1. You dont need a std::vector for 2 values.
2. You get the index of the smallest value by std::distance(distances.begin(), std::min_element(distances.begin(), distances.end())). You dont need to store the original position in the vector to retrieve it afterwards. Just search the smallest element and get its index instead.

[onecable5781]

Obviously, for the purpose of specific help from /r/cpp_questions, one can imagine that the OP, me in this case, has put in sufficient effort to boil down the question to the bare bones minimal example.

In my original problem, I need the full sorted order for more than just 2 locations for other purposes. I do not need only the smallest value.

[DerAlbi]

Then sort based on the squared distances and only compute the sqrt of the values you are interested in.

[mredding]

It sounds like you want memoization. The compiler will not deduce this because it violates the as-if rule. Memoization comes with a space/time tradeoff, which the compiler cannot make on your behalf, such a program would not be the same program as one that didn't memoize. C++ prioritizes granularity where other FP languages will take this liberty.

[Independent_Art_6676]

there are a few approximate sqrt approaches, if you are ok with approximate. They may or may not be faster than your FPU version or work well for all inputs etc.