dereferencing performance penalty?

Discussion in 'C Programming' started by Rui Maciel, Jul 27, 2009.

  1. Rui Maciel

    Rui Maciel Guest

    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
    Rui Maciel, Jul 27, 2009
    #1
    1. Advertising

  2. Rui Maciel

    bartc Guest

    "Richard Heathfield" <> wrote in message
    news:...
    > Rui Maciel said:
    >
    >> 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.


    >> So, does this way of doing things adds any performance penalty? If
    >> so, why?


    > 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.

    --
    Bart
    bartc, Jul 27, 2009
    #2
    1. Advertising

  3. Rui Maciel

    bartc Guest

    "Rui Maciel" <> wrote in message
    news:4a6ce696$0$27140$...
    > 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, Jul 27, 2009
    #3
  4. Rui Maciel

    bartc Guest

    "Richard Heathfield" <> wrote in message
    news:...
    > bartc said:
    >
    >>
    >> "Rui Maciel" <> wrote in message
    >> news:4a6ce696$0$27140$...

    >
    > <snip>
    >
    >>> 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?

    --
    Bartc
    bartc, Jul 27, 2009
    #4
  5. bartc wrote:
    > "Richard Heathfield" <> wrote in message
    > news:...
    >> bartc said:
    >>> "Rui Maciel" <> wrote in message
    >>> news:4a6ce696$0$27140$...
    >>>> 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

    --
    Stephen Sprunk "Stupid people surround themselves with smart
    CCIE #3723 people. Smart people surround themselves with
    K5SSS smart people who disagree with them." --Isaac Jaffe
    Stephen Sprunk, Jul 27, 2009
    #5
  6. Rui Maciel

    Tim Prince Guest

    bartc wrote:
    >
    > "Richard Heathfield" <> wrote in message
    > news:...
    >> bartc said:
    >>
    >>>
    >>> "Rui Maciel" <> wrote in message
    >>> news:4a6ce696$0$27140$...

    >>
    >> <snip>
    >>
    >>>> 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.
    Tim Prince, Jul 27, 2009
    #6
  7. On 27 July, 01:43, Richard Heathfield <> wrote:
    > bartc said:
    >
    >
    >
    > > "Rui Maciel" <> wrote in message
    > >news:4a6ce696$0$27140$...

    >
    > <snip>
    >
    > >> 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++]);
    >     }
    >   }


    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.
    Nick Keighley, Jul 27, 2009
    #7
  8. On 27 Jul 2009 at 0:13, Richard Heathfield wrote:
    > 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.
    Antoninus Twink, Jul 30, 2009
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Peter Bär
    Replies:
    2
    Views:
    418
    Yan-Hong Huang[MSFT]
    Jul 18, 2003
  2. Michael Andersson

    Exceptions performance penalty

    Michael Andersson, Sep 2, 2003, in forum: C++
    Replies:
    7
    Views:
    549
    Oliver S.
    Sep 3, 2003
  3. Yuri Victorovich

    Performance penalty for encapsulations ??

    Yuri Victorovich, Sep 6, 2003, in forum: C++
    Replies:
    1
    Views:
    336
    Kevin Goodsell
    Sep 6, 2003
  4. Sune
    Replies:
    2
    Views:
    331
    Martin Wells
    Oct 2, 2007
  5. Rui Maciel

    Function pointers: performance penalty?

    Rui Maciel, Oct 11, 2009, in forum: C Programming
    Replies:
    107
    Views:
    4,009
    Sjouke Burry
    Oct 27, 2009
Loading...

Share This Page