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?
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.
#ifndef __GNUC__
#define __restrict__ /* no-op */
or similar. And define it to __restrict
if _MSC_VER
is defined.
Apr 27, 2017 at 22:43
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 parameterrsi
= second parameterrdx
= third parameterGCC 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__
-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")
Jun 9, 2017 at 15:46
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!
Jul 30, 2022 at 21:49
Nothing. It was added to the C99 standard.
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.
Dec 27, 2009 at 14:00
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++.
__restrict__
keyword which is identical as far as I can tell.
Dec 27, 2009 at 12:45
restrict
. The behavior of the C++ program becomes undefined if it violates the restrictions implied by restrict
.
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.
Jun 18, 2020 at 10:56
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".
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++.
__restrict__
keyword which is identical as far as I can tell.
Dec 27, 2009 at 12:45
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.
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++.
Dec 27, 2009 at 12:44
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.
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.#warning
directive, or the function signature macros (__PRETTY_FUNCTION__
on GCC,__FUNCSIG__
on MSVC, etc.).restrict
isn't considered a C++ keyword (see en.cppreference.com/w/cpp/keyword ), and in fact, the only mention ofrestrict
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: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 containsrestrict
in C, therestrict
keyword must be removed from the C++ equivalent's signature.