6

私はいくつかのテストを行って、追加の境界チェックがループでどの程度の違いをもたらすかを確認してきました。これは、配列にアクセスするときに、C#、Java などの言語によって挿入される暗黙的な境界チェックのコストを考えると促されます。

更新: 私は同じ実行可能プログラムをいくつかの追加のコンピューターで試してみました。最初に元のコンピューターをリストし、2 番目に最新のラップトップをリストしました。私の最新のラップトップでは、ループに追加のチェックを追加しても、元のハードウェアの 3 ～ 30% と比較して、所要時間は 1 ～ 4% しか増加しません。

Processor   x86 Family 6 Model 30 Stepping 5 GenuineIntel ~2793 Mhz
Ratio 2 checks : 1 check = 1.0310
Ratio 3 checks : 1 check = 1.2769

Processor   Intel(R) Core(TM) i7-3610QM CPU @ 2.30GHz, 2301 Mhz, 4 Core(s), 8 Logical Processor(s)
Ratio 2 checks : 1 check = 1.0090
Ratio 3 checks : 1 check = 1.0393

Processor   Intel(R) Core(TM) i5-2500 CPU @ 3.30GHz, 4 Cores(s)
Ratio 2 checks : 1 check = 1.0035
Ratio 3 checks : 1 check = 1.0639

Processor   Intel(R) Core(TM)2 Duo CPU     T9300  @ 2.50GHz, 2501 Mhz, 2 Core(s), 2 Logical Processor(s)
Ratio 2 checks : 1 check = 1.1195
Ratio 3 checks : 1 check = 1.3597

Processor   x86 Family 15 Model 43 Stepping 1 AuthenticAMD ~2010 Mhz
Ratio 2 checks : 1 check = 1.0776
Ratio 3 checks : 1 check = 1.1451

以下のテスト プログラムでは、最初の関数は 1 つの境界のみをチェックし、2 番目の関数は 2 つをチェックし、3 番目の関数は 3 つをチェックします (呼び出しコード内n1=n2=n3)。2 回のチェック:1 回の比率は約 1.03、3回のチェック:1 回の比率は約 1.3であることがわかりました。チェックをもう 1 つ追加するだけでパフォーマンスが大きく変わることに驚きました。元の質問に対する最新のプロセッサでの境界チェックの低コストに関する興味深い回答を得ました。これは、ここで観察された違いに光を当てる可能性があります。

プログラム全体の最適化をオンにせずにプログラムをコンパイルすることが重要であることに注意してください。それ以外の場合、コンパイラは追加の境界チェックを単純に削除できます。

// dotprod.cpp
#include "dotprod.h"

double SumProduct(const double* v1, const double* v2, int n)
{
    double sum=0;
    for(int i=0;
        i<n;
        ++i)
        sum += v1[i]*v2[i];
    return sum;
}

double SumProduct(const double* v1, const double* v2, int n1, int n2)
{
    double sum=0;
    for(int i=0;
        i<n1 && i <n2;
        ++i)
        sum += v1[i]*v2[i];
    return sum;
}

double SumProduct(const double* v1, const double* v2, int n1, int n2, int n3)
{
    double sum=0;
    for(int i=0;
        i<n1 && i <n2 && i <n3;
        ++i)
        sum += v1[i]*v2[i];
    return sum;
}

このコードはもともと、Visual Studio 2010、Release、Win32 を使用してビルドされました (速度の違いの背後にある理由は C++ 固有ではなく、Windows 固有ではない可能性があるため、'C' タグを追加しました)。誰でも説明できますか？

情報として、以下のコードの残りの部分。これには、いくつかの C++ 固有のものがあります。

ヘッダーファイル

// dotprod.h
double SumProduct(const double*, const double*, int n);
double SumProduct(const double*, const double*, int n1, int n2);
double SumProduct(const double*, const double*, int n1, int n2, int n3);

テストハーネス

// main.cpp

#include <stdio.h>
#include <math.h>
#include <numeric>
#include <vector>

#include <windows.h>

#include "../dotprod/dotprod.h" // separate lib

typedef __int64 timecount_t;
inline timecount_t GetTimeCount()
{
    LARGE_INTEGER li;
    if (!QueryPerformanceCounter(&li)) {
        exit(1);
    }
    return li.QuadPart;
}

int main()
{
    typedef std::vector<double> dvec;
    const int N  = 100 * 1000;

    // Initialize
    dvec v1(N);
    dvec v2(N);
    dvec dp1(N);
    dvec dp2(N);
    dvec dp3(N);
    for(int i=0; i<N; ++i) {
        v1[i] = i;
        v2[i] = log(static_cast<double>(i+1));
    }

    const timecount_t t0 = GetTimeCount();

    // Check cost with one bound
    for(int n=0; n<N; ++n) {
        dp1[n] = SumProduct(&(v1[0]),&(v2[0]),n); 
    }

    const timecount_t t1 = GetTimeCount();

    // Check cost with two bounds
    for(int n=0; n<N; ++n) {
        dp2[n] = SumProduct(&(v1[0]),&(v2[0]),n,n); 
    }

    const timecount_t t2 = GetTimeCount();

    // Check cost with three bounds
    for(int n=0; n<N; ++n) {
        dp3[n] = SumProduct(&(v1[0]),&(v2[0]),n,n,n); 
    }
    const timecount_t t3 = GetTimeCount();

    // Check results
    const double sumSumProducts1 = std::accumulate(dp1.begin(), dp1.end(), 0.0);
    const double sumSumProducts2 = std::accumulate(dp2.begin(), dp2.end(), 0.0);
    const double sumSumProducts3 = std::accumulate(dp3.begin(), dp3.end(), 0.0);
    printf("Sums of dot products: %.1f, %.1f, %.1f\n", sumSumProducts1, sumSumProducts2, sumSumProducts3);

    // Output timings
    const timecount_t elapsed1 = t1-t0;
    const timecount_t elapsed2 = t2-t1;
    const timecount_t elapsed3 = t3-t2;
    printf("Elapsed: %.0f, %.0f, %.0f\n",
        static_cast<double>(elapsed1),
        static_cast<double>(elapsed2),
        static_cast<double>(elapsed3));
    const double ratio2to1 = elapsed2 / static_cast<double>(elapsed1);
    const double ratio3to1 = elapsed3 / static_cast<double>(elapsed1);
    printf("Ratio 2:1=%.2f\n", ratio2to1);
    printf("Ratio 3:1=%.2f\n", ratio3to1);

    return 0;
}

アセンブリを作成するために、この回答のアドバイス(ケース 2、プログラム全体の最適化をオフにする) を参考にして、次の asm ファイルを作成しました。

; Listing generated by Microsoft (R) Optimizing Compiler Version 16.00.40219.01 

    TITLE   C:\dev\TestSpeed\dotprod\dotprod.cpp
    .686P
    .XMM
    include listing.inc
    .model  flat

INCLUDELIB OLDNAMES

PUBLIC  __real@0000000000000000
PUBLIC  ?SumProduct@@YANPBN0HHH@Z           ; SumProduct
EXTRN   __fltused:DWORD
;   COMDAT __real@0000000000000000
; File c:\dev\testspeed\dotprod\dotprod.cpp
CONST   SEGMENT
__real@0000000000000000 DQ 00000000000000000r   ; 0
; Function compile flags: /Ogtp
CONST   ENDS
;   COMDAT ?SumProduct@@YANPBN0HHH@Z
_TEXT   SEGMENT
tv491 = -4                      ; size = 4
_v1$ = 8                        ; size = 4
_v2$ = 12                       ; size = 4
_n1$ = 16                       ; size = 4
_n2$ = 20                       ; size = 4
_n3$ = 24                       ; size = 4
?SumProduct@@YANPBN0HHH@Z PROC              ; SumProduct, COMDAT

; 25   : {

    push    ebp
    mov ebp, esp
    push    ecx

; 26   :     double sum=0;

    fldz
    push    ebx
    mov ebx, DWORD PTR _v2$[ebp]
    push    esi
    push    edi
    mov edi, DWORD PTR _n1$[ebp]

; 27   :     for(int i=0;

    xor ecx, ecx

; 28   :         i<n1 && i <n2 && i <n3;
; 29   :         ++i)

    cmp edi, 4
    jl  $LC8@SumProduct

; 26   :     double sum=0;

    mov edi, DWORD PTR _v1$[ebp]
    lea esi, DWORD PTR [edi+24]

; 30   :         sum += v1[i]*v2[i];

    sub edi, ebx
    lea edx, DWORD PTR [ecx+2]
    lea eax, DWORD PTR [ebx+8]
    mov DWORD PTR tv491[ebp], edi
$LN15@SumProduct:

; 28   :         i<n1 && i <n2 && i <n3;
; 29   :         ++i)

    mov ebx, DWORD PTR _n2$[ebp]
    cmp ecx, ebx
    jge $LN9@SumProduct
    cmp ecx, DWORD PTR _n3$[ebp]
    jge $LN9@SumProduct

; 30   :         sum += v1[i]*v2[i];

    fld QWORD PTR [eax-8]
    lea edi, DWORD PTR [edx-1]
    fmul    QWORD PTR [esi-24]
    faddp   ST(1), ST(0)
    cmp edi, ebx
    jge SHORT $LN9@SumProduct

; 28   :         i<n1 && i <n2 && i <n3;
; 29   :         ++i)

    cmp edi, DWORD PTR _n3$[ebp]
    jge SHORT $LN9@SumProduct

; 30   :         sum += v1[i]*v2[i];

    mov edi, DWORD PTR tv491[ebp]
    fld QWORD PTR [edi+eax]
    fmul    QWORD PTR [eax]
    faddp   ST(1), ST(0)
    cmp edx, ebx
    jge SHORT $LN9@SumProduct

; 28   :         i<n1 && i <n2 && i <n3;
; 29   :         ++i)

    cmp edx, DWORD PTR _n3$[ebp]
    jge SHORT $LN9@SumProduct

; 30   :         sum += v1[i]*v2[i];

    fld QWORD PTR [eax+8]
    lea edi, DWORD PTR [edx+1]
    fmul    QWORD PTR [esi-8]
    faddp   ST(1), ST(0)
    cmp edi, ebx
    jge SHORT $LN9@SumProduct

; 28   :         i<n1 && i <n2 && i <n3;
; 29   :         ++i)

    cmp edi, DWORD PTR _n3$[ebp]
    jge SHORT $LN9@SumProduct

; 30   :         sum += v1[i]*v2[i];

    fld QWORD PTR [eax+16]
    mov edi, DWORD PTR _n1$[ebp]
    fmul    QWORD PTR [esi]
    add ecx, 4
    lea ebx, DWORD PTR [edi-3]
    add eax, 32                 ; 00000020H
    add esi, 32                 ; 00000020H
    faddp   ST(1), ST(0)
    add edx, 4
    cmp ecx, ebx
    jl  SHORT $LN15@SumProduct
    mov ebx, DWORD PTR _v2$[ebp]
$LC8@SumProduct:

; 28   :         i<n1 && i <n2 && i <n3;
; 29   :         ++i)

    cmp ecx, edi
    jge SHORT $LN9@SumProduct
    mov edx, DWORD PTR _v1$[ebp]
    lea eax, DWORD PTR [ebx+ecx*8]
    sub edx, ebx
$LC3@SumProduct:
    cmp ecx, DWORD PTR _n2$[ebp]
    jge SHORT $LN9@SumProduct
    cmp ecx, DWORD PTR _n3$[ebp]
    jge SHORT $LN9@SumProduct

; 30   :         sum += v1[i]*v2[i];

    fld QWORD PTR [eax+edx]
    inc ecx
    fmul    QWORD PTR [eax]
    add eax, 8
    faddp   ST(1), ST(0)
    cmp ecx, edi
    jl  SHORT $LC3@SumProduct
$LN9@SumProduct:

; 31   :     return sum;
; 32   : }

    pop edi
    pop esi
    pop ebx
    mov esp, ebp
    pop ebp
    ret 0
?SumProduct@@YANPBN0HHH@Z ENDP              ; SumProduct
_TEXT   ENDS
PUBLIC  ?SumProduct@@YANPBN0HH@Z            ; SumProduct
; Function compile flags: /Ogtp
;   COMDAT ?SumProduct@@YANPBN0HH@Z
_TEXT   SEGMENT
tv448 = -4                      ; size = 4
_v1$ = 8                        ; size = 4
_v2$ = 12                       ; size = 4
_n1$ = 16                       ; size = 4
_n2$ = 20                       ; size = 4
?SumProduct@@YANPBN0HH@Z PROC               ; SumProduct, COMDAT

; 15   : {

    push    ebp
    mov ebp, esp
    push    ecx

; 16   :     double sum=0;

    fldz
    push    ebx
    mov ebx, DWORD PTR _v2$[ebp]
    push    esi
    push    edi
    mov edi, DWORD PTR _n1$[ebp]

; 17   :     for(int i=0;

    xor ecx, ecx

; 18   :         i<n1 && i <n2;
; 19   :         ++i)

    cmp edi, 4
    jl  SHORT $LC8@SumProduct@2

; 16   :     double sum=0;

    mov edi, DWORD PTR _v1$[ebp]
    lea edx, DWORD PTR [edi+24]

; 20   :         sum += v1[i]*v2[i];

    sub edi, ebx
    lea esi, DWORD PTR [ecx+2]
    lea eax, DWORD PTR [ebx+8]
    mov DWORD PTR tv448[ebp], edi
$LN19@SumProduct@2:
    mov edi, DWORD PTR _n2$[ebp]
    cmp ecx, edi
    jge SHORT $LN9@SumProduct@2
    fld QWORD PTR [eax-8]
    lea ebx, DWORD PTR [esi-1]
    fmul    QWORD PTR [edx-24]
    faddp   ST(1), ST(0)
    cmp ebx, edi
    jge SHORT $LN9@SumProduct@2
    mov ebx, DWORD PTR tv448[ebp]
    fld QWORD PTR [ebx+eax]
    fmul    QWORD PTR [eax]
    faddp   ST(1), ST(0)
    cmp esi, edi
    jge SHORT $LN9@SumProduct@2
    fld QWORD PTR [eax+8]
    lea ebx, DWORD PTR [esi+1]
    fmul    QWORD PTR [edx-8]
    faddp   ST(1), ST(0)
    cmp ebx, edi
    jge SHORT $LN9@SumProduct@2
    fld QWORD PTR [eax+16]
    mov edi, DWORD PTR _n1$[ebp]
    fmul    QWORD PTR [edx]
    add ecx, 4
    lea ebx, DWORD PTR [edi-3]
    add eax, 32                 ; 00000020H
    add edx, 32                 ; 00000020H
    faddp   ST(1), ST(0)
    add esi, 4
    cmp ecx, ebx
    jl  SHORT $LN19@SumProduct@2
    mov ebx, DWORD PTR _v2$[ebp]
$LC8@SumProduct@2:

; 18   :         i<n1 && i <n2;
; 19   :         ++i)

    cmp ecx, edi
    jge SHORT $LN9@SumProduct@2
    mov edx, DWORD PTR _v1$[ebp]
    lea eax, DWORD PTR [ebx+ecx*8]
    sub edx, ebx
$LC3@SumProduct@2:
    cmp ecx, DWORD PTR _n2$[ebp]
    jge SHORT $LN9@SumProduct@2

; 20   :         sum += v1[i]*v2[i];

    fld QWORD PTR [eax+edx]
    inc ecx
    fmul    QWORD PTR [eax]
    add eax, 8
    faddp   ST(1), ST(0)
    cmp ecx, edi
    jl  SHORT $LC3@SumProduct@2
$LN9@SumProduct@2:

; 21   :     return sum;
; 22   : }

    pop edi
    pop esi
    pop ebx
    mov esp, ebp
    pop ebp
    ret 0
?SumProduct@@YANPBN0HH@Z ENDP               ; SumProduct
_TEXT   ENDS
PUBLIC  ?SumProduct@@YANPBN0H@Z             ; SumProduct
; Function compile flags: /Ogtp
;   COMDAT ?SumProduct@@YANPBN0H@Z
_TEXT   SEGMENT
_v1$ = 8                        ; size = 4
_v2$ = 12                       ; size = 4
?SumProduct@@YANPBN0H@Z PROC                ; SumProduct, COMDAT
; _n$ = eax

; 5    : {

    push    ebp
    mov ebp, esp
    mov edx, DWORD PTR _v2$[ebp]

; 6    :     double sum=0;

    fldz
    push    ebx
    push    esi
    mov esi, eax

; 7    :     for(int i=0;

    xor ebx, ebx
    push    edi
    mov edi, DWORD PTR _v1$[ebp]

; 8    :         i<n;
; 9    :         ++i)

    cmp esi, 4
    jl  SHORT $LC9@SumProduct@3

; 6    :     double sum=0;

    lea eax, DWORD PTR [edx+8]
    lea ecx, DWORD PTR [edi+24]

; 10   :         sum += v1[i]*v2[i];

    sub edi, edx
    lea edx, DWORD PTR [esi-4]
    shr edx, 2
    inc edx
    lea ebx, DWORD PTR [edx*4]
$LN10@SumProduct@3:
    fld QWORD PTR [eax-8]
    add eax, 32                 ; 00000020H
    fmul    QWORD PTR [ecx-24]
    add ecx, 32                 ; 00000020H
    dec edx
    faddp   ST(1), ST(0)
    fld QWORD PTR [edi+eax-32]
    fmul    QWORD PTR [eax-32]
    faddp   ST(1), ST(0)
    fld QWORD PTR [eax-24]
    fmul    QWORD PTR [ecx-40]
    faddp   ST(1), ST(0)
    fld QWORD PTR [eax-16]
    fmul    QWORD PTR [ecx-32]
    faddp   ST(1), ST(0)
    jne SHORT $LN10@SumProduct@3

; 6    :     double sum=0;

    mov edx, DWORD PTR _v2$[ebp]
    mov edi, DWORD PTR _v1$[ebp]
$LC9@SumProduct@3:

; 8    :         i<n;
; 9    :         ++i)

    cmp ebx, esi
    jge SHORT $LN8@SumProduct@3
    sub edi, edx
    lea eax, DWORD PTR [edx+ebx*8]
    sub esi, ebx
$LC3@SumProduct@3:

; 10   :         sum += v1[i]*v2[i];

    fld QWORD PTR [eax+edi]
    add eax, 8
    dec esi
    fmul    QWORD PTR [eax-8]
    faddp   ST(1), ST(0)
    jne SHORT $LC3@SumProduct@3
$LN8@SumProduct@3:

; 11   :     return sum;
; 12   : }

    pop edi
    pop esi
    pop ebx
    pop ebp
    ret 0
?SumProduct@@YANPBN0H@Z ENDP                ; SumProduct
_TEXT   ENDS
END
4

1 に答える 1

2

CPU 間の大きな違いの 1 つは、パイプラインの最適化です。

CPU は、条件付き分岐に到達するまで、複数の命令を並行して実行できます。この時点から、すべての命令が実行されるまで待機する代わりに、CPU は、条件が使用可能になり、評価の準備が整うまで、並行して分岐を続行できます。仮定が正しければ、利益が得られます。それ以外の場合、CPU は他のブランチに移動します。

したがって、CPU にとってトリッキーな部分は、最良の仮定を見つけて、できるだけ多くの命令を並列に実行することです。

于 2013-06-19T14:13:19.170 に答える