Why looping over array using array indexing is slower than that of pointer access?

Question

I'm reading Kochan's book "Programming in C". In section Pointer and Arrays on p. 264 he says:

In general, the process of indexing an array takes more time to execute than does the process of accessing the contents of a pointer. In fact, this is one of the main reasons why pointers are used to access the elements of an array—the code that is generated is generally more efficient. Of course, if access to the array is not generally sequential, pointers accomplish nothing, as far as this issue is concerned, because the expression *(pointer + j) takes just as long to execute as does the expression array[j].

Can someone explain what is faster than what ? Specifically, if speed of array[j] = speed of *(pointer + j) then what is the process of indexing an array and what is the process of accessing the contents of a pointer ? Also, there are questions and answers on SO that mention that array[j] is converted to *(array+j) during compilation so there shouldn't be any difference.

Summary: Please give me a very simple example of what Kochan says. 2 pieces of code and point at faster one, don't have to explain why it is true.

I think that what Kochan is saying is that incrementing a pointer by the element size is faster than multiplying an index by the element size and adding that to the base address. This is one of those cases where the difference is small enough that it likely doesn't matter, and if you're working at a level where it really does matter then you'll probably already be well aware of the difference. — Caleb
– Caleb, Commented Oct 7, 2014 at 16:45
Afaik, this used to be true, and still often is when compiling without optimization (if you think of C as a "portable assembler language", traversing an array by incrementing a pointer takes less operations in the abstract machine). Today, in general, it isn't. With more complex loops this even can harden aliasing analysis for your compiler and lead to less efficient code. (This is what I remember from my last experiments on this, I needed a lot of restricts for non-trivial loops to make the pointer-increment versions equally fast to the array-indexing versions and didn't get them faster.) — mafso
– mafso, Commented Oct 7, 2014 at 16:56

haccks · Accepted Answer · 2014-10-07 17:07:13Z

6

Look at the snippet

int arr[5] = {0};
int *p = arr;
int c = 1;

Now, see the loop 1:

for(int i = 0; i < 5; i++)
     arr[i] = c++ + 1;

loop 2:

for(int i = 0; i < 5; i++)
     *p++ = c++ + 1;

The difference between these two loops is their body. First loop contains arr[i] = c++ + 1. This is equivalent to *(arr + i) = c++ + 1. What does it mean by *(arr + i)?
It means that:

Fetch the base pointer address.
Fetch the value of i
Add the value of i to the base address.
Dereference the final address.

While in case of second loop's body *p++ means:

Fetch the value of p
Dereference the address before incrementing it.
Increment the address by 1.

Of course second one will execute faster. But, now a days modern compilers are smart enough to optimize these codes and most probably you will get the same result for both loop.

edited Oct 7, 2014 at 17:07

answered Oct 7, 2014 at 16:58

haccks

107k28 gold badges181 silver badges274 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Maciej Szpakowski Over a year ago

I guess you meant int *p = arr;

haccks Over a year ago

@MaciejSzpakowski; Oops! That was typo.

user3629249 Over a year ago

Another oops, the value 'i' must be multiplied by the size of the array type. (I.E. do nothing for char array, but mult by 4 for int array, etc)

underscore_d Over a year ago

@user3629249 well, yeah, but let's be clear: not in any of the code itself - only in the conceptual explanations that follow, as wherever haccks talks about adding to an address, it's actually adding to a pointer, which is very different if we assume most people read "address" as a quantity with 1-char resolution: typedPointer + n is equivalent to castToCharPointer + sizeof(*typedPointer). That would benefit from better clarity IMO.

Collectives™ on Stack Overflow

Why looping over array using array indexing is slower than that of pointer access?

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related