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

非常惊人的是减少或者消除分支能提供如此显著的速度。

时间:

只有一个比较/分支才能完成这个操作。 是否会真正提高速度可能是一个开放性的问题,即使是这样,这可能是通知或关心太少,但是当你只是从两个比较,巨大的改进的可能性相当遥远。 代码看起来像:


//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 --,只不过是如何看待相同位的变化。

注意,在一个典型的情况下,你可以 pre-compute upper-lower ( 假定) 外循环,所以通常不提供任何重要的时间。 除了减少分支指令的数量外,这也可以改进分支预测。 在这种情况下,无论数字是否低于或者高于范围的顶端,都会得到相同的分支。

至于如何工作,基本的想法非常简单: 当被视为无符号数字时,负数将大于任何以正数开头的数字。

这取决于你希望在同一数据上执行测试的次数。

如果你是一次执行测试,可能没有一个有意义的方法来加速算法。

如果你是为一组非常有限的值做的,那么你可以创建一个查找表。 执行索引可能比较昂贵,但是如果你可以在缓存中容纳整个表,那么你可以从代码中删除所有分支,这样就可以加快工作速度。

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

你仍然需要对实际代码进行基准测试,以确定一个未分组的查找表是否比明显的比较快。

...