我正在努力尝试使用枚举和大量的宏魔术来实现vtables的替代方案，而这实际上已经开始使我的大脑陷入困惑。我开始认为我没有走正确的道路，因为代码变得越来越丑陋，并且无论如何都不适合生产。
如何用最少的重定向/操作量来实现以下代码的模式？
必须使用标准的c++(最多17个)完成。
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
}
PS:如果枚举，切换和宏确实是最好的选择，我想我将只是尝试刷新缓存并提出更好的设计。
PSS:我知道这是微观优化...哎呀，我需要对它进行纳米乃至微微优化(从形象上来说)，所以我将完全忽略可能出现的功利主义 react 。
最佳答案
如第一条评论所述，您在这里遇到XY问题。 Sorting / reordering没问题，并且您有许多对象，而不是大量不同的类，并且不需要支持代码在编译时不知道的类型。 多态+虚拟继承是的错误选择。
而是使用N个不同的容器，每种类型的对象一个，没有间接的容器。 让编译器将B::Update()内联到所有B对象的循环中会更好。。 (对于下面增加一个成员int的简单示例，我的静态性能分析(从asm来看，在L1D缓存中有热数据的情况下，Skylake在Skylake上的速度提高了约24倍。)AVX2自动矢量化与call循环循环的确是巨大的。)
如果对象之间(包括不同类型的对象之间)存在某些必需的顺序，则某种多态性或手动分派(dispatch)将是适当的。 (例如，如果您处理vecA的顺序很重要，那么将所有B对象与所有C对象分开将是不对等的。)
如果您关心性能，则必须意识到扩大源代码可能会简化编译器/asm输出中的操作。 根据内部循环内每个对象的类型进行检查/分派(dispatch)是昂贵的。 当您混合使用不同的对象时，使用每种对象的函数指针或枚举来分派(dispatch)，很容易遭受分支预测错误的困扰。
在多个容器上分别循环有效地提升了从内部循环中进行类型检查的类型，并使编译器进行虚拟化。 (或者更好的方法是，缩小每个对象，使其首先不需要vtable指针，枚举或函数指针，因为其类型是静态已知的。)
为具有不同类型的每个容器编写一个单独的循环有点像在将类型分配从内部循环中提升之后，在不同类型上完全展开一个循环。这对于编译器内联调用是必要的，如果每种类型的对象很多，则需要这些调用。内联使它可以在对象之间的寄存器中保持常量，在多个对象之间启用SIMD自动矢量化，并仅避免实际函数调用的开销。 (调用本身和寄存器的溢出/重装。)
如果确实需要按对象分派(dispatch)，那么使用是正确的，当使用final覆盖时，C++虚拟函数是获取它的昂贵方法。您所付出的运行时成本使代码可以支持新的任意大小的派生类，而这些派生类在编译时并不知道，但并不能从中获得任何好处。
虚拟分派(dispatch)仅适用于间接级别(例如您正在使用的指针 vector )，这意味着您需要以某种方式管理指向的对象，例如通过从vector<B> poolB和vector<C> poolC分配它们。尽管我不确定vector<>的大多数实现在需要增长时会使用realloc()； new/delete API没有realloc，因此vector实际上可以在每次增长时复制，而不是尝试扩展现有分配。检查您的C++实现是做什么的，因为与使用malloc/realloc相比，它可能很烂。
顺便说一句，只要您的所有类都是微不足道的，就应该可以使用RAII来进行new/delete的使用，而不会产生分配/取消分配的额外开销。 (但请注意 unique_ptr may defeat other optimizations用于使用指针的 vector )。 std::unique_ptr 警告说它是UB，它通过指向基类的指针来销毁它，因此您可能必须自己滚动。不过，在x86-64上的gcc上，sizeof(unique_ptr<class C>)仅是8，因此它只有一个指针成员。但是无论如何，分别分配成千上万个微小的对象很烂，因此首先不要这样做。
如果您确实需要某种发送方式，例如标题要求
如果对象的大小都相似，那么您真的想遍历对象，而不是指向对象的指针。这将避免指针 vector 的额外高速缓存占用空间，并且避免了无序执行必须隐藏以保持执行单元繁忙的额外指针追寻延迟。 但是C++虚拟继承没有提供任何符合标准的方式来获取union upoly { B b; C c; } poly_array[1024];的多态性您可以使用reinterpret_cast<>自己破解这种方式，该方式可能适用于x86-64 gcc，但您可能不应该这样做。请参阅@BeeOnRope的后续文章:Contiguous storage of polymorphic types。 (还有一个更老的问题解答:C++ polymorphism of a object in an array)。
如果需要，性能最高的方法可能是使用enum自己构建它，以对函数指针表进行索引(如果函数可以内联，则使用switch())。如果您的函数未内联，则一堆函数调用switch()的case通常不会优化到函数指针表，即使它们都具有相同的args(或没有args)也是如此。通常，您会获得到跳转指令块的跳转表，而不是实际执行间接call。因此，每次 dispatch 都有一个额外的跳跃。
带有std::visit的C++ 17 std::variant<B, C> (对B和C使用非虚拟继承)似乎可以根据内部enum进行分派(dispatch)。 std::visit使用自己的跳转表进行调度，即使只有两种可能的类型，也不必内联它们并使用条件分支。它还必须始终检查“未初始化”状态。您可以使用B *tmp = std::get_if<B>(&my_variant)获得良好的代码if you manually work around that，并使用__builtin_unreachable()告诉gcc不可能使用nullptr。但是在那时，如果不需要“未初始化”状态，您也可以只滚动自己的struct polymorph { enum type; union { B b; C c; }; };(带有非虚拟函数)。相关:C++ polymorphism of a object in an array。
在这种情况下，您只有一个函数，因此可以将函数指针作为成员放置在每个对象中。像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*，尤其是在制作单独的函数指针数组时。然后， union 成员无需从公共(public)基础继承。
您可以使用std::function<>存储指向实例成员函数的指针，但是在x86-64 gcc上，它是一个32字节的对象。最好只使用8字节的常规函数指针并编写知道传递与this指针等效的显式指针的代码，这对于您的缓存占用空间更好。
根据当前大小/对齐方式，将函数指针放置在每个对象中可能比enum或uint8_t占用更多空间。在函数指针表中使用小的整数索引可能会减少对象与指针成员的每个实例的大小，尤其是对于64位目标而言。较小的对象很容易值得这对额外的指令来索引一个函数指针数组，并且可能因额外的指针取消引用而导致更高的错误预测损失。内存/高速缓存未命中通常是瓶颈。
我假设您确实有按实例的状态，即使您不显示任何状态。如果不是这样，那么指向非成员函数的普通函数指针的 vector 将便宜得多!
开销比较:
我查看了编译器生成的asm(针对x86-64的gcc和clang)的几种实现方法。
Source for multiple ways of doing this + asm from x86-64 clang 5.0 on the Godbolt compiler explorer 。您可以将其翻转到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使用AVX2在vecB 上自动对循环进行矢量化处理，以并行处理8个int元素，因此，如果您不占用内存带宽(即L1D缓存中很热)，则此循环每个时钟周期可以增加8个元素。该循环的运行速度与vector<int>上的循环一样快；一切都内联并优化，这只是指针的增加。
vecC上的循环每个时钟周期只能执行1个元素，因为每个对象都是16字节(8字节vtable指针，4字节int m_c，到下一个对齐边界的4字节填充，因为指针具有8B对齐要求。)如果没有final，则编译器还会在使用内联C之前检查vtable指针，以查看其是否实际上是C::Update()，否则将分派(dispatch)。就像您在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成员的 vector 。之所以允许，因为它不包含float x,y成员任何 volatile 或原子成员，使用AVX2时每个时钟运行2个，使用AVX512时每个时钟运行4个。)如果对象较小且对象很多，则对象最多增大12个字节是一个主要缺点。
每个对象有多个成员，这并不一定会破坏SIMD，但仍然像每个枚举或函数指针一样，占用每个对象中的空间。
既然您提到了the separating axis theorem，我希望您不打算在每个对象中存储x对。 结构数组对于SIMD来说很烂，因为对于同一对象，将y和std::vector<float> x, y一起使用需要大量的改组。您需要的是x或类似的，因此您的CPU可以将4个y值加载到一个寄存器中，并将4个x值加载到另一个寄存器中。 (或使用AVX一次8个)。
有关如何为SIMD构造数据的介绍，请参阅Slides: SIMD at Insomniac Games (GDC 2015)，以及一些更高级的内容。另请参阅sse标签Wiki，以获取更多指南。另外，x86 tag wiki具有许多低级的x86优化 Material 。即使您没有手动向量化任何东西，对于y和gcc -O3 -march=native都使用单独的数组，编译器很有可能会为您自动向量化。 (查看asm输出，或基准gcc -O3 -march=native -fno-tree-vectorize与-ffast-math)。对于某些类型的FP矢量化，您可能需要-O3 -march=skylake。
C++虚拟调度:
使用虚拟继承和std::vector<A*> vecA{};
void vec_virtual_pointers() {
for(auto a: vecA)
a->Update();
}
我们从clang5.0 call [m]获得此循环 # 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())
因此，最终函数指针位于三个相关负载链的末尾。乱序执行使迭代之间可以重叠(如果分支正确预测的话)，但这仅是前端的全部指令中的大量开销，而且是错误预测的代价。 (class B是3 oups，所以循环本身是8 uops，并且只能在Skylake上每2个周期发出一个。调用/返回也有开销。如果被调用者不是很琐碎，那么我们可能不会在商店中造成瓶颈-转发以推送/弹出返回地址Loop with function call faster than an empty loop(我不确定在同一地址上独立存储/重载操作的吞吐量。这通常需要重命名内存，而Skylake不会这样做，以免造成瓶颈如果被调用者像这里一样小。)
Clang对C::Update()的定义是C::Update(): # @C::Update()
inc dword ptr [rdi + 8]
ret
如果在计算某些内容之前需要设置任何常量，则不进行内联将更加昂贵。因此，在虚拟分派(dispatch)中，在Skylake上，这大概每3到5个时钟运行一次，而不是每个时钟大约1个成员。 (或者使用AVX2，每个时钟8个成员用于非虚拟call，这不会浪费空间，并且可以使自动矢量化正常工作。)http://agner.org/optimize/说Skylake每3个时钟std::function吞吐量就有1个，因此可以说当数据为24x时，性能损失为24倍。 L1D缓存中很热。当然，不同的微体系结构会有所不同。有关更多x86性能信息，请参见x86标签Wiki。
联盟骇客:
也许您永远不要使用此功能，但是从asm可以看出它可以在带有clang和gcc的x86-64上运行。我做了一个 union 的数组，并遍历了它: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都在开始时都有其vtable，所以我认为这通常会起作用。我们基本上是一样的，只差了一步。 (我使用静态数组而不是 vector ，因为在整理强制转换时，我保持了简单和类似于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
这样会更好，并且占用更少的内存，但是对于开销而言却仅稍好一点。#include <functional>中的sizeof(std::function<void()>);
它可以容纳任何可调用的东西。但是它比vtable派发有更多的开销，因为允许它处于错误使用状态。因此，内部循环必须为此检查每个实例，并捕获是否存在。另外，call是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
因此，除非指针为nullptr，否则最多有三个-stdlib=libc++指令。这看起来远比虚拟调度差。
使用clang libstdc++看起来有点不同，而不是默认的call。 (https://libcxx.llvm.org/)。但是内循环中仍然有三个function<T>指令，并带有条件跳过或抛出。
除非不同的ojit_code的代码源都非常不同，否则如果您可以编写更有效的替代方法，那么甚至不值得为成员函数的指针查看它。
关于c++ - 在C++中最快实现简单，虚拟，观察者排序的模式？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/46579750/