7

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.

haccks
  • 104,019
  • 25
  • 176
  • 264
Maciej Szpakowski
  • 571
  • 1
  • 7
  • 22
  • 3
    From what year is that book? – 2501 Oct 07 '14 at 16:42
  • 1
    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 Oct 07 '14 at 16:45
  • http://stackoverflow.com/questions/4534617/lea-instruction – 2501 Oct 07 '14 at 16:48
  • It is 3rd edition, I think year 2005 – Maciej Szpakowski Oct 07 '14 at 16:49
  • This would be a better question if you provided the code sample for context. I cannot access it because it is not available as a preview in google books. –  Oct 07 '14 at 16:50
  • The problem is that he gives no example to this – Maciej Szpakowski Oct 07 '14 at 16:51
  • @Maciej Your paragraph is out of context. It comes directly after a code example in which he is looping and accessing the contents of an array. So "he gives no example to this" is false. –  Oct 07 '14 at 16:53
  • 2
    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 `restrict`s for non-trivial loops to make the pointer-increment versions equally fast to the array-indexing versions and didn't get them faster.) – mafso Oct 07 '14 at 16:56
  • I only said, that there is no example directly following this idea. I just don't know much from Kochan book I can post here that's why I didn't explain the entire context. I try to add some more. – Maciej Szpakowski Oct 07 '14 at 16:59

1 Answers1

5

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.

haccks
  • 104,019
  • 25
  • 176
  • 264
  • 1
    I guess you meant `int *p = arr;` – Maciej Szpakowski Oct 07 '14 at 17:06
  • @MaciejSzpakowski; Oops! That was typo. – haccks Oct 07 '14 at 17:07
  • 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) – user3629249 Oct 08 '14 at 02:36
  • @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. – underscore_d Jul 24 '16 at 15:30