为什么我观察多重继承比单一更快？

Question

我有以下两个文件: -

single.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指针的'thunk'调整): -

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

知道为什么会这样吗？就循环而言,就所有三种情况生成的汇编似乎没有任何差别.还有其他一些我需要看的地方吗？

此外,我已将进程绑定到特定的cpu核心,并且我使用SCHED_RR以实时优先级运行它.

编辑: - 这是由Mysticial注意到并由我复制.做一个

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

就在single.cpp中的循环之前导致单个也像8.4中的多个时钟一样快,就像公共A,公共虚拟.

Answer 1

请注意,这个答案是高度推测的.

与我对"为什么X比Y慢"这类问题的其他答案不同,我一直无法提供可靠的证据来支持这个答案.

经过大约一个小时的修补,我认为这是由于三件事的地址对齐:

• 的地址 obj
• 虚拟方法表的地址A
• 功能的地址 f()

(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秒

Answer 2

我想我至少还有一些关于为什么会发生这种情况的进一步领导.循环的程序集完全相同,但目标文件不是!

对于首先使用cout的循环(即)

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

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将插入数据/ NOP,直到下一条指令的指令计数器最后4位为0,最多7个NOP.现在,在没有cout和填充之前的p2align之后的指令的地址将是

0x400a59 = 0b101001011001

并且因为它需要<= 7个NOP来对齐下一条指令,所以它实际上会在目标文件中这样做.

另一方面,对于cout的情况,紧跟在.p2align之后的指令着陆

0x400932 = 0b100100110010

并且需要> 7个NOP才能将其填充到可被16个边界整除的位置.因此,它不会那样做.

因此,所花费的额外时间仅仅是由于编译器使用-O2标志编译时编译器填充的NOP(用于更好的高速缓存对齐)而不是由于错误的别名.

我认为这解决了这个问题.我使用http://sourceware.org/binutils/docs/as/P2align.html 作为我对.p2align实际做什么的参考.

Answer 3

这个答案更具有推测性.

经过5分钟修补并阅读Mysticials回答后,得出的结论是硬件问题:热循环中生成的代码基本相同,因此编译器不会出现问题,导致硬件保持不变唯一的嫌疑人.

一些随意的想法:

• 分支预测
• 分支(=函数)目标地址的对齐或部分别名
• L1缓存一直在读取相同的地址后运行热
• 宇宙射线