确定一个整数是否位于具有已知值集的两个整数（含）之间的最快方法

Question

在 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

减少或消除分支可以提供如此显着的加速，这真是太神奇了。

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

字节，这应该很适合大多数现代缓存。

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

Answer 4

对于任何变量范围检查：

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

使用位运算速度更快：

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

这会将两个分支减少为一个。

如果您关心类型安全：

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

您可以将更多变量范围检查组合在一起：

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

这会将 4 个分支减少为 1 个。

比 gcc 中的旧版本快 3.4 倍：

Answer 5

此答案是报告使用已接受的答案完成的测试。我对排序随机整数的大向量进行了封闭范围测试，令我惊讶的是 ( 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;

与上面接受的答案相比：

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

注意 randVec 是一个排序向量。对于任何大小的 MaxNum，第一种方法在我的机器上优于第二种方法！

Answer 6

我可以确切地告诉你为什么这很重要。 想象一下您正在模拟一个 MMU。 您必须不断确保给定的内存地址与给定的页面集一起存在。 这些小事加起来很快，因为你总是说

• 这个地址有效吗？
• 该地址属于哪个页面？
• 此页面有什么权利？

Answer 7

难道不能只对整数进行按位运算吗？

由于它必须在 0 到 128 之间，因此如果设置第 8 位 (2^7)，则它是 128 或更多。不过，边缘情况会很痛苦，因为你想要一个包容性的比较。