确定一个整数是否在两个整数之间(包括)与已知值集之间的最快方法

Question

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

更新:我的具体平台是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

相当令人惊讶的是，减少或消除分支可以提供如此戏剧性的速度。

Answer 1

只有一个比较/分支就能做到这一点，这是一个老把戏。它是否真的能提高速度可能是个值得怀疑的问题，即使它确实提高了速度，它也可能很少被注意或关心，但是当你仅仅从两个比较开始的时候，一个巨大的改进的机会是非常遥远的。代码看起来像：

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

对于一台典型的现代计算机(也就是任何使用两种互补方式的计算机)，向无符号的转换实际上是一个nop --只是改变了对相同位元的看法。

请注意，在典型情况下，您可以在(推定)循环之外预先计算upper-lower，因此通常不会贡献任何重要时间。随着减少分支指令的数量，这也(通常)改善分支预测。在这种情况下，无论数字在范围的底部或顶部以下，都采用相同的分支。

至于这是如何工作的，基本的想法是很简单的:一个负数，当被看作是一个无符号的数字时，将比任何从正数开始的数字都要大。

在实践中，此方法将number和区间转换为起始点，并检查number是否位于区间[0, D]中，其中D = upper - lower。如果number低于下限:否定，如果高于上限:大于D。

Answer 2

很少能够在如此小的范围内对代码进行重大的优化。从更高的层次上观察和修改代码可以获得很大的性能提升。您可以完全消除对范围测试的需求，或者只执行O(n)而不是O(n^2)。您可以重新排序测试，以便始终隐含不平等的一面。即使算法是理想的，当您看到这段代码如何进行1000万次的范围测试，并找到一种方法对它们进行批处理并使用SSE并行地进行许多测试时，就更有可能获得增益。

Answer 3

这取决于您要对同一数据执行多少次测试。

如果您只执行了一次测试，那么可能没有任何有意义的方法来加快算法的速度。

如果您是为一组非常有限的值执行此操作，则可以创建一个查找表。执行索引可能会更昂贵，但如果可以将整个表放入缓存中，则可以从代码中删除所有分支，这将加快速度。

对于数据，查找表为128^3 = 2,097,152。如果您可以控制这三个变量中的一个，因此可以同时考虑所有start = N的实例，那么工作集的大小就会下降到128^2 = 16432字节，这应该适合大多数现代缓存。

您仍然需要对实际代码进行基准测试，以查看无分支查找表是否比明显的比较更快。