The Obscure 'restrict” Keyword in C

Introduction

Among other things, C99 added the restrict keyword as a way for a programmer to specify that a pointer is the only pointer to a given object in a scope and, consequently, give the compiler a “hint” that it may perform additional optimizations when accessing the object via that pointer.

The Problem

To illustrate the problem that restrict was meant to solve, consider a function like:

void update_ptrs( int *p, int *q, int const *v ) {
  *p += *v;
  *q += *v;
}

for which the compiler will generate x86-64 code like:

mov eax, [rdx]  ; tmp = *v   // 1
add [rdi], eax  ; *p += tmp
mov eax, [rdx]  ; tmp = *v   // 3
add [rsi], eax  ; *q += tmp

You might wonder why it generates line 3 since it seems redundant with line 1. The problem is the compiler can’t know you didn’t do something like this:

int x = 1, v = 2;
update_ptrs( &v, &x, &v );   // x = 5, v = 4

In update_ptrs(), p and v would alias the same int, so the compiler has to play it safe and assume that the value of *v can change between reads, hence the additional mov instruction.

In general, pointers in C confound optimization since the compiler can’t know whether two pointers alias each other. In performance critical code, eliding memory reads could be a huge win if the compiler could do it safely.

The Solution

To solve the aforementioned problem, restrict was added to C to allow you specify that a given pointer is the only pointer to an object in the pointer’s scope, i.e., no other pointer in the same scope aliases it.

To use restrict, you insert it between the * and the pointer’s name in a declaration. An update_ptrs() rewritten to use restrict would be:

void update_ptrs_v2( int *restrict p, int *restrict q,
                     int const *restrict v ) {
  *p += *v;
  *q += *v;
}

(Read from right-to-left, e.g., v is a restricted pointer to a constant int; or use cdecl.)

By adding restrict, the the compiler can now generate code like:

mov eax, [rdx]  ; tmp = *v
add [rdi], eax  ; *p += tmp
add [rsi], eax  ; *q += tmp

Now, the compiler was able to elide the previous line 3 of the additional mov instruction.

Perhaps the best-known example where restrict is used is the standard library function memcpy(). It’s the fastest way to copy a chunk of memory if the source and destination addresses do not overlap. The slightly slower memmove() function exists for use when the addresses do overlap.

Pitfalls

Misuse of restrict results in undefined behavior, for example, by passing pointers that do alias each other to update_ptrs_v2() or memcpy(). In some cases, the compiler can warn you, but not in all cases, so don’t rely on the compiler to catch misuses.

Note that restrict is for a given scope. Assigning one restricted pointer to another in the same scope results in undefined behavior:

void f( int *restrict d, int *restrict s ) {
  int *restrict p = s;    // undefined behavior

However, you can assign a restricted pointer to an unrestricted pointer just fine:

void f( int *restrict d, int *restrict s ) {
  int *p = s;             // OK

Even though p is unrestricted, the compiler can still perform the same optimizations.

It’s also OK to assign a restricted pointer in an inner scope to another in an outer scope (but not the other way around):

void f( int *restrict d, int *restrict s ) {
  {                       // inner scope
    int *restrict p = s;  // OK
    // ...
    s = p;                // undefined behavior
  }
}

When (and When Not) to Use restrict

First, you should definitely profile your code (and perhaps even look at the generated assembly code) to see if using restrict actually makes a significant performance improvement to justify risking the potential pitfalls. Diagnosing bugs caused by misuse of restrict is very hard to do.

Second, if use of restrict is confined to the implementation of a function where the memory accessed via restricted pointers was allocated by you, then it’s safer. For example, given:

void safer( unsigned n ) {
  n += n % 2 != 0;  // make even by rounding up
  int *const array = malloc( n * sizeof(unsigned) );
  unsigned *restrict half_1st = array;
  unsigned *restrict half_2nd = array + n/2;
  // ...
  free( array );
}

the code could operate on the first and second halves of array safely because they don’t overlap (assuming you never access half_1st[n/2] or beyond).

Third, if restrict is used in a function’s parameters, then it’s potentially less safe. For example, contrast safer() with update_ptrs_v2() where the caller controls the pointers. For all you know, the caller got it wrong and passed pointers that alias.

Miscellaneous

Only pointers to objects (or void) can be qualified with restrict:

restrict int x;       // error: can't restrict object
int restrict *p;      // error: pointer to restrict object
int (*restrict f)();  // error: pointer-to-function

You can use restrict for struct members, for example:

struct node {
   void *restrict data;
   struct node *restrict left;
   struct node *restrict right;
};

says that data will the the only pointer to that data and that left and right will never point to the same node. However, using restrict for struct members is very uncommon.

Lastly, C++ does not have restrict. Why not? There’s a long answer, but the TL;DR version is that:

• It can be a source of hard-to-find bugs that the C++ committee didn’t want to import from C.
• C++’s increased use of pointers, e.g., this, make using restrict safely even harder.

However, many compilers have __restrict__ as an extension.

Conclusion

In limited cases, using restrict can lead to performance improvements, but there are several significant pitfalls. If you’re considering using restrict, profile your code first.

Use wisely.

The above is the detailed content of The Obscure 'restrict” Keyword in C. For more information, please follow other related articles on the PHP Chinese website!