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]

In the Brain and Denis' book "The C Programming Language" Section 5.3
"Pointes abd Arrays", a statment goes:

"Brain and Denis"? Sounds like an obscure cartoon about lab mice. =)

"Any operation that can be achieved by array subscripting can also be done
with pointers."

Yes, arrays "decay" into pointers in a value context. Chris Torek can
supply a 20-page post explaining this in detail.

Then the authors continute with "The pointer version will in general be
faster ...."

My question is why the pointer version would be faster?

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.

 

[infobahn]

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?

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 != '\0'; i++)
{
Sevens += ('7' == *s++);
}
return Sevens;
}

The array lookup s 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]

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

The array lookup s takes not-quite-zero time.

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 != '\0'; i++) {
Sevens += (s == '7');
}
return Sevens;
}

 

[Keith Thompson]

The array lookup s takes not-quite-zero time.

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 != '\0'; i++) {
Sevens += (s == '7');
}
return Sevens;
}

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.

 

[Jarno A Wuolijoki]

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

[...]

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.
[unsnip]

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

 

[CBFalconer]

"Brain and Denis"? Sounds like an obscure cartoon about lab mice. =)


Yes, arrays "decay" into pointers in a value context. Chris Torek
can supply a 20-page post explaining this in detail.



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.

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.

 

[Charlie Gordon]

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

[...]

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.
[unsnip]

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

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 ;-)

 

[Lawrence Kirby]

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

....

Bad answer.

Looks good to me.

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.

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.

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

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]

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

...


Looks good to me.


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.


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.

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);
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 and *p. Since a pointer to
dereference must be formed from a, and that pointer should be
identical to p, the conclusion seems obvious.