patterncppCritical
Fastest way to determine if an integer is between two integers (inclusive) with known sets of values
Viewed 0 times
twoknownwithinclusivedeterminebetweenintegerintegerswayvalues
Problem
Is there a faster way than
UPDATE: Here is the after and before code with assembler from XCode:
NEW WAY
OLD WAY
Pretty amazing how reducing or eliminating branching can provide such a dramatic speed up.
x >= start && 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_30OLD WAY
#define POINT_IN_RANGE_AND_INCREMENT(p, range) (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_36Pretty amazing how reducing or eliminating branching can provide such a dramatic speed up.
Solution
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
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`.Context
Stack Overflow Q#17095324, score: 571
Revisions (0)
No revisions yet.