415

Is there a faster way than x >= start && x <= end in C or C++ to test if an integer is between two integers?

UPDATE: My specific platform is iOS. This is part of a box blur function that restricts pixels to a circle in a given square.

UPDATE: After trying the accepted answer, I got an order of magnitude speedup on the one line of code over doing it the normal x >= start && x <= end way.

UPDATE: Here is the after and before code with assembler from XCode:

NEW WAY

// diff = (end - start) + 1
#define POINT_IN_RANGE_AND_INCREMENT(p, range) ((p++ - range.start) < range.diff)

Ltmp1313:
 ldr    r0, [sp, #176] @ 4-byte Reload
 ldr    r1, [sp, #164] @ 4-byte Reload
 ldr    r0, [r0]
 ldr    r1, [r1]
 sub.w  r0, r9, r0
 cmp    r0, r1
 blo    LBB44_30

OLD WAY

#define POINT_IN_RANGE_AND_INCREMENT(p, range) (p <= range.end && p++ >= range.start)

Ltmp1301:
 ldr    r1, [sp, #172] @ 4-byte Reload
 ldr    r1, [r1]
 cmp    r0, r1
 bls    LBB44_32
 mov    r6, r0
 b      LBB44_33
LBB44_32:
 ldr    r1, [sp, #188] @ 4-byte Reload
 adds   r6, r0, #1
Ltmp1302:
 ldr    r1, [r1]
 cmp    r0, r1
 bhs    LBB44_36

Pretty amazing how reducing or eliminating branching can provide such a dramatic speed up.

30
  • 30
    Why are you concerned that this isn't fast enough for you?
    – Matt Ball
    Jun 13, 2013 at 19:22
  • 101
    Who cares why, its an interesting question. Its just a challenge for the sake of a challenge. Jun 13, 2013 at 19:23
  • 47
    @SLaks So we should just ignore all such questions blindly and just say "let the optimizer do it?" Jun 13, 2013 at 19:27
  • 91
    it doesn't matter why the question is being asked. It's a valid question, even if the answer is no
    – tay10r
    Jun 13, 2013 at 19:28
  • 43
    This is a bottleneck in a function in one of my apps
    – jjxtra
    Jun 13, 2013 at 19:32

7 Answers 7

565

There's an old trick to do this with only one comparison/branch. Whether it'll really improve speed may be open to question, and even if it does, it's probably too little to notice or care about, but when you're only starting with two comparisons, the chances of a huge improvement are pretty remote. The code looks like:

// use a < for an inclusive lower bound and exclusive upper bound
// use <= for an inclusive lower bound and inclusive upper bound
// alternatively, if the upper bound is inclusive and you can pre-calculate
//  upper-lower, simply add + 1 to upper-lower and use the < operator.
    if ((unsigned)(number-lower) <= (upper-lower))
        in_range(number);

With a typical, modern computer (i.e., anything using twos complement), the conversion to unsigned is really a nop -- just a change in how the same bits are viewed.

Note that in a typical case, you can pre-compute upper-lower outside a (presumed) loop, so that doesn't normally contribute any significant time. Along with reducing the number of branch instructions, this also (generally) improves branch prediction. In this case, the same branch is taken whether the number is below the bottom end or above the top end of the range.

As to how this works, the basic idea is pretty simple: a negative number, when viewed as an unsigned number, will be larger than anything that started out as a positive number.

In practice this method translates number and the interval to the point of origin and checks if number is in the interval [0, D], where D = upper - lower. If number below lower bound: negative, and if above upper bound: larger than D.

32
  • 3
    @OliCharlesworth: Yes, but he's said both are greater than 0, so it can't overflow (i.e, upper-lower < upper). Jun 13, 2013 at 19:38
  • 9
    @TomásBadan: They'll both be one cycle on any reasonable machine. What's expensive is the branch. Jun 13, 2013 at 19:39
  • 6
    @AK4749, jxh: As cool as this nugget is, I'm hesitant to upvote, because there's unfortunately nothing to suggest this is any faster in practice (until someone does a comparison of resulting assembler and profiling info). For all we know, the OP's compiler may render the OP's code with a single branch opcode... Jun 13, 2013 at 19:50
  • 163
    WOW!!! This resulted in an order of magnitude improvement in my app for this specific line of code. By precomputing upper-lower my profiling went from 25% time of this function to less than 2%! Bottleneck is now addition and subtraction operations, but I think it might be good enough now :)
    – jjxtra
    Jun 13, 2013 at 19:54
  • 32
    Ah, now the @PsychoDad has updated the question, it's clear why this is faster. The real code has a side-effect in the comparison, which is why the compiler couldn't optimize the short-circuit away. Jun 14, 2013 at 17:57
23

It's rare to be able to do significant optimizations to code on such a small scale. Big performance gains come from observing and modifying the code from a higher level. You may be able to eliminate the need for the range test altogether, or only do O(n) of them instead of O(n^2). You may be able to re-order the tests so that one side of the inequality is always implied. Even if the algorithm is ideal, gains are more likely to come when you see how this code does the range test 10 million times and you find a way to batch them up and use SSE to do many tests in parallel.

1
  • 20
    Despite the downvotes I stand by my answer: The generated assembly (see the pastebin link in a comment to the accepted answer) is pretty terrible for something in the inner loop of a pixel processing function. The accepted answer is a neat trick but its dramatic effect is far beyond what is reasonable to expect for eliminating a fraction of a branch per iteration. Some secondary effect is dominating, and I still expect that an attempt to optimize the whole process over this one test would leave the gains of clever range comparison in the dust. Jun 14, 2013 at 7:58
17

It depends on how many times you want to perform the test over the same data.

If you are performing the test a single time, there probably isn't a meaningful way to speed up the algorithm.

If you are doing this for a very finite set of values, then you could create a lookup table. Performing the indexing might be more expensive, but if you can fit the entire table in cache, then you can remove all branching from the code, which should speed things up.

For your data the lookup table would be 128^3 = 2,097,152. If you can control one of the three variables so you consider all instances where start = N at one time, then the size of the working set drops down to 128^2 = 16432 bytes, which should fit well in most modern caches.

You would still have to benchmark the actual code to see if a branchless lookup table is sufficiently faster than the obvious comparisons.

3
  • So you would store some sort of lookup given a value, start and end and it would contain a BOOL telling you if it was in between?
    – jjxtra
    Jun 13, 2013 at 19:33
  • Correct. It would be a 3D lookup table: bool between[start][end][x]. If you know what your access pattern is going to look like (for example x is monotonically increasing) you can design the table to preserve locality even if the entire table doesn't fit in memory. Jun 13, 2013 at 19:36
  • I'll see if I can get around to trying this method and seeing how it goes. I'm planning on doing it with a bit vector per line where the bit will be set if the point is in the circle. Think that will be faster than a byte or int32 vs the bit masking?
    – jjxtra
    Jun 19, 2013 at 18:50
8

For any variable range checking:

if (x >= minx && x <= maxx) ...

It is faster to use bit operation:

if ( ((x - minx) | (maxx - x)) >= 0) ...

This will reduce two branches into one.

If you care about type safe:

if ((int32_t)(((uint32_t)x - (uint32_t)minx) | ((uint32_t)maxx - (uint32_t)x)) > = 0) ...

You can combine more variable range checking together:

if (( (x - minx) | (maxx - x) | (y - miny) | (maxy - y) ) >= 0) ...

This will reduce 4 branches into 1.

It is 3.4 times faster than the old one in gcc:

enter image description here

1
  • Is the reason this works because a bit-wise negative and positive will always produce a negative? I ask because it's a bit out of my weight class, but still wanna understand it.
    – netsplit
    Feb 12 at 17:46
4

This answer is to report on a testing done with the accepted answer. I performed a closed range test on a large vector of sorted random integer and to my surprise the basic method of ( low <= num && num <= high) is in fact faster than the accepted answer above! Test was done on HP Pavilion g6 (AMD A6-3400APU with 6GB ram. Here's the core code used for testing:

int num = rand();  // num to compare in consecutive ranges.
chrono::time_point<chrono::system_clock> start, end;
auto start = chrono::system_clock::now();

int inBetween1{ 0 };
for (int i = 1; i < MaxNum; ++i)
{
    if (randVec[i - 1] <= num && num <= randVec[i])
        ++inBetween1;
}
auto end = chrono::system_clock::now();
chrono::duration<double> elapsed_s1 = end - start;

compared with the following which is the accepted answer above:

int inBetween2{ 0 };
for (int i = 1; i < MaxNum; ++i)
{
    if (static_cast<unsigned>(num - randVec[i - 1]) <= (randVec[i] - randVec[i - 1]))
        ++inBetween2;
}

Pay attention that randVec is a sorted vector. For any size of MaxNum the first method beats the second one on my machine!

3
  • 1
    My data is not sorted and my tests are on iPhone arm CPU. Your results with different data and CPU may differ.
    – jjxtra
    Feb 3, 2017 at 14:24
  • sorted in my test was only to make sure upper limit is not smaller than lower limit.
    – rezeli
    Feb 14, 2017 at 23:53
  • 2
    Sorted numbers mean branch prediction will be very reliable and get all branches right except for a few at the switchover points. The advantage of branchless code is that it will get rid of these kinds of misspredictions on unpredictable data. Feb 7, 2019 at 0:07
0

I can tell you exactly why this would matter. Imagine you're simulating an MMU. You are constantly having to make sure a given memory address exists with a given page set. Those little bits add up very quickly because you're always saying

  • Is this address valid?
  • What page is this address part of?
  • What rights does this page have?
-4

Is it not possible to just perform a bitwise operation on the integer?

Since it has to be between 0 and 128, if the 8th bit is set (2^7) it is 128 or more. The edge case will be a pain, though, since you want an inclusive comparison.

3
  • 3
    He wants to know if x <= end, where end <= 128. Not x <= 128.
    – Ben Voigt
    Jun 14, 2013 at 13:15
  • 1
    This statement "Since it has to be between 0 and 128, if the 8th bit is set (2^7) it is 128 or more" is wrong. Consider 256. Jun 14, 2013 at 14:13
  • 1
    Yeah, apparently I didn't think that through enough. Sorry.
    – icedwater
    Jun 15, 2013 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.