最快的方法确定一个整数是否处于已知一组值中的两个整数之间（包括边界）

14 浏览
0 Comments

最快的方法确定一个整数是否处于已知一组值中的两个整数之间（包括边界）

在C或C++中，有没有比x >= start && x <= end更快的方法来测试一个整数是否在两个整数之间？

更新：我的具体平台是iOS。这是一个将像素限制在给定正方形内的圆形模糊函数的一部分。

更新：在尝试过接受的回答之后，我在一行代码上获得了一个数量级的加速，而不是用正常的x >= start && x <= end方法。

更新：这里是带有XCode汇编代码的更新前后代码：

新方法

// 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

减少或消除分支能够提供如此明显的加速，这真是很了不起。

admin 更改状态以发布 2023年5月24日
0

2 答案

0 Comments

在如此小的规模上对代码进行重要的优化并不常见。大幅性能提升来自于从更高的层次观察和修改代码。您可能能够完全消除对范围测试的需求，或者只执行O(n)而不是O(n^2)的测试。您可能能够重新排列测试，使不等式的一侧始终被暗示。即使算法是理想的，当您看到这段代码要进行1000万次范围测试时，也更有可能获得收益，并找到一种批量测试它们并使用SSE并行执行许多测试的方法。

0
0 Comments

有一个老的技巧可以只用一次比较/分支来完成。这是否真的能提高速度可能还有待商榷，即使它能够做到，它对于个人使用者来说也可能太微小，无需关心。但是当你只从两个比较开始时，巨大的改进的机会是相当渺茫的。代码如下：

// 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);

。\n使用典型的现代计算机（也就是使用二补数的任何计算机），无符号转换实际上是个“无操作”--仅仅是对同样的位进行不同的解释。\n要注意，在典型情况下，您可以在循环之外预先计算upper-lower，所以正常情况下不会对时间产生任何显著的贡献。除了减少分支指令数量外，这也（通常地）改善了分支预测性能。在这种情况下，当数字低于范围的下限时或高于范围的上限时，相同的分支被采取。\n至于它是如何工作的，基本思想非常简单：负数在被看作无符号数时会比任何开始作为正数的数都大。\n实际上，这种方法将number和范围转换为原点，并检查number是否在范围[0，D]内，其中D=upper-lower。如果number低于下限：则是负数；如果高于上限：则大于D。

0