44

次の2つのファイルがあります:-

シングル.cpp :-

#include <iostream>
#include <stdlib.h>

using namespace std;

unsigned long a=0;

class A {
  public:
    virtual int f() __attribute__ ((noinline)) { return a; } 
};

class B : public A {                                                                              
  public:                                                                                                                                                                        
    virtual int f() __attribute__ ((noinline)) { return a; }                                      
    void g() __attribute__ ((noinline)) { return; }                                               
};                                                                                                

int main() {                                                                                      
  cin>>a;                                                                                         
  A* obj;                                                                                         
  if (a>3)                                                                                        
    obj = new B();
  else
    obj = new A();                                                                                

  unsigned long result=0;                                                                         

  for (int i=0; i<65535; i++) {                                                                   
    for (int j=0; j<65535; j++) {                                                                 
      result+=obj->f();                                                                           
    }                                                                                             
  }                                                                                               

  cout<<result<<"\n";                                                                             
}

multiple.cpp :-

#include <iostream>
#include <stdlib.h>

using namespace std;

unsigned long a=0;

class A {
  public:
    virtual int f() __attribute__ ((noinline)) { return a; }
};

class dummy {
  public:
    virtual void g() __attribute__ ((noinline)) { return; }
};

class B : public A, public dummy {
  public:
    virtual int f() __attribute__ ((noinline)) { return a; }
    virtual void g() __attribute__ ((noinline)) { return; }
};


int main() {
  cin>>a;
  A* obj;
  if (a>3)
    obj = new B();
  else
    obj = new A();

  unsigned long result=0;

  for (int i=0; i<65535; i++) {
    for (int j=0; j<65535; j++) {
      result+=obj->f();
    }
  }

  cout<<result<<"\n";
}

フラグ -O2 で gcc バージョン 3.4.6 を使用しています

そして、これは私が得るタイミングの結果です:-

多数 :-

real    0m8.635s
user    0m8.608s
sys 0m0.003s

独身 :-

real    0m10.072s
user    0m10.045s
sys 0m0.001s

一方、 multiple.cpp でクラス派生の順序を逆にした場合:-

class B : public dummy, public A {

次に、次のタイミングを取得します (これは、コードが行う必要のある this ポインターへの「サンク」調整のおかげで、単一継承の場合よりもわずかに遅くなります) :-

real    0m11.516s
user    0m11.479s
sys 0m0.002s

なぜこれが起こっているのでしょうか?ループに関する限り、3 つのケースすべてで生成されたアセンブリに違いはないようです。私が見る必要がある他の場所はありますか?

また、プロセスを特定の CPU コアにバインドし、SCHED_RR を使用してリアルタイムの優先度で実行しています。

編集:- これは Mysticial によって認識され、私によって再現されました。する

cout << "vtable: " << *(void**)obj << endl;

single.cpp のループの直前に、パブリック A、パブリック ダミーのように、シングルも 8.4 秒で複数のクロッキングと同じくらい高速になります。

4

5 に答える 5

27

この回答は非常に推測に基づくものであることに注意してください。

「なぜ X は Y よりも遅いのか」というタイプの質問に対する私の他の回答とは異なり、この回答を裏付ける確固たる証拠を提供できませんでした。


これを約1時間いじった後、次の3つのアドレスの配置が原因であると思います。

owagh の回答は、命令のアライメントの可能性も示唆しています。)

多重継承が単一継承よりも遅い理由は、それが「魔法のように」速いからではなく、単一継承のケースがコンパイラーまたはハードウェアの「しゃっくり」に陥っているからです。


単一および複数の継承ケースのアセンブリをダンプすると、入れ子になったループ内でそれらは同一 (レジスタ名とすべて) になります。

コンパイルしたコードは次のとおりです。

#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
unsigned long a=0;


#ifdef SINGLE
class A {
  public:
    virtual int f() { return a; } 
};

class B : public A {
  public:
    virtual int f() { return a; }                                      
    void g() { return; }                                               
};       
#endif

#ifdef MULTIPLE
class A {
  public:
    virtual int f() { return a; }
};

class dummy {
  public:
    virtual void g() { return; }
};

class B : public A, public dummy {
  public:
    virtual int f() { return a; }
    virtual void g() { return; }
};
#endif

int main() {
    cin >> a;
    A* obj;
    if (a > 3)
        obj = new B();
    else
        obj = new A();

    unsigned long result = 0;


    clock_t time0 = clock();

    for (int i=0; i<65535; i++) {
        for (int j=0; j<65535; j++) {
            result += obj->f();
        }
    }      

    clock_t time1 = clock();   
    cout << (double)(time1 - time0) / CLOCKS_PER_SEC << endl;    

    cout << result << "\n";
    system("pause");  //  This is useless in Linux, but I left it here for a reason.
}

ネストされたループのアセンブリは、単一継承の場合と多重継承の場合で同じです。

.L5:
    call    clock
    movl    $65535, %r13d
    movq    %rax, %r14
    xorl    %r12d, %r12d
    .p2align 4,,10
    .p2align 3
.L6:
    movl    $65535, %ebx
    .p2align 4,,10
    .p2align 3
.L7:
    movq    0(%rbp), %rax
    movq    %rbp, %rdi
    call    *(%rax)
    cltq
    addq    %rax, %r12
    subl    $1, %ebx
    jne .L7
    subl    $1, %r13d
    jne .L6
    call    clock

それでも、私が見るパフォーマンスの違いは次のとおりです。

  • シングル:9.4秒
  • 複数: 8.06 秒

Xeon X5482、Ubuntu、GCC 4.6.1 x64。

これにより、違いはデータに依存しているに違いないという結論に至りました。

そのアセンブリを見ると、可変レイテンシーを持つ可能性がある唯一の命令がロードであることがわかります。

    ; %rbp = vtable

movq    0(%rbp), %rax   ; Dereference function pointer from vtable
movq    %rbp, %rdi
call    *(%rax)         ; Call function pointer - f()

続いて、呼び出し内でさらにいくつかのメモリ アクセスが行われますf()


たまたま、単一継承の例では、前述の値のオフセットがプロセッサにとって好ましくありません。理由がわかりません。しかし、私は何かを疑う必要がありました。それは、この質問の図の領域 2と同様に、キャッシュ バンクの競合であると考えられます。

コードを再配置してダミー関数を追加することで、これらのオフセットを変更できます。これにより、多くの場合、この速度低下が解消され、単一継承が多重継承の場合と同じくらい高速になります。


たとえばsystem("pause")、時間の反転を削除します。

#ifdef SINGLE
class A {
  public:
    virtual int f() { return a; } 
};

class B : public A {
  public:
    virtual int f() { return a; }                                      
    void g() { return; }                                               
};       
#endif

#ifdef MULTIPLE
class A {
  public:
    virtual int f() { return a; }
};

class dummy {
  public:
    virtual void g() { return; }
};

class B : public A, public dummy {
  public:
    virtual int f() { return a; }
    virtual void g() { return; }
};
#endif

int main() {
    cin >> a;
    A* obj;
    if (a > 3)
        obj = new B();
    else
        obj = new A();

    unsigned long result = 0;


    clock_t time0 = clock();

    for (int i=0; i<65535; i++) {
        for (int j=0; j<65535; j++) {
            result += obj->f();
        }
    }      

    clock_t time1 = clock();   
    cout << (double)(time1 - time0) / CLOCKS_PER_SEC << endl;    

    cout << result << "\n";
//    system("pause");
}
  • シングル:8.06秒
  • 複数:9.4秒
于 2012-05-03T23:21:23.283 に答える
16

なぜこれが起こっているのかについて、少なくともいくつかの手がかりを得たと思います。ループのアセンブリはまったく同じですが、オブジェクト ファイルは異なります。

最初に cout があるループの場合 (ie)

cout << "vtable: " << *(void**)obj << endl;

for (int i=0; i<65535; i++) {
  for (int j=0; j<65535; j++) {
    result+=obj->f();
  }
}

オブジェクトファイルで次を取得します:-

40092d:       bb fe ff 00 00          mov    $0xfffe,%ebx                                       
400932:       48 8b 45 00             mov    0x0(%rbp),%rax                                     
400936:       48 89 ef                mov    %rbp,%rdi                                          
400939:       ff 10                   callq  *(%rax)                                            
40093b:       48 98                   cltq                                                      
40093d:       49 01 c4                add    %rax,%r12                                          
400940:       ff cb                   dec    %ebx                                               
400942:       79 ee                   jns    400932 <main+0x42>                                 
400944:       41 ff c5                inc    %r13d                                              
400947:       41 81 fd fe ff 00 00    cmp    $0xfffe,%r13d                                      
40094e:       7e dd                   jle    40092d <main+0x3d>                                 

ただし、cout がないと、ループは :- (.cpp が最初) になります。

for (int i=0; i<65535; i++) {
  for (int j=0; j<65535; j++) {
    result+=obj->f();
  }
}

さて、.obj :-

400a54:       bb fe ff 00 00          mov    $0xfffe,%ebx
400a59:       66                      data16                                                    
400a5a:       66                      data16 
400a5b:       66                      data16                                                    
400a5c:       90                      nop                                                       
400a5d:       66                      data16                                                    
400a5e:       66                      data16                                                    
400a5f:       90                      nop                                                       
400a60:       48 8b 45 00             mov    0x0(%rbp),%rax                                     
400a64:       48 89 ef                mov    %rbp,%rdi                                          
400a67:       ff 10                   callq  *(%rax)
400a69:       48 98                   cltq   
400a6b:       49 01 c4                add    %rax,%r12                                          
400a6e:       ff cb                   dec    %ebx                                               
400a70:       79 ee                   jns    400a60 <main+0x70>                                 
400a72:       41 ff c5                inc    %r13d                                              
400a75:       41 81 fd fe ff 00 00    cmp    $0xfffe,%r13d
400a7c:       7e d6                   jle    400a54 <main+0x64>                          

したがって、Mysticial が指摘しているように、実際には偽のエイリアシングが原因ではなく、単にコンパイラ/リンカーが発行しているこれらの NOP が原因であると言わざるを得ません。

両方の場合のアセンブリは次のとおりです:-

.L30:
        movl    $65534, %ebx
        .p2align 4,,7                   
.L29:
        movq    (%rbp), %rax            
        movq    %rbp, %rdi
        call    *(%rax)
        cltq    
        addq    %rax, %r12                                                                        
        decl    %ebx
        jns     .L29
        incl    %r13d 
        cmpl    $65534, %r13d
        jle     .L30

ここで、.p2align 4,,7 は、次の命令の命令カウンターが最大 7 つの NOP に対して最後の 4 ビット 0 を持つまで、データ/NOP を挿入します。cout を使用しない場合の p2align の直後で、パディングの前の命令のアドレスは次のようになります。

0x400a59 = 0b101001011001

そして、次の命令をアラインするのに 7 以下の NOP が必要なので、実際にはオブジェクト ファイルでアラインします。

一方、cout の場合、.p2align の直後の命令は

0x400932 = 0b100100110010

16 で割り切れる境界までパディングするには、> 7 個の NOP が必要です。したがって、それはしません。

したがって、余分な時間がかかるのは、-O2 フラグを使用してコンパイルするときに、コンパイラがコードに (より適切なキャッシュの配置のために) パディングする NOP によるものであり、実際には偽のエイリアシングによるものではありません。

これで問題は解決すると思います。私はhttp://sourceware.org/binutils/docs/as/P2align.html を .p2align が実際に行うことのリファレンスとして使用しています。

于 2012-05-07T15:30:21.973 に答える
5

この答えはさらに推測的です。

これを5分間いじってMysticialsの回答を読んだ後、結論はハードウェアの問題であるということです.ホットループで生成されたコードは基本的に同じであるため、コンパイラの問題ではなく、ハードウェアを唯一の容疑者。

いくつかのランダムな考え:

  • 分岐予測
  • 分岐 (=関数) ターゲット アドレスのアライメントまたは部分的なエイリアシング
  • 常に同じアドレスを読み取った後、L1 キャッシュが過熱する
  • 宇宙線
于 2012-05-04T00:22:57.060 に答える
1

現在のコードでは、コンパイラは への呼び出しを自由に非仮想化できます。これは、 以外の動的な型を持つことができないためobj->f()です。objclass B

私は提案します

if (a>3) {
    B* objb = new B();
    objb->a = 5;
    obj = objb;
}
else
    obj = new A();
于 2012-05-03T20:52:54.083 に答える
0

私の推測では、関係class B : public dummy, public Aする限り、不利な属性を持ってAいます。16 バイトにパディングdummyして、違いがあるかどうかを確認します。

于 2012-05-03T20:51:58.027 に答える