c++ 5a0156e40feb 確定整數是否在具有已知值集的兩個整數(包含)之間的最快方法




eigen github (4)

在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

相當驚人的如何減少或消除分支可以提供如此戲劇性的加速。


這取決於您希望通過相同的數據執行測試的次數。

如果您一次執行測試,可能沒有一種有效的方法來加速算法。

如果你正在做一個非常有限的一組值,那麼你可以創建一個查找表。 執行索引可能會更加昂貴,但是如果您可以將整個表格放入緩存中,那麼您可以從代碼中刪除所有分支,這會加快速度。

對於您的數據,查找表將為128 ^ 3 = 2,097,152。 如果你可以控制三個變量中的一個,所以你考慮所有的實例,其中start = N ,那麼工作集的大小將下降到128^2 = 16432字節,這應該適用於大多數現代緩存。

您仍然必須對實際代碼進行基準測試,以查看無分支查找表是否比明顯比較快得多。


很少能夠進行重要的優化以在如此小規模上進行編碼。 性能提升的好處來自於觀察和修改更高級別的代碼。 你可以完全消除範圍測試的需要,或者只做O(n)而不是O(n ^ 2)。 您可能能夠重新排列測試,以便始終暗示不平等的一面。 即使算法是理想的,當你看到這段代碼如何測試1000萬次的範圍,並找到一種方法來批量並使用SSE並行地完成許多測試時,增益更有可能出現。


只有一個比較/分支可以做到這一點。 它是否真的能夠提高速度可能是值得商榷的,即使它確實存在,它可能太少也不足以注意到或關心,但是當你只開始兩次比較時,大幅改進的可能性相當小。 代碼如下所示:

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


這個答案是報告接受答案的測試。 我對排序的隨機整數的大型向量執行了一個封閉範圍測試,令我驚訝的是(low <= num && num <= high)的基本方法實際上比上面接受的答案更快! 測試是在惠普Pavilion g6(帶有6GB RAM的AMD A6-3400APU)上完成的,以下是用於測試的核心代碼:

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,第一種方法都會在我的機器上擊敗第二種方法!





math