How can I best iterate over a C array? With pointers or by index?

Question

I often see people iterating over C style arrays using a pointer, while I find it more readable to use an index. The example below illustrates the two ways I think about. They do not lead to the same disassembly...

My question: Is it advantageous to use a "runner" instead of an index? By the way, is there another name for the "runner" technique?

Does it depend on the underlying type, e.g. int, char or a struct?

struct somestruct
{
    float f;
    int i;
};

const unsigned int uiSize = 10000;
somestruct * myarray = new somestruct[uiSize];
const somestruct * const pEnd = myarray + uiSize;

// way 1: runner
somestruct * pRunner = myarray;
while(pRunner < pEnd)
{
    pRunner->f += 5;
    pRunner->i += 5;
    ++pRunner;
}

// way 2: index
unsigned int ui = 0;
for (ui = 0; ui < uiSize; ++ui)
{
    myarray[ui].f += 6;
    myarray[ui].i += 4;
}

This is C++ not C. And I think you mean "array" not "vector". — kaylum, Apr 29 '16 at 05:46
@SouravGhosh No - arrays and vectors on are not the same thing. C++ has both, and they behave differently — skrrgwasme, Apr 29 '16 at 05:49
@AnT: This is different than the `a[i]` vs `((a) + (i))` argument though, this is about whether advancing a pointer is more efficient than accessing by index. — dreamlax, Apr 29 '16 at 05:49
@skrrgwasme I'm not talking about arrays and vectors, i'm talking about usage of index vs direct pointers. — Sourav Ghosh, Apr 29 '16 at 05:50
@skrrgwasme this isn't quite the same question. That question is about the difference between `a[i]` and `((a)+(i))` but this one is about whether looping by incrementing a pointer is different to looping by index. — dreamlax, Apr 29 '16 at 06:00
@dreamlax: I never thought that the linked question is about `a + i`. The point I'm trying to make is: "As long as performance doesn't suffer, it is always a better idea to implement algorithms by relying on the minimal set of requirements. Random access is a stronger requirement than sequential access, meaning that the former should be avoided when reasonably possible." — AnT stands with Russia, Apr 29 '16 at 06:10
Also http://stackoverflow.com/questions/1856307/to-iterate-or-to-use-a-counter-that-is-the-question — AnT stands with Russia, Apr 29 '16 at 06:10

score 5 · Answer 1 · answered Apr 29 '16 at 05:51

It does not matter whether you use integral indexing or pointers. However, both of the examples you have provided do not follow standard practice in C (or C++). Here's a rewrite that does:

// way 1: runner
for (somestruct * pRunner = myarray; pRunner != pEnd; ++pRunner)

// way 2: index
for (size_t ui = 0; ui < uiSize; ++ui)

When simply iterating over all the elements of a container, we always use for loops, and never while loops, because it's more concise and idiomatic (meaning everyone does it this way, so everyone can read it quickly).

"It does not matter" -- while I agree with you on that, IMO you should nonetheless point out that both ways are **not** semantically equivalent. — Daniel Jour, Apr 29 '16 at 06:51

Daniel Jour · Answer 2 · 2016-04-29T06:47:15.150

0

array[index]

This is the same (in C) as *(array + index). Thus, additionally to incrementing the index, you also have some* additions in order to get the pointer array + index that you're dereferencing. This additional addition is not needed when you increment a pointer directly.

*) I'd expect from any decent compiler to bring this down to a single addition (and cache the result in some register or on the stack) per iteration. From a good compiler I'd expect it to recognize this pattern and generate code equal to using pointers directly.

Final remark: Unless you're using this in a very tight loop and your compiler is not able to generate decent code and your profiler told you that this is your performance bottleneck, prefer the solution that's easier to understand and read.

edited Apr 29 '16 at 06:47

answered Apr 29 '16 at 05:53

Daniel Jour

15,896
2
36
63

"his is not needed when you increment a pointer directly." And what do you think a pointer increment is then, if not an addition (by sizeof 1 item)? – Lundin Apr 29 '16 at 06:32
@Lundin With the pointer you increment one "thing", with the index you increment the index and add the index to the base pointer. Thus, two additions vs one. – Daniel Jour Apr 29 '16 at 06:46
With either method you load the base address inside an index register. The difference is that with the array method, the index register containing the base address is preserved, and you add that one with a value and store the result in a different index register. With the pointer method, you alter the index register by storing the result of the addition in the same register. It is not obvious why one form would be faster than the other on a generic computer. Most likely there is no difference, or at least none worth mentioning. – Lundin Apr 29 '16 at 07:00
That is, the compiler is (hopefully) not so stupid that it goes to fetch the base address of the array from RAM each time you access the array. – Lundin Apr 29 '16 at 07:02
@Lundin Of course there's no "real" difference in terms of performance here (mostly thanks to smart compilers, which I try to point out with the second half of my answer). There *is* a difference in semantics, though. – Daniel Jour Apr 29 '16 at 07:04

How can I best iterate over a C array? With pointers or by index?

2 Answers2