Для связанного списка, содержащего указатели на структуры, существует ли какая-либо связь между производительностью и «большой» структурой? - PullRequest
Новая
       8

Для связанного списка, содержащего указатели на структуры, существует ли какая-либо связь между производительностью и «большой» структурой?

0 голосов
/ 06 марта 2020

Просто любопытно, влияет ли это на производительность при итерации / доступе к объектам в списке. Я хочу предположить, что не будет никакой разницы, но все же любопытно.

пример: 

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

Ответы [ 3 ]

1 голос
/ 06 марта 2020

Наилучшей производительности можно достичь, если структуры настолько малы, что некоторые из них могут поместиться в строку кэша, а распределение выполняется таким образом, чтобы обеспечить вероятность того, что структуры, к которым осуществляется доступ вскоре после друг друга, действительно будут помещаться в одну и ту же строку кэша.

Если структуры намного больше, чем строки кэша, наилучшая производительность может быть достигнута за счет обеспечения того, чтобы части структуры, к которым часто обращаются в тесной последовательности, находились рядом друг с другом.

Рассмотрим следующие три структуры: 

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

, к которым обращаются следующие l oop: 

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

производительность второго, вероятно, будет намного лучше, чем первый из них, поскольку первый имел бы два промаха в кэше для большинства итераций l oop, в то время как второй - только один. Если небольшой размер позволил бы размещать структуры близко друг к другу, производительность третьего может быть даже выше, чем второго при обработке вышеупомянутого l oop (возможно, в среднем на одну итерацию приходится не более одного пропуска кэша), но гораздо хуже второго при доступе к первым нескольким элементам dat (поскольку перенос структуры в кеш также привел бы к первым нескольким элементам dat при использовании второй формы, но не при использовании третьей).

Обратите внимание, что тесты производительности могут быть обманчивы, если они не выполнены в реальных условиях. Маловероятно, что struct s2 будет работать хуже, чем s1 в большинстве реальных условий, но на относительную производительность между s2 и s3 могут оказать значительное влияние незначительные различия в действиях внешнего кода.

0 голосов
/ 06 марта 2020

Зависит от того, как вы распределяете узлы.

Если вы выделяете узлы из пула памяти таким образом, чтобы узлы имели высокую локальность, то более мелкие узлы позволяют большему количеству из них помещаться в кэш-память ЦП или страницу памяти. , что уменьшило бы частоту пропусков кэша и ошибок страниц.

Если узлы не имеют высокой локализации, тогда размер не имеет значения для итерации списка. Это, вероятно, имеет место при использовании глобального распределителя (то есть std::malloc) для каждого узла.

Чтобы выяснить, оказывает ли он значительный эффект в вашей программе, вы можете измерить его.

PS Если вы заботитесь о производительности, есть большая вероятность, что связанный список не самая лучшая структура данных для вас.

0 голосов
/ 06 марта 2020

Второй случай может быть быстрее, если вы выделите память следующим образом: одна структура рядом с другой. В результате CPU может считывать некоторые структуры в одну строку кэша.

...