What does the restrict keyword mean in C++?

Question

I was always unsure; what does the restrict keyword mean in C++?

Does it mean the two or more pointer given to the function does not overlap? What else does it mean?

Underquote

restrict is a c99 keyword. Yes, Rpbert S. Barnes, I know that most compilers support __restrict__. You will note that anything with double underscores is, by definition, implementation specific and thus NOT C++, but a compiler specific version of it. – Athelstan

What? Just because it's implementation specific does not make it not C++; the C++ allows for implementation specific stuff explicitly, and does not disallow it or render it not C++. – Morphinism

@Morphinism KitsuneYMG means that it's not part of ISO C++, and is instead considered a C++ extension. Compiler creators are allowed to make and distribute their own extensions, which coexist with ISO C++ and act as part of a usually-less-or-non-portable unofficial addition to C++. Examples would be MS's old Managed C++, and their more recent C++/CLI. Other examples would be preprocessor directives and macros supplied by some compilers, such as the common #warning directive, or the function signature macros (__PRETTY_FUNCTION__ on GCC, __FUNCSIG__ on MSVC, etc.). – Click

Basically, Kitsune means that it's not C++ strictly as defined by the standard, but is instead standard C++ plus the allowed implementation-specific stuff. – Click

@JustinTime Except that's not true; the C++11 standard requires all compliant compilers to support the restrict keyword; they just don't require any compiler to actually do anything but ignore it. – Morphinism

@Morphinism To my knowledge, C++11 doesn't mandate full support for all of C99, nor do C++14 or what I know of C++17. restrict isn't considered a C++ keyword (see en.cppreference.com/w/cpp/keyword ), and in fact, the only mention of restrict in the C++11 standard (see open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3337.pdf , a copy of the FDIS with minor editorial changes, §17.2 [library.c], PDF page 413) states that: – Click

"The descriptions of many library functions rely on the C standard library for the signatures and semantics of those functions. In all such cases, any use of the restrict qualifier shall be omitted." – Click

So, no, restrict isn't part of ISO C++ at the moment, at least not as far as I can tell. According to Herb Sutter ( herbsutter.com/2012/05/03/reader-qa-what-about-vc-and-c99 ): "Although it was specifically suggested for ISO C++11, it was rejected, in part because it’s not always obvious how it extends to C++ code because C++ is a larger language with more options and we would want to make sure the feature works correctly across the entire language." – Click

It may be worked into C++17, I'm not sure. However, at least at the moment, it's more important for C than it is C++, seeing how it's easier to prevent pointer aliasing in C++ than it is in C. Add to that that it would be more difficult to implement in C++ (there's also references to consider, and multiple standard classes would likely need to be updated with restrict), and it makes sense that it wouldn't have been added to the language, but instead left to compiler/interpreter creators to implement in a platform-specific manner. – Click

@JustinTime You just contradicted yourself. You stated the part of the C++11 standard that demands compatibility with restrict, and then take it away in the next statement. – Morphinism

@Morphinism How so? I stated the part that says that restrict is to be omitted from (excluded from, left out of) C standard library function signatures and semantics when those functions are included in the C++ standard library. Or in other words, I stated the fact that says that if a C standard library function's signature contains restrict in C, the restrict keyword must be removed from the C++ equivalent's signature. – Click

Answer 1

As others said, it means nothing as of C++14, so let's consider the __restrict__ GCC extension which does the same as the C99 restrict.

C99

restrict says that two pointers cannot point to overlapping memory regions. The most common usage is for function arguments.

This restricts how the function can be called, but allows for more compile optimizations.

If the caller does not follow the restrict contract, undefined behavior can occur.

The C99 N1256 draft 6.7.3/7 "Type qualifiers" says:

The intended use of the restrict qualifier (like the register storage class) is to promote optimization, and deleting all instances of the qualifier from all preprocessing translation units composing a conforming program does not change its meaning (i.e., observable behavior).

and 6.7.3.1 "Formal definition of restrict" gives the gory details.

A possible optimization

The Wikipedia example is very illuminating.

It clearly shows how as it allows to save one assembly instruction.

Without restrict:

void f(int *a, int *b, int *x) {
  *a += *x;
  *b += *x;
}

Pseudo assembly:

load R1 ← *x    ; Load the value of x pointer
load R2 ← *a    ; Load the value of a pointer
add R2 += R1    ; Perform Addition
set R2 → *a     ; Update the value of a pointer
; Similarly for b, note that x is loaded twice,
; because x may point to a (a aliased by x) thus 
; the value of x will change when the value of a
; changes.
load R1 ← *x
load R2 ← *b
add R2 += R1
set R2 → *b

With restrict:

void fr(int *restrict a, int *restrict b, int *restrict x);

Pseudo assembly:

load R1 ← *x
load R2 ← *a
add R2 += R1
set R2 → *a
; Note that x is not reloaded,
; because the compiler knows it is unchanged
; "load R1 ← *x" is no longer needed.
load R2 ← *b
add R2 += R1
set R2 → *b

Does GCC really do it?

g++ 4.8 Linux x86-64:

g++ -g -std=gnu++98 -O0 -c main.cpp
objdump -S main.o

With -O0, they are the same.

With -O3:

void f(int *a, int *b, int *x) {
    *a += *x;
   0:   8b 02                   mov    (%rdx),%eax
   2:   01 07                   add    %eax,(%rdi)
    *b += *x;
   4:   8b 02                   mov    (%rdx),%eax
   6:   01 06                   add    %eax,(%rsi)  

void fr(int *__restrict__ a, int *__restrict__ b, int *__restrict__ x) {
    *a += *x;
  10:   8b 02                   mov    (%rdx),%eax
  12:   01 07                   add    %eax,(%rdi)
    *b += *x;
  14:   01 06                   add    %eax,(%rsi) 

For the uninitiated, the calling convention is:

• rdi = first parameter
• rsi = second parameter
• rdx = third parameter

GCC output was even clearer than the wiki article: 4 instructions vs 3 instructions.

Arrays

So far we have single instruction savings, but if pointer represent arrays to be looped over, a common use case, then a bunch of instructions could be saved, as mentioned by supercat and michael.

Consider for example:

void f(char *restrict p1, char *restrict p2, size_t size) {
     for (size_t i = 0; i < size; i++) {
         p1[i] = 4;
         p2[i] = 9;
     }
 }

Because of restrict, a smart compiler (or human), could optimize that to:

memset(p1, 4, size);
memset(p2, 9, size);

Which is potentially much more efficient as it may be assembly optimized on a decent libc implementation (like glibc) Is it better to use std::memcpy() or std::copy() in terms to performance?, possibly with SIMD instructions.

Without, restrict, this optimization could not be done, e.g. consider:

char p1[4];
char *p2 = &p1[1];
f(p1, p2, 3);

Then for version makes:

p1 == {4, 4, 4, 9}

while the memset version makes:

p1 == {4, 9, 9, 9}

Does GCC really do it?

GCC 5.2.1.Linux x86-64 Ubuntu 15.10:

gcc -g -std=c99 -O0 -c main.c
objdump -dr main.o

With -O0, both are the same.

With -O3:

• with restrict:

  3f0:   48 85 d2                test   %rdx,%rdx
  3f3:   74 33                   je     428 <fr+0x38>
  3f5:   55                      push   %rbp
  3f6:   53                      push   %rbx
  3f7:   48 89 f5                mov    %rsi,%rbp
  3fa:   be 04 00 00 00          mov    $0x4,%esi
  3ff:   48 89 d3                mov    %rdx,%rbx
  402:   48 83 ec 08             sub    $0x8,%rsp
  406:   e8 00 00 00 00          callq  40b <fr+0x1b>
                          407: R_X86_64_PC32      memset-0x4
  40b:   48 83 c4 08             add    $0x8,%rsp
  40f:   48 89 da                mov    %rbx,%rdx
  412:   48 89 ef                mov    %rbp,%rdi
  415:   5b                      pop    %rbx
  416:   5d                      pop    %rbp
  417:   be 09 00 00 00          mov    $0x9,%esi
  41c:   e9 00 00 00 00          jmpq   421 <fr+0x31>
                          41d: R_X86_64_PC32      memset-0x4
  421:   0f 1f 80 00 00 00 00    nopl   0x0(%rax)
  428:   f3 c3                   repz retq
  

  Two memset calls as expected.

• without restrict: no stdlib calls, just a 16 iteration wide loop unrolling which I do not intend to reproduce here :-)

I haven't had the patience to benchmark them, but I believe that the restrict version will be faster.

Strict aliasing rule

The restrict keyword only affects pointers of compatible types (e.g. two int*) because the strict aliasing rules says that aliasing incompatible types is undefined behavior by default, and so compilers can assume it does not happen and optimize away.

See: What is the strict aliasing rule?

Does it work for references?

According to the GCC docs it does: https://gcc.gnu.org/onlinedocs/gcc-5.1.0/gcc/Restricted-Pointers.html with syntax:

int &__restrict__ rref

There is even a version for this of member functions:

void T::fn () __restrict__

Polyphemus

nice asnwer. What if strict aliasing is disabled -fno-strict-aliasing, then restrict should make no difference between pointers of same type or different types, no? ( i am refering to "The restrict keyword only affects pointers of compatible types") – Carpogonium

@tobi303 I don't know! Let me know if you find out for sure ;-) – Polyphemus

@jww yes, that is a better way of phrasing it. Updated. – Polyphemus

restrict does mean something in C++. If you call a C library function with restrict parameters from a C++ program, you have to obey the implications of that. Basically, if restrict is used in a C library API it means something to anyone calling it from any language, including dynamic FFI from Lisp. – Tiltyard

Nice answer! But there is one subtle thing "restrict says that two pointers cannot point to overlapping memory regions." - it's not 100% true. If you open C99 standard and read the formal definition of restrict, it's only about lvalue expressions. The memory can overlap in the case of using pointed objects as rvalues. For that aspect, also see Harbison, Steele. C A Reference, page 95, (3). One more time - Nice answer! – Comenius

@KonstantinBurlachenko thanks so much for the comment. I'd need to do a bit more research to fully understand what you mean, my C is not that good, but I believe you. Let me know if there's a simple example of that case that would be allowed somewhere and I will link to it/copy it here. I imagine it is something like a struct inside a struct, and pointer to the outer + a pointer to the inner one? – Polyphemus

"...my C is not that good.." - no! it's good if you have created such post! :) Example: // valid since C89 void add(int n, int* restrict dest, const int * restrict op1, const int * restrict op2) { // 1 int i = 0; // 2 for (i = 0; i < n; ++i) // 3 { dest[i] = op1[i] + op2[i]; // 4 } // 5 } // it's absolutely valid to call add whatever compiler will do with lines 1-3 when "op1==op2" in that circumstances. – Comenius

It's not deep; if you access values pointed by restricted pointers "for reading" - it's okay. But if use it for "write" - it's [not OK]. It's pretty subtle thing, but I think it will improve you answer if you cover it...Feel free to check Harbison Steele's book...The C99 standard defines restrict in a pretty complicated formal way... – Comenius

Suffice it to say, restrict/__restrict__ can be exceedingly beneficial to optimized performance... so who cares if it isn't an "official C++ keyword" (TM)? It's an "any compiler that doesn't support it probably sucks" keyword. – Reactant

Answer 2

In his paper, Memory Optimization, Christer Ericson says that while restrict is not part of the C++ standard yet, that it is supported by many compilers and he recommends it's usage when available:

restrict keyword

! New to 1999 ANSI/ISO C standard

! Not in C++ standard yet, but supported by many C++ compilers

! A hint only, so may do nothing and still be conforming

A restrict-qualified pointer (or reference)...

! ...is basically a promise to the compiler that for the scope of the pointer, the target of the pointer will only be accessed through that pointer (and pointers copied from it).

In C++ compilers that support it it should probably behave the same as in C.

See this SO post for details: Realistic usage of the C99 ‘restrict’ keyword?

Take half an hour to skim through Ericson's paper, it's interesting and worth the time.

Edit

I also found that IBM's AIX C/C++ compiler supports the __restrict__ keyword.

g++ also seems to support this as the following program compiles cleanly on g++:

#include <stdio.h>

int foo(int * __restrict__ a, int * __restrict__ b) {
    return *a + *b;
}

int main(void) {
    int a = 1, b = 1, c;
    
    c = foo(&a, &b);

    printf("c == %d\n", c);

    return 0;
}

I also found a nice article on the use of restrict:

Demystifying The Restrict Keyword

Edit2

I ran across an article which specifically discusses the use of restrict in C++ programs:

Load-hit-stores and the __restrict keyword

Also, Microsoft Visual C++ also supports the __restrict keyword.

Limber

The Memory Optimisation paper link is dead, here's a link to the audio from his GDC presentation. gdcvault.com/play/1022689/Memory – Tubman

@EnnMichael: Obviously if you're going to use it in a portable C++ project, you should #ifndef __GNUC__ #define __restrict__ /* no-op */ or similar. And define it to __restrict if _MSC_VER is defined. – Jointless

The slides can be found here lukasz.dk/mirror/research-scea/research/pdfs/… – Basal

Answer 3

Nothing. It was added to the C99 standard.

Giantess

That's not completely true. Apparently it's supported by some C++ compilers and some people strongly recommend it's usage when it's available, see my answer below. – Limber

@Robert S Barnes: The C++ standard does not recognize restrict as a keyword. Hence my answer stands correct. What you describe is implementation specific behavior and something that you should not really rely on. – Giantess

@dirkgently: With all due respect, why not? Many projects are tied to specific non-standard language extensions supported by only specific or very few compilers. The Linux Kernel and gcc comes to mind. It's not uncommon to stick with a specific compiler, or even a specific revision of a specific compiler for the entire useful lifetime of a project. Not every program needs to be strictly conforming. – Limber

@Rpbert S. Barnes: I cannot possibly stress any further why you should not depend on implementation specific behavior. As for Linux and gcc -- think and you'll see why they are not a good example in your defense. I am yet to see even a moderately successful piece of software run on a single compiler version for its lifetime. – Giantess

@Rpbert S. Barnes: The question said c++. Not MSVC, not gcc, not AIX. If acidzombie24 wanted compiler specific extensions, s?he should have said/tagged so. – Athelstan

@Giantess Linux, Word, Chrome – Morphinism

@Giantess I am thinking, but I don't quite see why Linux and gcc aren't excellent examples of what RobertSBarnes is talking about. – Glidewell

They may be but what RobertSBarnes is talking about is not what the OP asked about. The OP asked about C++. Period. – Vindication

Answer 4

This is the original proposal to add this keyword. As dirkgently pointed out though, this is a C99 feature; it has nothing to do with C++.

Hong

Many C++ compilers support the __restrict__ keyword which is identical as far as I can tell. – Limber

It has everything to do with C++, because C++ programs call C libraries, and C libraries use restrict. The behavior of the C++ program becomes undefined if it violates the restrictions implied by restrict. – Tiltyard

@kaz Totally wrong. It has nothing to do with C++ because it's not a keyword or feature of C++, and if you use C header files in C++ you must remove the restrict keyword. Of course if you pass aliased pointers to a C function that declares them restricted (which you can do from either C++ or C) then it's undefined, but that's on you. – Valenza

@JimBalter I see, so what you're saying is that C++ programs call C libraries, and C libraries use restrict. The behavior of the C++ program becomes undefined if it violates the restrictions implied by restrict. But this actually has nothing to do with C++, because it's "on you". – Tiltyard

Answer 5

There's no such keyword in C++. List of C++ keywords can be found in section 2.11/1 of C++ language standard. restrict is a keyword in C99 version of C language and not in C++.

Evitaevitable

Many C++ compilers support the __restrict__ keyword which is identical as far as I can tell. – Limber

@Robert: But there is no such keyword in C++. What individual compilers do is their own business, but it is not part of the C++ language. – Taegu

Answers like this are. It very helpful. This could be a comment to the original question, but if the question's true purpose is obvious enough (the purpose of the restrict keyword), then it's better to add the real answer after the factual nitpick. – Tack

Answer 6

Since header files from some C libraries use the keyword, the C++ language will have to do something about it.. at the minimum, ignoring the keyword, so we don't have to #define the keyword to a blank macro to suppress the keyword.

Clabo

I would guess that's either handled by using an extern C declaration, or by it being silently dropped, as is the case with the AIX C/C++ compiler, which instead handles the __rerstrict__ keyword. That keyword is also supported under gcc so that code will compile the same under g++. – Limber

Answer 7

With __restrict__, the compiler can do sophisticated optimizations, as programmer has guranteed the __restrict__ decorated pointers point to data ranges that will definetly not overlap each other.

This is usually the case, so for high performance goal, you can at most times put a __restrict__ decorator to the pointers in your code.

Dehlia