c++ - 缓存链表 - 有可能吗？

Question

我知道数组可以通过适应缓存行以及它们的顺序性来充分利用 x86_64 架构上的缓存机制。链表是一系列通过指针链接在一起的结构/对象，是否可以利用这种结构的缓存系统？链表的对象可以分配在内存中的任何位置

Answer 1

确实，链表条目可以在任何地方，但它们不必“在任何地方”。例如，您可以将它们分配到“区域”之外。一次分配一堆连续的条目，将它们串在一起形成一个“连续的空闲条目”列表，然后将它们打包出来。根据需要分配另一个 zone-full。使用一些不太干净的技巧，您最终可以重新线性化释放的条目，等等。

不过，在大多数情况下，实际上并不值得付出所有这些努力。

Answer 2

每个链表元素可以有多个条目，即每个元素中有一个小的条目数组。这允许缓存一些条目，同时仍保持列表的动态特性。

这是一个展开的列表，可以为您提供所需的内容。

Answer 3

您可能有一个链表元素包含超过 1 个数据条目。例如考虑下面的结构。

struct myll{
    int data[16];
    char valid[16/8];
    struct myll* next;
}

这样，您将粒度设置为每个节点 16 个条目。但是，您仍然可以选择使用另一个节点添加超过 16 个条目并使用“有效”标志删除。实施起来有点痛苦，但取决于您的要求。

我想，有些文件系统使用了一些类似的机制。