0

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
Graham Palmer
  • 53
  • 1
  • 6
  • 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 Jan 09 '19 at 20:57
  • Your tests are VERY lopsided; result is almost always false. – Scott Hunter Jan 09 '19 at 20:57
  • 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 Jan 09 '19 at 20:59
  • How are you compiling? I get `inRangeComp` as the fastest. Also, you can make the min max version with a single branch like [this](http://coliru.stacked-crooked.com/a/d31d2c98cf3798ac) – NathanOliver Jan 09 '19 at 21:00
  • [quick-bench results](http://quick-bench.com/0I7p8PIv-uqZ2bXq2sQwCh6FoNA) – Jarod42 Jan 09 '19 at 21:46
  • @FrançoisAndrieux Indeed I believe that is what was happening. I've updated the code to be a little more robust in terms of preventing optimization. Thanks for the tip as well about inline - I'm vaguely aware of the fact but decided to beat the dead fish in this case. The comp version appears marginally faster now, with the results being 351, 239, 236 respectively. I'm using Visual C++ 2017 64bit in release mode. – Graham Palmer Jan 09 '19 at 22:02
  • @GrahamPalmer That takes care of the result being ignored, but you still have an issue where since `a` is a compile time constant, the compiler could precalculate the results. That can be fixed by taking `a` as a user input. – François Andrieux Jan 09 '19 at 22:04
  • @FrançoisAndrieux I'm not following. How would that influence the difference in runtime between the three implementations? – Graham Palmer Jan 09 '19 at 22:08
  • @GrahamPalmer If the results are precalculated your functions don't have to be called at runtime. Edit : For example I'm pretty sure a conforming compiler could remove all of your benchmark, print 0 durations and just print the correct `res` result. – François Andrieux Jan 09 '19 at 22:09
  • Why are you using `p < v1 != p < v2` instead of `p >= v1 && p <= v2`? The performance is similar http://quick-bench.com/EPzOEo167ettFg-zZFqMn-lAHQw and for p == v1 or p == v2 it gives a different result from the other tests. – Bob__ Jan 09 '19 at 22:53
  • @Bob__ If p=3, v1 = 4, and v2 = 2, this would return false, even though 3 is clearly between 2 and 4. This distinction between my problem and the one I linked at the beginning is I don't know ahead of time which of v1 or v2 is larger - hence having to deal with std::max/min. – Graham Palmer Jan 09 '19 at 23:23
  • There's no reason to avoid min/max. Modern compilers compile them into a single very fast instruction, `minsd` / `maxsd`. – Soonts Jan 10 '19 at 02:22

1 Answers1

2

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.

Bob__
  • 12,361
  • 3
  • 28
  • 42
  • Nit, may be more readable as `? v1 <= p && p < = v2 : v2 <= p && p <= v1;` (up to you, some prefer Yoda conditionals) – David C. Rankin Jan 10 '19 at 01:27
  • It all does the same thing, but when you get old, it's just easier to read `p` in the middle of the other two values that way. Good eye on potential overflow issues. – David C. Rankin Jan 10 '19 at 01:34