restrict keyword from ISO C99?

T

tweak

Can someone give me a short example as how to best use this keyword in
your code?

This is my understanding: by definition restrict sounds like it is
suppose to restrict access to memory location(s) pointed to, so that
only one declared pointer can store that address and access the data in
those memory blocks, where I the data in those location(s) can be changed.

Is that a correct understanding?

Thanks,

Brian

P.S. I'm slowly making my way through the ISO C99 standard.
 
E

E. Robert Tisdale

tweak said:
Can someone give me a short example
as how to best use this keyword in your code?

#include <string.h>

void *memcpy(void *restrict dest,
const void *restrict src, size_t n);
This is my understanding: by definition restrict sounds like
it is suppose to restrict access to memory location(s) pointed to,
so that only one declared pointer
can store that address and access the data in those memory blocks,
where I the data in those location(s) can be changed.

Is that a correct understanding?

Probably not.

The restrict keyword is a promise by the programmer to the compiler
that the destination [dest] array is *not* an alias
for any part of the source [src] array -- they don't overlap.
But there is, in general, no way for the compiler to determine
whether they are actually aliases or not so the programmer can lie.
The behavior is *undefined*
if copying takes place between objects that overlap.
 
T

Tim Prince

tweak said:
Can someone give me a short example as how to best use this keyword in
your code?

This is my understanding: by definition restrict sounds like it is
suppose to restrict access to memory location(s) pointed to, so that
only one declared pointer can store that address and access the data in
those memory blocks, where I the data in those location(s) can be changed.

Is that a correct understanding?
Partly. When you use the keyword, you take responsibility for the pointers
not interfering with each other, and tell the compiler not to skip any
optimizations you request which might lead to changes in the order of memory
access.

int func(float * restrict a, float * restrict b, int n){
for(int i=0; i < n; ++i)a += b;
}

You tell the compiler not to be concerned that b[] may be changed as a
result of storing into a[], so it is OK to read as far ahead in a[] and b[]
as might be needed to generate fast code. Without restrict, it would not be
OK for the compiler to use parallel instructions, for example. With
restrict, you rule out cases such as a happening to be equal to b+1, in
which case each result feeds into the next operation. Should you compile
this with restrict, and then violate the pledge you made, the results are
undefined.
You may be having difficulty distinguishing this from the implications of
const. const merely tells the compiler to stop you from modifying
explicitly an object which you said would not be modified. It doesn't tell
the compiler to perform optimizations on that account, nor would it prevent
you from running this example with a == b+1. I found it difficult to sort
these out myself.
restrict seems to be a parting of the ways which distinguishes C99 from C89
and C++. No more "C/C++"
 
T

tweak

E. Robert Tisdale said:
tweak said:
Can someone give me a short example as how to best use this keyword in
your code?


#include <string.h>

void *memcpy(void *restrict dest,
const void *restrict src, size_t n);
This is my understanding: by definition restrict sounds like
it is suppose to restrict access to memory location(s) pointed to,
so that only one declared pointer
can store that address and access the data in those memory blocks,
where I the data in those location(s) can be changed.

Is that a correct understanding?


Probably not.

The restrict keyword is a promise by the programmer to the compiler
that the destination [dest] array is *not* an alias
for any part of the source [src] array -- they don't overlap.
But there is, in general, no way for the compiler to determine
whether they are actually aliases or not so the programmer can lie.
The behavior is *undefined*
if copying takes place between objects that overlap.

For clarity:

aliases == variables?
objects == memory locations (&) ?

So if an array with four elements (e.g. char name[4]) occupied 0x01
through 0x05, where 0x05 is '\0', and another array with four elements
(e.g. char fullname[4]) occupied 0x04 through 0x08, where 0x08 is '\0',
then overlap would occur. And the restrict keyword specifies that the
programmer promises to keep the overlapping from occurring, but the
compiler cannot confirm? Is this a better understanding?

Thanks,

Brian
 
T

tweak

Tim said:
Can someone give me a short example as how to best use this keyword in
your code?

This is my understanding: by definition restrict sounds like it is
suppose to restrict access to memory location(s) pointed to, so that
only one declared pointer can store that address and access the data in
those memory blocks, where I the data in those location(s) can be changed.

Is that a correct understanding?

Partly. When you use the keyword, you take responsibility for the pointers
not interfering with each other, and tell the compiler not to skip any
optimizations you request which might lead to changes in the order of memory
access.

int func(float * restrict a, float * restrict b, int n){
for(int i=0; i < n; ++i)a += b;
}

You tell the compiler not to be concerned that b[] may be changed as a
result of storing into a[], so it is OK to read as far ahead in a[] and b[]
as might be needed to generate fast code. Without restrict, it would not be
OK for the compiler to use parallel instructions, for example. With
restrict, you rule out cases such as a happening to be equal to b+1, in
which case each result feeds into the next operation. Should you compile
this with restrict, and then violate the pledge you made, the results are
undefined.
You may be having difficulty distinguishing this from the implications of
const. const merely tells the compiler to stop you from modifying
explicitly an object which you said would not be modified. It doesn't tell
the compiler to perform optimizations on that account, nor would it prevent
you from running this example with a == b+1. I found it difficult to sort
these out myself.
restrict seems to be a parting of the ways which distinguishes C99 from C89
and C++. No more "C/C++"

So the programmer takes the responsibility to manage the modifyable
pointers, allowing the compiler to generate faster machine code. But
because the compiler cannot confirm the programmer did not break his
promise, there is a possibility of undefined behavior should the
programmer break his promise. And the result is better machine code,
so if I disassemble after compiling with optimizations on, I should see
better assembly code, right?

And in your example of a == b+1, you have performed pointer math on b
that you had promised that you would not perform? Is the promise made
on the memory locations, what's contained in those locations, or both?

Thanks,

Brian
 
T

Tim Prince

tweak said:
Tim said:
Can someone give me a short example as how to best use this keyword in
your code?

This is my understanding: by definition restrict sounds like it is
suppose to restrict access to memory location(s) pointed to, so that
only one declared pointer can store that address and access the data in
those memory blocks, where I the data in those location(s) can be changed.

Is that a correct understanding?

Partly. When you use the keyword, you take responsibility for the pointers
not interfering with each other, and tell the compiler not to skip any
optimizations you request which might lead to changes in the order of memory
access.

int func(float * restrict a, float * restrict b, int n){
for(int i=0; i < n; ++i)a += b;
}

You tell the compiler not to be concerned that b[] may be changed as a
result of storing into a[], so it is OK to read as far ahead in a[] and b[]
as might be needed to generate fast code. Without restrict, it would not be
OK for the compiler to use parallel instructions, for example. With
restrict, you rule out cases such as a happening to be equal to b+1, in
which case each result feeds into the next operation. Should you compile
this with restrict, and then violate the pledge you made, the results are
undefined.
You may be having difficulty distinguishing this from the implications of
const. const merely tells the compiler to stop you from modifying
explicitly an object which you said would not be modified. It doesn't tell
the compiler to perform optimizations on that account, nor would it prevent
you from running this example with a == b+1. I found it difficult to sort
these out myself.
restrict seems to be a parting of the ways which distinguishes C99 from C89
and C++. No more "C/C++"

So the programmer takes the responsibility to manage the modifyable
pointers, allowing the compiler to generate faster machine code. But
because the compiler cannot confirm the programmer did not break his
promise, there is a possibility of undefined behavior should the
programmer break his promise. And the result is better machine code,
so if I disassemble after compiling with optimizations on, I should see
better assembly code, right?

You have no guarantee of "better" code, but if you use a "vectorizing" or
pipelining compiler, it should not perform those optimizations without at
least one of the restricts, or alternatively some option which gives more
freedom than C allows.
And in your example of a == b+1, you have performed pointer math on b
that you had promised that you would not perform? Is the promise made
on the memory locations, what's contained in those locations, or both?
It doesn't matter if you violate the restrict to the extent of having
overlapping read-only ranges of memory locations. What matters is that one
pointer isn't used to modify data pointed to by another. Strictly, of
course, you are promising no overlap in memory ranges. It's probably better
to stick to that from a maintainability point of view, in case you started
modifying the target of a pointer, and forgot that it overlapped the target
of another.
 
C

Christian Bau

tweak <[email protected]> said:
Can someone give me a short example as how to best use this keyword in
your code?

This is my understanding: by definition restrict sounds like it is
suppose to restrict access to memory location(s) pointed to, so that
only one declared pointer can store that address and access the data in
those memory blocks, where I the data in those location(s) can be changed.

Is that a correct understanding?

Two examples why restrict is useful:

int calc_area (int* width, int* height) {
*width = 5;
*height = 6;
return (*width) * (*height);
}

int f (const int* p, int* q) {
int x = *p;
*q = x + 1;
return *p;
}

In the first function, you would assume that the function returns 30, so
an optimising compiler can avoid reading *width and *height and
multiplying these values. Sadly, this is wrong. If I write

int x;
int a = calc_area (&x, &x);

the result is 36, not 30. An optimising compiler is forced to store 5
into *width, then store 6 into *height, then read *width, then multiply
that value by 6 and return the result.

In the second function, you would assume that the value returned is
always equal to x. Sadly, this is wrong, too. If I write

int x = 5;
int a = f (&x, &x);

then x will be changed to 6, and the value returned is six, not five.
"const int* p" only means that you cannot store to the object *p through
the pointer *p itself, but the same object can be modified by other
means - for example by storing to *q.

In both functions, the compiler is forced to produce slow code, to
handle situations that will never arise in practice. That is what
"restrict" is for.

If you declare a restrict pointer object, like

int* restrict p;

then all pointer values from then on fall into two categories: Pointer
values that are derived from p, and pointer values that are not derived
from p. Roughly speaking, pointer values derived from p are pointer
values that are calculated by starting with p, and adding or subtracting
to it in arbitrary complicated way. For example,

int a [100];
int* restrict p = &a [0];
int* q = p + 1;
int* r = q - 1;
int* s = &a [0];

q and r are derived from p. s is not derived from p. Even though r == s,
one is derived from p, the other is not.

You promise the compiler two things:

1. Any object that is modified through a pointer based on p, is not
accessed or modified through any pointer that is not based on p.
2. Any object that is modified through a pointer that is not based on p,
is not accessed or modified through any pointer that is based on p.

Declaring a "const restrict" pointer object is stronger. If you have

const int* restrict p = &a[0];

for example, then your promise to the compiler is:

Any object that is accessed through a pointer based on p is not modified
by any means whatsoever.

What does that mean for the examples above: If you wrote

int calc_area (int* restrict width, int* restrict height) { ... }

you promise that assigning to *height does not change *width and vice
versa (just read the rules above carefully). Actually, using one
restrict pointer would have had the same effect. As a result, the
compiler can assume that the result of this function is always 30.

In the second function, if you wrote

int f (const int* restrict p, int* q) { ... }

you would promise to the compiler that *p is not modified in that
function by any means, so you promse that q does not point to *p. An
optimising compiler needs to read *p only once and knows that it cannot
change its value in that function.
 
D

Dan Pop

In said:
Can someone give me a short example as how to best use this keyword in
your code?

This is my understanding: by definition restrict sounds like it is
suppose to restrict access to memory location(s) pointed to, so that
only one declared pointer can store that address and access the data in
those memory blocks, where I the data in those location(s) can be changed.

Is that a correct understanding?

Your description is not very coherent, so it's hard to tell whether your
understanding is correct or not. This is one of the cases where it's
better to avoid the normative text of the standard and focus on the
examples:

7 EXAMPLE 1 The file scope declarations

int * restrict a;
int * restrict b;
extern int c[];

assert that if an object is accessed using one of a, b, or c,
and that object is modified anywhere in the program, then it is
never accessed using either of the other two.

Dan
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top