时间戳

首页 > 解决方案 > 对于包含指向结构的指针的链接列表，性能与结构的“大小”之间是否存在任何关系？

c++ - 对于包含指向结构的指针的链接列表，性能与结构的“大小”之间是否存在任何关系？

问题描述

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

例子：

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;
}

标签： c++cperformancestructsingly-linked-list

解决方案

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

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

考虑以下三个结构：

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在使用第二种形式时引入前几个元素，但在使用第三种形式时不会引入）。

请注意，性能基准很可能具有欺骗性，除非它们是在“真实世界”条件下完成的。它的struct s2性能不太可能比s1在大多数现实世界条件下更差，但两者之间的相对性能s2可能s3会受到外部代码所做工作的细微变化的显着影响。

推荐阅读