在共同基础类型的家族中获取整数类型ID的最有效方法

Question

在共同基础类型的家族中获取整数类型ID的最有效方法

c++performancevtablememory-efficienttypeid

7

问题：

我有一个基于共同基类的对象家族，需要通过整数值来识别特定的具体类型。

有两种明显的方法可以做到这一点，但是在内存或CPU时间方面都带来了不可接受的开销。由于项目涉及数十亿个对象，即使是最小的开销也会被严重强调，我已经测试过了，这不是过早优化的情况。处理对象所涉及的操作都是微不足道的，虚拟调用的开销极大地降低了性能。

1.对于每个类型实现一个纯虚函数int type()，但不幸的是，这带来了虚拟调用的开销，对于返回静态整数值这样微不足道的事情而言，这是无法接受的。

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

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

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

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

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

也许有一种方法可以在vtable中具有我的类型id整数，或者也许有另一种完全不同的方法，这是非常可能的，因为我没有跟上潮流，而C++在过去几年中得到了许多新功能。

当然，这些ID需要是统一和一致的，而不是编译器内部生成的任意值。如果这不是一个要求，我将使用vtable指针值来实现更高效的解决方案，以避免间接寻址。

有什么想法吗？

- dtech

是的，对象涉及的实际操作都很琐碎，每个操作只有几条指令，而虚拟调用绝对会极大地影响性能。就像90%的CPU时间开销... - dtech

1

此外，你的对象已经有虚表了吗？如果没有，通常会添加8个字节[如果你确实有数十亿个对象，因为在32位系统中你不太可能有那么多，即使在那里达到10亿个对象也非常困难]。 - Mats Petersson

最后，请解释一下您计划使用这些ID做什么。仅用于调试？自制的dyn_cast？还是其他什么？ - Mats Petersson

@dtech “规模需求”怎么会使这个解决方案被淘汰？ - Andreas

@Andreas，因为这些池需要非常大，并且它们的利用率几乎是未知和随意的，会导致很多内存“浪费”和无法使用，而我没有太多的存储空间。这就是为什么我将会采取“微型池”的原因-与处理数据不同，我可以承担一些额外的CPU周期来高效地分配树。 - dtech

显示剩余11条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user4842163 · Accepted Answer

如果你的实例数量比类型数量多很多，那么最直接的解决方案是在同类容器层面上进行抽象，而不是单个实例。

举例来说：

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

相比于在访问内存时需要存储一些类型信息（如虚表、type 字段等）以区分每个元素，从而以最零散的方式访问内存，你可以采用：

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

您需要在容器内存储类型信息（vtable或其他）。这意味着您需要访问一种更加同质的模式，但通常在我遇到的大多数问题中都可以做到这样的安排。

游戏开发者曾经会做一些像按子类型对多态基指针进行排序，同时使用自定义分配器将它们连续存储的事情。按基指针地址排序并从单独的池中分配每种类型的组合使您获得类似于类比的等效性：

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

大多数对象都被连续存储，因为它们每个都使用自定义分配器，将所有的Foos放入与所有Bars分离的连续块中，例如。如果按顺序访问内容，则还可以在vtables上获得时间局部性。

但是对我来说，这比在容器级别进行抽象更加痛苦，以这种方式进行处理仍然需要每个对象两个指针的开销（64位机器上为128位）（一个vptr和指向对象本身的基指针）。与其通过基指针逐个处理兽人、地精、人类等，不如将它们存储在同质容器中，进行抽象化，并处理指向整个同质集合的指针。而不是：

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

使用这种策略，如果我们的视频游戏需要一百万只兽人，我们将把与虚拟调度、vptr和基指针相关的成本降低到原来的1/1,000,000，更不用说您还可以获得非常优化的引用局部性，而且是免费的。

如果在某些情况下我们需要对特定生物进行操作，您可能能够存储一个由两部分组成的索引（可以将其放入32位或48位中），其中存储了生物类型索引，然后是该容器中相对生物索引，尽管这种策略在您不必调用函数来处理关键路径中的一个生物时最为有益。通常，您可以将此适配到32位索引或可能是48位索引，如果然后为每个同类容器设置2^16的限制，直到它被视为“已满”，并为相同类型创建另一个容器，例如：如果我们想要塞满我们的索引，我们不必将所有同类生物存储在一个容器中。

我不能确定这是否适用于您的情况，因为它取决于访问模式，但通常在与多态性相关的性能问题时，我考虑的第一个解决方案是这种方法。我首先看的方式是，您以太粒度付出了成本（如虚拟调度、失去连续访问模式、vtable上的时间局部性损失、vptr的内存开销等）。将设计变得更粗略（更大的对象，如代表整个事物集合的对象，而不是每个事物的单个对象），成本再次变得可以忽略。

无论如何，不要考虑vtables和其他内容，而是考虑如何排列数据，只考虑位和字节，这样就不必为每个小对象存储指针或整数。仅考虑位和字节的情况下进行绘制，不考虑类、vtables、虚函数和漂亮的公共接口等。在解决了内存表示/布局后再考虑这些，一开始只考虑位和字节，如下所示:

我发现对于需要提前预期性能关键需求的数据导向设计，这种方式更容易思考，而不是尝试思考语言机制和良好接口设计等问题。相反，我首先以类似C的方式考虑位和字节，并将我的想法作为结构体进行沟通和勾画，找出位和字节应该放置的位置。然后一旦你弄清楚了这一点，就可以想办法在上面放置一个漂亮的接口。

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

答案在您的问题主题中有所嵌入：

在共同基础类型家族中获取整数类型ID的最有效方法[...]

你可以将整数ID每个家庭存储一次，或者至少每个家族的多个对象中存储一次，而不是每个对象都存储一次。无论你如何处理，这都是唯一的方法，以避免除非信息已经可用，否则每个对象都存储它。另一种选择是从其他可用信息推导出它，例如你可以从对象的索引或指针地址推导出它，在这种情况下，存储ID只是冗余信息。