Re: Array of pointer Vs Pointer to Array

• Previous message: T K See Tho: "Re: Free C\C++ compiler"
• In reply to: sangeetha: "Re: Array of pointer Vs Pointer to Array"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

Date: 09 Oct 2004 12:01:49 -0700

[The quoted material has been re-ordered into the order the pieces appeared.]

sangeetha_b@india.com (sangeetha) writes:

> smith7005@yahoo.com (Zian Smith) wrote in [...]
> > sangeetha_b@india.com (sangeetha) wrote in [...]
> > > Hello,
> > >
> > > Is there any performance difference in using of the following two declaration?
> > > int (*ptr)[10]; //Array of 10 int pointers
> > > int *ptr[10]; // pointer-to-array of 10.
> > >
> > > Regards,
> > > Sangeetha.
> >
> > Well, first you have it mixed up:
> >
> > int (*ptr)[10]; //pointer-to-array of 10 ints
> > int* ptr[10]; //array of 10 pointers (to ints)
> >
> > Second, they are essentially different structures, the first is simply
> > a single pointer, that points to an array. The second is an array that
> > contains 10 pointers.. If you can post an example of how you want to
> > use either of these, or what you are trying to accomplish, that might
> > be provide us with more information for comments regarding
> > performance/usage..

> Thx for every one, replied to my query. First of all it was my typo.
>
> Last week i attended one interview. I have explained correctly, by
> putting the diagram how it stores. Then he asked "wht is the
> performance difference between these two when using in the program". I
> said "These two are eniterly different things, cant be weighted". He
> didnt convenience on my answer.
>
> I was curious to know whether it can weigthed for performance point.
> "C" experts in this forum also conformed me it cant be.

My guess is people were thrown off by what seemed to be a lack of
experience in the original posting. Certainly it didn't help that the
two declarations had their types misidentified in the comments.

In fact, however, there is a sense in which these two variables can
meaningfully be compared: they both can be used as "two dimensional
arrays".

The pointer to array case -- int (*pa)[10]; -- is a little easier to
understand; consider for example:

    int matrix[100][10];
    int (*pa)[10] = matrix[0];

Now 'pa' is a pointer form of accessing the values in 'matrix'. Indeed
something like 'pa' is what one would normally use in the case where
'matrix' were being passed to a function. The expressions 'pa[i][j]'
and 'matrix[i][j]' access the same (int) element.

The array of pointers case -- int *ap[10]; -- is a somewhat less
easy to see immediately. Here is an example:

    int transposed_matrix[10][100];
    int *ap[10];
    int i;

    for( i = 0; i < 10; i++ ) ap[i] = transposed_matrix[i];

Now each of the pointers in 'ap' points to one of the 10 sub-arrays
in 'transposed_matrix', and & ap[i][j] == & transposed_matrix[i][j]
provided of course i and j are in the correct respective ranges.

So both 'pa' and 'ap' may be used as two-dimensional arrays, and
may reasonably be compared in that context.

Now, to the question. Performance difference between the two? Well
that depends on a variety of things - the size of the other dimension,
are accesses typically done varying the "10" dimension or the other
dimension most rapidly, are accesses typically sequential or typically
random, how good the compiler is at optimizing each of the two kinds
of access, to name some of the most obvious. For any particular piece
of code, either of the two types might yield better performance, and
conversely, if either of the two types were imposed by some external
constraint, a good C expert could probably re-work the code so that
the performance of the imposed type were better than the performance
of the other type. But basically it depends.

In the absence of other information, and especially in something like
an interview question, the form that is more like a regular array (in
other words the pointer-to-array 'pa' choice) is more likely to be
seen as the right answer. The two main reasons for this are, (1) less
indirection, and (2) compilers are generally better at optimizing
ordinary two-dimensional indexing arithmetic than they are at
optimizing the "index, follow a pointer and index again" kind of
operation that is used in the array-of-pointers 'ap' choice.

If it were me doing the interviewing, I'd be reasonably happy with
the answer in the last paragraph - the regular indexing style is
likely to be better, because it's more like what C typically does.
I'd be happier though to see an answer like "it depends; normally
the regular indexing style is a good first guess, but in an actual
situation other factors might dominate" and then list some factors
like those listed above. This is a person who thinks more deeply,
and who understands that performance questions are often difficult
to answer in the absence of specific details or measurement.

The question posed is not a trivial one. The way it was phrased in
the original article probably caused most people to just dismiss it.

• Previous message: T K See Tho: "Re: Free C\C++ compiler"
• In reply to: sangeetha: "Re: Array of pointer Vs Pointer to Array"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]