背景

在游戏引擎开发中,我们通常使用面向数据的设计来获得最佳的内存和计算性能.

我们以粒子系统为例.

在粒子系统中,我们有很多粒子,每个粒子可能有几个属性,如位置,速度等.

C++中的典型实现如下:

struct Particle {
    float positionX, positionY, positionZ;
    float velocityX, velocityY, velocityZ;
    float mass;
    // ...
};

struct ParticleSystem {
    vector<Particle> particles;
    // ...
};

该实现的一个问题是粒子属性彼此交错.此内存布局不是缓存友好的,可能不适合SIMD计算.

而是在面向数据的设计中,我们编写以下代码:

struct ParticleAttribute {
    size_t size;
    size_t alignment;
    const char* semantic;
};

struct ParticleSystem {
    ParticleSystem(
        size_t numParticles,
        const ParticleAttribute* attributes,
        size_t bufferSize) {
        for (size_t i = 0; i < numAttributes; ++i) {
            bufferSize += attributes[i].size * numParticles;
            // Also add paddings to satisfy the alignment requirements.
        }
        particleBuffer …

我一直在使用https://github.com/google/benchmark和g++ 9.4.0来检查不同场景下数据访问的性能（用“ -O3”编译）。结果令我惊讶。

我的基线是访问std::array（“减少数据”）中的长数。我想添加一个额外的字节数据。一次我创建一个额外的容器（“拆分数据”），一次我在数组中存储一个结构（“组合数据”）。

这是代码：

#include <benchmark/benchmark.h>

#include <array>
#include <random>

constexpr int width  = 640;
constexpr int height = 480;

std::array<std::uint64_t, width * height> containerWithReducedData;

std::array<std::uint64_t, width * height> container1WithSplitData;
std::array<std::uint8_t, width * height>  container2WithSplitData;

struct CombinedData
{
    std::uint64_t first;
    std::uint8_t  second;
};

std::array<CombinedData, width * height> containerWithCombinedData;

void fillReducedData(const benchmark::State& state)
{
    // Variable is intentionally unused
    static_cast<void>(state);

    // Generate pseudo-random numbers (no seed, therefore always the same numbers)
    // NOLINTNEXTLINE
    auto engine …

我需要从中创建中小型静态哈希表.通常,这些将有5-100个条目.当创建哈希表时,所有键哈希都是预先知道的(即键已经是哈希值.)目前,我创建了一个HashMap,这是我对键进行排序所以我得到O(log n)查找3-5平均查找我关心的尺寸.维基百科称,与链接一个简单的哈希表会导致平均的全表3个查找,所以这还不值得我的麻烦(即以散%N作为第一项,并做了链接.)鉴于我知道所有哈希都在前面,似乎应该有一个简单的方法来获得一个快速,静态完美的哈希 - 但我找不到一个好的指针如何.即摊销O(1)访问没有(少？)额外的开销.我该如何实现这样的静态表？

内存使用很重要,因此我需要存储的越少越好.

编辑:请注意,如果我必须手动解决一次碰撞,那就没问题.也就是说,如果我能做一些链接,例如平均有直接访问和最坏情况3的间接,那就没问题.这不是我需要一个完美的哈希.

我最近发现了面向数据设计的好处。它看起来非常令人印象深刻。要点之一是按类型和访问对数据进行分组，不是全部放在对象中，而是放在数组中，以防止缓存未命中并进行更好的处理。

所以在游戏中我们仍然有实例，用户可以销毁它们中的任何一个（不仅仅是数组中的最后一个）。我不知道如何有效地处理数组中间的对象删除。

我有一个想法：要isAlive有价值，但这会对条件数量造成相当大的影响，因为每个对象在处理、绘图、...

另一个想法是移动整个数组以填充必须删除的空间，但这会在删除时消耗大量资源。

人如何在国防部处理这个问题？

所以提出要求：

• 它必须是数组，以减少 DOD 中描述的缓存未命中
• 它必须具有快速随机位置对象删除，最大 o(log n)
• 对象自创建以来就不能移动，因为它们可能在未知的地方被引用，因此会导致程序错误行为

现在，当阅读 Internet 中的不同资源时，如果您要按顺序处理大型数组，那么数组结构似乎是一种非常高效的数据存储方式。

例如在 C++ 中

struct CoordFrames
{
    float* x_pos;
    float* y_pos;
    float* z_pos;
    float* scaleFactor;
    float* x_quat;
    float* y_quat;
    float* z_quat;
    float* w_quat;
};

允许比数组更快地处理大数组（感谢 SIMD）

struct CoordFrame
{
    glm::vec3 position;
    float scaleFactor;
    glm::quat quaternion;
};

GPU 是专为大规模并行计算而设计的处理器。SIMD 是这里的“必备”。所以结论是数组结构在这里最有用。

但 ...

• 我从未在任何地方看到过这样的 GLSL 着色器（这对我来说是错误的）：

  #define NUM_POINT_LIGHTS 16
  uniform float point_light_x[NUM_POINT_LIGHTS];
  uniform float point_light_y[NUM_POINT_LIGHTS];
  uniform float point_light_z[NUM_POINT_LIGHTS];
  uniform float point_light_radius[NUM_POINT_LIGHTS];
  uniform float point_light_color_r[NUM_POINT_LIGHTS];
  uniform float point_light_color_g[NUM_POINT_LIGHTS];
  uniform float point_light_color_b[NUM_POINT_LIGHTS];
  uniform float point_light_power[NUM_POINT_LIGHTS];
  

  Run Code Online (Sandbox Code Playgroud)

  或类似的东西也不经常看到：

  #define NUM_POINT_LIGHTS 16
  uniform vec3 point_light_pos[NUM_POINT_LIGHTS]; …

  Run Code Online (Sandbox Code Playgroud)

假设我有一个使用Array of Structures(AoS)内存布局的大代码.我想在C++中构建一个零成本的抽象,它允许我在尽可能少的重构努力之间切换AoS和SoA.例如,使用具有访问成员函数的类

 struct Item{
   auto& myDouble(){ return mDouble; }
   auto& myChar(){ return mChar; }
   auto& myString(){ return mString; }
 private:
   double mDouble;
   char mChar;
   std::string mString;
 };

它在循环中的容器内使用

std::vector<Item> vec_(1000);
for (auto& i : vec_)
  i.myDouble()=5.;

我想改变第一个片段,而第二个片段保持相似...例如,有类似的东西

MyContainer<Item, SoA> vec_(1000)
for (auto& i : vec_)
  i.myDouble()=5.;

我可以使用"SoA"或"AoS"模板参数选择内存布局.我的问题是:这样的事情存在于某个地方吗？如果没有,最好如何实施？

目前，我的应用程序包含三种类型的类。它应该遵循面向数据的设计，如果不是，请纠正我。这是三种类型的类。代码示例并不那么重要，您可以根据需要跳过它们。他们只是为了给人留下印象。我的问题是，我应该向我的类型类添加方法吗？

当前设计

类型只是保存值。

struct Person {
    Person() : Walking(false), Jumping(false) {}
    float Height, Mass;
    bool Walking, Jumping;
};

每个模块实现一个独特的功能。它们可以访问所有类型，因为它们是全局存储的。

class Renderer : public Module {
public:
    void Init() {
        // init opengl and glew
        // ...
    }
    void Update() {
        // fetch all instances of one type
        unordered_map<uint64_t, *Model> models = Entity->Get<Model>();
        for (auto i : models) {
            uint64_t id = i.first;
            Model *model = i.second;
            // fetch single instance by id
            Transform *transform = Entity->Get<Transform>(id);
            // …