Ответ 1
Как сказал первый комментарий, у вас есть проблема XY. Сортировка/переупорядочение в порядке, и у вас много объектов, а не огромное количество разных классов, и нет необходимости поддерживать типы, которые ваш код не знает о компиляции время. Полиморфизм + виртуальное наследование - неправильный выбор.
Вместо этого используйте N разных контейнеров, по одному для каждого типа объектов, без косвенности. Предоставление компилятору inline B::Update() в цикл по всем объектам B намного лучше. (Для тривиального примера ниже приращения одного члена int мой статический анализ производительности от взгляда на asm ставит его примерно на 24 раза быстрее на Skylake с горячими данными в кеше L1D. Автоинъекция AVX2 против call в цикл действительно такой огромный.)
Если между объектами, в том числе между различными типами объектов, существовал некоторый требуемый порядок, тогда был бы необходим какой-то полиморфизм или ручная диспетчеризация. (например, если было важно, какой заказ вы обработали vecA, оставив все объекты B отдельно от всех объектов C не эквивалентными.)
Если вы заботитесь о производительности, вы должны понимать, что увеличение источника может упростить работу компилятора/выхода asm. Проверка/диспетчеризация на основе типа каждого объекта внутри внутреннего цикла является дорогостоящей. Использование любого вида указателя функции или перечисления для отправки по каждому объекту может легко страдать от неверных прогнозов ветки, когда у вас есть смешивание разных объектов.
Цикл отдельно по нескольким контейнерам эффективно поднимает этот тип проверки внутреннего цикла и позволяет компилятору девиртуализировать. (Или лучше, сжимает каждый объект, чтобы в первую очередь не требовался указатель указателя, перечисления или указателя функции, поскольку его тип статически известен.)
Записывание отдельного цикла для каждого контейнера с другим типом похоже на полное разворачивание цикла по различным типам после подъема типа диспетчеризации из внутреннего цикла. Это необходимо, чтобы компилятор ввел вызовы, которые вы хотите, если есть много объектов каждого типа. Inlining позволяет сохранять константы в регистре по всем объектам, активировать автоинъекцию SIMD для нескольких объектов и просто избегать накладных расходов на фактический вызов функции. (И сам вызов, и разлив/перезагрузка регистров.)
Вы были правы, что , если вам нужна диспетчеризация для каждого объекта, виртуальные функции С++ - это дорогостоящий способ получить это, когда вы используете переопределения final. Вы платите ту же стоимость времени исполнения, которая позволила бы вашему коду поддерживать новые производные классы произвольного размера, о которых он не знал во время компиляции, но не получая от этого никакой пользы.
Виртуальная диспетчеризация работает только с уровнем косвенности (например, вектором указателей, который вы используете), что означает, что вам нужно каким-то образом управлять объектами с указателем. путем выделения их из vector<B> poolB и vector<C> poolC. Хотя я не уверен, что большинство реализаций vector<> используют realloc(), когда им нужно расти; API new/delete не имеет realloc, поэтому vector может копировать каждый раз, когда он растет, вместо того, чтобы пытаться расширить существующее распределение на месте. Проверьте, что делает ваша реализация на С++, поскольку она может сосать по сравнению с тем, что вы можете делать с malloc/realloc.
И BTW, должно быть возможно сделать new/delete с RAII без дополнительных накладных расходов для распределения/освобождения, если все ваши классы тривиально разрушаемы. (Но обратите внимание, что unique_ptr может победить другие оптимизации для использования вектора указателей). std::unique_ptr предупреждает, что UB уничтожает его с помощью указателя на базовый класс, поэтому вам, возможно, придется катиться самостоятельно. Тем не менее, на gcc на x86-64, sizeof(unique_ptr<class C>) всего 8, поэтому он имеет только один элемент-указатель. Но что бы то ни было, отдельно выделяя циллионы крошечных объектов, так что не делайте этого в первую очередь.
Если вам нужна какая-то отправка, как в заголовке, запрашивается
Если объекты имеют одинаковые размеры, вы действительно хотите перебирать объекты, а не указатели на объекты. Это позволило бы избежать лишнего размера кеша вектора указателей, и это позволит избежать дополнительной задержки лазера указателя, которую не удалось выполнить из-за порядка выполнения, чтобы сохранить рабочие блоки. Но виртуальное наследование С++ не предоставляет никакого стандартного способа получения полиморфизма для union upoly { B b; C c; } poly_array[1024];Вы можете взломать это с помощью reinterpret_cast<> таким образом, который, вероятно, работает на x86-64 gcc, но вы, вероятно, не должны этого делать. См. @BeeOnRope followup: Смежное хранение полиморфных типов. (Также более старый Q & A: С++ полиморфизм объекта в массиве).
Если вам это нужно, наиболее эффективным способом, вероятно, будет создание его с помощью enum для индексирования таблицы указателей функций (или используйте switch(), если ваши функции могут быть встроены). Если ваши функции не встроены, switch() в кучу функции-вызова case обычно не оптимизируется до таблицы указателей функций, даже если все они имеют одни и те же аргументы (или без аргументов). Обычно вы получаете таблицу перехода в блок инструкций вызова, вместо того, чтобы делать косвенный call. Таким образом, в каждой отправке есть дополнительный прыжок.
С++ 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; }; }; (с не виртуальными функциями), если вам не нужно "неинициализированное" состояние. Связанный: С++ полиморфизм объекта в массиве.
В этом случае у вас есть только одна функция, поэтому вы можете поместить указатель функции внутри каждого объекта в качестве члена. Как void (*m_update)(A* this_object). В вызывающем, передайте указатель на объект как void* или A*, так как он является нечленой функцией. Реализация функции будет reinterpret_cast<C*>(this_object). (Не dynamic_cast: мы делаем нашу рассылку, не используя С++).
Если вы хотите использовать 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 targeting 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_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 в каждом объекте. Array-of-structs в основном отстой для SIMD, потому что ему нужно много перетасовки, чтобы использовать x с y для одного и того же объекта. То, что вы хотите, это std::vector<float> x, y или подобное, поэтому ваш CPU может загружать значения 4 x в регистр и 4 y значения в другой регистр. (Или 8 одновременно с AVX).
См. Слайды: SIMD в Insomniac Games (GDC 2015) для ознакомления с тем, как структурировать ваши данные для SIMD и некоторые более продвинутые вещи. См. Также sse теги wiki для получения дополнительных руководств, Кроме того, x86 тег wiki имеет множество низкоуровневых материалов для оптимизации x86. Даже если вы ничего не рисуете вручную, с отдельными массивами для x и y есть хороший шанс, что компилятор может авто-векторизовать для вас. (Посмотрите на выход asm или на тест gcc -O3 -march=native vs. gcc -O3 -march=native -fno-tree-vectorize). Вам может понадобиться -ffast-math для некоторых видов векторизации FP.
Виртуальная диспетчеризация С++:
Написание его так, как вы делаете в вопросе, с виртуальным наследованием и
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())
Итак, конечный указатель функции находится в конце цепочки из трех зависимых нагрузок. Выполнение вне порядка позволяет это совпадение между итерациями (если ветвь предсказывает правильно), но что много накладных расходов просто в общих инструкциях для front-end, а также в неправильном предложении. (call [m] - это 3 uops, так что только сам цикл равен 8 uops, и он может выдавать только один за 2 цикла на Skylake. Call/return также имеет накладные расходы. Если вызываемый пользователь не является полностью тривиальным, мы, вероятно, store-forwarding для push/popping обратного адреса. Loop с вызовом функции быстрее, чем пустой цикл. (Я не уверен в пропускной способности независимых операций хранения/перезагрузки на том же адресе. Это обычно требует переименования памяти, которое Skylake не делает, чтобы не быть узким местом в этом случае, если вызывающая сторона крошечная, как здесь.)
Определение Clang для C:: Update() -
C::Update(): # @C::Update()
inc dword ptr [rdi + 8]
ret
Если это необходимо для настройки каких-либо констант, прежде чем вычислять что-то, было бы еще дороже не иметь его вложенным. Таким образом, с виртуальной диспетчеризацией это, вероятно, работает примерно от одного на 3 до 5 тактов, а не около 1 члена за такт, на Skylake. (Или 8 членов за такт с AVX2 для не виртуальных class B, которые не теряют места и делают автоинтеграцию хорошо работать.) http://agner.org/optimize/ говорит, что Skylake имеет одну пропускную способность в течение 3 часов call, поэтому позволяет сказать, что потеря производительности 24 раза, когда данные горячие в кеше L1D. Разумеется, разные микроархитектуры будут разными. См. x86 теги wiki для более x86 perf Информация.
Взлом соединения:
Вероятно, вы никогда не должны использовать это, но вы можете видеть из 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
}
}
A B и C все имеют свою виртуальную таблицу в начале, поэтому я думаю, что это, как правило, будет работать. Мы asm, что в основном то же самое, с одним меньшим шагом в стрельбе. (Я использовал статический массив вместо вектора, так как я делал вещи простыми и C-like, сортируя, что делать.)
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>, он, вероятно, даже не стоит рассматривать его для указателей на функции-члены, если вы можете написать более эффективную альтернативу.