Most efficient way to determine if value between two other values, inclusive

Question

Similar to Fastest way to determine if an integer is between two integers (inclusive) with known sets of values, I wish to figure out if some value (most likely a double-precision floating point number) is between two other values (of the same type). The caveat is that I don't know already which value is larger than the other and I'm trying to determine if I should/how I should avoid using std::max/min. Here is some code I've tried to test this with already:

inline bool inRangeMult(double p, double v1, double v2) {
    return (p - v1) * (p - v2) <= 0;
}

inline bool inRangeMinMax(double p, double v1, double v2) {
    return p <= std::max(v1, v2) && p >= std::min(v1, v2);
}

inline bool inRangeComp(double p, double v1, double v2) {
    return p < v1 != p < v2;
}

int main()
{
    double a = 1e4;

    std::clock_t start;
    double duration;
    bool res = false;

    start = std::clock();
    for (size_t i = 0; i < 2e4; ++i) {
        for (size_t j = 0; j < 2e4; ++j) {
            res = inRangeMult(a, i, j) ? res : !res;
        }
    }
    duration = std::clock() - start;
    std::cout << "InRangeMult: " << duration << std::endl;

    start = std::clock();
    for (size_t i = 0; i < 2e4; ++i) {
        for (size_t j = 0; j < 2e4; ++j) {
            res = inRangeMinMax(a, i, j) ? res : !res;
        }
    }
    duration = std::clock() - start;
    std::cout << "InRangeMinMax: " << duration << std::endl;

    start = std::clock();
    for (size_t i = 0; i < 2e4; ++i) {
        for (size_t j = 0; j < 2e4; ++j) {
            res = inRangeComp(a, i, j) ? res : !res;
        }
    }
    duration = std::clock() - start;
    std::cout << "InRangeComp: " << duration << std::endl;

    std::cout << "Tricking the compiler by printing inane res: " << res << std::endl;
}

On most runs I'm finding that using std::min/max is still fastest, (latest run prints 346, 310, and 324 respectively), but I'm not 100% confident this is the best test setup, or that I've exhausted all of the reasonable implementations.

I'd appreciate anyone's input with a better profiling setup and/or better implementation.

EDIT: Updated code to make it less prone to compiler optimization.

2nd EDIT: Tweaked value of a and number of iterations. Results for one run are:

inRangeMult: 1337
inRangeMinMaz: 1127
inRangeComp: 729

Know that if you are using inline to inline those functions for a performance gain that the inline keyword doesn't carry much weight (if any) in determining when functions are inlined anymore. — François Andrieux
Your tests are VERY lopsided; result is almost always false. — Scott Hunter
It seems likely that since a is essentially a constexpr and you never use the result of your functions your function calls can both be precalculated at compile time and completely optimized out. I wouldn't count on the accuracy of this benchmark. — François Andrieux
How are you compiling? I get inRangeComp as the fastest. Also, you can make the min max version with a single branch like this — NathanOliver

Bob__ Bob__ · Accepted Answer · 2019-01-10T01:11:42

The first test:

(p - v1) * (p - v2) <= 0

May result in overflow or underflow, due to the arithmetic operations.

The last one:

p < v1 != p < v2

Doesn't provide the same results as the others, which are inclusive in respect of the boundaries v1 and v2. It's an admittedly small difference, considering the range and precision of the type double, but it may be significant.

Another option is to explicitly expand the logic of the second function:

p <= std::max(v1, v2) && p >= std::min(v1, v2)     // v1 and v2 are compared twice

Into something like this:

bool inRangeComp(double p, double v1, double v2) {
    return v1 <= v2                                // <- v1 and v2 are compared only once
        ? v1 <= p && p <= v2 
        : v2 <= p && p <= v1;
}

At least one compiler (gcc 8.2), HERE (thanks to jarod42 for the linked snippet), seems to prefer this version over the alternatives.

Most efficient way to determine if value between two other values, inclusive

1 Answers