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

在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

令人惊讶的是，减少或消除分支能够提供如此惊人的速度。

85202 次浏览
小开

这取决于您希望对相同的数据执行多少次测试。

如果您只执行一次测试，可能没有有效的方法来加快算法的速度。

如果您正在为一个非常有限的值集执行此操作，那么您可以创建一个查找表。执行索引的代价可能更大，但是如果您可以将整个表放入缓存中，那么您就可以从代码中删除所有分支，这应该会加快速度。

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

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

小开
最佳答案

只有一个比较/分支时，有一个老技巧可以做到这一点。它是否真的能提高速度还有待商榷，即使它真的能提高速度，可能也太小了，不值得注意或关心，但当你只从两次比较开始时，巨大提高的机会是相当渺茫的。代码如下:

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

对于典型的现代计算机(即任何使用双补码的计算机)，转换到unsigned实际上是一个nop——只是改变了相同位的看待方式。

注意，在典型情况下，你可以在(假定的)循环之外预先计算upper-lower，所以这通常不会占用任何重要的时间。除了减少分支指令的数量，这也(通常)改善了分支预测。在这种情况下，无论该数字低于范围的底端还是高于范围的顶端，都采用相同的分支。

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

在实际操作中，此方法将number和interval转换到原点，并检查number是否在interval [0, D]中，其中D = upper - lower. c是number。如果number低于下界:负，如果高于上界:大于D。

小开

能够在如此小的规模上对代码进行重大优化是非常罕见的。从更高的级别观察和修改代码可以获得较大的性能提升。您可以完全消除范围测试的需要，或者只做O(n)个，而不是O(n²)个。您可以重新排序测试，以便始终隐含不平等的一方。即使算法是理想的，当您看到这段代码如何进行1000万次范围测试，并找到一种方法将它们批处理并使用SSE并行执行许多测试时，更有可能获得收益。

小开

难道不可能只对整数执行位操作吗?

因为它必须在0到128之间，如果第8位被设置(2^7)，它是128或更多。但是，边界情况会很麻烦，因为您需要一个包含比较。

小开

这个答案是报告用接受的答案所做的测试。我在一个排序随机整数的大向量上进行了一个闭范围测试，令我惊讶的是(low <= num &&Num <= high)实际上比上面接受的答案要快!测试在惠普Pavilion g6 (AMD A6-3400APU, 6GB内存)上完成。下面是用于测试的核心代码:

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的任何大小，第一个方法在我的机器上胜过第二个方法!

小开

对于任何变量范围检查:

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个。

它是3.4倍快，而不是gcc中的旧版本:

enter image description here

小开

我可以告诉你为什么这很重要。假设你正在模拟一个MMU。您必须经常确保给定的页面集存在给定的内存地址。这些小细节累积起来很快因为你总是说

  • 这个地址有效吗?
  • 这个地址在哪一页?
  • 这个页面有什么权限?

提交答案