了解缓存友好,面向数据的对象和句柄

Question

using namespace std;

考虑实体/对象管理的传统OOP方法:

struct Entity { bool alive{true}; }

struct Manager {        
    vector<unique_ptr<Entity>> entities; // Non cache-friendly

    void update() {
        // erase-remove_if idiom: remove all !alive entities
        entities.erase(remove_if(begin(entities), end(entities),
            [](const unique_ptr<Entity>& e){ return !e->alive; }));
    }
};

struct UserObject {
    // Even if Manager::entities contents are re-ordered
    // this reference is still valid (if the entity was not deleted)
    Entity& entity;
};

但是,我想尝试一种面向数据的方法:不动态分配Entity实例,而是将它们存储在缓存友好的线性内存中.

struct Manager {
    vector<Entity> entities; // Cache-friendly
    void update() { /* erase-remove_if !alive entities */ }
};

struct UserObject {
    // This reference may unexpectedly become invalid
    Entity& entity;
};

看起来很好.但是......如果std::vector需要重新分配其内部数组,对实体的所有引用都将变为无效.

解决方案是使用句柄类.

struct Entity { bool alive{true}; };
struct EntityHandle { int index; };

struct Manager {
    vector<Entity> entities; // Cache-friendly      
    void update() { /* erase-remove_if !alive entities */ }
    Entity& getEntity(EntityHandle h) { return entities[h.index]; }
};

struct UserObject { EntityHandle entity; };

如果我只是在向量的后面添加/删除实体,它似乎工作.我可以使用该getEntity方法来检索我想要的实体.

但是,如果我Entity从矢量中间删除一个怎么办？所有EntityHandle实例现在都将保留不正确的索引,因为所有实例都已移位.例:

---

句柄指向索引:2

---

实体A在update()期间被删除

现在句柄指向错误的实体.

---

这个问题通常是如何处理的？

句柄索引是否更新？

死者实体是否被占位符取代？

---

澄清:

这和这是我所说的意思实例缓存的人性化设计.

此外,Artemis等组件系统声称采用线性缓存友好设计,并且使用类似于句柄的解决方案.他们如何处理我在这个问题中描述的问题？

Answer 1

如果您需要稳定的索引或指针，那么您的数据结构要求开始类似于内存分配器的要求。内存分配器也是一种特殊类型的数据结构，但面临这样的要求，即它们不能乱序或重新分配内存，因为这会使客户端存储的指针无效。所以我建议查看内存分配器的实现，从经典的空闲列表开始。

免费列表

这是我写的一个简单的 C 实现来向同事说明这个想法（不打扰线程同步）：

typedef struct FreeList FreeList;

struct FreeList
{
    /// Stores a pointer to the first block in the free list.
    struct FlBlock* first_block;

    /// Stores a pointer to the first free chunk.
    struct FlNode* first_node;

    /// Stores the size of a chunk.
    int type_size;

    /// Stores the number of elements in a block.
    int block_num;
};

/// @return A free list allocator using the specified type and block size, 
/// both specified in bytes.
FreeList fl_create(int type_size, int block_size);

/// Destroys the free list allocator.
void fl_destroy(FreeList* fl);

/// @return A pointer to a newly allocated chunk.
void* fl_malloc(FreeList* fl);

/// Frees the specified chunk.
void fl_free(FreeList* fl, void* mem);

// Implementation:   
typedef struct FlNode FlNode;
typedef struct FlBlock FlBlock;
typedef long long FlAlignType;

struct FlNode
{
    // Stores a pointer to the next free chunk.
    FlNode* next;
};

struct FlBlock
{
    // Stores a pointer to the next block in the list.
    FlBlock* next;

    // Stores the memory for each chunk (variable-length struct).
    FlAlignType mem[1];
};

static void* mem_offset(void* ptr, int n)
{
    // Returns the memory address of the pointer offset by 'n' bytes.
    char* mem = ptr;
    return mem + n;
}

FreeList fl_create(int type_size, int block_size)
{
    // Initialize the free list.
    FreeList fl;
    fl.type_size = type_size >= sizeof(FlNode) ? type_size: sizeof(FlNode);
    fl.block_num = block_size / type_size;
    fl.first_node = 0;
    fl.first_block = 0;
    if (fl.block_num == 0)
        fl.block_num = 1;
    return fl;
}

void fl_destroy(FreeList* fl)
{
    // Free each block in the list, popping a block until the stack is empty.
    while (fl->first_block)
    {
        FlBlock* block = fl->first_block;
        fl->first_block = block->next;
        free(block);
    }
    fl->first_node = 0;
}

void* fl_malloc(FreeList* fl)
{
    // Common case: just pop free element and return.
    FlNode* node = fl->first_node;
    if (node)
    {
        void* mem = node;
        fl->first_node = node->next;
        return mem;
    }
    else
    {
        // Rare case when we're out of free elements.
        // Try to allocate a new block.
        const int block_header_size = sizeof(FlBlock) - sizeof(FlAlignType);
        const int block_size = block_header_size + fl->type_size*fl->block_num;
        FlBlock* new_block = malloc(block_size);

        if (new_block)
        {
            // If the allocation succeeded, initialize the block.
            int j = 0;
            new_block->next = fl->first_block;
            fl->first_block = new_block;

            // Push all but the first chunk in the block to the free list.
            for (j=1; j < fl->block_num; ++j)
            {
                FlNode* node = mem_offset(new_block->mem, j * fl->type_size);
                node->next = fl->first_node;
                fl->first_node = node;
            }

            // Return a pointer to the first chunk in the block.
            return new_block->mem;
        }

        // If we failed to allocate the new block, return null to indicate failure.
        return 0;
    }
}

void fl_free(FreeList* fl, void* mem)
{
    // Just push a free element to the stack.
    FlNode* node = mem;
    node->next = fl->first_node;
    fl->first_node = node;
}

随机访问序列，嵌套自由列表

理解自由列表的想法后，一种可能的解决方案是：

这种类型的数据结构将为您提供不会失效的稳定指针，而不仅仅是索引。但是，如果您想为其使用迭代器，它会增加随机访问和顺序访问的成本。它可以vector像使用for_each方法一样进行顺序访问。

这个想法是使用上面的空闲列表的概念，除了每个块存储一个自己的空闲列表，聚合块的外部数据结构存储一个块的空闲列表。一个块只有在它完全满时才会从空闲堆栈中弹出。

并行占用位

另一种方法是使用位的并行阵列来指示阵列的哪些部分被占用/空闲。这样做的好处是，您可以在顺序迭代期间检查是否一次占用了许多索引（一次 64 位，此时您可以访问循环中的所有 64 个连续元素，而无需单独检查它们是否被占用）占据）。当并非所有 64 个索引都被占用时，您可以使用FFS指令快速确定设置了哪些位。

您可以将其与空闲列表结合起来，然后使用这些位来快速确定迭代期间占用的索引，同时具有快速的恒定时间插入和删除。

实际上，std::vector与使用侧面的索引/指针列表相比，您可以获得更快的顺序访问，因为我们可以再次检查 64 位以查看要在数据结构中遍历哪些元素，并且因为访问模式将始终是顺序的（类似于在数组中使用排序的索引列表）。

所有这些概念都围绕着在数组中留下空白空间以在后续插入时回收，如果您不希望索引或指针对尚未从容器中删除的元素无效，这将成为一个实际要求。

单链索引列表

另一种解决方案是使用单向链表，大多数人可能认为它涉及每个节点的单独堆分配，并且在遍历时缓存未命中数不胜数，但事实并非如此。我们可以将节点连续存储在一个数组中并将它们链接在一起。如果您不认为链表是一个容器，而只是将存储在另一个容器中的现有元素（如数组）链接在一起，以允许不同的遍历和搜索模式，那么优化机会的世界实际上会打开。将所有内容都存储在一个带有索引的连续数组中以将它们链接在一起的示例：

像这样存储数据：

struct Bucket
{
    struct Node
    {
         // Stores the element data.
         T some_data;

         // Points to either the next node in the bucket
         // or the next free node available if this node
         // has been removed.
         int next;
    };
    vector<Node> data;

    // Points to first node in the bucket.
    int head;

    // Points to first free node in the bucket.
    int free_head;
};

这不允许随机访问，如果您从中间删除并经常插入，它的空间局部性会降低。但是使用后处理副本恢复它很容易。如果您只需要顺序访问并希望恒定时间删除和插入，它可能是合适的。如果您需要稳定的指针而不仅仅是索引，那么您可以将上述结构与嵌套的空闲列表一起使用。

当您有很多非常动态的小列表（不断删除和插入）时，索引 SLL 往往会做得很好。粒子连续存储的另一个示例，但 32 位索引链接仅用于将它们划分为网格以进行快速碰撞检测，同时允许粒子移动每一帧，并且只需更改几个整数即可将粒子从一个帧转移网格单元格到另一个：

在这种情况下，您可以将 1000x1000 的网格存储在 4 兆字节以下——这绝对胜过存储一百万个std::listor实例，std::vector并且必须在粒子四处移动时不断地从它们中删除和插入它们。

入住指数

如果您只需要稳定的索引，另一个简单的解决方案就是使用，例如，std::vector使用std::stack<int>of 自由索引来回收/覆盖插入。这遵循常量时间删除的空闲列表原则，但效率稍低，因为它需要内存来存储空闲索引堆栈。免费列表使堆栈免费。

但是，除非您手动滚动它并避免仅使用 ，否则您std::vector<T>无法非常有效地使其触发您在删除时存储的元素类型的析构函数（我一直没有跟上 C++，更多的是一个 C 程序员这些天来，但可能有一种方法可以很好地做到这一点，它仍然尊重您的元素析构函数，而无需手动滚动您自己的等价物std::vector- 也许 C++ 专家可以参与）。如果您的类型是平凡的 POD 类型，那可能没问题。

template <class T>
class ArrayWithHoles
{
private:
    std::vector<T> elements;
    std::stack<size_t> free_stack;

public:
    ...

    size_t insert(const T& element)
    {
        if (free_stack.empty())
        {
            elements.push_back(element);
            return elements.size() - 1;
        }
        else
        {
            const size_t index = free_stack.top();
            free_stack.pop();
            elements[index] = element;
            return index;
        }
    }

    void erase(size_t n)
    {
        free_stack.push(n);
    }
};

这种效果的东西。这让我们陷入两难境地，因为我们无法判断哪些元素已从容器中移除以在迭代过程中跳过。在这里，您可以再次使用并行位数组，或者您也可以只在侧面存储有效索引列表。

如果这样做，有效索引列表可能会在内存访问模式方面降级到数组中，因为它们会随着时间的推移变得未排序。一种快速修复方法是不时对索引进行基数排序，此时您已经恢复了顺序访问模式。

Answer 2

失眠者做了一个伟大的powerpoint,他们的解决方案是这样的

template<typename T, int SIZE>
class ResourceManager
{
    T data[SIZE];
    int indices[SIZE];
    int back;

    ResourceManager() : back(0)
    {
        for(int i=0; i<SIZE; i++)
            indices[i] = i;
    }

    int Reserve()
    { return indices[back++]; }

    void Release(int handle)
    {
        for(int i=0; i<back; i++)
        {
            if(indices[i] == handle)
            {
                back--;
                std::swap(indices[i], indices[back]);
                return;
            }
        }
    }

    T GetData(int handle)
    { return data[handle]; }
};

我希望这个例子清楚地表明了这个想法