确定整数是否在具有已知值集的两个整数(包括)之间的最快方法
jjx*_*tra 376 c c++ math performance
是否有比x >= start && x <= endC或C++ 更快的方法来测试整数是否在两个整数之间？
更新:我的特定平台是iOS.这是盒子模糊功能的一部分,它将像素限制为给定方块中的圆圈.
更新:在尝试接受的答案后,我在一行代码上以正常x >= start && x <= end方式执行了一个数量级的加速.
更新:这是来自XCode的汇编程序的after和before代码:
新方法
// 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
老路
#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
非常惊人的是如何减少或消除分支可以提供如此惊人的速度.
Jer*_*fin 517
只用一个比较/分支就可以做到这一点.它是否能真正提高速度可能会受到质疑,即使它确实如此,它可能太少注意或不关心,但当你只是开始两次比较时,巨大改进的可能性非常小.代码如下:
// 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);
对于典型的现代计算机(即使用二进制补码的任何东西),转换为无符号实际上是一个不必要的 - 只是改变了相同位的查看方式.
请注意,在典型情况下,您可以upper-lower在(假定的)循环之外预先计算,因此通常不会贡献任何重要时间.随着减少分支指令的数量,这也(通常)改进了分支预测.在这种情况下,无论数字是低于底端还是高于范围的顶端,都会采用相同的分支.
至于它是如何工作的,基本思路非常简单:当被视为无符号数时,负数将大于以正数开头的任何数字.
在实践中,此方法将number间隔转换为原点,并检查是否number在区间中[0, D],在哪里D = upper - lower.如果number低于下限:负,如果高于上限:大于D.
- 哇!!!这导致我的应用程序针对此特定代码行进行了一个数量级的改进.通过预先计算上下 - 我的分析从此函数的25%时间变为小于2%!瓶颈现在是加法和减法操作,但我认为它现在可能已经足够了:) (149认同)
- 啊,现在@PsychoDad更新了这个问题,很明显为什么这个更快.**real**代码在比较中有副作用,这就是编译器无法优化短路的原因. (28认同)
- @TomásBadan:他们在任何合理的机器上都是一个循环.分支是多么昂贵. (8认同)
- @ AK4749,jxh:就像这个金块一样酷,我对upvote犹豫不决,因为遗憾的是没有任何迹象表明这在实践中更快(直到有人对得到的汇编程序和分析信息进行比较).据我们所知,OP的编译器可以使用单个分支操作码呈现OP的代码...... (6认同)
- 由于短路,还会进行额外的分支吗？如果是这种情况,那么`lower <= x&x <= upper`(而不是`lower <= x && x <= upper`)会导致更好的性能吗？ (3认同)
- 我认为*这是未经优化的代码,但我可能错了,有人告诉我,如果这看起来有点:Ltmp1313:ldr r0,[sp,#176] @ 4-byte Reload ldr r1,[sp,#164] @ 4字节重载ldr r0,[r0] ldr r1,[r1] sub.w r0,r9,r0 cmp r0,r1 blo LBB44_30 (3认同)
- 汇编程序的[a pastebin](http://pastebin.com/JG4mNVyR),希望更具可读性. (3认同)
- @OliCharlesworth:是的,但是他说两者都大于0,所以它不能溢出(即上下<上). (2认同)
- @JerryCoffin:啊,我没注意到! (2认同)
- @OliCharlesworth,即使测试显示它在大多数处理器和编译器上没有差别甚至更糟,如果有一个更好的话,那么它是一个值得回答的问题. (2认同)
- @PsychoDad:为了满足我们中间的好奇心,您是否介意在每种情况下发布编译器生成的汇编程序？ (2认同)
- 我认为这是较慢的版本: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字节重新加载r6,r0,#1 Ltmp1302:ldr r1,[r1] cmp r0,r1 bhs LBB44_36 (2认同)
- @MarkusMayr用gcc资源管理器检查,使用`&&`并使用`&`产生完全相同的代码,即短路(`&&`)方法. (2认同)
- @PatrickSanan：有点晚了，我知道，但我认为这个特别的技巧在 ["Hacker's Delight" by Henry S. Warren](https://www.amazon.co.uk/Hackers-Delight-Henry) 中有详细介绍-S-Warren/dp/0321842685）（以及许多其他很酷的低级黑客）。 (2认同)
Ben*_*son 18
能够对如此小规模的代码进行重要优化是很少见的.从更高级别观察和修改代码可以获得巨大的性能提升.您可以完全消除对范围测试的需要,或者仅执行O(n)而不是O(n ^ 2).您可以重新排序测试,以便始终隐含不平等的一面.即使算法是理想的,当您看到此代码如何进行1000万次范围测试并且您找到一种方法来批量处理并使用SSE并行执行多个测试时,更有可能获得增益.
- 尽管存在这些问题,但我仍然坚持我的回答:生成的程序集(请参阅对已接受答案的注释中的pastebin链接)对于像素处理函数的内部循环中的某些内容来说非常糟糕.接受的答案是一个巧妙的技巧,但它的戏剧性效果远远超出了每次迭代消除一小部分分支的合理预期效果.一些次要影响占主导地位,我仍然期望在这一次测试中优化整个过程的尝试将使得巧妙的范围比较的收益在尘埃中. (16认同)
And*_*ock 17
这取决于您希望对同一数据执行测试的次数.
如果您一次执行测试,可能没有一种有意义的方法来加速算法.
如果您为一组非常有限的值执行此操作,则可以创建查找表.执行索引可能会更昂贵,但如果您可以将整个表放在缓存中,那么您可以从代码中删除所有分支,这样可以加快速度.
对于您的数据,查找表将是128 ^ 3 = 2,097,152.如果您可以控制三个变量中的一个,那么您可以同时考虑所有实例start = N,那么工作集的大小将下降到128^2 = 16432字节,这应该适合大多数现代缓存.
您仍然需要对实际代码进行基准测试,以查看无分支查找表是否比明显的比较快得多.
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.
比 gcc 中的旧版本快3.4 倍：
