Почему я наблюдаю за множественным наследованием быстрее одного?
У меня есть следующие два файла: -
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.
Ответы
Ответ 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 байтов и посмотреть, есть ли разница.
