2

I want to iterate over objects which are stored very close together (to reduce cache misses). Would I be right in that I could achieve this by creating a vector so that all my objects are located continuously and then just create the linked list using references to X? This way I can insert to the head of the list very quickly and when i iterate through the list elements they won't be too far away from each other because they were all from the same vector?

4

3 回答 3

1

简短的回答是肯定的。由于连续的内存存储，Vector 比链表更适合您的需求。迭代向量并获取其元素通常比链表快得多，前提是向量中的项目不太大。

于 2013-10-04T18:23:05.353 回答
0

您需要随机访问存储中的每个项目，还是顺序访问。内存存储有多大，有多少元素？最长的元素有多大？

有很多方法可以访问您的存储，

  • 原始顺序遍历存储
  • 用指向下一个元素的指针扩充每个存储元素
  • 将每个存储元素增加一个偏移量（跳过计数）到下一个元素
  • 在存储中创建一个单独的指针数组（向量）
  • 在存储中创建一个带有偏移量的单独数组（向量）
于 2013-10-04T18:37:25.493 回答
0

在某些情况下，使用std::vector为链表存储节点可能是一种非常有用且有效的策略，例如您需要能够在恒定时间内从中间删除元素，仍然回收空白空间，将元素插入到前面/middle 在恒定时间，遍历顺序匹配插入顺序，保留合理的缓存友好访问模式，并将 64 位链接的内存使用减半，如下所示：

template <class T>
struct Node
{
     // Stores the memory for the element stored in the node.
     typename std::aligned_storage<sizeof(T), alignof(T)>::type data;

     // Points to previous node in the array or previous
     // free node in the array if the node has been removed.
     // Stores -1 if there is no previous node.
     int32_t prev;

     // Points to next node in the array or next free
     // node in the array if the node has been removed.
     // Stores -1 if there is no next node.
     int32_t next;
};

template <class T>
struct List
{
    // Stores all the nodes contiguously.
    std::vector<Node<T>> nodes;

    // Points to the first node in the list.
    // Stores -1 if the list is empty.
    int32_t head;

    // Points to the first free node in the list.
    // Stores -1 if the free list is empty.
    int32_t free_head;
};

std::vector作为内存分配器

在这种情况下，我们实际上是在转换std::vector为节点内存分配器，并且将存储绝对地址的 64 位指针转换为存储数组相对索引的 32 位索引。

在此处输入图像描述

但是，正如您在上面的图表中可以看出的那样，此解决方案的一个缺点（抱歉，如果有点混乱，该图表表示擦除和重新插入后会发生什么）是，如果您开始从中间擦除元素并重新插入和回收空置空间，虽然您可以继续以原始插入顺序遍历元素，但您开始招致更多的缓存未命中，因为跟随链接可以让您开始在内存中来回曲折（不再以完美的顺序访问模式遍历数组）。当您插入到中间时也会发生同样的事情（这允许在恒定时间内完成，但中间的节点可能被分配到数组的后面，从而降低了引用的局部性）。

优化通行证

因此，这些类型的“混合”数组/链表解决方案往往具有降低空间局部性的缺点，您从/到中间擦除和插入元素的次数越多。一种缓解这种情况的方法是偶尔对列表进行“优化复制/交换”，这会恢复空间局部性并让您回到每个prev链接都指向数组中的前一个索引的点，以及每个next链接指着下一个。

仍然比平时好很多

然而，即使没有这些“优化通道”，即使在从中间多次删除和重新插入之后，与使用通用分配器分配节点的链表相比，它仍然倾向于产生更多、更少的缓存未命中。在后一种情况下，节点可能分散在内存中的各个位置，以至于您访问的每个节点都可能导致缓存未命中，这就是当您遇到链表在许多使用中效率特别低的恶名时案例。此外，您还可以使用 32 位索引（除非您实际上需要数十亿个节点）而不是 64 位机器上的 64 位指针，从而将链接的内存使用量减半。

索引链表

我经常使用链表，但他们总是使用这样的解决方案，将节点存储在连续数组中（一个连续的缓冲区来存储所有节点，或者一系列连续的缓冲区，每个缓冲区存储 256 个节点，例如），并且经常使用相对索引而不是绝对指针指向节点。当像这样使用链表时，它们在实践中变得更加有效。

内存池

回到 32 位时代，我曾经只使用内存池，就像一个符合std::allocator此目的的空闲列表，但是在 64 位硬件变得流行之后，指针的大小在内存使用中翻了一番，我发现它更有用开始使用随机访问数据结构作为类比的“内存分配器”和相对的 32 位索引。如果您存储在列表中的元素只是 3 个单精度浮点数（12 个字节），那么将指针大小减半绝非微不足道。我发现最大的实际麻烦是只需要处理所有内容的索引，而不能直接获取指针数据，因为这会使链接的内存使用加倍并且不会std::vector

交换和pop_back

请注意，如果您不关心遍历顺序，不关心索引失效，并且不需要能够在恒定时间内插入任何位置，那么这种数据结构就没那么有用了。在这种情况下，更有用的是只使用一个向量，在其中将要删除的中间元素与最后一个 and 交换pop_back。这种结构的主要好处是保持从列表中任何位置的恒定时间删除，恒定时间插入到列表中的任何位置，同时允许您以原始插入顺序和合理的缓存友好方式遍历。

于 2018-01-17T05:49:48.577 回答