Restricted Pointers in C

A very important concept introduced in the C99 standard is that of restricted pointers.

Through them it is possible to optimize memory access, improving program performance. In this lesson we will see what restricted pointers are, how to use them and when to use them.

Pointers and Aliasing

Before explaining what restricted pointers are and how they are used, it is necessary to explain what the phenomenon of aliasing is.

When we began studying pointers, we saw that one of their simplest uses is to use them as aliases of variables, that is, as alternative names to access the same variable.

Let's take the following example:

int a = 10;

int *p = &a;

*p = 20;

printf("%d\n", a); // Prints 20

In this case, p is a pointer to integer. Through the use of the address operator and the dereferencing operator, p is used as an alias of a, and therefore the modification of *p is equivalent to the modification of a.

We can also use multiple pointers as aliases of the same variable:

int a = 10;

int *p = &a;
int *q = &a;

*p = 20;

*q = 30;

printf("%d\n", a); // Prints 30

In this case, p and q are two pointers to integer that point to the same variable a. By modifying *p or *q, a is modified.

When multiple pointers are used as aliases of the same variable, we speak of aliasing:

The phenomenon of pointer aliasing, by itself, does not represent a problem but, on the contrary, is often used precisely to be able to access the same memory area from multiple points of the program.

However, there is a case in which aliasing can cause problems. But, to understand, we must analyze an example. Suppose we want to implement a function that takes two arrays as input, a source array and a destination array, and copies the values from the first into the other:

void copy_array(int *dest, int *src, int n) {
    for (int i = 0; i < n; i++) {
        dest[i] = src[i];
    }
}

The implementation is very simple: we scan the source array src and copy the values into the destination array dest.

Written this way, the code works correctly but is not optimal. In fact, modern processors are able to access memory, and therefore the two arrays, in parallel. That is, rather than reading memory byte by byte, as processors used to do in the past, modern processors read memory in blocks, meaning they read multiple bytes at once.

In light of this, modern compilers can optimize the above code to read and write to memory in blocks, improving program performance. So, instead of reading one integer at a time and then writing it, the compiler could read and write blocks of more than one integer at a time. For example, it could read them two at a time, or four at a time, depending on the processor architecture.

This optimization would work in theory. In practice, unfortunately, C compilers do not apply this optimization due to the phenomenon of aliasing. In fact, compilers cannot make assumptions about the two input pointers, meaning that they could point to any memory locations: either different memory areas, or overlapping memory areas.

The problem arises in the second case: if the two arrays overlap, the optimization cannot be applied.

To clarify, suppose we have two 8-element arrays that partially overlap as shown in the figure:

In this case, src points to the beginning of the first array and dest points to the beginning of the second array. The two arrays overlap except for the first two elements.

If we call the copy_array function with src and dest pointing to the two overlapping memory locations, and the compiler does not apply any optimization, the result will be as follows:

1. Copy of the first integer:

   

2. Copy of the second integer:

   

3. Copy of the third integer:

   

And so on.

In the end, the result will be as follows:

Let's assume, instead, that the processor on which we execute this function is able to read and write to memory in blocks of four integers at a time. Furthermore, suppose that the compiler has optimized the copy_array function to read and write to memory in blocks of four integers at a time. What happens?

1. First, the first block of four integers is copied:

   

   After the copy the result will be:

   

2. Subsequently, the second and last block is copied:

   

   After the copy the result will be:

   

As can be observed, the result is completely different compared to the non-optimized case. However, the compiler must always respect the programmer's intentions, so it must ensure that the final result is the same, regardless of the optimizations it applies.

The problem is that the compiler is not able to determine whether there is actually aliasing or not. This is a difficult problem to solve because at each function call the compiler would have to verify whether the two input pointers overlap or not. This is a computationally very expensive problem that would slow down program execution.

Moral of the story: In the presence of possible aliasing, C language compilers disable optimizations regarding memory access. Note that we used the term possible, in fact the compiler cannot know if two pointers actually point to the same memory location. But precisely for this reason, it must guard against possible aliasing by disabling optimizations.

Restricted Pointers

The issue of aliasing and the disabling of optimizations is a particularly felt problem when writing numerical computation programs in which operations are performed on data arrays, especially on vectors and matrices. In these cases, optimizing memory access is fundamental to obtaining high performance.

To solve this problem, starting from the C99 standard, restricted pointers have been introduced.

To define a restricted pointer, the keyword restrict is used:

int * restrict p;

When we define a pointer in this way, we are telling the compiler that pointer p is the only pointer that can access the memory location it points to and, above all, that there will be no other pointers that will access the same memory location or portions of it.

Let's return to the example of the copy_array function. We can rewrite it using restricted pointers:

void copy_array(int * restrict dest, int * restrict src, int n) {
    for (int i = 0; i < n; i++) {
        dest[i] = src[i];
    }
}

In this way, we are essentially telling the compiler that src and dest do not overlap, and therefore it can apply the optimizations it deems appropriate. In this way the copy_array function will be faster and more efficient.

Obviously there is a contraindication. When we use restrict we are making a promise to the compiler that we will not use other pointers to access the same memory location. But, the responsibility for keeping this promise is entirely on the developer: the compiler will take this information as good and will not perform any checks.

Furthermore, the use of restrict is still a suggestion for the compiler. This means that the compiler might not apply the optimizations it deems appropriate, even if we have used restrict.

In summary:

type * restrict pointer_name;

We said that it is the programmer's job to ensure that there are no overlaps between the memory locations pointed to by restricted pointers and that the compiler will not perform any checks. But what happens if the programmer does not keep the promise? What happens if the pointer uniqueness rule is violated?

Let's see an example without the use of restrict:

int n = 10;
int *p;
int *q;

p = (int *) malloc(sizeof(int) * n);

q = p;

q[0] = 20;

This example is perfectly legal. We allocated a memory block of n integers and assigned to q the memory address of p. Therefore, p and q point to the same memory location. Then we modified the first element of the array pointed to by q. In practice, we exploited aliasing to access the same memory location from two different points.

Let's modify the program using restrict:

int n = 10;
int * restrict p;
int * restrict q;

p = (int *) malloc(sizeof(int) * n);

q = p;

q[0] = 20;

In this case, we declared p and q as restricted pointers. This means that p and q cannot access the same memory location. However, we violated the pointer uniqueness rule, as p and q point to the same memory location. What happens?

The compiler does not perform any checks, so the above code compiles without issues. However, the program behavior is undefined. It could happen that nothing occurs, or that the program crashes, or that the result is unpredictable.

Conclusions

In this lesson we studied a series of advanced concepts regarding pointers in C Language:

• We saw that aliasing is the phenomenon by which the same memory location is accessed through multiple names (variables or pointers).
• Aliasing can be an intentional or unintentional phenomenon. In the second case, it can cause performance problems.
• We saw how compilers disable optimizations regarding memory access in the possible presence of aliasing.
• We introduced restricted pointers, which allow declaring to the compiler that a pointer is the only means to access a certain memory location.
• We saw that the use of restrict is an optimization that should be used with caution and only if necessary.