对于包含指向结构的指针的链表，性能与结构 "big" 之间是否存在任何关系？

Question

只是好奇 iterating/accessing 列表中的对象是否对性能有任何影响。我想假设不会有什么区别，但仍然很好奇。

示例：

typedef struct BigStruct {
  int bigList[1000];
  AnotherStruct massiveStruct;
  struct BigStruct *next;
  int someValue;
  // and a bunch more variables etc.
} BigStruct;


BigStruct *temp;
temp = head;
while (temp) {
  // do some stuff
  temp = temp->next;
}

VS

typedef struct LittleStruct {
  int someValue;
  struct LittleStruct* next;
} LittleStruct;

LittleStruct *temp;
temp = head;
while (temp) {
  // do some stuff
  temp = temp->next;
}

Answer 1

如果你这样分配内存，第二种情况会更快：一个结构靠近另一个。因此，CPU 可以将一些结构读入单个缓存行。

Answer 2

取决于您如何分配节点。

如果您从内存池分配节点，使节点具有高局部性，那么较小的节点允许更多节点容纳在 CPU 缓存或内存页中，这会降低缓存的频率未命中和页面错误。

如果节点的局部性不高，则大小对于列表的迭代无关紧要。当为每个节点使用全局分配器（即 std::malloc）时，很可能就是这种情况。

想知道它在你的程序中是否有显着的效果，你可以衡量一下。

P.S。如果您关心性能，那么链表很可能不是最适合您的数据结构。

Answer 3

如果结构足够小以至于它们中的几个可以放在一个缓存行中，并且分配的方式使得很可能在彼此之后很快访问的结构将被访问，则可以获得最佳性能实际上放在同一个缓存行中。

如果结构比高速缓存行大得多，则可以通过确保经常连续访问的结构部分彼此靠近来实现最佳性能。

考虑以下三个结构：

struct s1 { struct s1 *next; int dat[1000]; int x,y; };
struct s2 { struct s1 *next; int x,y; int dat[1000]; };
struct s3 { struct s1 *next; int x,y; int *dat; };

通过以下循环访问：

while(p->x)
  p = p->next;

第二个的性能可能会比第一个好得多，因为对于循环的大多数迭代，第一个会导致两次缓存未命中，而第二个只会导致一次。如果小尺寸允许结构彼此靠近放置，则在处理上述循环时，第三种的性能甚至可能比第二种更好（每次迭代可能导致平均不到一次缓存未命中），但比第二个在访问 dat 的前几个元素时（因为在使用第二种形式时将结构放入缓存也会引入 dat 的前几个元素，但在使用第三个时则不会）。

请注意，性能基准测试可能具有欺骗性，除非它们是在 "real-world" 条件下完成的。在大多数现实条件下，struct s2 的表现不太可能比 s1 差，但 s2 和 s3 之间的相对表现可能会受到外界细微变化的显着影响代码正在做。

对于包含指向结构的指针的链表，性能与结构 "big" 之间是否存在任何关系？

For a Linked List containing pointers to structs, is there any relationship between performance and how "big" the struct is?

c

c++

performance

struct

singly-linked-list

示例：

VS