2012-05-03 3 views
40

У меня есть следующие два файла: -Почему я наблюдаю за множественным наследованием быстрее одного?

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 

одного: -

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

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

class B : public dummy, public A { 

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

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

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

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

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

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

непосредственно перед тем, петля в single.cpp приводит выделить также быть так же быстро, как множественные с тактовой частотой 8,4 х так же, как общественные, общественной соска.

+0

+1 для хорошо сформулированного, интересного вопроса. –

+0

Я бы не ожидал, что скорость целочисленной арифметики будет зависеть от значений (конечно, с плавающей запятой), но установите «obj-> a» на согласованное значение, чтобы убедиться. –

+0

Установка его на 5. Принимая это как ввод, но да, это 5 для всех окон. Но, как вы сами указываете, это не имеет значения. – owagh

ответ

14

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

Для цикла с соиЬ в первом (т.е.)

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>         

Однако без соиЬ, петли становятся: - (.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>       

Поэтому я должен сказать, что это не связано с ложным псевдонимом, поскольку 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 НОП. Теперь адрес инструкции сразу после p2align в случае без соиЬ и до заполнения будет

0x400a59 = 0b101001011001 

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

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

0x400932 = 0b100100110010 

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

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

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

+0

+1 Мне это нравится. Я также рассмотрел возможность выравнивания инструкций. Но я не смог проверить это. – Mysticial

0

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

+1

Я думаю, что часть ожидалась. Проблема заключается в разнице во времени между «классом B: public A» и «class B: public A, public dummy» в пользу множественного наследования. –

+0

Да, это было понято: «как можно было бы ожидать благодаря настройкам« thunk ». – Joe

+0

ok, не знал, что означал «thunk» – Anycorn

1

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

Я предлагаю

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

Почему не может быть «А»? – David

+0

Потому что нет никакого заявления? – owagh

+0

О, я вижу. Умный компилятор - не знал, что он может это сделать. – David

25

Примечание, этот ответ является спекулятивной.

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


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

(owagh's 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 

Однако разница в производительности я вижу это:

  • Single: 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().


Это просто случается, что в одном примере наследования, смещение указанных выше значений не является благоприятным для процессора. Понятия не имею почему. Но я должен был что-то заподозрить, это были бы конфликты с кеш-банками аналогично region 2 in the diagram of this question.

Переставив код и добавив фиктивные функции, я могу изменить эти смещения, что во многих случаях устранит это замедление и сделает единое наследование столь же быстрым, как и случай множественного наследования.


Например, удаление 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 секунды
  • Multiple: 9,4 секунды
+2

Я не думаю, что виноваты конфликты банков кэша, кеш команд принципиально отличается от данных L1 (предварительное кодирование, границы команд и т. Д.). Я предпочел бы, чтобы что-то странное происходило с предсказанием ветвления или выравниванием функций, но это еще более спекулятивный – hirschhornsalz

+0

Да, это было, очевидно, просто дикое предположение. Трудно проверить что-либо, потому что любая модификация кода изменит все смещения. – Mysticial

+0

Думаю, если бы вы могли приостановить выполнение и проверить текущий код в памяти (что-то вроде игрового тренера), что может вам помочь? – owagh

5

Этот ответ канун n более спекулятивный.

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

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

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

+1 для космических лучей ... – owagh

+0

Можете ли вы рассказать о том, что вы подразумеваете под выравниванием или частичным наложением и как это может повлиять на вещи «L1 cache running hot должен на самом деле сделать это быстрее, чем медленнее?» – owagh

+0

@owagh [Этот вопрос, который я связал с] (http://stackoverflow.com/questions/8547778/why-is-one-loop-so-much- более медленные, чем два-петли) из моего ответа, вероятно, является самым известным примером в StackOverflow, где выравнивание и частичное сглаживание могут снизить производительность. Таким образом, это может быть хорошо прочитано. Как это относится к вашему вопросу, неясно. гипотеза требует изменения кода, который сдвинет выравнивание всего. Таким образом, это движущаяся цель, на которую я не могу попасть. (как я показал, комментируя ненужную строку кода, чтобы инвертировать номера производительности ...) – Mysticial

Смежные вопросы