C++ structure: more members, MUCH slower member access time?

Question

I have a linked list of structures. Lets say I insert x million nodes into the linked list, then I iterate trough all nodes to find a given value.

The strange thing is (for me at least), if I have a structure like this:

struct node
    {
    int a;
    node *nxt;
    };

Then I can iterate trough the list and check the value of a ten times faster compared to when I have another member in the struct, like this:

struct node_complex
   {
   int a;
   string b;
   node_complex *nxt;
   };

I also tried it with C style strings (char array), the result was the same: just because I had another member (string), the whole iteration (+ value check) was 10 times slower, even if I did not even touched that member ever! Now, I do not know how the internals of structures work, but it looks like a high price to pay...

What is the catch?

Edit: I am a beginner and this is the first time I use pointers, so chances are, the mistake is on my part. I will post the code ASAP (not being at home now).

Update: I checked the values again, and I know see a much smaller difference: 2x instead of 10x. It is much more reasonable for sure.

While it is certainly possible it was the case yesterday too and I was just so freaking tired last night I could not divide two numbers, I have just made more tests and the results are mind blowing.

The times for a the same number of nodes is:

1. One int and a pointer the time to iterate trough is 0.101
2. One int and a string: 0.196
3. One int and 2 strings: 0.274
4. One int and 3 strings: 0.147 (!!!)
5. For two ints it is: 0.107

Look what happens when there is more than two strings in the structure! It gets faster! Did somebody drop LSD into my coffee? No! I do not drink coffee.

It is way too fckd up for my brain at the mo' so I think I will just figure it out on my own instead of draining public resources here at SO.

(Ad: I do not think my profiling class is buggy, and anyway I can see the time difference with my own eyes).

Anyhow, thanks for the help. Cheers.

Answer 1

I must be related to memory access. You speak of a million linked elements. With just an int and a pointer in the node, it takes 8 bytes (assuming 32 bits pointers). This takes up 8 MB memory, which is around the size of cache memory sizes.

When you add other members, you increase the overall size of your data. It does not fit anymore entirely in the cache memory. You revert to plain memory accesses that are much slower.

Answer 2

This may also be caused because during the iteration you may create a copy of your structures. That is:

node* pHead;
// ...

for (node* p = pHead; p; p = p->nxt)
{
    node myNode = *p; // here you create a copy!
    // ...
}

Copying a simple structure very fast. But the member you've added is a string, which is a complex object. Copying it is a relatively complex operation, with heap access.