Most efficient way to test multiple a <= b <=c in a condition

Question

I have multiple numbers (3 at least) each to test against a range obtained by a lower and an upper bound (I can be sure lower <= upper condition is always satisfied).

Now having lower[1...n], x[1...n] and upper[1...n] my aims here are I'd like to optimize for performance...

I know, after I had a look at this other Q&A here on StackOverflow, I could go with an

(unsigned)(x[n]-lower[n]) <= (upper[n]-lower[n]) form

over the "classical" lower[n] <= x[n] && x[n] <= upper[n]

I need to go with JavaScript in this occasion, and I know I can obtain the same "trick" with this language using:

the JavaScript >>> bitwise operator
or by using JavaScript Uint32Array object

I'm quite sure the second method would have worst impact on performance so, excluding it on departure, and considering only the first one, I could do:

// Example 1
function everything_is_in_range(lower, x, upper) {
    return ( ((x[0]-lower[0]) >>> 0) <= (upper[0]-lower[0]) && 
             ((x[1]-lower[1]) >>> 0) <= (upper[1]-lower[1]) &&
             ...
             ((x[n-1]-lower[n-1]) >>> 0) <= (upper[n-1]-lower[n-1]) );
}

Or I could do:

// Example 2
function everything_is_in_range(lower, x, upper) {
    if ( ((x[0]-lower[0]) >>> 0) > (upper[0]-lower[0]) ) return false; 
    if ( ((x[1]-lower[1]) >>> 0) > (upper[1]-lower[1]) ) return false; 
    ...
    return ( ((x[n-1]-lower[n-1]) >>> 0) <= (upper[n-1]-lower[n-1]) );
}

My questions are:

will the unsigned shifting be not convenient on general performance so that I should stay with the "classical" lower[n] <= x[n] && x[n] <= upper[n] form for the purpose?
in case the answer to my first answer is no, which way would be the most efficient one? But more important: do you know an even better one you could suggest maybe?

P.S. I know I could do with a for loop in the following way:

// Loop example
function everything_is_in_range(lower, x, upper) {
    for (i=0; i<n; ++i) if ( ((x[i]-lower[i]) >>> 0) > (upper[i]-lower[i]) ) return false; 
    return true;
}

BUT

It would be only convenient for letting me write less code but it's something very analogue to the second code approach in the end, no?
I don't want to use this form because all values may happen to be passed as single separated parameters (that is my real case, in which I'm dealing with 3 or 4 numbers + bound ranges set of variables and I can't change this) and not as arrays of values (like in this example).

Javascript doesn't have a concept of unsigned numbers, so you're not going to be able to take advantage of that particular trick — Hamms, Nov 10 '17 at 00:12
`function withinRange(num, begin, end){ if(num >= begin && num <= end){ return true; } else{ return false; } }` — StackSlave, Nov 10 '17 at 00:19
making it "unsigned" will most likely make it a tiny bit slower because of the extra conversion step https://stackoverflow.com/questions/14890994/javascript-c-style-type-cast-from-signed-to-unsigned, but my guess is that the function call itself will have bigger overhead than the comparisons — Slai, Nov 10 '17 at 00:45
@PHPglue : I knew this "classical" way to do it (btw `return (num >= begin && num <= end)` would be better) but, anyway, I was asking if there's possible optimization on this and, also, I have multiple numbers to test in the same condition. — danicotra, Nov 10 '17 at 19:48
@Hamms : Yeah, I understand I can't apply the same identical C/C++ trick but I also knew it could be possible to use `Uint32Array` (but I'm afraid that would be overkill on performances) or a `>>> 0` trick... and I think it would be the only way to take in comparison to the "classical" way (I edited my question now) — danicotra, Nov 10 '17 at 19:50
@Slai : I just feared that and that's why I asked... Well, anyway, hold on, I'm gonna measure it... — danicotra, Nov 10 '17 at 19:53

score 0 · Answer 1 · answered Nov 10 '17 at 20:13

I made this:

<html>
    <head>
        <meta charset="utf-8"/>
    </head>
<body>
<script>

// Loop example
function everything_is_in_range(lower, x, upper) {
    for (i=0; i<3; ++i) if ( ((x[i]-lower[i]) >>> 0) > (upper[i]-lower[i]) ) return false; 
    return true;
}

// E.2
function everything_is_in_range_2(lower, x, upper) {
    if ( ((x[0]-lower[0]) >>> 0) > (upper[0]-lower[0]) ) return false; 
    if ( ((x[1]-lower[1]) >>> 0) > (upper[1]-lower[1]) ) return false; 
    return ( ((x[2]-lower[2]) >>> 0) <= (upper[2]-lower[2]) );
}

// E.1
function everything_is_in_range_1(lower, x, upper) {
    return ( ((x[0]-lower[0]) >>> 0) <= (upper[0]-lower[0]) && 
             ((x[1]-lower[1]) >>> 0) <= (upper[1]-lower[1]) &&
             ((x[2]-lower[2]) >>> 0) <= (upper[2]-lower[2]) );
}

// Loop C example
function everything_is_in_range_C(lower, x, upper) {
    for (i=0; i<3; ++i) if ( lower[i] > x[i] || x[i] > upper[i] ) return false; 
    return true;
}

// E.C2
function everything_is_in_range_C2(lower, x, upper) {
    if ( lower[0] > x[0] || x[0] > upper[0] ) return false; 
    if ( lower[1] > x[1] || x[1] > upper[1] ) return false; 
    return ( lower[2] <= x[2] && x[2] <= upper[2] );
}

// E.C1
function everything_is_in_range_C1(lower, x, upper) {
    return ( lower[0] <= x[0] && x[0] <= upper[0] && 
             lower[1] <= x[1] && x[1] <= upper[1] && 
             lower[2] <= x[2] && x[2] <= upper[2] );
}

let u = [50, 100, 150],
    x = [100, 100, 100],
    l = [25, 100, 125];

var t0, t1, m, m1, m2, mc, mc1, mc2, r;
m = m1 = m2 = mc = mc1 = mc2 = 0;
for (r=0; r < 100; ++r) {
//console.log("Round " + (r+1) + ":");

t0 = performance.now();
everything_is_in_range_1(l, x, u);
t1 = performance.now();
//console.log("Call 1 " + (t1 - t0) + " ms.");
m1 += (t1 - t0);

t0 = performance.now();
everything_is_in_range_2(l, x, u);
t1 = performance.now();
//console.log("Call 2 " + (t1 - t0) + " ms.");
m2 += (t1 - t0);

t0 = performance.now();
everything_is_in_range(l, x, u);
t1 = performance.now();
//console.log("Call loop " + (t1 - t0) + " ms.");
m += (t1 - t0);

t0 = performance.now();
everything_is_in_range_C1(l, x, u);
t1 = performance.now();
//console.log("Call C1 " + (t1 - t0) + " ms.");
mc1 += (t1 - t0);

t0 = performance.now();
everything_is_in_range_C2(l, x, u);
t1 = performance.now();
//console.log("Call C2 " + (t1 - t0) + " ms.");
mc2 += (t1 - t0);

t0 = performance.now();
everything_is_in_range_C(l, x, u);
t1 = performance.now();
//console.log("Call loop C " + (t1 - t0) + " ms.");
mc += (t1 - t0);
}

console.log("------------- AVERAGE RESULTS (after " + r + " rounds)-------------");
console.log("1: " + (m1 / r) + " ms.");
console.log("2: " + (m2 / r) + " ms.");
console.log("Loop: " + (m / r) + " ms.");
console.log("C1: " + (mc1 / r) + " ms.");
console.log("C2: " + (mc2 / r) + " ms.");
console.log("Loop C: " + (mc / r) + " ms.");

</script>
</body>
</html>

I put in it both the "tricky" and the "classic" form (including loops) and I get this:

------------- AVERAGE RESULTS (after 100 rounds)-------------
1: 0.0017500000000001137 ms.  
2: 0.0014500000000009549 ms. 
Loop: 0.002749999999998636 ms. 
C1: 0.0014500000000003865 ms. 
C2: 0.001150000000000091 ms.  
Loop C: 0.0019000000000011141 ms.

So... it seems the best way to go in JavaScript is the "classical" form and, in particular, this "verbose" way seems even better than the loop one:

function everything_is_in_range_C2(lower, x, upper) {
    if ( lower[0] > x[0] || x[0] > upper[0] ) return false; 
    if ( lower[1] > x[1] || x[1] > upper[1] ) return false; 
    return ( lower[2] <= x[2] && x[2] <= upper[2] );
}

Well, I think when having a lot of numbers to test and everything already in arrays the efforts of writing all the code instead of taking advantage of a loop it's not worth the slight gain on performances anyway...

Slai · Answer 2 · 2017-11-11T19:02:44.207

The main point of the optimization is not the unsigned part, but minimizing branch misprediction.

If by any chance you haven't seen the most up-voted question and answer on Stack Overflow yet:
Why is it faster to process a sorted array than an unsorted array?

function f1(l, x, u) { if ( l[0] > x[0] || x[0] > u[0] ) return false; 
                       if ( l[1] > x[1] || x[1] > u[1] ) return false; 
                       return ( l[2] <= x[2] && x[2] <= u[2] ); }

function f2(l, x, u) { return !!( ( x[0] - u[0] ^ x[0] - l[0] ) & 
                                  ( x[1] - u[1] ^ x[1] - l[1] ) &
                                  ( x[2] - u[2] ^ x[2] - l[2] ) ) }

let l = [1, 1, 1], x = [2, 2, 2], u = [3, 3, 3], t, b, p = performance, c = 12345678
t = p.now(); for (let i = c; i--;) b = f1(l, x, u); t = p.now() - t; console.log(1, t|0, b)
t = p.now(); for (let i = c; i--;) b = f2(l, x, u); t = p.now() - t; console.log(2, t|0, b)

l = [1, 2, 3], x = [2, 2, 2], u = [3, 3, 3]
t = p.now(); for (let i = c; i--;) b = f1(l, x, u); t = p.now() - t; console.log(1, t|0, b)
t = p.now(); for (let i = c; i--;) b = f2(l, x, u); t = p.now() - t; console.log(2, t|0, b)

l = [3, 3, 3], x = [2, 2, 2], u = [3, 3, 3]
t = p.now(); for (let i = c; i--;) b = f1(l, x, u); t = p.now() - t; console.log(1, t|0, b)
t = p.now(); for (let i = c; i--;) b = f2(l, x, u); t = p.now() - t; console.log(2, t|0, b)

As you can probably notice, the branchless version without comparisons seems a bit faster on average with pretty constant time, but slower when the comparison version can exit early.

Note that the branchless version is probably incorrect (definitely incorrect with negative numbers), because it was mostly the result of trial and error and I didn't do extensive testing.

Both version can be optimized with SIMD instructions, but they are supported only in few browsers.

Most efficient way to test multiple a <= b <=c in a condition

2 Answers2