Подтвердить что ты не робот

Почему я наблюдаю за множественным наследованием быстрее одного?

У меня есть следующие два файла: -

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";
}

Я использую gcc версии 3.4.6 с флагами -O2

И это результаты таймингов, которые я получаю: -

несколько: -

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

single: -

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

С другой стороны, если в multiple.cpp я инвертирую порядок вывода класса таким образом: -

class B : public dummy, public A {

Затем я получаю следующие тайминги (которые немного медленнее, чем для одиночного наследования, как можно было бы ожидать благодаря настройкам "thunk" для этого указателя, который должен выполнить код): -

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

Любая идея, почему это может произойти? Кажется, что нет никакой разницы в сборке, сгенерированной для всех трех случаев, в отношении цикла. Есть ли другое место, на которое мне нужно посмотреть?

Кроме того, я привязал процесс к конкретному ядру процессора, и я запускаю его в режиме реального времени с SCHED_RR.

EDIT: - Это было замечено Mystical и воспроизведено мной. Выполнение

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

как раз перед тем, как цикл в single.cpp приведет к тому, что он также будет таким же быстрым, как и множественный такт в 8,4 с, как открытый публичный макет A.

4b9b3361

Ответ 1

Думаю, я получил хотя бы некоторое продолжение, почему это может произойти. Сборка для петель точно идентична, но объектные файлы нет!

Для цикла с 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>                          

Поэтому я должен сказать, что это не из-за ложного псевдонима, как указывает Mystical, а просто из-за этих 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, пока счетчик команд для следующей команды не будет иметь последние четыре бита 0 для максимум 7 NOP. Теперь адрес инструкции сразу после p2align в случае без cout и перед заполнением будет

0x400a59 = 0b101001011001

И поскольку для выравнивания следующей команды требуется <= 7 NOP, она фактически сделает это в объектном файле.

С другой стороны, для случая с cout инструкция сразу после .p2align приземляется на

0x400932 = 0b100100110010

и потребовалось бы > 7 NOP, чтобы поместить его на границу с делимыми на 16. Следовательно, он этого не делает.

Таким образом, дополнительное время просто связано с NOP, что компилятор подставляет код с (для лучшего выравнивания кеша) при компиляции с флагом -O2 и на самом деле не из-за ложного сглаживания.

Я думаю, что это решает проблему. Я использую http://sourceware.org/binutils/docs/as/P2align.html как моя ссылка на то, что делает .p2align.

Ответ 2

Обратите внимание: этот ответ является весьма спекулятивным.

В отличие от некоторых других моих ответов на вопросы типа "Почему X медленнее Y", я не смог предоставить убедительные доказательства для резервного копирования этого ответа.


После того, как я занялся этим около часа, я думаю, что это связано с выравниванием адреса из трех вещей:

(owagh answer также указывает на возможность выравнивания команд.)

Причина, по которой множественное наследование происходит медленнее, чем одиночное наследование, происходит не потому, что оно "волшебно" быстро, а потому, что случай одиночного наследования запущен либо в компиляторе, либо в аппаратном "икоте".


Если вы выгружаете сборку для одного и нескольких случаев наследования, они идентичны (имена регистров и все) внутри вложенного цикла.

Здесь код, который я скомпилировал:

#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 секунды

Ответ 3

Этот ответ еще более спекулятивен.

После того, как он провел 5 минут и прочитал ответы Mysticals, вывод состоит в том, что это аппаратная проблема: код, созданный в горячем цикле, в основном тот же, поэтому это не проблема с компилятором, который оставляет аппаратное обеспечение единственным подозреваемым.

Некоторые случайные мысли:

  • Прогнозирование ветвей
  • Выравнивание или частичное сглаживание адресных адресов ветки (= функции)
  • Кэш L1 работает горячим после прочтения одного и того же адреса все время
  • Космические лучи

Ответ 4

С вашим текущим кодом компилятор может девиртуализировать вызовы obj->f(), так как obj не может иметь никакого динамического типа, кроме class B.

Я предлагаю

if (a>3) {
    B* objb = new B();
    objb->a = 5;
    obj = objb;
}
else
    obj = new A();

Ответ 5

Моя догадка class B : public dummy, public A имеет неблагоприятное выравнивание до A. Pad dummy до 16 байтов и посмотреть, есть ли разница.