Снижение производительности при поиске vtable в C++

Что заставляет вас думать, что накладные расходы на поиск в 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]);                                         
}       

Код С++:

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

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

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

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

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

Как уже упоминалось, вы можете использовать шаблоны, чтобы избавиться от динамической отправки. Вот пример, который делает это:

template <typename FirstCb, typename ... RestCb>
struct InterruptHandler {
    void execute() {
        // I construct temporary objects here since I could not figure out how you
        // construct your objects. You can change these signatures to allow for 
        // passing arbitrary params to these handlers.
        FirstCb().execute();
        InterruptHandler<RestCb...>().execute();
    }
}

InterruptHandler</* Base, Derived1, and so on */> handler;

void realtime(void) {
    handler.execute();
}

Это должно полностью исключить поиск в vtable, предоставляя больше возможностей для оптимизации компилятора, поскольку код внутри execute может быть встроен.

Однако обратите внимание, что вам нужно будет изменить некоторые части в зависимости от того, как вы инициализируете свои обработчики. Базовая структура должна остаться прежней. Кроме того, для этого требуется компилятор, совместимый с C++11.

Я предлагаю использовать статические методы в ваших производных классах и помещать эти функции в ваш массив. Это устранило бы накладные расходы на поиск в v-таблице. Это ближе всего к вашей реализации на языке C.

В конечном итоге вы можете пожертвовать полиморфизмом ради скорости.
Необходимо ли наследование?
Тот факт, что вы переходите на C++, не означает, что вы должны переключиться на объектно-ориентированный.

Кроме того, пробовали ли вы развернуть свой цикл в ISR?
Например, выполните 2 или более вызовов выполнения, прежде чем вернуться к началу цикла.

Кроме того, можете ли вы перенести какую-либо функциональность из ISR? Может ли какая-то часть функционала выполняться "фоновым циклом" вместо ISR? Это уменьшит время в вашем ISR.

Вы можете скрыть стирание типа void* и восстановить тип внутри шаблонов. Результатом будет (надеюсь) тот же массив для указателей на функции. Эта помощь с приведением и совместимостью с вашим кодом:

#include <iostream>

template<class ParamType,class F>
void fun(void* param) {
  F f;
  f(*static_cast<ParamType*>(param));
}

struct my_function {
  void operator()(int& i) {
    std::cout << "got it " << i << std::endl;
  }
};


int main() {
  void (*func)(void*) = fun<int, my_function>;

  int j=4;
  func(&j);

  return 0;
}

В этом случае вы можете создавать новые функции как объект функции с более безопасным типом. «Обычный» подход ООП с виртуальными функциями здесь не помогает.

В случае среды C++11 вы можете создать массив с помощью вариативных шаблонов во время компиляции (но со сложным синтаксисом).

Это не связано с вашим вопросом, но если вы заинтересованы в производительности, вы можете использовать шаблоны для развертывания цикла для списка задач:

void (*todo[3])(void *);
void *param[3];

void f1(void*) {std::cout<<"1" << std::endl;}
void f2(void*) {std::cout<<"2" << std::endl;}
void f3(void*) {std::cout<<"3" << std::endl;}

template<int N>
struct Obj {
    static void apply()
    {
        todo[N-1](param[N-1]);
        Obj<N-1>::apply();
    }
};

template<> struct Obj<0> { static void apply() {} };

todo[0] = f1;
todo[1] = f2;
todo[2] = f3;

Obj<sizeof todo / sizeof *todo>::apply();

Узнайте, куда ваш компилятор помещает виртуальную таблицу, и получите к ней прямой доступ, чтобы получить указатели на функции и сохранить их для использования. Таким образом, у вас будет почти тот же подход, что и в C, с массивом указателей на функции.