C/C++: What's faster: a for loop, or incrementing a pointer

Question

I am wondering which of the following code segments would be fastest, assuming that the goal is to read from the elements of type T in amount numElements pointed to by somePointer and do something with them. I'm specifically interested in the efficiency of the looping structure itself, not what's being done with the elements.

1st Candidate

for (int i = 0; i < numElements; i++) {
    T val = somePointer[i];
    ... // Do something
}

2nd Candidate

T* tempPointer = somePointer;
T* endPointer = somePointer + numElements;
while (tempPointer < endPointer) {
    T val = *tempPointer;
    ... // Do something
    tempPointer++;
}

Certainly the first candidate is more clear and less prone to errors. However, if it is actually getting compiled into the code it seems it would generate, I would think it would be slower. Using a for loop requires an increment of i every loop iteration, as well as an offset from the address pointed to by somePointer by amount i * sizeOf(t) before dereferencing. The pointer incrementation method seems to require only one addition operation for every loop cycle, thus leading me to believe it would be faster.

However, as I understand compilers try to vectorize for loops as possible with SIMD instructions; if the compiler can successfully detect an opportunity for vectorization in a for loop but not with incrementing pointers, the for then would seem to be the faster option. Of course, for all I know, the compiler is detecting cases where for loops can be converted to pointer incrementation and making the conversion before the vectorization, which would make it irrelevant.

In short, in real-world scenarios, which is faster?

Answer 1

Theoretically, the answer to your question is the former, simpler code.

An actual implementation need not evaluate part of an expression if it can deduce that its value is not used and that no needed side effects are produced (including any caused by calling a function or accessing a volatile object).

This is a quote from the C standard demonstrating the power placed upon the compiler to make optimisations. In this case, the parts of the expression that aren't needed are related to the int index (which should probably be a size_t).

Realistically, the answer to your question is also the former, simpler code. You may be pleasantly surprised to find that the common compilers of today can perform optimisations such as the one you mention (and more complex, yet) quite easily. However, due to the many aspects of computer systems that combine to build a bigger picture of performance, it's not possible to give an answer as to which of these will be faster... We'd need to know every relevant aspect about your implementation (CPU, memory, OS, compiler, etc).

See "Will it Optimise?", for a few similar examples that gcc happily optimises. This is a form of loop invariant computation optimisation. Make sure you compile your code with full optimisations enabled (-O3, typically).

It's not just optimisation that you need to consider, however. As you've mentioned, the former, simpler code is easier to read. This is important for anybody who may end up maintaining your code.

When considering optimisation, here's a handy hint: Your boss will want to see something that works, even if it's too slow, sooner rather than later. If you don't have a boss, great! Consider that you can't measure optimised code without having something to compare it to, however...

Write clear, concise code for the purpose of maintainability. If your boss (or your team, or yourself, or whatever) decides when it's complete that it's not fast enough, use your profiler to determine where the most significant bottlenecks are, then you should have some idea of what to focus on... You'll be optimising your time and your code.

Once you've completed an optimisation, use your profiler again to determine whether or not it was an effective optimisation. This way you remove the negative effect that your guesswork could have.

Todays common compilers can often even perform optimisations based on the output of a profiler. This technique is called "profile-guided optimisation", and might be worth researching...

Answer 2

As a general rule, the worst case running time of a for loop, and also a while loop like this one is O(n). That said, it will grow linearly based on the number of elements you have.

In this case, it is of very little value of considering which one is faster, as they are essentially the same, assuming that what you'll be doing under

//Do something

is the same.

When considering the efficiency of your program, it is worth considering both running time and memory efficiency.

I think what's written within your for loop/while loop is of greater importance of what's affecting your running time.

Hope this helps!