c++ - 在常见基类型系列中获取整数类型 ID 的最有效方法

Question

问题:

我有一系列具有共同基础的对象，我需要能够通过整数值识别特定的具体类型。

有两种明显的方法可以做到这一点，但是两者在内存或 CPU 时间方面都有 Not Acceptable 开销。由于该项目处理数十亿个对象，因此最小的开销最终会非常明显，我已经对此进行了测试，这不是过早优化的情况。处理对象所涉及的操作都是微不足道的，虚拟调用的开销极大地降低了性能。

纯虚int type()为每种类型实现的函数，不幸的是伴随着虚拟调用的开销，比如返回一个静态整数值

int type每个实例的成员，在构造函数类型中指定，这为这数十亿个对象中的每一个引入了 4 字节的开销，浪费了内存，污染了缓存等等

我记得前段时间有人问“静态虚拟成员变量”，答案自然归结为“不，那没有意义”，但是能够将用户变量放入 vtable 并能够设置其值对于每种特定类型似乎是解决我的问题的非常有效的方法。

这样就避免了上述两种开销，不需要虚拟调用，也没有每个实例的内存开销。唯一的开销是获取 vtable 的间接开销，但考虑到该数据的访问频率，它很可能大部分时间都保存在 cpu 缓存中。

我目前明显的选择是做“手动 OOP”——手动做 vtables 以便将必要的“元”数据合并到它们中，为每种类型初始化 vtable 指针并使用笨拙的语法来调用伪“成员”函数。或者甚至完全省略 vtable 指针的使用，而是存储 id，并将其用作 vtable 表的索引，这将更加有效，因为它将避免间接，并且会缩小大小，因为我只需要 2^14 个不同的类型。

如果我能避免重新发明轮子就好了。我对解决方案并不挑剔，只要它能给我效率保证。

也许有一种方法可以将我的类型 id 整数放在 vtable 中，或者完全有另一种方法，这是很有可能的，因为我没有跟上趋势，而且 C++ 在最近的几个中获得了很多新功能年。

自然地，这些 id 需要统一和一致，而不是编译器内部编造的任意值。如果这不是必需的，我只会使用 vtable 指针值来获得更有效的解决方案，以避免间接。

有任何想法吗？

Answer 1

如果实例比类型多，那么最直接的解决方案是在同构容器级别而不是单个实例级别进行抽象。

代替:

{PolymorphicContainer}: Foo*, Bar*, Baz*, Foo*, Bar*, Bar*, Baz*, ...

...并且必须存储一些类型信息(vtable，type 字段等)以在以最零星的方式访问内存时区分每个元素，您可以拥有:

{FooContainer}: Foo, Foo, Foo, Foo, Foo, ...
{BarContainer}: Bar, Bar, Bar, Bar, Bar, ...
{BazContainer}: Baz, Baz, Baz, Baz, Baz, ...
{PolymorphicContainer}: FooContainer*, BarContainer*, BazContainer*

并且您将类型信息(vtable 或其他)存储在容器内。这确实意味着您需要一种更趋同的访问模式，但通常可以在我遇到的大多数问题中进行这样的安排。

Gamedevs 过去常常做一些事情，比如按子类型对多态基指针进行排序，同时为每个指针使用自定义分配器来连续存储它们。按基指针地址排序和从不同的池中分配每种类型的组合使得你得到类似的等价物:

Foo*, Foo*, Foo*, Foo*, ..., Bar*, Bar*, Bar*, Bar*, ..., Baz*, Baz*, Baz*, ...

它们中的大多数是连续存储的，因为它们每个都使用自定义分配器，将所有 Foo 放入与所有 Bar 分开的连续块中，例如然后在空间局部性之上，如果您以顺序模式访问事物，您还会在 vtable 上获得时间局部性。

但这对我来说比在容器级别抽象更痛苦，这样做仍然需要每个对象(一个 vptr 和一个指向对象本身的基指针)的两个指针(64 位机器上的 128 位)的开销)。而不是通过 Creature* 单独处理兽人、地精、人类等。基指针，对我来说将它们存储在同构容器中，抽象它并处理 Creatures* 是有意义的。指向整个同类集合的指针。代替:

class Orc: public Creature {...};

... 我们的确是:

// vptr only stored once for all orcs in the entire game.
class Orcs: public Creatures
{
public:
    // public interface consists predominantly of functions
    // which process entire ranges of orcs at once (virtual
    // dispatch only paid once possibly for a million orcs
    // rather than a million times over per orc).
    ...

private:
    struct OrcData {...};
    std::vector<OrcData> orcs;
};

代替:

for each creature:
     creature.do_something();

我们的确是:

for each creatures:
     creatures.do_something();

使用这种策略，如果我们在视频游戏中需要一百万个兽人，我们会将与虚拟调度、vptrs 和基本指针相关的成本降低到原始成本的 1/1,000,000，更不用说您获得了非常理想的位置也可以免费引用。

如果在某些情况下我们需要对特定生物做一些事情，您可能能够存储一个由两部分组成的索引(可能能够适应 32 位或 48 位)，存储生物类型索引，然后是相对生物索引那个容器，虽然当你不必调用函数来处理关键路径中的一个生物时，这种策略最有用。通常，您可以将其放入 32 位索引或可能的 48 位索引中，如果然后在将其视为“已满”之前为每个 2^16 的同类容器设置限制，并为相同类型创建另一个容器，例如如果我们想塞满索引，我们不必将一种类型的所有生物都存储在一个容器中。

我不能确定这是否适用于您的情况，因为它取决于访问模式，但是当您遇到与多态相关的性能问题时，它通常是我考虑的第一个解决方案。我看待它的第一种方式是，您正在支付成本，例如虚拟调度、连续访问模式的丢失、vtables 上的时间局部性丢失、vptr 的内存开销等，这些成本太细化了。使设计更粗糙(更大的对象，例如代表整个事物集合的对象，而不是每个事物的单个对象)，并且成本再次变得可以忽略不计。

不管是什么情况，与其从 vtables 的角度考虑这个问题，还不如从你如何安排数据的角度来考虑它，只是位和字节，这样你就不必存储一个指针或整数单个小物体。只考虑位和字节，而不是类和虚表、虚函数和漂亮的公共(public)接口(interface)等等。在确定内存表示/布局之后再考虑一下，然后开始只考虑位和字节，如下所示:



我发现对于具有性能关键需求的面向数据的设计来说，这比尝试考虑语言机制和漂亮的界面设计等等要容易得多。相反，我首先以类似 C 的方式思考位和字节，然后将我的想法传达和勾勒为 structs并找出位和字节应该去哪里。然后一旦你弄清楚了，你就可以弄清楚如何把一个漂亮的界面放在上面。

无论如何，为了避免每个小对象的类型信息开销，这意味着以某种方式在内存中将它们组合在一起，并且每组存储一次类比类型字段而不是组中的每个元素一次。以统一的方式分配特定类型的元素也可能会根据它们的指针地址或索引为您提供该信息，例如有很多方法可以解决这个问题，但只需将存储在内存中的数据作为一般策略来考虑。

答案在某种程度上嵌入到您的问题主题中:

Most efficient way to get an integer type id in a family of common base types [...]

您可以为每个系列存储一次整数 ID，或者至少为该系列中的多个对象存储一次整数 ID，而不是每个对象存储一次。除非信息已经可用，否则这是避免每个对象存储一次的唯一方法。另一种方法是从一些其他可用信息中推断出它，就像您可以从对象的索引或指针地址中推断出它一样，此时存储 ID 将只是冗余信息。