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

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

class B: public A
{
override void Update() final
{
// DO B STUFF
}
}

class C: public A
{
override void Update() final
{
// DO C STUFF
}
}

// class...

int main()
{
std::vector<A*> vecA{};

// Insert instances of B, C, ..., into vecA

for(auto a: vecA) // This for will be inside a main loop
a->Update(); // Ridiculous amount of calls per unit of time

// Free memory
}

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

Вместо этого используйте N разных контейнеров, по одному для каждого типа объекта, без косвенного обращения. Пусть компилятор встроен B::Update() в петле по всем B объекты много лучше. (Для приведенного ниже тривиального примера увеличения на один элемент intмой статический анализ производительности при взгляде на asm показывает, что он примерно в 24 раза быстрее в Skylake с горячими данными в кеше L1D. AVX2 Auto-векторизация против 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.

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

---

Если вам нужна какая-то отправка, например, заголовок запрашивает

Если все объекты имеют одинаковый размер, то вы действительно хотите зацикливаться на объектах, а не на указателях на объекты. Это позволило бы избежать дополнительной кэш-памяти вектора указателей и избежать дополнительной задержки отслеживания указателя, которую неявное выполнение должно скрывать, чтобы сохранить занятость исполнительных блоков. Но виртуальное наследование C ++ не обеспечивает никакого совместимого со стандартами способа получить полиморфизм для union upoly { B b; C c; } poly_array[1024]; Вы можете взломать это сами reinterpret_cast<> таким образом, что, вероятно, работает на x86-64 GCC, но вы, вероятно, не должны. Смотрите продолжение @ BeeOnRope: Смежное хранилище полиморфных типов. (Также старый Q&A: C ++ полиморфизм объекта в массиве).

Если вам это нужно, возможно, самый эффективный способ — это создать его самостоятельно с enum индексировать таблицу указателей функций (или использовать switch() если ваши функции могут быть встроены). Если ваши функции не встроены, switch() к куче вызова функции caseОбычно s не оптимизируется до таблицы указателей на функции, даже если все они имеют одинаковые аргументы (или не имеют аргументов). Вы обычно получаете таблицу перехода к блоку инструкций вызова, вместо того, чтобы фактически делать косвенный call, Так что в каждой отправке есть дополнительный прыжок.

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<> хранить указатели на функции-члены экземпляра, но на x86-64 gcc это 32-байтовый объект. Для вашего кэша лучше использовать только 8-байтовые регулярные указатели на функции и писать код, который знает, как передать явный указатель, эквивалентный this указатель.

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

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

---

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

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

Источник для нескольких способов сделать это + asm из x86-64 clang 5.0 в проводнике компилятора Godbolt. Вы можете перевернуть его на gcc или на архитектуры не x86.

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();
}

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

Цикл за vecC может сделать только 1 элемент за такт, потому что каждый объект составляет 16 байтов (8-байтовый указатель vtable, 4 байта int m_c4 байта заполнения до следующей границы выравнивания, потому что указатель имеет требование выравнивания 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).

Увидеть Слайды: SIMD на Играх бессонницы (GDC 2015) для введения в то, как структурировать ваши данные для SIMD, и некоторые более сложные вещи. Смотрите также ссе пометьте вики для большего количества руководств. Так же x86 tag wiki имеет много низкоуровневого материала для оптимизации x86. Даже если вы ничего не векторизуете вручную, с отдельными массивами для x а также y есть хороший шанс, что компилятор может автоматически векторизовать для вас. (Посмотрите на вывод asm или тест gcc -O3 -march=native против gcc -O3 -march=native -fno-tree-vectorize). Вам может понадобиться -ffast-math для некоторых видов FP векторизации.

---

C ++ виртуальная рассылка:

Написание так, как вы делаете в вопросе, с виртуальным наследованием и

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

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

Мы получаем этот цикл из clang5.0 -O3 -march=skylake

   # 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())

Таким образом, последний указатель на функцию находится в конце цепочки из трех зависимых нагрузок. Внеочередное выполнение позволяет этому перекрываться между итерациями (если ветвление предсказывает правильно), но это много накладных расходов только в общем количестве инструкций для внешнего интерфейса, а также в штрафе за неверный прогноз. (call [m] 3 мопа, так что сам цикл равен 8 мопам, и он может выдавать только один цикл за 2 цикла на Skylake. Вызов / возврат тоже накладные расходы. Если вызываемый объект не является полностью тривиальным, мы, вероятно, не являемся узким местом при пересылке магазина для отправки / возврата адреса возврата. Цикл с вызовом функции быстрее, чем пустой цикл. (Я не уверен в пропускной способности независимых операций сохранения / перезагрузки на одном и том же адресе. Это обычно требует переименования памяти, чего не делает Skylake, чтобы не ограничивать это, если вызываемый объект крошечный, как здесь.)

Определение Clang для C :: Update ():

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

Если для этого нужно установить какие-либо константы, прежде чем что-то вычислять, было бы еще дороже, если бы они не были встроены. Таким образом, при виртуальной диспетчеризации это, вероятно, работает на Skylake примерно по одному на каждые 3–5 часов вместо 1 члена в такт. (Или 8 участников в час с AVX2 для не виртуальных class B который не тратит пространство, и делает автоматическую векторизацию работать хорошо.) http://agner.org/optimize/ говорит, что Skylake имеет один на 3 часа call пропускная способность, так скажем, 24-кратная потеря производительности, когда данные горячие в кэш L1D. Конечно, разные микроархитектуры будут разными. Увидеть x86 Отметьте вики для получения дополнительной информации о x86.

---

Союз взломать:

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

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
}
}

Все B и C имеют свои vtable в начале, так что я думаю, что это будет работать в целом. По сути, это то же самое, с одним меньшим шагом в погоне за указателем. (Я использовал статический массив вместо вектора, так как я сохранял простоту и C-подобность, сортируя, что бросить.)

    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

Это лучше и затрагивает меньше памяти, но это только немного лучше для накладных расходов.

---

std::function от #include <functional>

Он может содержать любую вызываемую вещь. Но у него даже больше накладных расходов, чем у vtable, потому что он может находиться в состоянии ошибки, если используется. Таким образом, внутренний цикл должен проверять каждый экземпляр для этого и ловушку, если это так. Также, sizeof(std::function<void()>); составляет 32 байта (на x86-64 System V ABI).

#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

Таким образом, есть до трех call инструкции, если указатель не является nullptr. Это выглядит намного хуже, чем виртуальная рассылка.

Это выглядит немного иначе с Clang -stdlib=libc++вместо значения по умолчанию libstdc++, (https://libcxx.llvm.org/). Но все же три call инструкции во внутреннем цикле, с условными пропусками их или броском.

Если код-ген сильно отличается для разных видов function<T>Вероятно, даже не стоит искать указатели на функции-члены, если вы можете написать более эффективную альтернативу.

void virtual_call_unswitch(std::vector<A*>& vec) {

// first create a bitmap which specifies whether each element is B or C type
std::vector<uint64_t> bitmap(vec.size() / 64);

for (size_t block = 0; block < bitmap.size(); block++) {
uint64_t blockmap = 0;
for (size_t idx = block * 64; idx < block * 64 + 64; idx++) {
blockmap >>= 1;
blockmap |= (uint64_t)vec[idx + 0]->typecode_ << 63;
}
bitmap[block] = blockmap;
}

// now loop over the bitmap handling all the B elements, and then again for all the C elements

size_t blockidx;
// B loop
blockidx = 0;
for (uint64_t block : bitmap) {
block = ~block;
while (block) {
size_t idx = blockidx + __builtin_ctzl(block);
B* obj = static_cast<B*>(vec[idx]);
obj->Update();
block &= (block - 1);
}
blockidx += 64;
}

// C loop
blockidx = 0;
for (uint64_t block : bitmap) {
while (block) {
size_t idx = blockidx + __builtin_ctzl(block);
C* obj = static_cast<C*>(vec[idx]);
obj->Update();
block &= (block - 1);
}
blockidx += 64;
}
}

-----------------------------------------------------------------------------
Benchmark                                      Time           CPU Iterations
-----------------------------------------------------------------------------
BenchWithFixture/VirtualDispatchTrue       30392 ns      30364 ns      23033   128.646M items/s
BenchWithFixture/VirtualDispatchFakeB       3564 ns       3560 ns     196712   1097.34M items/s
BenchWithFixture/StaticBPtr                 3496 ns       3495 ns     200506    1117.6M items/s
BenchWithFixture/UnswitchTypes              8573 ns       8571 ns      80437   455.744M items/s
BenchWithFixture/StaticB                    1981 ns       1981 ns     352397    1.9259G items/s

for (A *a : vecA) {
a->Update();
}

for (A *a : vecA) {
((B *)a)->Update();
}

// type 1 (code 11)
for (size_t i = 0; i < bitmap1.size(); i++) {
block = bitmap1[i] & bitmap2[i];
...
}// type 2 (code 01)
for (size_t i = 0; i < bitmap1.size(); i++) {
block = ~bitmap1[i] & bitmap2[i];
...
}

...