c++ - 避免与实体组件系统中与1:N关系相关的缓存未命中

如何避免实体组件系统(ECS)中与1:N(pirateship-cannon)关系相关的缓存丢失？

例如，PirateShip可以具有1-100 cannons。 (1:N)
每个cannon可以随时自由地分离/附加到任何pirateship。

对于某些reasons，PirateShip和Cannon应该是实体。

内存图

在大约第一个时间步中，当逐渐创建ship / cannon时，ECS内存看起来非常漂亮:-

图片备注:

左=低位地址，右=高位地址

尽管似乎存在差距，但ShipCom和CannonCom实际上是紧凑的数组。

从cannon中访问ship信息的速度非常快，反之亦然(伪代码):-

Ptr<ShipCom> shipCom=....;
EntityPtr ship =  shipCom;  //implicitly conversion
Array<EntityPtr> cannons = getAllCannonFromShip(ship);
for(auto cannon: cannons){
    Ptr<CannonCom> cannonCom=cannon;
    //cannonCom-> ....
}

问题

在随后的时间步中，将随机创建/销毁一些ship / cannon。
结果，Entity，ShipCom和CannonCom数组周围有间隙散射。
当我想分配它们时，我将从池中获得一个随机的内存块。

EntityPtr ship = .....  (an old existing ship)
EntityPtr cannon = createNewEntity();
Ptr<CannonCom> cannonCom= createNew<CannonCom>(cannon);
attach_Pirate_Cannon(ship,cannon);
//^ ship entity and cannon tend to have very different (far-away) address

因此，上面的“真正快速”的代码变成了瓶颈。 (我分析了。)

(编辑)我认为，底层缓存未命中也可能是同一艘船内加农炮之间的不同地址造成的。

例如(@是炮塔组件的地址)，

ShipA将turret@01转换为turret@49

ShipB将turret@50转换为turret@99

在以后的时间步中，如果将turret@99移到ShipA，它将是:-

ShipA将turret@01转换为turret@49 + turret@99 (内存跳转)

ShipB将turret@50转换为turret@98

问题

什么是设计模式/ C++魔术可以减少频繁使用的关系导致的缓存丢失？

更多信息:

在实际情况下，存在许多1:1和1:N关系。特定关系将特定类型的组件绑定(bind)到特定类型的组件。

例如，relation_Pirate_Cannon = (ShipCom:CannonCom)，relation_physic_graphic = (PhysicCom:GraphicCom)

通常只有一些关系是“间接的”。

当前体系结构对Entity / ShipCom / CannonCom的数量没有限制。
我不想在程序开始时限制它。

我更喜欢而不是的改进，这使得游戏逻辑编码更加困难。

我想到的第一个解决方案是启用重定位，但是我认为这是不得已的方法。

最佳答案

一种可能的解决方案是添加间接的另一层。它会使事情放慢一点，但有助于保持阵列紧凑，并可以加快整个过程。剖析是唯一知道是否真的有帮助的方法。

话虽这么说，该怎么做？
Here是稀疏集合的简要介绍，值得一读，以便更好地理解我的意思。

与其在同一数组中的项目之间创建关系，不如使用第二个指向的数组。
让我们将两个数组称为反向和直接:

reverse通过实体标识符(一个数字，因此仅是数组中的索引)进行访问。每个插槽都包含直接数组中的索引。

直接访问

，好吧……直接，每个插槽都包含实体标识符(这是访问反向数组的索引)和实际组件。

每当您添加大炮时，都将获取其实体标识符和直接数组中的第一个空闲插槽。使用您的实体标识符设置slot.entity，并将reverse[entity]放入插槽的索引。每当您放下东西时，都复制直接数组中的最后一个元素以使其紧凑并调整索引，以保持关系。
船会将索引存储到外部数组(反向)，以便您可以自由地在内部数组(直接)之间来回切换。

优点和缺点是什么？
好吧，每当您通过外部阵列访问大炮时，由于存在额外的间接层，您都会有一个额外的跳跃。无论如何，只要您成功地减少了以此方式进行的访问次数，并且您访问了系统中的直接阵列，就可以使用紧凑的阵列进行迭代，并且使高速缓存未命中的次数最少。

关于c++ - 避免与实体组件系统中与1:N关系相关的缓存未命中，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45316989/