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

Question

仅在迭代/访问列表中的对象时是否会对性能产生影响。我想假设没有区别，但仍然很好奇。

示例：

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。如果您关心性能，那么很有可能链表不是您的最佳数据结构。