爲什麼這段代碼效率不高？

Question

我想提高下一個代碼，計算平均值：

void calculateMeanStDev8x8Aux(cv::Mat* patch, int sx, int sy, int& mean, float& stdev) 
{ 

    unsigned sum=0; 
    unsigned sqsum=0; 
    const unsigned char* aux=patch->data + sy*patch->step + sx; 
    for (int j=0; j< 8; j++) { 
     const unsigned char* p = (const unsigned char*)(j*patch->step + aux); //Apuntador al inicio de la matrix   

     for (int i=0; i<8; i++) { 
      unsigned f = *p++; 
      sum += f; 
      sqsum += f*f; 
     }   
    }  

    mean = sum >> 6; 
    int r = (sum*sum) >> 6; 
    stdev = sqrtf(sqsum - r); 

    if (stdev < .1) { 
     stdev=0; 
    } 
} 

我還改善了與NEON內在的下一個循環：

for (int i=0; i<8; i++) { 
      unsigned f = *p++; 
      sum += f; 
      sqsum += f*f; 
     } 

這是其他循環提高代碼：

 int32x4_t vsum= { 0 }; 
     int32x4_t vsum2= { 0 }; 

     int32x4_t vsumll = { 0 }; 
     int32x4_t vsumlh = { 0 }; 
     int32x4_t vsumll2 = { 0 }; 
     int32x4_t vsumlh2 = { 0 }; 

     uint8x8_t f= vld1_u8(p); // VLD1.8 {d0}, [r0] 

     //int 16 bytes /8 elementos 
     int16x8_t val = (int16x8_t)vmovl_u8(f); 

     //int 32 /4 elementos *2 
     int32x4_t vall = vmovl_s16(vget_low_s16(val)); 
     int32x4_t valh = vmovl_s16(vget_high_s16(val)); 

     // update 4 partial sum of products vectors 

     vsumll2 = vmlaq_s32(vsumll2, vall, vall); 
     vsumlh2 = vmlaq_s32(vsumlh2, valh, valh); 

     // sum 4 partial sum of product vectors 
     vsum = vaddq_s32(vall, valh); 
     vsum2 = vaddq_s32(vsumll2, vsumlh2); 

     // do scalar horizontal sum across final vector 

     sum += vgetq_lane_s32(vsum, 0); 
     sum += vgetq_lane_s32(vsum, 1); 
     sum += vgetq_lane_s32(vsum, 2); 
     sum += vgetq_lane_s32(vsum, 3); 

     sqsum += vgetq_lane_s32(vsum2, 0); 
     sqsum += vgetq_lane_s32(vsum2, 1); 
     sqsum += vgetq_lane_s32(vsum2, 2); 
     sqsum += vgetq_lane_s32(vsum2, 3); 

但是它差不多是30毫秒慢。有誰知道爲什麼？

所有的代碼工作正常。

Answer 1

添加到Lundin。是的，像ARM這樣的指令集可以讓你有一個基於寄存器的索引，或者有一些直接索引到達，你可能會受益於鼓勵編譯器使用索引。同樣，儘管ARM例如可以在加載指令中增加它的指針寄存器，但是在一個指令中基本上是* p ++。

它總是使用p [i]或p [i ++] vs * p或* p ++來折騰，有些指令集更明顯地採用哪條路徑。

同樣，你的索引。如果你沒有使用它而不是向上計數，則可以在每個循環中保存一條指令，也許更多。如果您在倒數雖然你可能會節省每循環的指令

inc reg 
cmp reg,#7 
bne loop_top 

：

dec reg 
bne loop_top 

甚至一個處理器，我知道的

decrement_and_jump_if_not_zero loop_top 

編譯器通常是一些可以這樣做知道這一點，你不必鼓勵他們。但是如果你使用內存讀取順序很重要的p [i]形式，那麼編譯器不能或至少不應該任意改變讀取順序。所以對於這種情況，你會希望代碼倒數。

所以我嘗試了所有的這些事情：

unsigned fun1 (const unsigned char *p, unsigned *x) 
{ 
    unsigned sum; 
    unsigned sqsum; 
    int i; 
    unsigned f; 


    sum = 0; 
    sqsum = 0; 
    for(i=0; i<8; i++) 
    { 
     f = *p++; 
     sum += f; 
     sqsum += f*f; 
    } 
    //to keep the compiler from optimizing 
    //stuff out 
    x[0]=sum; 
    return(sqsum); 
} 

unsigned fun2 (const unsigned char *p, unsigned *x ) 
{ 
    unsigned sum; 
    unsigned sqsum; 
    int i; 
    unsigned f; 


    sum = 0; 
    sqsum = 0; 
    for(i=8;i--;) 
    { 
     f = *p++; 
     sum += f; 
     sqsum += f*f; 
    } 
    //to keep the compiler from optimizing 
    //stuff out 
    x[0]=sum; 
    return(sqsum); 
} 

unsigned fun3 (const unsigned char *p, unsigned *x) 
{ 
    unsigned sum; 
    unsigned sqsum; 
    int i; 

    sum = 0; 
    sqsum = 0; 
    for(i=0; i<8; i++) 
    { 
     sum += (unsigned)p[i]; 
     sqsum += ((unsigned)p[i])*((unsigned)p[i]); 
    } 
    //to keep the compiler from optimizing 
    //stuff out 
    x[0]=sum; 
    return(sqsum); 
} 

unsigned fun4 (const unsigned char *p, unsigned *x) 
{ 
    unsigned sum; 
    unsigned sqsum; 
    int i; 

    sum = 0; 
    sqsum = 0; 
    for(i=8; i;i--) 
    { 
     sum += (unsigned)p[i-1]; 
     sqsum += ((unsigned)p[i-1])*((unsigned)p[i-1]); 
    } 
    //to keep the compiler from optimizing 
    //stuff out 
    x[0]=sum; 
    return(sqsum); 
} 

與GCC和LLVM（鐺）。當然，因爲它是一個常量，所以展開循環。海灣合作委員會，每個實驗產生相同的代碼，在情況下微妙的寄存器組合改變。我會爭論一個錯誤，因爲其中至少有一個讀取不是按代碼描述的順序。

海灣合作委員會的所有四個解決方案是這樣的，有一些讀取重新排序，注意讀取順序從源代碼。如果這是針對依賴於代碼所描述的順序的硬件/邏輯，那麼您將遇到大問題。

00000000 <fun1>: 
    0: e92d05f0 push {r4, r5, r6, r7, r8, sl} 
    4: e5d06001 ldrb r6, [r0, #1] 
    8: e00a0696 mul sl, r6, r6 
    c: e4d07001 ldrb r7, [r0], #1 
    10: e02aa797 mla sl, r7, r7, sl 
    14: e5d05001 ldrb r5, [r0, #1] 
    18: e02aa595 mla sl, r5, r5, sl 
    1c: e5d04002 ldrb r4, [r0, #2] 
    20: e02aa494 mla sl, r4, r4, sl 
    24: e5d0c003 ldrb ip, [r0, #3] 
    28: e02aac9c mla sl, ip, ip, sl 
    2c: e5d02004 ldrb r2, [r0, #4] 
    30: e02aa292 mla sl, r2, r2, sl 
    34: e5d03005 ldrb r3, [r0, #5] 
    38: e02aa393 mla sl, r3, r3, sl 
    3c: e0876006 add r6, r7, r6 
    40: e0865005 add r5, r6, r5 
    44: e0854004 add r4, r5, r4 
    48: e5d00006 ldrb r0, [r0, #6] 
    4c: e084c00c add ip, r4, ip 
    50: e08c2002 add r2, ip, r2 
    54: e082c003 add ip, r2, r3 
    58: e023a090 mla r3, r0, r0, sl 
    5c: e080200c add r2, r0, ip 
    60: e5812000 str r2, [r1] 
    64: e1a00003 mov r0, r3 
    68: e8bd05f0 pop {r4, r5, r6, r7, r8, sl} 
    6c: e12fff1e bx lr 

的指數爲負載和細微寄存器混合來自GCC的功能之間的唯一差別，所有的操作都是以相同的順序是相同的。

LLVM /鐺：

00000000 <fun1>: 
    0: e92d41f0 push {r4, r5, r6, r7, r8, lr} 
    4: e5d0e000 ldrb lr, [r0] 
    8: e5d0c001 ldrb ip, [r0, #1] 
    c: e5d03002 ldrb r3, [r0, #2] 
    10: e5d08003 ldrb r8, [r0, #3] 
    14: e5d04004 ldrb r4, [r0, #4] 
    18: e5d05005 ldrb r5, [r0, #5] 
    1c: e5d06006 ldrb r6, [r0, #6] 
    20: e5d07007 ldrb r7, [r0, #7] 
    24: e08c200e add r2, ip, lr 
    28: e0832002 add r2, r3, r2 
    2c: e0882002 add r2, r8, r2 
    30: e0842002 add r2, r4, r2 
    34: e0852002 add r2, r5, r2 
    38: e0862002 add r2, r6, r2 
    3c: e0870002 add r0, r7, r2 
    40: e5810000 str r0, [r1] 
    44: e0010e9e mul r1, lr, lr 
    48: e0201c9c mla r0, ip, ip, r1 
    4c: e0210393 mla r1, r3, r3, r0 
    50: e0201898 mla r0, r8, r8, r1 
    54: e0210494 mla r1, r4, r4, r0 
    58: e0201595 mla r0, r5, r5, r1 
    5c: e0210696 mla r1, r6, r6, r0 
    60: e0201797 mla r0, r7, r7, r1 
    64: e8bd41f0 pop {r4, r5, r6, r7, r8, lr} 
    68: e1a0f00e mov pc, lr 

更容易閱讀和跟隨，也許想着緩存和獲取讀取所有在一杆。至少在一個案例中，llvm也得到了無序的讀取。

00000144 <fun4>: 
144: e92d40f0 push {r4, r5, r6, r7, lr} 
148: e5d0c007 ldrb ip, [r0, #7] 
14c: e5d03006 ldrb r3, [r0, #6] 
150: e5d02005 ldrb r2, [r0, #5] 
154: e5d05004 ldrb r5, [r0, #4] 
158: e5d0e000 ldrb lr, [r0] 
15c: e5d04001 ldrb r4, [r0, #1] 
160: e5d06002 ldrb r6, [r0, #2] 
164: e5d00003 ldrb r0, [r0, #3] 

是的，對於從ram平均一些值，順序不是問題，繼續前進。

所以編譯器選擇展開的路徑並且不關心微觀光學。由於循環的大小，每個循環都選擇刻錄一堆保存一個加載值的寄存器，然後從這些臨時讀取或乘法中執行加法操作。如果我們稍微增加循環的大小，我希望看到展開循環內的sum和sqsum累積，因爲它在寄存器中用完，或者在他們選擇不展開循環的位置達到閾值。

如果我將長度傳入，並將上面的代碼中的8代入長度傳遞，強制編譯器將此循環寫出。你看八九不離十了優化，這樣的指令用於：

a4: e4d35001 ldrb r5, [r3], #1 

而且是手臂他們做環寄存器的在一個地方的指令的修改和分支，如果不相等的一些後來......因爲他們可以。

授予這是一個數學函數，但使用浮動是痛苦的。而使用多層是痛苦的，分隔更糟糕，幸運的是使用了換擋。幸運的是，這是沒有簽名的，所以你可以使用shift（編譯器應該知道使用算術移位，如果可用的話，如果你對有符號數字使用了除法）。因此，基本上集中在內部循環的微觀優化，因爲它可以被多次運行，並且如果這可以被改變，所以如果可能的話，它將變成移位並添加，或者排列數據，以便您可以將它從循環（如果可能，不要在別處浪費其他拷貝循環來做到這一點）

const unsigned char* p = (const unsigned char*)(j*patch->step + aux); 

你可以得到一些速度。我沒有嘗試它，但因爲它是一個循環中的循環編譯器可能不會展開該循環...

長話短說，你可能會得到一些收益取決於設置對一個笨的編譯器指令，但是這個代碼是不是真的不好使編譯器可以優化它，以及你可以。

Answer 2

首先，如果您在Code review處發帖，您可能會獲得非常好的詳細答案。

關於效率和可疑變量類型一些評論：

unsigned f = *p++;你可能會更好，如果你通過數組索引訪問p，然後用P [I]來訪問數據。這很大程度上取決於編譯器，緩存內存優化等（某些ARM guru可以在這方面給出比我更好的建議）。

Btw整個const char到int看起來高度可疑。我認爲這些字符被認爲是8位無符號整數？標準C uint8_t可能是一個更好的類型，char有你想避免的各種未定義的簽名問題。

另外，你爲什麼要做unsigned和int的野生混合？您正在尋求隱式整數平衡錯誤。

stdev < .1。只是一件小事：將其更改爲.1f，或者強制將float的隱式提升加倍，因爲.1是雙字面值。

Answer 3

當你的數據在8個字節組被讀入，這取決於你的硬件總線和陣列本身的定位上，你或許可以通過一個很長很長的讀在讀內環得到一些收益，然後可以手動將數字拆分成單獨的值，也可以使用ARM內部函數使用add8指令並行執行某些內聯彙總（每次在1個寄存器中一次添加4個數字），或者輕觸一下並使用add16來允許值溢出到16位值的空間。還有一個雙重有符號乘法和累加指令，使您的第一個累加循環幾乎完全通過ARM支持，只需一點幫助。而且，如果進入的數據可以被按摩爲16位值，那也可以加快速度。至於爲什麼NEON速度較慢，我的猜測是設置矢量的開銷以及你用更大的類型推動的附加數據造成的損失可能會導致這樣一小組數據可能獲得的性能。原始代碼非常適合ARM開始使用，這意味着設置開銷可能會讓您失望。如有疑問，請查看組件輸出。這將告訴你真正發生了什麼。也許編譯器在嘗試使用內在函數時會推送和彈出各處的數據 - 這不會是我第一次看到這種行爲。

Answer 4

感謝Lundin，dwelch和Michel。 我做了下一個改進，它似乎是我的代碼最好的。 我試圖減少改善緩存訪問的週期數，因爲它只訪問緩存一次。

int step=patch->step; 
for (int j=0; j< 8; j++) { 
     p = (uint8_t*)(j*step + aux);/

     i=8; 
     do {     
      f=p[i]; 
      sum += f; 
      sqsum += f*f; 

     } while(--i); 

}