C++结构体：成员越多，成员访问时间越慢？

Question

我有一个结构体链表。假设我向该链表插入x百万个节点，然后我遍历所有节点以查找给定值。

奇怪的是（至少对我来说），如果我的结构体像这样：

struct node
    {
    int a;
    node *nxt;
    };

然后我可以遍历列表并检查一个值，速度比当我有另一个结构成员时快十倍，就像这样：

struct node_complex
   {
   int a;
   string b;
   node_complex *nxt;
   };

我还尝试使用 C 风格的字符串（char 数组），结果是一样的：即使我从未触及那个成员，只因为我有另一个成员（字符串），整个迭代（+值检查）也变慢了 10 倍。现在，我不知道结构体的内部工作原理，但看起来这是一个很高的代价...

问题出在哪里？ 编辑： 我是个初学者，这是我第一次使用指针，所以错误很可能是我自己的问题。 我会尽快发布代码（现在不在家）。 更新： 我再次检查了值，并且现在看到的差异要小得多：2 倍而不是 10 倍。 这显然更加合理。

虽然昨天也可能是这种情况，但我太累了，无法计算两个数字，但我已经进行了更多测试，结果令人惊讶。

相同节点数量的时间如下：

1. 一个 int 和一个指针迭代所需的时间为 0.101。 2. 一个 int 和一个字符串：0.196。 3. 一个 int 和两个字符串：0.274。 4. 一个 int 和三个字符串：0.147 (!!!)。 5. 对于两个 int，它是：0.107。

当结构中有两个以上的字符串时会发生什么！ 它会变得更快！ 有人向我的咖啡里放了LSD吗？ 不！ 我不喝咖啡。

对于我目前的大脑来说，这太过疯狂了，所以我想自己找出问题，而不是浪费公共资源。

（广告：我不认为我的分析类有错误，无论如何我都可以用自己的眼睛看到时间差异）

不管怎样，谢谢你的帮助。

- johnny-john

---

你确定你所测量的是纯迭代时间，不包括列表元素的创建时间吗？创建字符串比创建整数要昂贵得多。你尝试过用两个 int 字段吗？ - Péter Török

你可能正在看到某种处理器缓存效应，当向结构体添加一个成员时，测试数据不再完全适合L2缓存。 - Doug

我们能看到遍历列表的代码吗？ - Mike Seymour

1. 为什么要实现自己的列表？这肯定比使用std::list更容易出错，而且可能不如效率高。
2. 为什么要使用列表？列表可以说是你可能使用的最糟糕的容器。它们几乎没有缓存一致性，需要频繁使用动态分配，即使它们的好处（常数时间插入/删除）也被前面的问题严重压倒。
3. 因此，请使用std::vector或std::deque并享受更好的缓存使用率。像往常一样，性能问题通常只是糟糕的设计选择。

- GManNickG

看到你的程序性能与b所占实际大小的关系将会很有趣。在这种情况下，因此看到性能如何随字符串b的长度变化而变化将会很有趣。 - gspr

Answer 1

我必须与内存访问有关。您提到了一百万个链接元素。只需一个int和节点中的指针，它就需要8个字节（假设32位指针）。这占用了8 MB的内存，大约是缓存内存大小。

当您添加其他成员时，会增加数据的总体大小。它不再完全适合缓存内存中。您将回归到更慢的普通内存访问。

- Didier Trosset

---

此外，更大的内存可能会使用更多的TLB条目，可能会触发一些TLB抖动。 - ConcernedOfTunbridgeWells

我认为总缓存大小并不重要，因为数据已经如此分散，几乎每个节点在第一次访问时都会是缓存未命中，并且由于以后不再使用，从缓存中驱逐它再次出现也没有影响。最有可能的是，缓存未命中正在发生，并且至少部分地导致了减速，但并不是因为总缓存大小。 - jalf

Answer 2

这可能是由于在迭代过程中，您可能会创建您的结构的副本所致。例如：

node* pHead;
// ...

for (node* p = pHead; p; p = p->nxt)
{
    node myNode = *p; // here you create a copy!
    // ...
}

复制一个简单的结构非常快。但是你添加的成员是一个字符串，这是一个复杂的对象。复制它是一项相对复杂的操作，并涉及堆访问。

- valdo

Answer 3

很可能，问题在于您的较大结构体不再适合单个高速缓存线。我记得，主流CPU通常使用32字节的高速缓存线。这意味着数据每次以32字节的块读入高速缓存中，如果移动超过这32字节，则需要进行第二次内存获取。查看您的结构体，它以一个int开始，占用4个字节（通常），然后是std :: string（我假设，即使没有指定名称空间），在我的标准库实现（来自VS2010）中占用28个字节，共计32个字节。这意味着初始的int和next指针将放置在不同的高速缓存线中，使用两倍的高速缓存空间，并在迭代期间访问两倍的内存。如果仅访问指针，则不应有任何影响，因为只需从内存中检索第二个高速缓存线。如果始终访问int和指针，并且较少需要字符串，则重新排序成员可能会有所帮助：

struct node_complex
{
   int a;
   node_complex *nxt;
   string b;
};

在这种情况下，next指针和int位于同一缓存行上，可以在不需要额外内存读取的情况下进行读取。但是，一旦需要读取string，就会产生额外的开销。

当然，你的基准测试代码可能也包括节点的创建，或者（有意或无意地）创建节点的副本，这显然也会影响性能。

- jalf

Answer 4

我并不是专家，但是在阅读你的问题时，“缓存未命中”问题在我的脑海中响起。

当你有一个成员时，它会使结构体的大小变大，同时也可能导致在遍历链表时发生缓存未命中（如果你没有在内存中分配节点并且这些节点不远离彼此，则链表自然是缓存不友好的）。

我找不到其他的解释。

然而，由于我们没有提供创建和循环的代码，因此仍然很难猜测你是否只是没有以有效的方式执行列表探索的代码。

- Klaim

Answer 5

也许一个解决方案是使用指向对象的指针链表。这可能会使事情更加复杂（除非您使用智能指针等），但它可能会增加搜索时间。

- Alexander Rafferty