在 C++ 中最快实现简单、虚拟、观察者类型的模式？
Fastest implementation of simple, virtual, observer-sort of, pattern in c++?
我正在竭尽全力尝试使用枚举和大量宏魔术实现 vtable 的替代方案，这真的开始扰乱我的大脑。我开始认为我没有走在正确的道路上，因为代码变得越来越丑陋，并且无论如何都不适合生产。
如何用最少的redirection/operations实现下面代码的pattern？
必须用标准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：我知道这是微观优化...哎呀，我需要 nano 甚至 pico 优化这个（打个比方），所以我会简单地忽略可能出现的任何功利主义反应.
正如第一条评论所说，你这里有一个 XY 问题。 Sorting / reordering 没问题，你有很多 object，而不是大量不同的 class，并且不需要支持你的代码在编译时不知道的类型。 多态+虚继承是错误的选择.
相反，使用 N 个不同的容器，每个容器对应一种 object，没有间接寻址。 让编译器将 B::Update() 内联到所有 B object 的循环中 多 更好 。 （对于下面增加一个成员 int 的简单示例，我通过查看 asm 进行的静态性能分析表明，在 L1D 缓存中数据热的情况下，它在 Skylake 上的速度提高了大约 24 倍。AVX2 auto-vectorization 与 call在一个循环中真的有那么大。）
如果 object 之间需要某种顺序，包括不同类型的 object 之间，那么某种多态性或手动调度将是合适的。 （例如，如果你处理 vecA 的顺序很重要，那么将所有 B object 与所有 C object 分开是不等价的.)
如果您关心性能，则必须意识到，增大源代码可能 简化 编译器/asm 输出中的事情。 根据内部循环中每个 object 的类型检查/调度是昂贵的。 使用任何类型的函数指针或枚举在 per-object 基础上调度可以当您混合使用不同的 objects.
时，很容易出现分支预测错误
在多个容器上分别循环有效地提升了内部循环的类型检查并让编译器去虚拟化。 （或者更好的是，首先将每个 object 缩小到不需要 vtable 指针、枚举或函数指针，因为它的类型是静态已知的。）
为每个具有不同类型的容器编写一个单独的循环有点像在将类型调度提升到内部循环之外之后完全展开一个不同类型的循环。这对于编译器内联调用是必要的，如果每种类型有很多 object，这是你想要的。内联允许它在跨 objects 的寄存器中保留常量，跨多个 objects 启用 SIMD auto-vectorization，并且简单地避免了实际函数调用的开销。 （调用本身和寄存器的 spill/reload。）
你是对的 如果 你确实需要 per-object dispatch，C++ 虚函数是一种昂贵的获取方式当您使用 final 覆盖时。您付出了相同的 运行 时间成本，让您的代码支持新的派生 class 编译时不知道的任意大小的 es，但不会从中获得任何好处。
Virtual dispatch 仅适用于间接级别（例如，您正在使用的指针向量），这意味着您需要以某种方式管理 pointed-to objects，例如通过从 vector<B> poolB 和 vector<C> poolC 中分配它们。尽管我不确定 vector<> 的大多数实现在需要增长时都使用 realloc()； new/delete API 没有 realloc，因此 vector 实际上可能会在每次增长时进行复制，而不是尝试扩展现有分配。检查你的 C++ 实现做了什么，因为与你可以用 malloc/realloc.
可以做的相比，它可能很糟糕
顺便说一句，只要你所有的 classes是微不足道的破坏。 （但请注意，unique_ptr may defeat other optimizations for using the vector of pointers). std::unique_ptr 警告说通过指向基 class 的指针销毁它是 UB，因此您可能必须自己动手。不过，在 x86-64 上的 gcc 上，sizeof(unique_ptr<class C>) 只有 8，所以它只有一个指针成员。但是无论如何，单独分配数以亿计的微小 objects 很糟糕，所以首先不要这样做.
如果您确实需要像标题要求的某种调度
如果 object 的大小都相似，那么您确实希望遍历 object，而不是 pointers-to-objects。这将避免指针向量的额外缓存占用空间，并避免 pointer-chasing 执行必须隐藏以保持执行单元忙碌的额外 pointer-chasing 延迟。 但 C++ 虚拟继承不提供任何 standards-compliant 方法来获得 union upoly { B b; C c; } poly_array[1024]; 的多态性你可以用 reinterpret_cast<> 自己破解这个可能适用于 x86-64 gcc，但你可能不应该。请参阅@BeeOnRope 的跟进：Contiguous storage of polymorphic types. (Also an older Q&A: C++ polymorphism of a object in an array).
如果您需要，highest-performance 方法可能是使用 enum 自己构建它以索引 table 函数指针（或使用 switch() 如果你的函数可以内联）。如果你的函数不内联，switch() 到一堆 function-call case 通常不会优化到 table 函数指针，即使它们都有相同的参数（或没有参数）。您通常会 table 跳转到调用指令块，而不是实际执行ng 间接 call。所以每次调度都有一个额外的跳跃。
C++17 std::visit with std::variant<B, C> (using non-virtual inheritance for B and C) seems to give you dispatch based on an internal enum. std::visit uses its own jump table to dispatch, even with only 2 possible types, instead of inlining them both and using a conditional branch. It also has to check for the "uninitialized" state all the time. You can get good code if you manually work around that with B *tmp = std::get_if<B>(&my_variant), and a __builtin_unreachable() to tell gcc that nullptr isn't a possibility. But at that point you might as well just roll your own struct polymorph { enum type; union { B b; C c; }; }; (with non-virtual functions) if you don't need an "uninitialized" state. Related: C++ polymorphism of a object in an array.
在这种情况下你只有一个函数，所以你可以在每个object中放置一个函数指针作为成员。喜欢void (*m_update)(A* this_object)。在调用者中，将指向 object 的指针作为 void* 或 A* 传递，因为它是一个 non-member 函数。该函数的执行将reinterpret_cast<C*>(this_object)。 （不是 dynamic_cast：我们正在做我们自己的调度，而不是使用 C++ 的）。
如果您想在 function-pointer 成员占用 space 的其他上下文中使用 B 和 C 而没有任何好处，您可以将函数指针保存在单独的容器而不是在基础 class 中。所以它将是 for(i=0..n) funcptrs[i]( &objects[i] );。只要你的容器没有失去同步，你总是传递一个指向知道如何处理它的函数的指针。将其与 union {B b; C c} objects[]（或 vector<union>）一起使用。
如果你愿意，你可以使用void*，尤其是当你制作一个单独的函数指针数组时。那么工会成员就不需要从共同的基础上继承了。
您 可以 使用 std::function<> 来存储指向实例成员函数的指针，但在 x86-64 gcc 上，这是一个 32 字节 object。最好只使用 8 字节的常规函数指针并编写知道传递相当于 this 指针的显式指针的代码。
在每个 object 中放置函数指针可能比 enum 或 uint8_t 花费更多 space，具体取决于当前 size/alignment。 table 函数指针的小整数索引可能会减少 object 的每个实例与指针成员的大小，尤其是对于 64 位目标。较小的 objects 很容易值得一对额外的指令来索引函数指针数组，并且可能因额外的指针取消引用而导致更高的错误预测惩罚。内存/缓存未命中通常是瓶颈。
我假设您确实有一些 per-instance 状态，即使您没有显示任何状态。如果不是，那么指向 non-member 函数的普通函数指针向量会便宜得多！
开销比较：
我查看了 compiler-generated 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 auto-vectorize 使用 AVX2 在 vecB 上循环并行处理 8 个 int 元素，所以如果你不t 内存带宽瓶颈（即 L1D 高速缓存中的热），此循环可以在每个时钟周期递增 8 个元素。这个循环 运行s 和 vector<int> 上的循环一样快；一切都内联并优化掉，它只是一个指针增量。
循环vecC每个时钟周期只能做1个元素，因为每个object是16字节（8字节vtable pointer, 4 byte int m_c, 4 bytes padding to next alignment boundary 因为指针有8B对齐要求。）没有final，编译器也会检查vtable指针到在使用内联 C::Update() 之前查看它是否实际上是 C，否则它会调度。这就像你在 struct { int a,b,c,d; } vecC[SIZE]; 上循环执行 vecC[i].c++;
得到的结果
final 允许完全去虚拟化，但我们的数据与 vtable 指针混合，因此编译器只执行标量 add [mem], 1，每个时钟只能 运行 1 （如果存储在 L1D 缓存中很热，则无论存储的大小如何，每个时钟存储吞吐量都会出现 1 个瓶颈）。对于此示例，这主要击败了 SIMD。 （使用 -march=skylake-avx512，gcc 和 clang 做一些荒谬的洗牌或 gather/scatter 甚至比标量慢，而不是 loading/restoring 整个 object 并添加一个只改变的矢量int 成员。这是允许的，因为它不包含任何易失性或原子成员，并且 运行 使用 AVX2 每个时钟 2 个，或者使用 AVX512 每个时钟 4 个。）让你的 objects 最多 12 个字节大是一个主要的缺点，如果它们很小而且你有很多。
每个 object 有多个成员，这不一定会打败 SIMD，但它仍然在每个 object 中花费 space，就像枚举或函数指针一样。
既然您提到了 the separating axis theorem，我希望您不打算在每个 object 中存储 float x,y 对。 Array-of-structs 对于 SIMD 来说基本上很糟糕，因为它需要大量的改组才能将 x 与 y 用于相同的 object .你想要的是 std::vector<float> x, y 或类似的，所以你的 CPU 可以将 4 个 x 值加载到一个寄存器中，并将 4 个 y 值加载到另一个寄存器中。 （或者使用 AVX 一次 8 个）。
看到 Slides: SIMD at Insomniac Games (GDC 2015) for an intro to how to structure your data for SIMD, and some more advanced stuff. See also the sse tag wiki for more guides. Also, the x86 tag wiki 有 很多 的 low-level x86 优化 material。即使您不手动向量化任何内容，使用 x 和 y 的单独数组，编译器也很有可能为您 auto-vectorize。 （查看 asm 输出，或基准测试 gcc -O3 -march=native 与 gcc -O3 -march=native -fno-tree-vectorize）。对于某些类型的 FP 向量化，您可能需要 -ffast-math。
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())
所以最终的函数指针位于三个依赖加载链的末尾。 Out-of-order 执行允许在迭代之间重叠（如果分支预测正确），但这只是 front-end 的总指令以及错误预测惩罚中的大量开销。 （call [m] 是 3 微指令，所以循环本身是 8 微指令，并且在 Skylake 上每 2 个周期只能发出一个。Call/return 也有开销。如果被调用者不是完全微不足道的，我们可能不会在 store-forwarding 上推送/弹出 return 地址没有瓶颈。Loop with function call faster than an empty loop。（我不确定在同一地址上独立 store/reload 操作的吞吐量。那通常需要内存重命名，而 Skylake 不会这样做，如果被调用者像这里一样小，就不会成为瓶颈。）
Clang 对 C::Update() 的定义是
C::Update(): # @C::Update()
inc dword ptr [rdi + 8]
ret
如果这需要在计算之前设置任何常量，那么不将其内联会更加昂贵。因此，对于虚拟调度，在 Skylake 上，这可能 运行 大约每 3 到 5 个时钟一个，而不是每个时钟大约 1 个成员。 （或者每个时钟 8 个成员使用 AVX2 for non-virtual class B，这不会浪费 space，并使 auto-vectorization 工作得很好。）http://agner.org/optimize/ says Skylake has one per 3 clock call throughput, so lets say 24x performance loss when the data is hot in L1D cache. Different microarchitectures will be different, of course. See the x86 标记 wiki 以获取更多信息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
}
}
A B 和 C 都以 vtable 开头，所以我认为这通常会起作用。我们认为基本相同，少了一步pointer-chasing。 （我使用静态数组而不是向量，因为我在整理要投射的内容时保持简单和 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 dispatch 的开销还要大，因为它允许处于 error-if-used 状态。因此，内部循环必须为此检查每个实例，如果是则捕获。此外，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
所以最多有3条call指令，除非指针是nullptr。这看起来比虚拟调度差得多。
使用 clang -stdlib=libc++ 而不是默认的 libstdc++ 看起来有点不同。 (https://libcxx.llvm.org/)。但是内部循环中仍然有三个 call 指令，有条件可以跳过它们或抛出。
除非 code-gen 对于不同类型的 function<T> 有很大不同，如果您可以编写更有效的替代方法，则可能甚至不值得查看指向成员函数的指针。
如果您确实需要 虚拟分派，一种在不同派生类型的对象列表上加速同一虚拟方法分派的方法是使用我将调用 类型取消切换.
有点类似于 loop unswitching，这将按顺序在每个对象上调用方法的单个循环转换为 N 个循环（对于 N 个支持的类型），每个循环在特定类型的所有对象上调用方法。这避免了不可预测的虚拟调度的主要成本：间接调用 vtable 中未知的、不可预测的函数所隐含的分支预测错误。
此技术的一般实现涉及按类型划分对象的第一遍：有关此分区的信息由第二遍使用，第二遍对每种类型都有单独的循环1，调用方法。如果仔细实施，这通常根本不涉及任何不可预测的分支。
在两个派生的情况下类 B和C你可以简单地使用位图来存储类型信息。这是一个示例实现，使用问题代码中的类型 A、B、C：
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;
}
}
这里，typecode是A中的公共字段，用于标识对象类型，0用于B，1用于C.需要类似的东西才能使按类型分类可行（它不能是虚拟调用，因为进行不可预测的调用是我们首先要避免的）。
上述略微优化的版本显示，与普通虚拟分派循环相比，未切换版本的加速大约为 3.5 倍，虚拟版本每次分派的时钟周期约为 19 个周期，而未切换版本约为 5.5 倍。完整结果：
-----------------------------------------------------------------------------
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
VirtualDispatchTrue 是在 A:
类型的指针上调用 Update() 的简单循环
for (A *a : vecA) {
a->Update();
}
VirtualDispatchFakeB 在调用 Update() 之前将指针转换为 B*（不管底层类型是什么）。由于 B::Update() 是最终的，编译器可以完全去虚拟化和内联调用。当然，这根本不是在做正确的事情：它将任何 C 对象视为 B 并因此调用了错误的方法（并且完全是 UB）——但它是用来估计你的速度的如果每个对象都是相同的静态已知类型，则可以在指针向量上调用方法。
for (A *a : vecA) {
((B *)a)->Update();
}
StaticBPtr 遍历 std::vector<B*> 而不是 std::vector<A*>。正如预期的那样，性能与上面的 "fake B" 代码相同，因为 Update() 的目标是静态已知的并且完全可内联。它在这里作为完整性检查。
UnswitchTypes 是上面描述的类型取消切换技巧。
StaticB 迭代 std::vector<B>。也就是说，连续分配 B 个对象而不是 指针 的向量到 B 对象。这删除了一个间接级别并显示了此对象布局的最佳情况2.
full source 可用并发布到 public 域。
限制
副作用和顺序
此技术的主要限制是 Update() 调用的顺序无关紧要。虽然 Update() 仍然在每个对象上调用一次，但顺序已明显改变。只要对象不更新任何可变的全局或共享状态，这应该很容易满足。
支持两种类型
上面的代码只支持两种类型，基于使用位图来记录类型信息。
这个限制很容易解除。首先，可以扩展位图方法。例如，为了支持 4 种类型，可以创建两个相似的位图，每个位图的相应位基本上用于编码类型的 2 位字段。循环是相似的，除了在外循环中它们 & 和 ~ 位图以超过所有 4 种类型的方式组合在一起。例如：
// 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];
...
}
...
另一种方法是根本不使用位图，而是简单地存储每种类型的索引数组。数组中的每个索引都指向主数组中该类型的对象。本质上，它是对类型代码的单次基数排序。这可能会使类型排序部分变慢一些，但可能会加速循环迭代逻辑（x & (x - 1) 和 ctz 东西消失了，代价是另一个间接寻址）。
固定数量的支持类型
上面的代码支持固定数量的编译时已知类型（即 B 和 C）。如果引入新类型，上面的代码要么中断，要么肯定无法调用这些新类型的 Update()。
但是，添加对未知类型的支持很简单。只需将所有未知类型分组，然后仅针对这些类型，在循环内执行完整的虚拟分派（即直接在 A* 上调用 Update()）。您将支付全价，但仅限于您未明确支持的类型！这样，该技术零售了虚拟调度机制的通用性。
聚合集合
您可能对 Boost 的 PolyCollection 感兴趣。它基本上是一个专门用于这种情况的类似向量的容器：保存各种多态类型的对象并以有效的方式迭代它们。
它支持virtual基于方法的多态，也支持类函数对象多态和基于鸭子类型的多态。它通过在存储中隔离各种对象类型来实现上述 "unswitching"：因此它不会保持不同类型对象之间的插入顺序。如果满足您的需求，它可以是现成的解决方案。
1 实际上，对于所有 共享虚方法的相同实现 的类型，您只需要一个循环，尽管这可能难以以通用方式实施，因为此信息不容易获得。例如，如果 类 Y 和 Z 都派生自 X，但都没有覆盖 X 中某些虚方法的实现，则所有 X、Y 和 Z 可以由同一个循环处理。
2 "object layout" 我的意思是 B 仍然具有虚拟方法并因此具有 vtable 的对象。如果你删除所有虚拟方法并摆脱 vtable，事情会变得更快，因为编译器然后将加法矢量化到紧凑排列的字段。 vtable 搞砸了。
我正在竭尽全力尝试使用枚举和大量宏魔术实现 vtable 的替代方案，这真的开始扰乱我的大脑。我开始认为我没有走在正确的道路上，因为代码变得越来越丑陋，并且无论如何都不适合生产。
如何用最少的redirection/operations实现下面代码的pattern？
必须用标准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：我知道这是微观优化...哎呀，我需要 nano 甚至 pico 优化这个（打个比方），所以我会简单地忽略可能出现的任何功利主义反应.
正如第一条评论所说，你这里有一个 XY 问题。 Sorting / reordering 没问题，你有很多 object，而不是大量不同的 class，并且不需要支持你的代码在编译时不知道的类型。 多态+虚继承是错误的选择.
相反，使用 N 个不同的容器，每个容器对应一种 object，没有间接寻址。 让编译器将 B::Update() 内联到所有 B object 的循环中 多 更好 。 （对于下面增加一个成员 int 的简单示例，我通过查看 asm 进行的静态性能分析表明，在 L1D 缓存中数据热的情况下，它在 Skylake 上的速度提高了大约 24 倍。AVX2 auto-vectorization 与 call在一个循环中真的有那么大。）
如果 object 之间需要某种顺序，包括不同类型的 object 之间，那么某种多态性或手动调度将是合适的。 （例如，如果你处理 vecA 的顺序很重要，那么将所有 B object 与所有 C object 分开是不等价的.)
如果您关心性能，则必须意识到，增大源代码可能 简化 编译器/asm 输出中的事情。 根据内部循环中每个 object 的类型检查/调度是昂贵的。 使用任何类型的函数指针或枚举在 per-object 基础上调度可以当您混合使用不同的 objects.
时，很容易出现分支预测错误在多个容器上分别循环有效地提升了内部循环的类型检查并让编译器去虚拟化。 （或者更好的是，首先将每个 object 缩小到不需要 vtable 指针、枚举或函数指针，因为它的类型是静态已知的。）
为每个具有不同类型的容器编写一个单独的循环有点像在将类型调度提升到内部循环之外之后完全展开一个不同类型的循环。这对于编译器内联调用是必要的，如果每种类型有很多 object，这是你想要的。内联允许它在跨 objects 的寄存器中保留常量，跨多个 objects 启用 SIMD auto-vectorization，并且简单地避免了实际函数调用的开销。 （调用本身和寄存器的 spill/reload。）
你是对的 如果 你确实需要 per-object dispatch，C++ 虚函数是一种昂贵的获取方式当您使用 final 覆盖时。您付出了相同的 运行 时间成本，让您的代码支持新的派生 class 编译时不知道的任意大小的 es，但不会从中获得任何好处。
Virtual dispatch 仅适用于间接级别（例如，您正在使用的指针向量），这意味着您需要以某种方式管理 pointed-to objects，例如通过从 vector<B> poolB 和 vector<C> poolC 中分配它们。尽管我不确定 vector<> 的大多数实现在需要增长时都使用 realloc()； new/delete API 没有 realloc，因此 vector 实际上可能会在每次增长时进行复制，而不是尝试扩展现有分配。检查你的 C++ 实现做了什么，因为与你可以用 malloc/realloc.
顺便说一句，只要你所有的 classes是微不足道的破坏。 （但请注意，unique_ptr may defeat other optimizations for using the vector of pointers). std::unique_ptr 警告说通过指向基 class 的指针销毁它是 UB，因此您可能必须自己动手。不过，在 x86-64 上的 gcc 上，sizeof(unique_ptr<class C>) 只有 8，所以它只有一个指针成员。但是无论如何，单独分配数以亿计的微小 objects 很糟糕，所以首先不要这样做.
如果您确实需要像标题要求的某种调度
如果 object 的大小都相似，那么您确实希望遍历 object，而不是 pointers-to-objects。这将避免指针向量的额外缓存占用空间，并避免 pointer-chasing 执行必须隐藏以保持执行单元忙碌的额外 pointer-chasing 延迟。 但 C++ 虚拟继承不提供任何 standards-compliant 方法来获得 union upoly { B b; C c; } poly_array[1024]; 的多态性你可以用 reinterpret_cast<> 自己破解这个可能适用于 x86-64 gcc，但你可能不应该。请参阅@BeeOnRope 的跟进：Contiguous storage of polymorphic types. (Also an older Q&A: C++ polymorphism of a object in an array).
如果您需要，highest-performance 方法可能是使用 enum 自己构建它以索引 table 函数指针（或使用 switch() 如果你的函数可以内联）。如果你的函数不内联，switch() 到一堆 function-call case 通常不会优化到 table 函数指针，即使它们都有相同的参数（或没有参数）。您通常会 table 跳转到调用指令块，而不是实际执行ng 间接 call。所以每次调度都有一个额外的跳跃。
C++17 std::visit with std::variant<B, C> (using non-virtual inheritance for B and C) seems to give you dispatch based on an internal enum. std::visit uses its own jump table to dispatch, even with only 2 possible types, instead of inlining them both and using a conditional branch. It also has to check for the "uninitialized" state all the time. You can get good code if you manually work around that with B *tmp = std::get_if<B>(&my_variant), and a __builtin_unreachable() to tell gcc that nullptr isn't a possibility. But at that point you might as well just roll your own struct polymorph { enum type; union { B b; C c; }; }; (with non-virtual functions) if you don't need an "uninitialized" state. Related: C++ polymorphism of a object in an array.
在这种情况下你只有一个函数，所以你可以在每个object中放置一个函数指针作为成员。喜欢void (*m_update)(A* this_object)。在调用者中，将指向 object 的指针作为 void* 或 A* 传递，因为它是一个 non-member 函数。该函数的执行将reinterpret_cast<C*>(this_object)。 （不是 dynamic_cast：我们正在做我们自己的调度，而不是使用 C++ 的）。
如果您想在 function-pointer 成员占用 space 的其他上下文中使用 B 和 C 而没有任何好处，您可以将函数指针保存在单独的容器而不是在基础 class 中。所以它将是 for(i=0..n) funcptrs[i]( &objects[i] );。只要你的容器没有失去同步，你总是传递一个指向知道如何处理它的函数的指针。将其与 union {B b; C c} objects[]（或 vector<union>）一起使用。
如果你愿意，你可以使用void*，尤其是当你制作一个单独的函数指针数组时。那么工会成员就不需要从共同的基础上继承了。
您 可以 使用 std::function<> 来存储指向实例成员函数的指针，但在 x86-64 gcc 上，这是一个 32 字节 object。最好只使用 8 字节的常规函数指针并编写知道传递相当于 this 指针的显式指针的代码。
在每个 object 中放置函数指针可能比 enum 或 uint8_t 花费更多 space，具体取决于当前 size/alignment。 table 函数指针的小整数索引可能会减少 object 的每个实例与指针成员的大小，尤其是对于 64 位目标。较小的 objects 很容易值得一对额外的指令来索引函数指针数组，并且可能因额外的指针取消引用而导致更高的错误预测惩罚。内存/缓存未命中通常是瓶颈。
我假设您确实有一些 per-instance 状态，即使您没有显示任何状态。如果不是，那么指向 non-member 函数的普通函数指针向量会便宜得多！
开销比较：
我查看了 compiler-generated 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 auto-vectorize 使用 AVX2 在 vecB 上循环并行处理 8 个 int 元素，所以如果你不t 内存带宽瓶颈（即 L1D 高速缓存中的热），此循环可以在每个时钟周期递增 8 个元素。这个循环 运行s 和 vector<int> 上的循环一样快；一切都内联并优化掉，它只是一个指针增量。
循环vecC每个时钟周期只能做1个元素，因为每个object是16字节（8字节vtable pointer, 4 byte int m_c, 4 bytes padding to next alignment boundary 因为指针有8B对齐要求。）没有final，编译器也会检查vtable指针到在使用内联 C::Update() 之前查看它是否实际上是 C，否则它会调度。这就像你在 struct { int a,b,c,d; } vecC[SIZE]; 上循环执行 vecC[i].c++;
final 允许完全去虚拟化，但我们的数据与 vtable 指针混合，因此编译器只执行标量 add [mem], 1，每个时钟只能 运行 1 （如果存储在 L1D 缓存中很热，则无论存储的大小如何，每个时钟存储吞吐量都会出现 1 个瓶颈）。对于此示例，这主要击败了 SIMD。 （使用 -march=skylake-avx512，gcc 和 clang 做一些荒谬的洗牌或 gather/scatter 甚至比标量慢，而不是 loading/restoring 整个 object 并添加一个只改变的矢量int 成员。这是允许的，因为它不包含任何易失性或原子成员，并且 运行 使用 AVX2 每个时钟 2 个，或者使用 AVX512 每个时钟 4 个。）让你的 objects 最多 12 个字节大是一个主要的缺点，如果它们很小而且你有很多。
每个 object 有多个成员，这不一定会打败 SIMD，但它仍然在每个 object 中花费 space，就像枚举或函数指针一样。
既然您提到了 the separating axis theorem，我希望您不打算在每个 object 中存储 float x,y 对。 Array-of-structs 对于 SIMD 来说基本上很糟糕，因为它需要大量的改组才能将 x 与 y 用于相同的 object .你想要的是 std::vector<float> x, y 或类似的，所以你的 CPU 可以将 4 个 x 值加载到一个寄存器中，并将 4 个 y 值加载到另一个寄存器中。 （或者使用 AVX 一次 8 个）。
看到 Slides: SIMD at Insomniac Games (GDC 2015) for an intro to how to structure your data for SIMD, and some more advanced stuff. See also the sse tag wiki for more guides. Also, the x86 tag wiki 有 很多 的 low-level x86 优化 material。即使您不手动向量化任何内容，使用 x 和 y 的单独数组，编译器也很有可能为您 auto-vectorize。 （查看 asm 输出，或基准测试 gcc -O3 -march=native 与 gcc -O3 -march=native -fno-tree-vectorize）。对于某些类型的 FP 向量化，您可能需要 -ffast-math。
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())
所以最终的函数指针位于三个依赖加载链的末尾。 Out-of-order 执行允许在迭代之间重叠（如果分支预测正确），但这只是 front-end 的总指令以及错误预测惩罚中的大量开销。 （call [m] 是 3 微指令，所以循环本身是 8 微指令，并且在 Skylake 上每 2 个周期只能发出一个。Call/return 也有开销。如果被调用者不是完全微不足道的，我们可能不会在 store-forwarding 上推送/弹出 return 地址没有瓶颈。Loop with function call faster than an empty loop。（我不确定在同一地址上独立 store/reload 操作的吞吐量。那通常需要内存重命名，而 Skylake 不会这样做，如果被调用者像这里一样小，就不会成为瓶颈。）
Clang 对 C::Update() 的定义是
C::Update(): # @C::Update()
inc dword ptr [rdi + 8]
ret
如果这需要在计算之前设置任何常量，那么不将其内联会更加昂贵。因此，对于虚拟调度，在 Skylake 上，这可能 运行 大约每 3 到 5 个时钟一个，而不是每个时钟大约 1 个成员。 （或者每个时钟 8 个成员使用 AVX2 for non-virtual class B，这不会浪费 space，并使 auto-vectorization 工作得很好。）http://agner.org/optimize/ says Skylake has one per 3 clock call throughput, so lets say 24x performance loss when the data is hot in L1D cache. Different microarchitectures will be different, of course. See the x86 标记 wiki 以获取更多信息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
}
}
A B 和 C 都以 vtable 开头，所以我认为这通常会起作用。我们认为基本相同，少了一步pointer-chasing。 （我使用静态数组而不是向量，因为我在整理要投射的内容时保持简单和 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 dispatch 的开销还要大，因为它允许处于 error-if-used 状态。因此，内部循环必须为此检查每个实例，如果是则捕获。此外，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
所以最多有3条call指令，除非指针是nullptr。这看起来比虚拟调度差得多。
使用 clang -stdlib=libc++ 而不是默认的 libstdc++ 看起来有点不同。 (https://libcxx.llvm.org/)。但是内部循环中仍然有三个 call 指令，有条件可以跳过它们或抛出。
除非 code-gen 对于不同类型的 function<T> 有很大不同，如果您可以编写更有效的替代方法，则可能甚至不值得查看指向成员函数的指针。
如果您确实需要 虚拟分派，一种在不同派生类型的对象列表上加速同一虚拟方法分派的方法是使用我将调用 类型取消切换.
有点类似于 loop unswitching，这将按顺序在每个对象上调用方法的单个循环转换为 N 个循环（对于 N 个支持的类型），每个循环在特定类型的所有对象上调用方法。这避免了不可预测的虚拟调度的主要成本：间接调用 vtable 中未知的、不可预测的函数所隐含的分支预测错误。
此技术的一般实现涉及按类型划分对象的第一遍：有关此分区的信息由第二遍使用，第二遍对每种类型都有单独的循环1，调用方法。如果仔细实施，这通常根本不涉及任何不可预测的分支。
在两个派生的情况下类 B和C你可以简单地使用位图来存储类型信息。这是一个示例实现，使用问题代码中的类型 A、B、C：
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;
}
}
这里，typecode是A中的公共字段，用于标识对象类型，0用于B，1用于C.需要类似的东西才能使按类型分类可行（它不能是虚拟调用，因为进行不可预测的调用是我们首先要避免的）。
上述略微优化的版本显示，与普通虚拟分派循环相比，未切换版本的加速大约为 3.5 倍，虚拟版本每次分派的时钟周期约为 19 个周期，而未切换版本约为 5.5 倍。完整结果：
-----------------------------------------------------------------------------
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
VirtualDispatchTrue 是在 A:
Update() 的简单循环
for (A *a : vecA) {
a->Update();
}
VirtualDispatchFakeB 在调用 Update() 之前将指针转换为 B*（不管底层类型是什么）。由于 B::Update() 是最终的，编译器可以完全去虚拟化和内联调用。当然，这根本不是在做正确的事情：它将任何 C 对象视为 B 并因此调用了错误的方法（并且完全是 UB）——但它是用来估计你的速度的如果每个对象都是相同的静态已知类型，则可以在指针向量上调用方法。
for (A *a : vecA) {
((B *)a)->Update();
}
StaticBPtr 遍历 std::vector<B*> 而不是 std::vector<A*>。正如预期的那样，性能与上面的 "fake B" 代码相同，因为 Update() 的目标是静态已知的并且完全可内联。它在这里作为完整性检查。
UnswitchTypes 是上面描述的类型取消切换技巧。
StaticB 迭代 std::vector<B>。也就是说，连续分配 B 个对象而不是 指针 的向量到 B 对象。这删除了一个间接级别并显示了此对象布局的最佳情况2.
full source 可用并发布到 public 域。
限制
副作用和顺序
此技术的主要限制是 Update() 调用的顺序无关紧要。虽然 Update() 仍然在每个对象上调用一次，但顺序已明显改变。只要对象不更新任何可变的全局或共享状态，这应该很容易满足。
支持两种类型
上面的代码只支持两种类型，基于使用位图来记录类型信息。
这个限制很容易解除。首先，可以扩展位图方法。例如，为了支持 4 种类型，可以创建两个相似的位图，每个位图的相应位基本上用于编码类型的 2 位字段。循环是相似的，除了在外循环中它们 & 和 ~ 位图以超过所有 4 种类型的方式组合在一起。例如：
// 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];
...
}
...
另一种方法是根本不使用位图，而是简单地存储每种类型的索引数组。数组中的每个索引都指向主数组中该类型的对象。本质上，它是对类型代码的单次基数排序。这可能会使类型排序部分变慢一些，但可能会加速循环迭代逻辑（x & (x - 1) 和 ctz 东西消失了，代价是另一个间接寻址）。
固定数量的支持类型
上面的代码支持固定数量的编译时已知类型（即 B 和 C）。如果引入新类型，上面的代码要么中断，要么肯定无法调用这些新类型的 Update()。
但是，添加对未知类型的支持很简单。只需将所有未知类型分组，然后仅针对这些类型，在循环内执行完整的虚拟分派（即直接在 A* 上调用 Update()）。您将支付全价，但仅限于您未明确支持的类型！这样，该技术零售了虚拟调度机制的通用性。
聚合集合
您可能对 Boost 的 PolyCollection 感兴趣。它基本上是一个专门用于这种情况的类似向量的容器：保存各种多态类型的对象并以有效的方式迭代它们。
它支持virtual基于方法的多态，也支持类函数对象多态和基于鸭子类型的多态。它通过在存储中隔离各种对象类型来实现上述 "unswitching"：因此它不会保持不同类型对象之间的插入顺序。如果满足您的需求，它可以是现成的解决方案。
1 实际上，对于所有 共享虚方法的相同实现 的类型，您只需要一个循环，尽管这可能难以以通用方式实施，因为此信息不容易获得。例如，如果 类 Y 和 Z 都派生自 X，但都没有覆盖 X 中某些虚方法的实现，则所有 X、Y 和 Z 可以由同一个循环处理。
2 "object layout" 我的意思是 B 仍然具有虚拟方法并因此具有 vtable 的对象。如果你删除所有虚拟方法并摆脱 vtable，事情会变得更快，因为编译器然后将加法矢量化到紧凑排列的字段。 vtable 搞砸了。