なぜこのコードは効率的ではありませんか？

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

しかし、30ms程度遅くなります。なぜ誰が知っていますか？

すべてのコードは正しく動作しています。

Answer 1

Lundinに追加します。はい、ARMのような命令セットは、レジスタベースのインデックスを持っているか、即時のインデックスを持つリーチを使用すると、コンパイラがインデックスを使用するのに役立つ場合があります。また、例えばARMはロード命令でポインタレジスタをインクリメントすることができますが、基本的には1つの命令で* 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]形式を使用すると、コンパイラは読み込みの順序を任意に変更することはできません。その場合、コード数を減らしたいと思うでしょう。gccとLLVM（打ち鳴らす）の両方で

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では、微妙なレジスタミックスの変更があった場合、それぞれの実験で同じコードが生成されます。そして、私は少なくとも1人の読者がコードによって記述された順序ではないので、バグを主張するだろう。

すべての4つのgccソリューションは、いくつかの読み込み順序を変更して、ソースコードから順不同であることに気付きました。これが、コードに記述されている順序で読み込みに依存しているハードウェア/ロジックに対するものであれば、大きな問題があります。

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 

はるかに簡単。少なくとも1つのケースでは、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] 

はい、ラムからの値の平均値は、問題ありません。

コンパイラはアンロールされたパスを選択し、マイクロオプティマイズについて気にしませんでした。ループのサイズのために、ループごとにロードされた値の1つを保持している一連のレジスタを書き込んだ後、それらの一時的な読み込みまたは乗算から加算を実行することを選択します。私たちがループのサイズを少し増やした場合、アンロールされたループ内でsumとsqsumの累算がレジスタを使い果たしたときに累積することが予想されます。あるいは、ループをアンロールすることを選択したところでしきい値に達するでしょう。

長さを渡して、上のコードの8を長さが渡されたものに置き換えて、コンパイラーがこれをループするように強制します。あなたはみかんの最適化を参照して、このような命令が使用されています。

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

以降の命令の数と等しくない場合、彼らは一つの場所や枝にループレジスタの修正を行うアームであることを...彼らは可能性があるため。

これは数学関数ですが、floatを使用すると痛いです。マルチプルを使うのは苦痛で、分裂はずっと悪く、幸いにもシフトが使われました。幸いにも、これは符号なしであったので、シフトを使用することができました（コンパイラは、符号付きの数値との除算を使用した場合、算術シフトを使用することがわかっていたはずです）。

基本的には、内部ループが複数回実行されるため、マイクロオプティマイズに焦点を当てます。これを変更することが可能であれば、シフトや追加を行い、可能であればデータを並べ替えることができます。ループ（可能な場合は、廃棄物その他のコピーをいけない、これを行うために他の場所でループ）

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

あなたには、いくつかの速度を得ることができます。私はそれを試してみませんでしたが、それはループ内のループであるため、コンパイラはおそらくそのループをアンロールしません...

短い話ですが、ダンベルコンパイラに対する命令セットによってはいくらか利益が得られるかもしれませんが、このコードは実際には悪くないので、コンパイラは最適化することもできます。

Answer 2

まず、Code reviewに投稿すると、このようなものについて非常に良い詳細な回答が得られるでしょう。

効率や不審な変数の型に関するいくつかのコメント：

unsigned f = *p++;あなたは、配列のインデックスを通じてpにアクセスし、[i]のデータにアクセスするためのpを使用する場合は、おそらくほうが良いでしょう。これは、コンパイラ、キャッシュメモリの最適化などに大きく依存しています（この点については、ARMの専門家が私にとってより良い助言を与えることができます）。

Btw intのconst char全体が非常に疑わしいです。私はそれを取るそれらの文字は8ビットの符号なし整数と見なされるのですか？これには標準C uint8_tが適している可能性があります。charには、未定義のさまざまな問題があります。

さらに、野生的に混合する理由は、unsignedとintですか？暗黙の整数バランシングのバグを求めています。

stdev < .1。ちょっとしたこと：これを.1fに変更するか、.1がダブルリテラルなので、floatの倍精度宣言を強制します。

Answer 3

データが8バイトのグループで読み込まれているので、ハードウェアバスとアレイ自体の配置によっては、1回の長い読み取りでインナーループを読み取ることで多少の利益を得ることができます手動で数値を別々の値に分割するか、またはARMコンパイラを使用してadd8命令を使用していくつかのインラインasmと並列で加算を実行するか（1つのレジスタに同時に4つの数値を加算する）、シフトを行いadd16を使用して値は16ビット分の領域にオーバーフローします。また、二重符号付きの乗算および累算命令もあります。これにより、最初の累算ループはARMを介してほぼ完全にサポートされます。また、入ってくるデータを16ビット値にマッサージすることができれば、これも高速化する可能性があります。

なぜNEONが遅いのかというと、ベクターをセットアップする際のオーバーヘッドが大きいデータ型を使用しているため、このような小さなデータセットで得られるパフォーマンスが低下するということです。元のコードは非常にARMに優しいので、セットアップオーバーヘッドがおそらくあなたを殺していることになります。不確かな場合は、アセンブリの出力を見てください。それは本当に何が起こっているかを教えてくれるでしょう。おそらくコンパイラは、組み込み関数を使用しようとすると、どこにでもデータをプッシュしてポップしています。この種の動作を初めて見たことはないでしょう。

Answer 4

Lundin、dwelchおよびMichelに感謝します。 私は次の改善を行い、それは私のコードのために最もよいようです。 キャッシュアクセスを向上させるサイクル数を減らそうとしています。これは、キャッシュに1回だけアクセスするためです。

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

}