Does using a pointer to access memory in a loop affect program efficiency?

Question

Here is an illustration:

#include <stdio.h>

void loop(int *a)
{
    int b = *a;

    for (int i = 0; i < b; ++i)
    {
        ;
    }
}

void loop_pointer(int *a)
{
    for (int i = 0; i < *a; ++i)
    {
        ;
    }
}

int main(void)
{
    // Nothing to see here

    return 0;
} 

In the loop function, the memory is first stored on the stack and then accessed on every iteration. The memory would be cached.

My question is the following: Could the indirection in the loop_pointer function result in cache misses? And if so, would a cache miss only occur when the memory is modified(written to) and then accessed(read from) or would it happen on every read?

Answer 1

Yes, referring to objects using pointers can impair efficiency. Consider this code:

void foo(int *a, int *b)
{
    for (int i = 0; i < *a; ++i)
        *b++ = SomeCalculation(i);
}

After *b++ = SomeCalculation(i);, has the value of *a changed? The compiler cannot know, because the caller might have passed an address for a that is somewhere in the memory that b++ will cover during the loop. Therefore, it must either reload *a after each iteration or it must generate extra code to compare a and b and the value of *a before the loop. (If that run-time test determines *b++ never updates the memory of a, it can branch to a loop like your first example, where *a is loaded once and cached. Otherwise, it must use branch to another loop that accounts for *a changing.)

C provides the restrict qualifier to tell the compiler that something like this will not happen. In this code:

void foo(int * restrict a, int *b)
{
    …
}

the compiler may assume that *a never changes while foo is executing except through a. (restrict does allow this change to be indirect; if you have int *c = a; inside foo, then changing *a via *c is allowed with restrict, because the compiler can see c derives from a inside foo, but changing *a via b would violate the restrict.)

Similarly, one might wish to add restrict to the b parameter to tell the compiler that the things b points to are not affected by changes via other points.