Самая быстрая реализация простого виртуального шаблона типа наблюдателя на с ++?

Как сказано в первом комментарии, у вас есть проблема XY. Сортировка / переупорядочение в порядке, и у вас много объектов, а не огромное количество разных классов, и нет необходимости поддерживать типы, о которых ваш код не знает во время компиляции. Полиморфизм + виртуальное наследование - неправильный выбор.

Вместо этого используйте N разных контейнеров, по одному для каждого типа объекта, без косвенного обращения. Разрешить компилятору встроить B::Update() в цикл по всем B объектам намного лучше. (Для тривиального примера увеличения одного члена int, приведенного ниже, мой статический анализ производительности при просмотре asm показывает, что он примерно в 24 раза быстрее на Skylake с горячими данными в кеше L1D. Автоматическая векторизация AVX2 по сравнению с call в цикле - это действительно то, что огромный.)

Если бы между объектами существовал некоторый требуемый порядок, в том числе между разными типами объектов, тогда был бы уместен какой-то полиморфизм или отправка вручную. (например, если бы имело значение, в каком порядке вы обрабатываете vecA, сохранение всех объектов B отдельно от всех объектов C не было бы эквивалентным.)

Если вы заботитесь о производительности, вы должны понимать, что увеличение размера исходного кода может упростить вещи для компилятора / в выводе asm. Проверка / диспетчеризация на основе типа каждого объекта во внутреннем цикле обходится дорого. Использование любого типа указателя на функцию или перечисления для диспетчеризации для каждого объекта может легко привести к ошибочным прогнозам ветвления, если у вас есть смесь разных предметов.

Зацикливание по отдельности по нескольким контейнерам эффективно выводит проверку типа из внутреннего цикла и позволяет компилятору девиртуализировать. (Или, лучше, сжимает каждый объект, чтобы в первую очередь не нуждаться в указателе vtable, перечислении или указателе функции, поскольку его тип известен статически.)

Написание отдельного цикла для каждого контейнера с другим типом похоже на полное развертывание цикла для разных типов после поднятия диспетчеризации типа из внутреннего цикла. Это необходимо для компилятора, чтобы встроить вызовы, что вы хотите, если имеется много объектов каждого типа. Встраивание позволяет сохранять константы в регистрах между объектами, обеспечивает автоматическую векторизацию SIMD для нескольких объектов и просто позволяет избежать накладных расходов на фактический вызов функции. (И сам вызов, и сброс / перезагрузка регистров.)

Вы были правы в том, что вам действительно нужна отправка для каждого объекта, виртуальные функции C ++ - дорогой способ получить это, когда вы используете final переопределения. Вы платите те же затраты времени выполнения, которые позволили бы вашему коду поддерживать новые производные классы произвольного размера, о которых он не знал во время компиляции, но не получаете от этого никакой выгоды.

Виртуальная отправка работает только с уровнем косвенности (например, вектор указателей, как вы используете), что означает, что вам нужно каким-то образом управлять указанными объектами, например выделив их из vector<B> poolB и vector<C> poolC. Хотя я не уверен, что большинство реализаций vector<> используют realloc(), когда им нужно расти; у new/delete API нет realloc, поэтому vector может фактически копировать каждый раз, когда он растет, вместо того, чтобы пытаться расширить существующее выделение на месте. Проверьте, что делает ваша реализация C ++, поскольку она может показаться отстойной по сравнению с тем, что вы можете сделать с помощью malloc / realloc.

И, кстати, должно быть возможно выполнять _16 _ / _ 17_ с RAII без дополнительных накладных расходов на выделение / освобождение, если все ваши классы тривиально разрушаемы. (Но обратите внимание, что unique_ptr может помешать другим оптимизациям для использования вектор указателей). std::unique_ptr предупреждает, что UB уничтожает его через указатель на базовый класс, так что вам, возможно, придется свернуть свой собственный. Тем не менее, в gcc на x86-64 sizeof(unique_ptr<class C>) всего 8, поэтому он имеет только один член-указатель. Но что бы то ни было, раздельное размещение миллиардов крошечных объектов - отстой, так что не делайте этого в первую очередь.

Сравнение накладных расходов:

Если все объекты одинакового размера, тогда вы действительно хотите перебирать объекты, а не указатели на объекты. Это позволило бы избежать лишнего следа в кэше вектора указателей и избежать дополнительной задержки при поиске указателей, которую неупорядоченное выполнение должно скрывать, чтобы загружать исполнительные блоки. ' т. См. Продолжение @ BeeOnRope: Непрерывное хранилище полиморфных типов. (Также более старые вопросы и ответы: C ++ полиморфизм объекта в массиве ).

C ++ 17 std::visit с std::variant<B, C> (с использованием невиртуального наследования для B и C), кажется, дает вам отправку на основе внутреннего enum. std::visit использует свою собственную таблицу переходов для диспетчеризации, даже с двумя возможными типами, вместо того, чтобы встраивать их оба и использовать условную ветвь. Он также должен постоянно проверять состояние "неинициализировано". Вы можете получить хороший код , если вручную обойдете это с помощью B *tmp = std::get_if<B>(&my_variant) и __builtin_unreachable(), чтобы сообщить gcc, что nullptr невозможен. Но в этот момент вы можете просто запустить свой собственный struct polymorph { enum type; union { B b; C c; }; }; (с невиртуальными функциями), если вам не нужно «неинициализированное» состояние. Связано: C ++ полиморфизм объекта в массиве.

В этом случае у вас есть только одна функция, поэтому вы можете поместить указатель на функцию внутри каждого объекта как члена. Вроде void (*m_update)(A* this_object). В вызывающей программе передайте указатель на объект как void* или A*, поскольку это функция, не являющаяся членом. Реализация функции будет reinterpret_cast<C*>(this_object). (Не dynamic_cast: мы сами занимаемся диспетчеризацией, а не используем C ++).

Если вы хотите использовать B и C в других контекстах, где член указателя на функцию будет бесполезно занимать место, вы можете сохранить указатели на функции в отдельном контейнере, а не в базовом классе. Так было бы for(i=0..n) funcptrs[i]( &objects[i] );. Пока ваши контейнеры не рассинхронизируются, вы всегда передаете указатель на функцию, которая знает, что с ней делать. Используйте это с union {B b; C c} objects[] (или vector<union>).

Вы можете использовать void*, если хотите, особенно если вы создаете отдельный массив указателей на функции. Тогда членам союза не нужно наследовать от общей базы.

Вы можете использовать std::function<> для хранения указателей на функции-члены экземпляра, но в gcc x86-64 это 32-байтовый объект. Для вашего места в кэше лучше использовать только 8-байтовые обычные указатели на функции и писать код, который знает, что нужно передавать явный указатель, эквивалентный указателю this.

Размещение указателя функции в каждом объекте может занять больше места, чем enum или uint8_t, в зависимости от текущего размера / выравнивания. Небольшой целочисленный индекс в таблице указателей функций может уменьшить размер каждого экземпляра ваших объектов по сравнению с элементом указателя, особенно для 64-битных целей. Меньшие объекты могут легко стоить пары дополнительных инструкций для индексации массива указателей на функции и, возможно, более высокого штрафа за неправильный прогноз из-за дополнительного разыменования указателя. Промахи памяти / кеша часто являются узким местом.

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

Виртуальная диспетчеризация C ++:

Я взглянул на сгенерированный компилятором asm (gcc и clang, нацеленный на x86-64), чтобы найти несколько способов сделать это.

clang и gcc автоматически векторизуют цикл по vecB с помощью AVX2 для параллельной обработки 8 int элементов, поэтому, если вы не ограничиваете пропускную способность памяти (например, горячую в кэше L1D), этот цикл может увеличиваться на 8 элементов за такт. Этот цикл выполняется так же быстро, как и цикл над vector<int>; все встраивается и оптимизируется, и это просто приращение указателя.

class A{
    public:
    virtual void Update() = 0; // A is so pure *¬*
};

struct C : public A {
    int m_c = 0;
    public:
    void Update() override final
    {  m_c++;  }
};
int SC = sizeof(C);  // 16 bytes because of the vtable pointer

C global_c;  // to instantiate a definition for C::Update();

// not inheriting at all gives equivalent asm to making Update non-virtual
struct nonvirt_B //: public A
{
    int m_b = 0;
    void Update() //override final
    {  m_b++;  }
};
int SB = sizeof(nonvirt_B);  // only 4 bytes per object with no vtable pointer

void separate_containers(std::vector<nonvirt_B> &vecB, std::vector<C> &vecC)
{
    for(auto &b: vecB)        b.Update();
    for(auto &c: vecC)        c.Update();   
}

Цикл над vecC может выполнять только 1 элемент за такт, потому что каждый объект имеет размер 16 байтов (8-байтовый указатель vtable, 4 байта int m_c, 4 байта заполнения до следующей границы выравнивания, потому что указатель имеет Требование выравнивания 8B.) Без final компилятор также проверяет указатель vtable, чтобы увидеть, действительно ли это C, прежде чем использовать встроенный C::Update(), в противном случае он отправляет. Это похоже на то, что вы получили бы за цикл по struct { int a,b,c,d; } vecC[SIZE];, выполняя vecC[i].c++;

final разрешена полная девиртуализация, но наши данные смешаны с указателями vtable, поэтому компиляторы просто делают скаляр add [mem], 1, который может работать только с частотой 1 за такт (узким местом является пропускная способность хранилища 1 за такт, независимо от размера хранилища, если он горячий в кеше L1D ). Это в основном побеждает SIMD в этом примере. (С -march=skylake-avx512, gcc и clang выполняют нелепое перемешивание или сбор / разброс, которое даже медленнее, чем скаляр, вместо простой загрузки / восстановления всего объекта и добавления с помощью вектора, который изменяет только член int. Это разрешено, потому что он не содержит любые изменчивые или атомарные элементы, и будет запускать 2 за такт с AVX2 или 4 за такт с AVX512.) Наличие ваших объектов размером до 12 байт является серьезным недостатком, если они маленькие, а у вас их много.

При наличии нескольких членов на объект это не обязательно побеждает SIMD, но по-прежнему требует места в каждом объекте, как это было бы с перечислением или указателем на функцию.

Поскольку вы упомянули теорему о разделяющей оси, надеюсь, вы не планируете хранить float x,y пары в каждом объекте. Массив структур в основном отстой для SIMD, потому что для использования x с y для одного и того же объекта требуется много перетасовки. Вам нужно std::vector<float> x, y или подобное, чтобы ваш ЦП мог загрузить 4 значения x в регистр и 4 значения y в другой регистр. (Или 8 одновременно с AVX).

std::vector<A*> vecA{};

void vec_virtual_pointers() {
    for(auto a: vecA)
        a->Update();
}

   # rbx = &vecA[0]
.LBB2_1:                         # do{
    mov     rdi, qword ptr [rbx]   # load a pointer from the vector (will be the this pointer for Update())
    mov     rax, qword ptr [rdi]   # load the vtable pointer
    call    qword ptr [rax]        # memory-indirect call using the first entry in the vtable
    add     rbx, 8                 # pointers are 8 bytes
    cmp     r14, rbx
    jne     .LBB2_1              # }while(p != vecA.end())

C::Update():                         # @C::Update()
    inc     dword ptr [rdi + 8]
    ret

union upoly {
    upoly() {}   // needs an explicit constructor for compilers not to choke
     B b;
     C c;
} poly_array[1024];

void union_polymorph() {
    upoly *p = &poly_array[0];
    upoly *endp = &poly_array[1024];
    for ( ; p != endp ; p++) {
        A *base = reinterpret_cast<A*>(p);
        base->Update();           // virtual dispatch
    }
}

    lea     rdi, [rbx + poly_array]       ; this pointer
    mov     rax, qword ptr [rbx + poly_array]   ; load it too, first "member" is the vtable pointer
    call    qword ptr [rax]
    add     rbx, 16                       ; stride is 16 bytes per object
    cmp     rbx, 16384                    ; 16 * 1024
    jne     .LBB4_1

#include <functional>
// pretty crappy: checks for being possibly unset to see if it should throw().
std::vector<std::function<void()>> vecF{};
void vec_functional() {
    for(auto f: vecF)     f();
}

                                # do {
.LBB6_2:                                # =>This Inner Loop Header: Depth=1
    mov     qword ptr [rsp + 16], 0       # store a 0 to a local on the stack?
    mov     rax, qword ptr [rbx + 16]
    test    rax, rax
    je      .LBB6_5           # throw on pointer==0  (nullptr)
    mov     edx, 2            # third arg:  2
    mov     rdi, r14          # first arg: pointer to local stack memory (r14 = rsp outside the loop)
    mov     rsi, rbx          # second arg: point to current object in the vector
    call    rax               # otherwise call into it with 2 args
    mov     rax, qword ptr [rbx + 24]    # another pointer from the std::function<>
    mov     qword ptr [rsp + 24], rax    # store it to a local
    mov     rcx, qword ptr [rbx + 16]    # load the first pointer again
    mov     qword ptr [rsp + 16], rcx
    test    rcx, rcx
    je      .LBB6_5           # check the first pointer for null again (and throw if null)
    mov     rdi, r14
    call    rax               # call through the 2nd pointer
    mov     rax, qword ptr [rsp + 16]
    test    rax, rax
    je      .LBB6_12          # optionally skip a final call
    mov     edx, 3
    mov     rdi, r14
    mov     rsi, r14
    call    rax
.LBB6_12:                               #   in Loop: Header=BB6_2 Depth=1
    add     rbx, 32
    cmp     r15, rbx
    jne     .LBB6_2

.LBB6_13:                       # return
    add     rsp, 32
    pop     rbx
    pop     r14
    pop     r15
    ret

.LBB6_5:
    call    std::__throw_bad_function_call()
    jmp     .LBB6_16
    mov     rdi, rax
    call    __clang_call_terminate