CODEWITHSUNDEEP
c++cperformancestructsingly-linked-list
scottc11
scottc11

Reputation: 926

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

Just curious if there is any effect on performance when iterating/accessing the objects in the list. I want to assume there would be no difference, but still curious.

example:

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

Upvotes: 0

Views: 101

Answers (3)

supercat
supercat

Reputation: 81247

The best performance can be achieved if structs are small enough that several of them can fit in a cache line, and allocation is done in such a way as to make it likely that structs which are accessed soon after each other will in fact be placed in the same cache line.

If structs are much larger than cache lines, best performance can be achieved by ensuring that parts of a struct which will often be accessed in close succession will be near each other.

Consider the following three structures:

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

as accessed by the following loop:

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

the performance of the second will likely be much better than that of the first since the first would incur two cache misses for most iterations of the loop while the second would incur only one. If the small size would allow structures to be placed close to each other, performance of the third might be even better than the second when processing the above loop (possibly incurring an average of less than one cache miss per iteration), but much worse than the second when accessing the first few elements of dat (since bringing the structure into cache would also bring in the first few elements of dat when using the second form, but not when using the third).

Note that performance benchmarks are likely to be deceptive unless they're done under "real-world" conditions. It's unlikely that struct s2 would perform worse than s1 under most real-world conditions, but the relative performance between s2 and s3 could be significantly affected by subtle variations in what outside code is doing.

Upvotes: 1

eerorika
eerorika

Reputation: 238421

Depends on how you allocate the nodes.

If you allocate the nodes from a memory pool such that the nodes have high locality, then smaller nodes allow more of them to fit within CPU cache or a memory page, which would reduce the frequency of cache misses and page faults.

If the nodes don't have a high locality, then the size doesn't matter for iteration of the list. This is likely to be the case when using the global allocator (i.e. std::malloc) for each node.

To find out whether it has significant effect in your program, you can measure it.

P.S. If you care about performance, then there is a good chance that linked list is not the best data structure for you.

Upvotes: 0

Evgeny
Evgeny

Reputation: 1072

The second case can be faster if you allocate memory like this: one struct near other. As a result, CPU can read some structures into single cache line.

Upvotes: 0

Related Questions