dereferencing performance penalty?

[Rui Maciel]

I'm writing a program that makes use of a couple of data structures which basically consist in a series of
pointers and multi-dimensional arrays. In some iterations I'm currently accessing some nested objects through
dereferencing a series of pointers and arrays. As these data structures demand a good number of pointer/array
dereferencing I've started to suspect that it may affect the performance. Yet, I couldn't find anything
related to this through google (and google groups search is becoming even more frustrating and irrelevant
over time).

So, does this way of doing things adds any performance penalty? If so, why? And is it better to declare a
bunch of temporary variables or cursor pointers instead of relying on dereferencing the data structures?


Thanks in advance,
Rui Maciel

 

[bartc]

Rui Maciel said:

Bottom line? Measure, measure, measure. And don't optimise until you
absolutely have to, and can prove you have to, and can prove that
the optimisation does in fact improve performance by a sufficiently
significant margin. Consider a routine that currently takes one
second to execute, and which is called 3155760000 times. This will
take 100 years to execute. If you spend an hour optimising it and
succeed in reducing the routine's execution time by one
microsecond, the total runtime will be reduced to 99 years 364 days
23 hours 7 minutes and 25 seconds, but the start *time* will be an
hour later. In other words, you will have succeeded in *delaying*
the program's completion by over seven minutes.

Or just start the program 18 months from now. On the faster hardware
available the program will finish only 50 years later.

 

[bartc]

I'm writing a program that makes use of a couple of data structures which
basically consist in a series of
pointers and multi-dimensional arrays. In some iterations I'm currently
accessing some nested objects through
dereferencing a series of pointers and arrays. As these data structures
demand a good number of pointer/array
dereferencing I've started to suspect that it may affect the performance.
Yet, I couldn't find anything
related to this through google (and google groups search is becoming even
more frustrating and irrelevant
over time)

Dereferencing is quite a fast machine operation. It might slow things down
if you do nothing else but dereferencing, and there is an easy way of
avoiding it.

I wouldn't bother about it unless it's an obvious bottleneck or your data
structures could do with simplifying anyway.

So, does this way of doing things adds any performance penalty? If so,
why? And is it better to declare a
bunch of temporary variables or cursor pointers instead of relying on
dereferencing the data structures?

You'll have to give an example of what you mean by this.

 

[bartc]

bartc said:

You'll have to give an example of what you mean by this.

He means something like this:

for(i = 0; i < n; i++)
{
cursor = complicated[m].structure->p[0];
while(cursor != NULL)
{
dosomethingwith(cursor++);
}
}

as opposed to something like this:

for(i = 0; i < n; i++)
{
j = 0;
while(complicated[m].structure->p[j] != NULL)
{
dosomethingwith(complicated[m].structure->p[j++]);
}
}

Oh, OK. That would depend on the exact arrangement in memory and whether
serial access is being used.

But aren't compilers supposed to be good at this sort of optimising?

 

[Stephen Sprunk]

bartc said:

And is it better to declare a
bunch of temporary variables or cursor pointers instead of
relying on dereferencing the data structures?

You'll have to give an example of what you mean by this.

He means something like this:

for(i = 0; i < n; i++)
{
cursor = complicated[m].structure->p[0];
while(cursor != NULL)
{
dosomethingwith(cursor++);
}
}

as opposed to something like this:

for(i = 0; i < n; i++)
{
j = 0;
while(complicated[m].structure->p[j] != NULL)
{
dosomethingwith(complicated[m].structure->p[j++]);
}
}

Oh, OK. That would depend on the exact arrangement in memory and whether
serial access is being used.

But aren't compilers supposed to be good at this sort of optimising?

In general, they are, but C places all sorts of limitations on them
which may or may not be relevant in a particular case. For instance, a
compiler may be able to use constant subexpression elimination to turn
the second example above into this:

for(i = 0; i < n; i++) {
j = 0;
q = complicated[m].structure->p;
while(q[j] != NULL) {
dosomethingwith(q[j++]);
}
}

However, it can only do that if it can _prove_ that dosomethingwith()
does not modify complicated (if it's a pointer and not an array), m,
structure (if it's a pointer and not an array), i, or p (if it's a
pointer and not an array). It may not be able to prove one or more of
those things and therefore would not be allowed to do (parts of) the
optimization. In such a case, if the programmer can prove all of those
conditions due to outside knowledge, he/she can make the optimization
_for_ the compiler.

After the above optimization, changing q to a cursor is relatively minor
and isn't likely to have a measurable effect.

However, nobody should even consider micro-optimizations like this until
they are absolutely sure that no algorithmic improvements can be made
_and_ they have measured the effect of the change and determined that it
does in fact help enough to merit making the code less clear -- and
possibly less correct, if the added complexity causes the programmer to
make mistakes.

S

 

[Tim Prince]

bartc said:

news:[email protected]...

And is it better to declare a
bunch of temporary variables or cursor pointers instead of
relying on dereferencing the data structures?

You'll have to give an example of what you mean by this.

He means something like this:

for(i = 0; i < n; i++)
{
cursor = complicated[m].structure->p[0];
while(cursor != NULL)
{
dosomethingwith(cursor++);
}
}

as opposed to something like this:

for(i = 0; i < n; i++)
{
j = 0;
while(complicated[m].structure->p[j] != NULL)
{
dosomethingwith(complicated[m].structure->p[j++]);
}
}

Oh, OK. That would depend on the exact arrangement in memory and whether
serial access is being used.

But aren't compilers supposed to be good at this sort of optimising?

Yes, but some people prefer to write out optimizations explicitly, or
avoid depending on features such as C99 restrict qualifier. This
example isn't sufficient to show whether that would be relevant.
Someone might like to point out that the question about the need for
more optimization is better answered by turning on compiler optimization
reports than by asking us to guess about details which aren't shown.

 

[Nick Keighley]

bartc said:

You'll have to give an example of what you mean by this.

He means something like this:

  for(i = 0; i < n; i++)
  {
    cursor = complicated[m].structure->p[0];
    while(cursor != NULL)
    {
      dosomethingwith(cursor++);
    }
  }

as opposed to something like this:

  for(i = 0; i < n; i++)
  {
    j = 0;
    while(complicated[m].structure->p[j] != NULL)
    {
      dosomethingwith(complicated[m].structure->p[j++]);
    }
  }

I'd favour the "optimised" version simply because I don't
have to write (and more importantly, read) a complex expression
twice. I'm a great believer in saving *my* CPU cycles.

 

[Antoninus Twink]

By far the best way to make your program run quickly is to choose
good algorithms. If you do that, performance is likely to be
acceptable in all normal circumstances, and the advantage to be
gained from micro-optimisations is likely to be small or zero. It
could even be a negative gain.

I'm flattered that you've managed to swallow your pride and learn
something from my posts. It looks like my patient explanations of the
systematically poor choices of algorithms in your publically available
code have finally had some effect.

It'll be interesting to see how your future code turns out in the light
of this new knowledge of yours, that choosing a good algorithm is
important.