我有一个具有共同基础的对象族,我需要能够通过整数值来识别特定的具体类型.
有两种明显的方法可以做到这一点,但是在内存或cpu时间方面都会产生不可接受的开销.由于该项目涉及数十亿个对象,因此最微小的开销最终会发出严重的声音,而且我已经对此进行了测试,这不是过早优化的情况.处理对象所涉及的操作都是微不足道的,虚拟调用的开销极大地降低了性能.
>为每种类型实现的纯虚拟int类型()函数,不幸的是,它带来了虚拟调用的开销,这对于返回静态整数值一样微不足道
>构造函数类型中指定的每个实例的int类型成员,它为这些数十亿个对象中的每一个引入了4字节开销,浪费内存,污染缓存等等
我记得前段时间有人询问“静态虚拟成员变量”,自然答案归结为“不,这没有意义”,但是能够将用户变量放在vtable中并且能够设置其值对于每个特定类型似乎是一个非常有效的解决我的问题.
这样就避免了上述两种开销,不需要虚拟调用,也没有每个实例的内存开销.唯一的开销是获取vtable的间接,但考虑到访问该数据的频率,它很可能大部分时间都保存在cpu缓存中.
我目前显而易见的选择是做“手动OOP” – 手动执行vtables以便将必要的“元”数据合并到它们中,为每种类型初始化vtable指针并使用笨拙的语法来调用伪“成员”函数.或者甚至完全省略vtable指针的使用,而是存储id,并将其用作vtable表的索引,这将更有效,因为它将避免间接,并将缩小大小,因为我只需要2 ^ 14种不同的类型.
如果我能避免重新发明轮子那就太好了.只要能给我效率保证,我对解决方案并不挑剔.
也许有一种方法可以在vtable中使用我的类型id整数,或者可能还有另一种方式,这很可能因为我跟不上趋势,而C在最后几个中获得了很多新功能年份.
当然,那些id需要统一和一致,而不是编译器内部编写的任何值.如果这不是一个要求,我只是使用vtable指针值来获得更有效的解决方案,避免间接.
有任何想法吗？
解决方法
代替：
{PolymorphicContainer}: Foo*,Bar*,Baz*,Foo*,...
…并且必须存储一些类型信息(vtable,类型字段等)以区分每个元素,同时以最零星的方式访问内存,您可以：
{FooContainer}: Foo,Foo,...
{BarContainer}: Bar,Bar,...
{BazContainer}: Baz,Baz,...
{PolymorphicContainer}: FooContainer*,BarContainer*,BazContainer*
并且您将容器内的类型信息(vtable或不是)存储起来.这确实意味着你需要一种更加同质的访问模式,但通常这种安排可以在我遇到的大多数问题中进行.
Gamedevs过去常常按照子类型对多态基本指针进行排序,同时使用自定义分配器为每个按钮连续存储它们.通过基指针地址排序和从不同的池中分配每种类型的组合使得您可以获得类似的等效：
Foo*,...,...
其中大多数都是连续存储的,因为它们各自使用一个自定义分配器,它将所有Foos放入与所有条形分开的连续块中,例如,然后,在空间局部性的顶部,如果以连续模式访问事物,则还可以在vtable上获得时间局部性.
但是这对我来说比在容器级别抽象更痛苦,并且这样做仍然需要每个对象的两个指针(64位机器上128位)的开销(vptr和指向对象本身的基指针) ).不是通过Creature * base指针单独处理orcs,goblins,human等,我将它们存储在同类容器中,抽象出来,并处理指向整个同类集合的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,更不用说你得到的最佳位置了参考也是免费的.
如果在某些情况下我们需要对特定生物做某事,你可能能够存储一个两部分索引(可能能够适合32位或48个)存储生物类型索引,然后存储相对生物指数那个容器,虽然这个策略最有用,当你不必调用函数来处理关键路径中的一个生物时.通常,您可以将此值设置为32位索引或者可能是48位,如果您在每个同类容器设置为2 ^ 16之前设置其限制,然后再将其视为“已满”,并为同一类型创建另一个容器,例如如果我们想要填充索引,我们不必将一种类型的所有生物存储在一个容器中.
我不能确定这是否适用于您的情况,因为它取决于访问模式,但它通常是我遇到与多态性相关的性能问题时考虑的第一个解决方案.我看待它的第一种方式是你付出的代价是虚拟调度,连续访问模式的丢失,vtable上时间局部性的丢失,vptr的内存开销等等.使设计更粗糙(更大的对象,如代表整个事物集合的对象,而不是每个事物的单个对象),成本再次可以忽略不计.
无论情况如何,而不是在vtable方面考虑这个问题,而不是考虑如何排列数据,只考虑位和字节,这样你就不必每次都存储一个指针或整数.单个小物件.只考虑位和字节,而不是类和vtable和虚函数以及漂亮的公共接口等等.在确定内存表示/布局之后再考虑一下,然后开始考虑位和字节,如下所示：
我发现这对于面向数据的设计来说更容易思考,而不是试图考虑语言机制和漂亮的界面设计以及所有这些,这些设计具有令人期待的性能关键需求.相反,我认为首先是以类似于C的方式使用位和字节,并将我的想法作为结构进行通信和绘制,并找出位和字节的位置.然后,一旦你想出来,你就可以弄清楚如何在顶部放置一个漂亮的界面.
无论如何,为了避免每个青少年对象的类型信息的开销,这意味着它们以某种方式在内存中组合在一起并且每组存储该类比类型字段而不是每组中的元素存储一次.以统一的方式分配特定类型的元素也可能会根据指针地址或索引为您提供信息,例如：有很多方法可以解决这个问题,但只需考虑存储在内存中的数据作为一般策略.
答案有点嵌入您的问题主题：
Most efficient way to get an integer type id in a family of common
base types […]
您可以为每个族存储一次整数ID,或者为该族中的每个多个对象存储至少一次,而不是每个对象存储一次.这是唯一的方法,无论你接近它,避免每个对象存储一次,除非信息已经可用.另一种方法是从其他一些可用的信息中推断出它,就像你可以从对象的索引或指针地址中推断它一样,此时存储ID只是冗余信息.
