Modulo優化

Question

我有一個C程序，它在大型陣列上做了一些廣泛的交換操作。它在緊密的循環中有模操作。實際上，範圍[-N | N [有N的整數範圍是2的冪，它應該被換成[0，N [。

實施例與N = 4：-4 => 0，-3 => 1，-2 => 2，-1 => 3，0 => 0，...，3 => 3

起初，我嘗試了下面的版本1，但感到驚訝的是即使它有一個條件表達式，版本2實際上也顯着更快。

你能解釋爲什麼版本2比版本1更快爲這種特殊情況？

版本1：

#define N (1<<(3*5)) 

inline int modBitAnd(int x) 
{ 
    return (x & (N-1)); 
} 

運行時間：17.1秒（對於整個程序）

版本2：

inline int modNeg1(int x) 
{ 
    return (x < 0 ? x + N : x); 
} 

運行時間：14.6秒（對於整個程序）

程序在GCC 4.8.2上編譯。與-std = c99 -O3。

編輯：

這裏是我在程序的主循環：

int en(uint16_t* p, uint16_t i, uint16_t v) 
{ 
    uint16_t n1 = p[modNeg1((int)i - 1)]; 
    uint16_t n2 = p[modBitAnd((int)i + 1)]; 
    uint16_t n3 = p[modNeg1((int)i - C_WIDTH)]; 
    uint16_t n4 = p[modBitAnd((int)i + C_WIDTH)]; 
    return d(n1,v) + d(n2,v) + d(n3,v) + d(n4,v); 
} 

void arrange(uint16_t* p) 
{ 
    for(size_t i=0; i<10000000; i++) { 
     uint16_t ia = random(); // random integer [0|2^15[ 
     uint16_t va = p[ia]; 
     uint16_t ib = random(); // random integer [0|2^15[ 
     uint16_t vb = p[ib]; 
     if(en(p,ia,vb) + en(p,ib,va) < en(p,ia,va) + en(p,ib,vb)) { 
      p[ia] = vb; 
      p[ib] = va; 
     } 
    } 
} 

int d(uint16_t a, uint16_t b)是距離函數例如abs((int)a-(int)b)。

這是p如何初始化：

uint16_t* p = malloc(sizeof(uint16_t)*N); 
for(unsigned i=0; i<N; i++) *p++ = i; 

首先，我用modBitAnd無處不在，但發現該modNeg1是實際上可以更快的爲兩種情況下可以使用。

Answer 1

第一個take a few stackshots找出時間到了哪裏。你的mod函數將獲取樣本的一小部分，但你也有兩個調用random，加上相當數量的數組索引。此外，它看起來像你有四個電話en與一些相同的參數，所以也許你的模塊化導致重複調用mod函數。