2

次のように、逆参照演算子を使用して、2D 配列への行優先イテレータがあります。

int& Iterator::operator*(){ return matrix_[y_][x_]; }  //matrix_ has type int**

(プレフィックス) インクリメント演算子は次のとおりです。

Iterator& Iterator::operator++()
{
    if((++x_ == xs_) && (++y_ != ys_)) //ys_, xs_ are the dimensions of the matrix
        x_ = 0;
    return *this;   
}

この反復子を std::transform の最適化されたバージョンで使用できます (いくつかの命令を節約するために、不要な結果を返しません)

template < class InputIterator, class OutputIterator, class UnaryOperator >
inline void MyTransform( InputIterator first1, InputIterator last1,
                         OutputIterator result, UnaryOperator op )
{
    for (; first1 != last1; ++first1, ++result)
        *result = op(*first1);
}

次のように呼び出します。

MyTransform(matrix1.begin(),matrix1.end(),matrix2.begin(), MyFunctor());

ただし、パフォーマンスを従来のネストされた for ループと比較すると、次のようになります。

MyFunctor() f;
for (int y=0; y<ySize; y++)
    for (int x=0; x<xSize; x++)
        matrix2.[y][x] = f(matrix1.[y][x]);

イテレータベースのソリューションは約です。ネストされた for ループ ソリューションよりも 25% 遅くなります。これは、MSVC コンパイラと Intel C++ コンパイラの両方に当てはまります (どちらも必要に応じて自動インライン化されるようです)。

問題は、イテレータのインクリメント演算子にあるようには見えません。イテレータ トラバーサルと生の配列アクセスを組み合わせた次の (醜い) ハイブリッド ソリューションを実行したかのようです (後者は、イテレータの内部カウントを使用してインデックス付けされます)。

MyFunctor f;
for (; mat1Begin != mat1End; ++mat1Begin, ++mat2Begin)
{ 
    //mat1 and mat2 are type int**
    mat2[mat2Begin.y_][mat2Begin.x_] = f(mat1[mat1Begin.y_][mat1Begin.x_]);
}

実際には、ネストされた for ループ ソリューションよりも少し高速です。これは、割り当てを行うときのイテレータの逆参照にパフォーマンス ヒットがあることを示唆しています。

私の質問は、割り当てでイテレータを逆参照するのはなぜですか

*result = op(*first1);

生の配列アクセスと比較して、そのような大規模なパフォーマンス ヒットが発生しますか? 生の配列バージョンと (ほぼ) 同等のパフォーマンスを得るために、この単純な設計に使用できる手法はありますか?

このコミュニティからの有益なフィードバックに応えて、ループの外側のカウンターがキャッシュされるようにコードを修正したので、コードは次のようになりました。

int& Iterator::operator*()
{
    return column_[x_]; 
} 

Iterator& Iterator::operator++()
{
    if(++x_ == xs_)      //ys_, xs_ are the dimensions of the matrix
    {
        if(++y_ != ys_)
        { 
            x_ = 0;
            column_ = matrix_[y_];
        }
    }
    return *this;
}

これにより、インテル® C++ コンパイラーの生の 2D 配列のパフォーマンスの最大 85% までパフォーマンスが向上し、MSVC コンパイラーでも同様です (実際には、MSVC では MyTransform の呼び出しが遅くなります - より多くのアセンブリ命令が生成されます)。ループ/逆参照の動作にもっと興味があります)。

次のようにコードをポインター演算 (再び列をキャッシュする) を使用するように変換すると、Intel コンパイラーでは生の 2D 配列 (~70%) よりもパフォーマンスが大幅に低下しますが、MSVC コンパイラーでは生の 2D 配列の~85% になります。

int& Image32Iterator::operator*()
{
    return *ptr_;
} 

//prefix
Image32Iterator& Image32Iterator::operator++()
{
    if(++ptr_ == ptrEnd_)
    {
        if(++row_ != rowEnd_)
        { 
            ptrEnd_ = (ptr_ = *row_) + xs_;
        }
    }
    return *this;
}

したがって、イテレータベースのソリューションを使用して最大 85% のパフォーマンスが得られるかどうかを理解しようとしています。ポインター演算ソリューションのパフォーマンスが非常に悪いことに驚いています (ポインター演算を使用して > 85% を取得できるかどうかを確認しようとしていたので、うんざりしました!)。

私は調査を続け、発見を更新しますが、どんな洞察も歓迎します...

…だから、イテレータのポインタ演算バージョンが Intel ではうまく動作しないのに、MSVC コンパイラでは問題なく動作する理由の問題に焦点を当てて、アセンブリを調べたところ、問題はコードにあるようですループ用に生成されます。他のすべての関数 (つまり、コンストラクター、イテレーターと逆参照演算子、不等式演算子など) については、生成されたコードは Intel と MSVC の両方でほとんど同じですが、Intel の方が少し簡潔です)。

これは、インテルが生成したコードのアセンブラーであり、その後に MSVC が生成したコードのアセンブラーが続きます。生成されたアセンブラを読みやすくするために、for ループから while ループに変更しました。

インテルが生成したコード:

while(begin != end)
01392D31  push        eax  
01392D32  lea         eax,[begin]  
01392D35  lea         edx,[end]  
01392D38  mov         dword ptr [esp],edx  
01392D3B  mov         ecx,eax  
01392D3D  call        ImageExperiments::Image32Iterator::operator!= (139103Ch)  
01392D42  mov         byte ptr [ebp-74h],al  
01392D45  movzx       eax,byte ptr [ebp-74h]  
01392D49  movzx       eax,al  
01392D4C  test        eax,eax  
01392D4E  je          ImageExperiments::greyscale_iterator2+0BCh (1392DACh)  
{
    *it8 = gsf(*begin);
01392D50  lea         eax,[begin]  
01392D53  mov         ecx,eax  
01392D55  call        ImageExperiments::Image32Iterator::operator* (13910A5h)  
01392D5A  mov         dword ptr [ebp-10h],eax  
01392D5D  push        eax  
01392D5E  lea         eax,[gsf]  
01392D61  mov         edx,dword ptr [ebp-10h]  
01392D64  mov         edx,dword ptr [edx]  
01392D66  mov         dword ptr [esp],edx  
01392D69  mov         ecx,eax  
01392D6B  call        ImageExperiments::GreyScaleFunctor::operator() (139101Eh)  
01392D70  mov         byte ptr [ebp-72h],al  
01392D73  movzx       eax,byte ptr [ebp-72h]  
01392D77  mov         byte ptr [ebp-71h],al  
01392D7A  lea         eax,[it8]  
01392D7D  mov         ecx,eax  
01392D7F  call        ImageExperiments::Image8Iterator::operator* (1391050h)  
01392D84  mov         dword ptr [ebp-0Ch],eax  
01392D87  mov         eax,dword ptr [ebp-0Ch]  
01392D8A  movzx       edx,byte ptr [ebp-71h]  
01392D8E  mov         byte ptr [eax],dl  
    ++begin; 
01392D90  lea         eax,[begin]  
01392D93  mov         ecx,eax  
01392D95  call        ImageExperiments::Image32Iterator::operator++ (1391028h)  
01392D9A  mov         dword ptr [ebp-8],eax  
    ++it8;
01392D9D  lea         eax,[it8]  
01392DA0  mov         ecx,eax  
01392DA2  call        ImageExperiments::Image8Iterator::operator++ (1391014h)  
01392DA7  mov         dword ptr [ebp-4],eax  
01392DAA  jmp         ImageExperiments::greyscale_iterator2+41h (1392D31h)  
}
}
00CA2DAC  leave  
00CA2DAD  ret

MSVC 生成コード:

while(begin != end)
010316E0  lea         eax,[end]  
010316E3  push        eax  
010316E4  lea         ecx,[begin]  
010316E7  call        ImageExperiments::Image32Iterator::operator!= (1031096h)  
010316EC  movzx       ecx,al  
010316EF  test        ecx,ecx  
010316F1  je          ImageExperiments::greyscale_iterator2+74h (1031724h)  
{
    *it8 = gsf(*begin);
010316F3  lea         ecx,[begin]  
010316F6  call        ImageExperiments::Image32Iterator::operator* (10311EAh)  
010316FB  mov         eax,dword ptr [eax]  
010316FD  push        eax  
010316FE  lea         ecx,[gsf]  
01031701  call        ImageExperiments::GreyScaleFunctor::operator() (1031032h)  
01031706  mov         bl,al  
01031708  lea         ecx,[it8]  
0103170B  call        ImageExperiments::Image8Iterator::operator* (1031118h)  
01031710  mov         byte ptr [eax],bl  
    ++begin; 
01031712  lea         ecx,[begin]  
01031715  call        ImageExperiments::Image32Iterator::operator++ (1031041h)  
    ++it8;
0103171A  lea         ecx,[it8]  
0103171D  call        ImageExperiments::Image8Iterator::operator++ (103101Eh)  
}
01031722  jmp         ImageExperiments::greyscale_iterator2+30h (10316E0h)  
}
01031724  pop         edi  
01031725  pop         esi  
01031726  pop         ebx  
01031727  mov         esp,ebp  
01031729  pop         ebp  
0103172A  ret

したがって、Intelコンパイラが約を生成するように見えます。50% 多い命令数。ポインタを __restrict で修飾して、それが Intel 世代に違いをもたらすかどうかを確認しようとしましたが、違いはありませんでした。MSVC++ コンパイラと比較して、Intel コンパイラのループ コードが非常にかさばる/遅い理由について何か提案があれば、私は非常に興味があります!

4

4 に答える 4

2

私はあなたのコードを再作成することに挑戦しました。ここを参照してください。

g ++（4.6.3、-O3）で実行すると、次のことがわかります。

1）非イテレーターバージョンは確かに高速ですが、私の場合は約4倍です。2）イテレーターバージョンは、イテレーターを尊重するか、カウンターを抽出して配列に直接アクセスするかどうかに関係なく、次のようになります。遅い（前述の要因による）。

2つのバージョンのアセンブラーをキャプチャしましたが、バージョン2のイテレーターインクリメントロジックに関連付けられた大量のコードで、それらがまったく異なることがわかりました。どちらの場合も、すべてがインライン化されていることに注意してください。

ケース1の内部ループ、イテレータなし：

.L18:
    xorl    %eax, %eax
    .p2align 4,,10
    .p2align 3
.L19:
    movq    24(%rsp), %rdx
    movq    40(%rsp), %rsi
    movq    (%rdx,%rcx), %rdx
    movq    (%rsi,%rcx), %rsi
    movl    (%rdx,%rax), %edx
    imull   %edx, %edx
    movl    %edx, (%rsi,%rax)
    addq    $4, %rax
    cmpq    $20000, %rax
    jne .L19
    addq    $8, %rcx
    cmpq    $40000, %rcx
    jne .L18
    movl    $.LC2, %esi
    movl    std::cout, %edi

ケース2の内部ループ、イテレータ：

.L34:
    movl    %eax, 56(%rsp)
    movl    %ecx, 60(%rsp)
    movl    %edi, 72(%rsp)
    movl    %edi, 76(%rsp)
    movq    72(%rsp), %rdi
    cmpq    %rdi, 56(%rsp)
    je  .L36
    movq    24(%rsp), %rdi
    movslq  %eax, %r10
    movslq  %ecx, %r9
    movslq  %edx, %r11
    addl    $1, %eax
    movq    (%rdi,%r10,8), %rdi
    movslq  %esi, %r10
    movl    (%rdi,%r9,4), %edi
    movq    40(%rsp), %r9
    imull   %edi, %edi
    movq    (%r9,%r11,8), %r9
    movl    %edi, (%r9,%r10,4)
    movl    16(%rsp), %edi
    cmpl    %edi, %eax
    je  .L37
.L20:
    addl    $1, %edx
    cmpl    32(%rsp), %edx
    jne .L34
    addl    $1, %esi
    cmpl    %esi, %edx
    cmovne  %r8d, %edx
    jmp .L34
.L37:
    addl    $1, %ecx
    cmpl    %ecx, %eax
    cmovne  %r8d, %eax
    jmp .L20
.L36:

最終的に、イテレータパターンが好きな場合は、行列の内部配列をとして再定義しint*、イテレータをポインタの単純なラッパーにすることをお勧めします。intこれは明らかに、与えられた配列への1次元オフセットの計算x、yおよび行幅の計算を処理する必要がある行列のランダムアクセスインデックス付けを犠牲にします（ただし、ロケット科学はほとんどありません！）。

于 2012-06-29T20:54:45.710 に答える
1

イテレータが大きすぎると思います。operator*()最悪の場合を呼び出すときは、コンパイラがat 、の値をフェッチする前にy_フェッチする必要があるということです。可能であれば、イテレータとして生のポインタを使用しようとします。つまり、は、反復の開始および終了として使用できるように定義されます。そしてもちろん、常にあります。x_matrix_x_y_matrix_int matrix_[N][M]&matrix_[0][0]&matrix_[N-1][M]valarray

于 2012-06-29T17:25:04.283 に答える
0

matrix_[y_][x_]関数呼び出しからループへの二重間接参照を巻き上げています。おそらく、コンパイラーは、ある場合にはポインターをキャッシュしているmatrix_[y_]が、他の場合にはキャッシュしていない。matrix_[y_]イテレータでキャッシュしてみてください。

于 2012-06-29T17:05:03.087 に答える
0

1. メモリのローカリゼーション。連続保証。変数 mat1 と mat2 が int** であることを明確にしたことに気付きました。しかし、matrix_ はメモリ内でどのように処理されますか。インターレーターは、考えられる限りどこでも指すだけです。matrix_ のメモリはローカライズされていますか? ヒープベースの多次元配列は連続していない場合があります。しかし、Vector<> はそうです。

このコード行は、実際のインターレーターを使用していませんが、それらの変数を使用して、ローカライズされた配列にインデックスを付けています。

mat2[mat2Begin.y_][mat2Begin.x_] = f(mat1[mat1Begin.y_][mat1Begin.x_]);

2. 最適化を忘れています。インクリメント演算子を使用する 2 番目の使用法では、ファンクターを呼び出す前にそのステップを実行しています。

これは、オペレーターを介して逆参照されるオブジェクトを渡すファンクターを呼び出すと、オプティマイザーが順序を優先する機能に干渉していることを意味する場合があります。

op() を呼び出す前に逆参照されたオブジェクトを保存してみて、それによってコストが削減されるかどうかを確認してください。

for (; first1 != last1; ++first1, ++result)
{
    InputIterator::value_type val = *first1;
    *result = op(val);
}

引数の代入で演算子を使用すると、奇妙なことがいくつか見られました。呼び出しの後まで解決が延期され (式の他の解釈を送信し、呼び出しの後に式を解決する)、引数の解決順序が保証されないところまで。効率に問題がある場合は、引数を介して実際に意図したオブジェクトを送信することをお勧めします。

于 2012-06-29T16:38:38.230 に答える