ベクトルのアクセス時間を短縮する方法

Question

私はアルゴリズムの速度を上げようとしています。そのため、iOS用の「Instruments」でアプリケーションを実行しました。その結果、ほぼ75％の時間が計算をベクター。

誰もがCPUの量を消費せずにデータを保存する良い方法を知っていますか？私は、キャッシュメモリやそのようなものへのアクセスに関連していると思います。行にはコメントがついています。この行には、短絡配列で短い行が保存されています。

short XY[32*32*2] 
Mat _XY(bh, bw, CV_16SC2, XY), matA; 
Mat dpart(dst, Rect(x, y, bw, bh)); 

for(y1 = 0; y1 < bh; y1++) 
{ 
    short* xy = XY + y1*bw*2; 
    int X0 = M[0]*x + M[1]*(y + y1) + M[2]; 
    int Y0 = M[3]*x + M[4]*(y + y1) + M[5]; 
    float W0 = M[6]*x + M[7]*(y + y1) + M[8]; 

    M2[2] = X0; 
    M2[3] = Y0; 

    for(x1=0; x1<bw; x1++) 
    { 

     float W  = W0 + M[6]*x1; 
     W   = 1./W; 
     float x12[2] = {x1*W,W}; 


     matvec2_c(M2,x12,M3); 
     short aux = (M3[0]); 
     int aux2  = x1*2; 
     xy[aux2]  = aux;   // %60 CPU TIME 
     xy[x1*2+1] = (M3[1]);  // 11% CPU TIME 
    } 
    // ... 
} 

void matvec2_c(float m[4], float v[2], float d[2]) 
{ 
    d[0] = m[0]*v[0] + m[2]*v[1]; 
    d[1] = m[1]*v[0] + m[3]*v[1]; 
} 

Answer 1

これは私ができる最高のものでした：

short XY[32*32*2]; 
int XYI[32*32*2]; 
Mat _XY(bh, bw, CV_16SC2, XY), matA; 
Mat _XYI(bh, bw, CV_32S, XYI); 
Mat dpart(dst, Rect(x, y, bw, bh)); 

for(y1 = 0; y1 < bh; y1++) 
{ 
    int * xyi = XYI + y1*bw; 
    short * xy = XY + y1*bw*2; 

    int X0 = M[0]*x + M[1]*(y + y1) + M[2]; 
    int Y0 = M[3]*x + M[4]*(y + y1) + M[5]; 

    float W0 = M[6]*x + M[7]*(y + y1) + M[8]; 
    M2[2]=X0; 
    M2[3]=Y0; 

    for(x1=0;x1<bw;x1++){ 

    float W = W0 + M[6]*x1; 
    W= 1./W; 
    float x12[2]={x1*W,W}; 


    matvec2_c(M2,x12,M3); 

    xyi[x1*2] = (M3[0]);//9% 
    xyi[x1*2+1]=(M3[1]);//6% 



} 
for(x1=0;x1<bw;x1++){ 

    xy[x1*2] = xyi[x1*2];//4% 
    xy[x1*2+1]=xyi[x1*2+1];//3% 
} 

コードを2つの部分に分けた部分を分割しただけなので、CPUにキャッシュにアクセスする方法や、さまざまな形式に関連するものと関連していると思います。 アルゴリズムの時間が93ミリ秒から78ミリ秒に減少します。

Answer 2

私の推測では、それはコンパイラ最適化の問題です：XY用ポインタ計算がため内で行われる（X1 = -loopないでため（Y1 = -loop、それは多くを行ってますので、必要以上の時間

解決策：私はあなたのコードはありません、それは本当にメンテナ優しいwrittinされていないのかわからないのです

#include <assert.h> 

... 
short* xy = XY + y1*bw*2; 
assert (xy!=NULL); 
... 

Answer 3

しかし、あなたがそれらのデータにアクセスする場合：インスタンス化を強制するassert()を使用しています。すべての方向（左、上、右、下）の配列、次にフォローインgはあなたのためかもしれません。

Morton Code/Z order curve.を使用して配列のインデックスを作成します。 locality of referenceが増加します。これにより、要素を完全に囲む要素にアクセスするときのキャッシングの動作が向上します。

考えてみましょう：古典的な2d索引付けを使用すると、上部と下部の隣接物までの距離はピッチまたは幅です。幅/高さが非常に高い場合は、配列の非常に遠い要素にアクセスしています。 CPUが多くの投機的キャッシングを行うことを考慮すると、これらの推測の多くは無駄な努力を招く（いわゆるcache-miss）。あなたは良い指標（左右の隣人）といくつかの非常に悪い（上下の隣人）があります。

モートンの索引付けでは、理想的な左右の隣接はありませんが、同様に、上下の隣には遠く離れていません。

平均的に、あなたはは、キャッシュされたデータをヒットしない場合、これらのデータにアクセスすることはあなたもそれへのアクセスを開始する前に（既にデータがキャッシュにあるかもしれない本当に安いです、[http://en.wikipedia.orgのおかげで/ wiki/Speculative_execution]（投機的実行）とprefetching

もちろん、コードの大部分が左から右の順番で要素にアクセスする場合、または関連するボトルネックではない場合は、実行したくない場合があります