Повышение производительности поиска в vtable в Stack Overflow

Что заставляет вас думать, что поиск vtable составляет 20 циклов? Если это действительно так, вам нужен лучший компилятор C ++.

Я попытался сделать это на корпусе Intel, ничего не зная о процессоре, который вы используете, и, как и ожидалось, разница между кодом отправки C и отправкой vtable C ++ — это одна инструкция, связанная с тем фактом, что vtable включает в себя дополнительный косвенные.

Код C (на основе OP):

void (*todolist[200])(void *parameters);
void *paramlist[200];
void realtime(void)
{
int i;
for (i = 0; i < 200; i++)
(*todolist[i])(paramlist[i]);
}

Код C ++:

class Base {
public:
Base(void* unsafe_pointer) : unsafe_pointer_(unsafe_pointer) {}
virtual void operator()() = 0;
protected:
void* unsafe_pointer_;
};

Base* todolist[200];
void realtime() {
for (int i = 0; i < 200; ++i)
(*todolist[i])();
}

Оба скомпилированы с gcc 4.8, -O3:

realtime:                             |_Z8realtimev:
.LFB0:                                |.LFB3:
.cfi_startproc                |        .cfi_startproc
pushq   %rbx                  |        pushq   %rbx
.cfi_def_cfa_offset 16        |        .cfi_def_cfa_offset 16
.cfi_offset 3, -16            |        .cfi_offset 3, -16
xorl    %ebx, %ebx            |        movl    $todolist, %ebx
.p2align 4,,10                |        .p2align 4,,10
.p2align 3                    |        .p2align 3
.L3:                                  |.L3:
movq    paramlist(%rbx), %rdi |        movq    (%rbx), %rdi
call    *todolist(%rbx)       |        addq    $8, %rbx
addq    $8, %rbx              |        movq    (%rdi), %rax
|        call    *(%rax)
cmpq    $1600, %rbx           |        cmpq    $todolist+1600, %rbx
jne     .L3                   |        jne     .L3
popq    %rbx                  |        popq    %rbx
.cfi_def_cfa_offset 8         |        .cfi_def_cfa_offset 8
ret                           |        ret

В коде C ++ первый movq получает адрес виртуальной таблицы, а call затем индексирует через это. Так что это одна инструкция накладных расходов.

Согласно OP, компилятор C ++ DSP производит следующий код. Я вставил комментарии, основанные на моем понимании того, что происходит (что может быть неправильно). Обратите внимание, что (IMO) цикл начинается на одну позицию раньше, чем указывает OP; в противном случае это не имеет смысла (для меня).

# Initialization.
# i3=todolist; i5=paramlist           | # i5=todolist holds paramlist
i3=0xb27ba;                           | # No paramlist in C++
i5=0xb28e6;                           | i5=0xb279a;
# r15=count
r15=0xc8;                             | r15=0xc8;

# Loop. We need to set up r4 (first parameter) and figure out the branch address.
# In C++ by convention, the first parameter is 'this'
# Note 1:
r4=dm(i5,m6); # r4 = *paramlist++;    | i5=modify(i5,m6); # i4 = *todolist++
| i4=dm(m7,i5);     # ..
# Note 2:
| r2=i4;            # r2 = obj
| i4=dm(m6,i4);     # vtable = *(obj + 1)
| r1=dm(0x3,i4);    # r1 = vtable[3]
| r4=r2+r1;         # param = obj + r1

i12=dm(i3,m6); # i12 = *todolist++;   | i12=dm(0x5,i4);   # i12 = vtable[5]

# Boilerplate call. Set frame pointer, push return address and old frame pointer.
# The two (push) instructions after jump are actually executed before the jump.
r2=i6;                                | r2=i6;
i6=i7;                                | i6=i7;
jump (m13,i12) (db);                  | jump (m13,i12) (db);
dm(i7,m7)=r2;                         | dm(i7,m7)=r2;
dm(i7,m7)=0x1279de;                   | dm(i7,m7)=0x1279e2;

# if (count--) loop
r15=r15-1;                            | r15=r15-1;
if ne jump (pc, 0xfffffff2);          | if ne jump (pc, 0xffffffe7);

Заметки:

1. В версии C ++ кажется, что компилятор решил выполнить постинкремент в два этапа, предположительно потому, что он хочет получить результат в i зарегистрироваться, а не в r4, Это, несомненно, связано с проблемой ниже.

2. Компилятор решил вычислить базовый адрес реального класса объекта, используя vtable объекта. Это занимает три инструкции, и, вероятно, также требует использования i4 как временное на шаге 1. Сам поиск vtable занимает одну инструкцию.

Итак: проблема не в vtable lookup, который мог бы быть выполнен в одной дополнительной инструкции (но на самом деле требуется две). Проблема в том, что компилятор чувствует необходимость «найти» объект. Но почему gcc / i86 не должен этого делать?

Ответ: раньше, но больше нет. Во многих случаях (например, при отсутствии множественного наследования) приведение указателя к производному классу к указателю базового класса не требует изменения указателя. Следовательно, когда мы вызываем метод производного класса, мы можем просто дать ему указатель базового класса в качестве его this параметр. Но в других случаях это не работает, и мы должны настроить указатель, когда мы выполняем приведение, и, следовательно, отрегулировать его обратно, когда мы сделаем вызов.

Есть (как минимум) два способа выполнить вторую настройку. Одним из них является способ, показанный сгенерированным кодом DSP, где корректировка сохраняется в виртуальной таблице — даже если она равна 0 — и затем применяется во время вызова. Другой способ, (называется vtable-thunks) это создать thunk — немного исполняемого кода — который регулирует this Указатель, а затем переходит к точке входа метода и помещает указатель на этот блок в виртуальную таблицу. (Все это можно сделать во время компиляции.) Преимущество решения Thunk состоит в том, что в общем случае, когда не требуется выполнять настройку, мы можем оптимизировать Thunk, и код настройки не остался. (Недостатком является то, что если нам нужна корректировка, мы создали дополнительную ветку.)

Насколько я понимаю, VisualDSP ++ основан на gcc и может иметь -fvtable-thunks а также -fno-vtable-thunks опции. Таким образом, вы можете скомпилировать с -fvtable-thunks, Но если вы сделаете это, вам нужно будет скомпилировать все библиотеки C ++, которые вы используете с этой опцией, потому что вы не можете смешивать два стиля вызова. Кроме того (15 лет назад) были различные ошибки в реализации vcc-thunks для gcc, поэтому, если версия gcc, используемая VisualDSP ++, достаточно старая, вы можете столкнуться и с этими проблемами (IIRC, они все включали множественное наследование, поэтому они могли бы не относится к вашему случаю использования.)

(Оригинальный тест, перед обновлением):

Я попробовал следующий простой случай (без множественного наследования, которое может замедлить процесс):

class Base {
public:
Base(int val) : val_(val) {}
virtual int binary(int a, int b) = 0;
virtual int unary(int a) = 0;
virtual int nullary() = 0;
protected:
int val_;
};

int binary(Base* begin, Base* end, int a, int b) {
int accum = 0;
for (; begin != end; ++begin) { accum += begin->binary(a, b); }
return accum;
}

int unary(Base* begin, Base* end, int a) {
int accum = 0;
for (; begin != end; ++begin) { accum += begin->unary(a); }
return accum;
}

int nullary(Base* begin, Base* end) {
int accum = 0;
for (; begin != end; ++begin) { accum += begin->nullary(); }
return accum;
}

И скомпилировал его с помощью gcc (4.8), используя -O3. Как я и ожидал, он произвел точно такой же ассемблерный код, как и ваша C-отправка. Вот for петля в случае unary функция, например:

.L9:
movq    (%rbx), %rax
movq    %rbx, %rdi
addq    $16, %rbx
movl    %r13d, %esi
call    *8(%rax)
addl    %eax, %ebp
cmpq    %rbx, %r12
jne     .L9