pointer and array

[Winston Li]

In the Brain and Denis' book "The C Programming Language" Section 5.3
"Pointes abd Arrays", a statment goes:
"Any operation that can be achieved by array subscripting can also be done
with pointers."
Then the authors continute with "The pointer version will in general be
faster ...."

My question is why the pointer version would be faster?

Thanks in advance!

Winston

[Joona I Palaste]

Re: pointer and array

Winston Li <wnstnl@gmail.c om> scribbled the following:[color=blue]
> In the Brain and Denis' book "The C Programming Language" Section 5.3
> "Pointes abd Arrays", a statment goes:[/color]

"Brain and Denis"? Sounds like an obscure cartoon about lab mice. =)
[color=blue]
> "Any operation that can be achieved by array subscripting can also be done
> with pointers."[/color]

Yes, arrays "decay" into pointers in a value context. Chris Torek can
supply a 20-page post explaining this in detail.
[color=blue]
> Then the authors continute with "The pointer version will in general be
> faster ...."[/color]
[color=blue]
> My question is why the pointer version would be faster?[/color]

It won't. Nor will it be slower. Not in the general case, anyway. Dennis
and The Brain were most probably talking about some common UNIX C
implementation, not the C programming language in general. There's no
rule that says which operation must be faster than which.

--
/-- Joona Palaste (palaste@cc.hel sinki.fi) ------------- Finland --------\
\-------------------------------------------------------- rules! --------/
"C++. C++ run. Run, ++, run."
- JIPsoft

[infobahn]

Re: pointer and array

Winston Li wrote:[color=blue]
> In the Brain and Denis' book "The C Programming Language" Section 5.3
> "Pointes abd Arrays", a statment goes:
> "Any operation that can be achieved by array subscripting can also be done
> with pointers."
> Then the authors continute with "The pointer version will in general be
> faster ...."
>
> My question is why the pointer version would be faster?[/color]

On a platform where a dereference is faster than an
index-plus-dereference, the pointer version might be
infinitesimally faster.

Consider this:

size_t Count6s(const char *s)
{
size_t Sixes = 0;
while(*s != '\0')
{
Sixes += ('6' == *s++);
}
return Sixes;
}

against this:

size_t Count7s(const char *s)
{
size_t Sevens = 0;
int i;
for(i = 0; s[i] != '\0'; i++)
{
Sevens += ('7' == *s++);
}
return Sevens;
}

The array lookup s[i] takes not-quite-zero time.


The chances of this forming a bottleneck in your code
are so remote that it's just not worth worrying about
until you have real justification for chasing such
nebulous performance gains.

Until then, write clear code.

[Charlie Gordon]

Re: pointer and array

"infobahn" <infobahn@btint ernet.com> wrote in message
news:cq9uro$s21 $1@hercules.bti nternet.com...[color=blue]
> size_t Count7s(const char *s)
> {
> size_t Sevens = 0;
> int i;
> for(i = 0; s[i] != '\0'; i++)
> {
> Sevens += ('7' == *s++);
> }
> return Sevens;
> }
>
> The array lookup s[i] takes not-quite-zero time.[/color]

I agree, but Count7s should be written this way ;-)

size_t Count7s(const char *s) {
size_t Sevens = 0;
int i;

for (i = 0; s[i] != '\0'; i++) {
Sevens += (s[i] == '7');
}
return Sevens;
}

--
Chqrlie.

[Keith Thompson]

Re: pointer and array

"Charlie Gordon" <news@chqrlie.o rg> writes:[color=blue]
> "infobahn" <infobahn@btint ernet.com> wrote in message
> news:cq9uro$s21 $1@hercules.bti nternet.com...[/color]
[...][color=blue][color=green]
>> The array lookup s[i] takes not-quite-zero time.[/color]
>
> I agree, but Count7s should be written this way ;-)
>
> size_t Count7s(const char *s) {
> size_t Sevens = 0;
> int i;
>
> for (i = 0; s[i] != '\0'; i++) {
> Sevens += (s[i] == '7');
> }
> return Sevens;
> }[/color]

If a pointer version of this code is faster than the array indexing
version, a decent optimizing compiler is likely to generate code that
uses pointers anyway. Doing micro-optimizations in source code (at
the expense of clarity) is as likely to interfere with the optimizer
as it is to improve performance.

This was probably less true when K&R wrote the first edition.

--
Keith Thompson (The_Other_Keit h) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Jarno A Wuolijoki]

Re: pointer and array

On Tue, 21 Dec 2004, Keith Thompson wrote:
[color=blue]
> "Charlie Gordon" <news@chqrlie.o rg> writes:[color=green]
> > I agree, but Count7s should be written this way ;-)[/color][/color]
[...][color=blue]
>
> If a pointer version of this code is faster than the array indexing
> version, a decent optimizing compiler is likely to generate code that
> uses pointers anyway. Doing micro-optimizations in source code (at
> the expense of clarity) is as likely to interfere with the optimizer
> as it is to improve performance.[/color]

[unsnip]
[color=blue][color=green]
> > "infobahn" <infobahn@btint ernet.com> wrote in message
> > news:cq9uro$s21 $1@hercules.bti nternet.com...[color=darkred]
>>> size_t Count7s(const char *s)
>>> {
>>> size_t Sevens = 0;
>>> int i;
>>> for(i = 0; s[i] != '\0'; i++)[/color][/color][/color]
^^^^ ^^^[color=blue][color=green][color=darkred]
>>> {
>>> Sevens += ('7' == *s++);[/color][/color][/color]
^^^[color=blue][color=green][color=darkred]
>>> }
>>> return Sevens;
>>> }[/color][/color][/color]

[CBFalconer]

Re: pointer and array

Joona I Palaste wrote:[color=blue]
> Winston Li <wnstnl@gmail.c om> scribbled the following:
>[color=green]
>> In the Brain and Denis' book "The C Programming Language" Section
>> 5.3 "Pointes abd Arrays", a statment goes:[/color]
>
> "Brain and Denis"? Sounds like an obscure cartoon about lab mice. =)
>[color=green]
>> "Any operation that can be achieved by array subscripting can also
>> be done with pointers."[/color]
>
> Yes, arrays "decay" into pointers in a value context. Chris Torek
> can supply a 20-page post explaining this in detail.
>[color=green]
>> Then the authors continute with "The pointer version will in
>> general be faster ...."[/color]
>[color=green]
> > My question is why the pointer version would be faster?[/color]
>
> It won't. Nor will it be slower. Not in the general case,
> anyway. Dennis and The Brain were most probably talking about
> some common UNIX C implementation, not the C programming
> language in general. There's no rule that says which operation
> must be faster than which.[/color]

Bad answer. There are two pieces of information involved, the
subscript, and the array identity. These have to be combined in
order to access the data. If they are already combined, that
operation becomes somewhat unnecessary.

However if either the subscript or the identity are needed
separately, the efficiency answer may well be different.


--
Chuck F (cbfalconer@yah oo.com) (cbfalconer@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!

[Charlie Gordon]

Re: pointer and array

"Jarno A Wuolijoki" <jwuolijo@cs.He lsinki.FI> wrote in message
news:Pine.LNX.4 .58.04122123483 80.29154@sbz-31.cs.Helsinki. FI...[color=blue]
> On Tue, 21 Dec 2004, Keith Thompson wrote:
>[color=green]
> > "Charlie Gordon" <news@chqrlie.o rg> writes:[color=darkred]
> > > I agree, but Count7s should be written this way ;-)[/color][/color]
> [...][color=green]
> >
> > If a pointer version of this code is faster than the array indexing
> > version, a decent optimizing compiler is likely to generate code that
> > uses pointers anyway. Doing micro-optimizations in source code (at
> > the expense of clarity) is as likely to interfere with the optimizer
> > as it is to improve performance.[/color]
>
> [unsnip]
>[color=green][color=darkred]
> > > "infobahn" <infobahn@btint ernet.com> wrote in message
> > > news:cq9uro$s21 $1@hercules.bti nternet.com...
> >>> size_t Count7s(const char *s)
> >>> {
> >>> size_t Sevens = 0;
> >>> int i;
> >>> for(i = 0; s[i] != '\0'; i++)[/color][/color]
> ^^^^ ^^^[color=green][color=darkred]
> >>> {
> >>> Sevens += ('7' == *s++);[/color][/color]
> ^^^[color=green][color=darkred]
> >>> }
> >>> return Sevens;
> >>> }[/color][/color][/color]

Thank you Jarno for setting the record straight.
The bug was there in broad daylight, naked and innocent,
Just slightly dimmed by the uncanny idiom.

Code proofing is such a black art ;-)

--
Chqrlie.

[Lawrence Kirby]

Re: pointer and array

On Tue, 21 Dec 2004 22:42:16 +0000, CBFalconer wrote:

....
[color=blue][color=green]
>> It won't. Nor will it be slower. Not in the general case,
>> anyway. Dennis and The Brain were most probably talking about
>> some common UNIX C implementation, not the C programming
>> language in general. There's no rule that says which operation
>> must be faster than which.[/color]
>
> Bad answer.[/color]

Looks good to me.
[color=blue]
> There are two pieces of information involved, the
> subscript, and the array identity. These have to be combined in
> order to access the data. If they are already combined, that
> operation becomes somewhat unnecessary.[/color]

In the abstract machine yes, after you've put the code through an
optimiser all bets are off. It is trivially true that if two pieces of
code have identical behaviour in the abstract machine then a compiler can
generate identical code for them. Compilers tend to be good at optimising
pointer+index combinations because this is an easy way to get a good
benefit. This is especially true when the pointer is an invariant. An
invariant pointer+index can be easier to analyse for aliasing issues etc.
than a single non-invariant pointer. Where the two code forms produce
different object code I wouldn't bet on the plain pointer version being
the faster.
[color=blue]
> However if either the subscript or the identity are needed
> separately, the efficiency answer may well be different.[/color]

You cannot base efficiency analysis simply on an operation count in the
abstract machine, at least when then difference is just a small constant
factor.

Lawrence

[CBFalconer]

Re: pointer and array

Lawrence Kirby wrote:[color=blue]
> On Tue, 21 Dec 2004 22:42:16 +0000, CBFalconer wrote:
>
> ...
>[color=green][color=darkred]
>>> It won't. Nor will it be slower. Not in the general case,
>>> anyway. Dennis and The Brain were most probably talking about
>>> some common UNIX C implementation, not the C programming
>>> language in general. There's no rule that says which operation
>>> must be faster than which.[/color]
>>
>> Bad answer.[/color]
>
> Looks good to me.
>[color=green]
>> There are two pieces of information involved, the
>> subscript, and the array identity. These have to be combined in
>> order to access the data. If they are already combined, that
>> operation becomes somewhat unnecessary.[/color]
>
> In the abstract machine yes, after you've put the code through an
> optimiser all bets are off. It is trivially true that if two pieces
> of code have identical behaviour in the abstract machine then a
> compiler can generate identical code for them. Compilers tend to be
> good at optimising pointer+index combinations because this is an
> easy way to get a good benefit. This is especially true when the
> pointer is an invariant. An invariant pointer+index can be easier
> to analyse for aliasing issues etc. than a single non-invariant
> pointer. Where the two code forms produce different object code
> I wouldn't bet on the plain pointer version being the faster.
>[color=green]
>> However if either the subscript or the identity are needed
>> separately, the efficiency answer may well be different.[/color]
>
> You cannot base efficiency analysis simply on an operation count
> in the abstract machine, at least when then difference is just a
> small constant factor.[/color]

Please don't strip attributions for any material you leave in your
quotes.

We are not talking about the net effect after a compilers code
generator has optimized them all into the same code, but about the
effect of using pointers vs indices. The sort of loops concerned
(after some initialization code) are:

for (i = 0; i < MAX; i++) operateon(a[i]);
and
for (p = &a[0]; p < top; p++) operateon(*p);

where the only point of interest is comparing the execution time
etc. within the loop proper. If the compiler will generate the
same code you use the clearest, which is probably the indexed
version. If the loop speed is critical, you choose the fastest,
which you can't really resolve without experimentation . But, on
the reasonable assumption that (p < top) and (i < MAX) take the
same effort, as do p++ and i++, the difference comes down to the
relative effort of evaluating a[i] and *p. Since a pointer to
dereference must be formed from a[i], and that pointer should be
identical to p, the conclusion seems obvious.


--
Chuck F (cbfalconer@yah oo.com) (cbfalconer@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!