restrict

[gc]

Hi,
What is the purpose of the restrict keyword?
gc

 

[Andreas Kahari]

Hi,
What is the purpose of the restrict keyword?

The data pointed to by a pointer declared with the restrict
qualifier may not be pointed to by any other pointer. This
allows for more effective optimization.

For example, the two pointers used as arguments to memcpy() are
declared with restrict, which simply means that the two data
areas may not overlap.

 

[E. Robert Tisdale]

The data pointed to by a pointer declared with the restrict
qualifier may not be pointed to by any other pointer.
This allows for more effective optimization.

For example, the two pointers used as arguments to memcpy()
are declared with restrict, which simply means that
the two data areas may not overlap.

Would you mind elaborating a little on this?
My memcpy doesn't use the *restrict* keyword:

MEMCPY(3) Linux Programmer’s Manual MEMCPY(3)

NAME
memcpy - copy memory area

SYNOPSIS
#include <string.h>

void *memcpy(void *dest, const void *src, size_t n);

.
.
.

> cat memcpy.c

#include <stddef.h>
void *memcpy(void *restrict dest,
const void *restrict src, size_t n);

int main(int argc, char* argv[]) {
char a[256];
memcpy(a, &a[12], 50);
return 0;
}

> gcc -Wall -std=c99 -pedantic -O2 -c memcpy.c

In the example above, &a[12] is an alias for part of array a
but my compiler doesn't complain. Is this a bug in my compiler?

 

[Andreas Kahari]

What is the purpose of the restrict keyword?

[cut]
For example, the two pointers used as arguments to memcpy()
are declared with restrict, which simply means that
the two data areas may not overlap.

Would you mind elaborating a little on this?
My memcpy doesn't use the *restrict* keyword:

C isn't defined by Linux manual pages.

I chose that example because thæt's the example that the
standard )or was it the rationale) uses. Later, the standard
indeed defines memcpy() as taking two restrict pointers. For
Unix-type systems that claims to be POSIX compatible, see also
the Single Unix Specification at

http://www.opengroup.org/onlinepubs/007904975/functions/memcpy.html

 

[E. Robert Tisdale]

I chose that example because that's the example that the
standard )or was it the rationale) uses. Later, the standard
indeed defines memcpy() as taking two restrict pointers. For
Unix-type systems that claims to be POSIX compatible, see also
the Single Unix Specification at

http://www.opengroup.org/onlinepubs/007904975/functions/memcpy.html

NAME

memcpy - copy bytes in memory

SYNOPSIS

#include <string.h>

void *memcpy(void *restrict s1, const void *restrict s2, size_t n);

DESCRIPTION

The functionality described on this reference page
is aligned with the ISO C standard.
Any conflict between the requirements described here
and the ISO C standard is unintentional.
This volume of IEEE Std 1003.1-2001 defers to the ISO C standard.

The memcpy() function shall copy n bytes
from the object pointed to by s2 into the object pointed to by s1.
If copying takes place between objects that overlap,
the behavior is undefined.


This behavior is no different from the behavior described in
the old ANSI/ISO C89 standard and my Linux man page.
The restrict keyword appears to serve *no* useful function
in the above declaration of memcpy.
Which begs the question,
"What is the purpose of the restrict keyword?"

 

[Mark Gordon]

NAME

memcpy - copy bytes in memory

SYNOPSIS

#include <string.h>

void *memcpy(void *restrict s1, const void *restrict s2, size_t
n);

DESCRIPTION

The functionality described on this reference page
is aligned with the ISO C standard.
Any conflict between the requirements described here
and the ISO C standard is unintentional.
This volume of IEEE Std 1003.1-2001 defers to the ISO C standard.

The memcpy() function shall copy n bytes
from the object pointed to by s2 into the object pointed to by
s1. If copying takes place between objects that overlap,
the behavior is undefined.


This behavior is no different from the behavior described in
the old ANSI/ISO C89 standard and my Linux man page.
The restrict keyword appears to serve *no* useful function
in the above declaration of memcpy.
Which begs the question,
"What is the purpose of the restrict keyword?"

It means that if the memcpy routine in the library is written in C the
compiler is free to make use of the fact the pointers point to different
objects in it's optimisation. This increases the potential for an
implementation to write the libraries in C whilst still having them
efficient.

It makes it easier if the compiler writer wants to make the compiler
generate diagnostics if at compiler time it is possible to determine
that the two pointer are in fact the same without having to treat memcpy
as a special case. Not that the compiler writer is obliged to generate a
diagnostic for this, but it is permitted.

It also means that the prototype provides more information to anyone
reading it than would otherwise be the case.

Even prototypes for library functions should be designed indicate as
much about the use of parameters as is practical, even if there is no
obvious benefit other than making it clearer to a human reader.

 

[Serve La]

This behavior is no different from the behavior described in
the old ANSI/ISO C89 standard and my Linux man page.
The restrict keyword appears to serve *no* useful function
in the above declaration of memcpy.
Which begs the question,
"What is the purpose of the restrict keyword?"

That the memory may not overlap in memcpy (ok, UB if it does) is well known.
In this case restrict only makes the code document itself. However, if I
create a function myself you and the compiler don't automatically know this.
With restrict you do and you know you cause UB if you have other pointers
aliasing the restricted pointer.

 

[j]

NAME

memcpy - copy bytes in memory

SYNOPSIS

#include <string.h>

void *memcpy(void *restrict s1, const void *restrict s2, size_t n);

DESCRIPTION

The functionality described on this reference page
is aligned with the ISO C standard.
Any conflict between the requirements described here
and the ISO C standard is unintentional.
This volume of IEEE Std 1003.1-2001 defers to the ISO C standard.

The memcpy() function shall copy n bytes
from the object pointed to by s2 into the object pointed to by s1.
If copying takes place between objects that overlap,
the behavior is undefined.


This behavior is no different from the behavior described in
the old ANSI/ISO C89 standard and my Linux man page.
The restrict keyword appears to serve *no* useful function
in the above declaration of memcpy.
Which begs the question,
"What is the purpose of the restrict keyword?"

restrict is an assertion that there are no aliases in effect
for the scope of a given operation.
That is, pointer operations will affect distinct vectors.
This is why memcpy can use the restrict qualifier(unlike say,
memmove; which may produce an alias inadvertantly) for
further optimizations.

 

[E. Robert Tisdale]

It means that if the memcpy routine in the library is written in C the
compiler is free to make use of the fact the pointers point to different
objects in it's optimization. This increases the potential for an
implementation to write the libraries in C whilst still having them
efficient.

It makes it easier if the compiler writer wants to make the compiler
generate diagnostics if at compile time it is possible to determine
that the two pointer are in fact the same without having to treat memcpy
as a special case. Not that the compiler writer is obliged to generate a
diagnostic for this, but it is permitted.

It also means that the prototype provides more information to anyone
reading it than would otherwise be the case.

Even prototypes for library functions should be designed to indicate as
much about the use of parameters as is practical, even if there is no
obvious benefit other than making it clearer to a human reader.

Evidently, you are saying that a C 99 compiler is permitted
to do a better job of optimizing this definition:

void *memcpy(void *restrict s1,
const void *restrict s2, size_t n) {
for (int j = 0; j < n; ++j)
((char*)s1)[j] = ((char*)s2)[j];
return s1;
}

than it is allowed to do for this definition:

void *memcpy(void *s1,
const void *s2, size_t n) {
for (int j = 0; j < n; ++j)
((char*)s1)[j] = ((char*)s2)[j];
return s1;
}

Further, you appear to be saying that
the appearance of the restrict keyword in the
declaration of memcpy (what you call the prototype)
serves no purpose except for documentation
as the ANSI/ISO C99 standard does *not*
require the compiler to detect any aliases
and issue a diagnostic for it when memcpy is invoked.

 

[Arthur J. O'Dwyer]

It means that if the memcpy routine in the library is written in C the
compiler is free to make use of the fact the pointers point to different
objects in it's optimization. This increases the potential for an
implementation to write the libraries in C whilst still having them
efficient.

It makes it easier if the compiler writer wants to make the compiler
generate diagnostics if at compile time it is possible to determine
that the two pointer are in fact the same without having to treat memcpy
as a special case. Not that the compiler writer is obliged to generate a
diagnostic for this, but it is permitted.

It also means that the prototype provides more information to anyone
reading it than would otherwise be the case.

Even prototypes for library functions should be designed to indicate as
much about the use of parameters as is practical, even if there is no
obvious benefit other than making it clearer to a human reader.

Evidently, you are saying that a C 99 compiler is permitted
to do a better job of optimizing this definition:

void *memcpy(void *restrict s1,
const void *restrict s2, size_t n) {
for (int j = 0; j < n; ++j)
((char*)s1)[j] = ((char*)s2)[j];
return s1;
}

than it is allowed to do for this definition:

void *memcpy(void *s1,
const void *s2, size_t n) {
for (int j = 0; j < n; ++j)
((char*)s1)[j] = ((char*)s2)[j];
return s1;
}

Further, you appear to be saying that
the appearance of the restrict keyword in the
declaration of memcpy (what you call the prototype)
serves no purpose except for documentation
as the ANSI/ISO C99 standard does *not*
require the compiler to detect any aliases
and issue a diagnostic for it when memcpy is invoked.

Yes. All correct.

-Arthur

 

[Jack Klein]

NAME

memcpy - copy bytes in memory

SYNOPSIS

#include <string.h>

void *memcpy(void *restrict s1, const void *restrict s2, size_t n);

DESCRIPTION

The functionality described on this reference page
is aligned with the ISO C standard.
Any conflict between the requirements described here
and the ISO C standard is unintentional.
This volume of IEEE Std 1003.1-2001 defers to the ISO C standard.

The memcpy() function shall copy n bytes
from the object pointed to by s2 into the object pointed to by s1.
If copying takes place between objects that overlap,
the behavior is undefined.


This behavior is no different from the behavior described in
the old ANSI/ISO C89 standard and my Linux man page.
The restrict keyword appears to serve *no* useful function
in the above declaration of memcpy.
Which begs the question,
"What is the purpose of the restrict keyword?"

Because the "restrict" keyword replaces the entire paragraph:

The memcpy() function shall copy n bytes
from the object pointed to by s2 into the object pointed to by s1.
If copying takes place between objects that overlap,
the behavior is undefined.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++ ftp://snurse-l.org/pub/acllc-c++/faq

 

[Keith Thompson]

On Wed, 01 Oct 2003 12:47:43 -0700, "E. Robert Tisdale"


Because the "restrict" keyword replaces the entire paragraph:

Well, theoretically it replaces only the second sentence of the
paragraph; the presence of "restrict" doesn't imply that memcpy()
copies bytes.

Note that the sentence still appears in the standard. I suppose it's
strictly redundant and could have been moved to a footnote. (I don't
understand "restrict" well enough to be sure of this.)

 

[Jeremy Yallop]

For example, the two pointers used as arguments to memcpy()
are declared with restrict, which simply means that
the two data areas may not overlap.

Would you mind elaborating a little on this?
My memcpy doesn't use the *restrict* keyword: [snip]
In the example above, &a[12] is an alias for part of array a
but my compiler doesn't complain. Is this a bug in my compiler?

It's not a bug in your compiler. By "may not", Andreas means that
you, the programmer, cannot pass pointers to overlapping data areas to
memcpy() with reliable results, not that the compiler is required to
detect and reject calls with pointers to overlapping regions. Indeed,
it's not possible in general for the compiler to determine whether the
regions overlap:

#include <string.h>

int main(int argc, char **argv)
{
char buf[10] = {0};
memcpy(buf, buf + argc, 3);
/* ... */
}

It is precisely because aliasing cannot be easily and reliably
detected that "restrict" is needed: it allows the programmer to
provide extra information that the compiler cannot (and ought not to)
deduce unaided. (It also has the secondary purpose of documentation
for human readers, of course).

Jeremy.

 

[E. Robert Tisdale]

It is precisely because aliasing cannot be easily and reliably
detected that "restrict" is needed: it allows the programmer to
provide extra information that the compiler cannot (and ought not to)
deduce unaided. (It also has the secondary purpose of documentation
for human readers, of course).

No.

The restrict keyword does *not* provide any extra information
to the compiler.
It simple allows the programmer to *lie* to the C compiler.
It tells the C compiler to *assume* that
source and destination arrays are disjoint
even though there is no way for either the programmer
or the C compiler to ensure that
source and destination arrays do *not* overlap.

 

[Alan Balmer]

No.

The restrict keyword does *not* provide any extra information
to the compiler.
It simple allows the programmer to *lie* to the C compiler.
It tells the C compiler to *assume* that
source and destination arrays are disjoint
even though there is no way for either the programmer
or the C compiler to ensure that
source and destination arrays do *not* overlap.

?

I agree that I don't expect the compiler to know, but I don't have a
problem knowing when source and destinations buffers overlap.

 

[E. Robert Tisdale]

?

I agree that I don't expect the compiler to know, but I don't have a
problem knowing when source and destinations buffers overlap.

Really!

void *memcpy(void *restrict dest,
const void *restrict src, size_t n) {
// Please show us how you you would know
// when dest and src overlap.
return dest;
}

 

[Chris Torek]

I am going to leave out all the quoting etc., and just describe
what "restrict"ed pointers are really about.

First, let me write a reasonably portable (albeit inefficient)
restrict-less variant of memcpy() in ordinary C99:

void *mc0(void *dst, const void *src, size_t len) {
unsigned char *d = dst;
const unsigned char *s = src;

while (len--)
*d++ = *s++;
return dst;
}

This simply copies bytes from "src" to "dst", using "unsigned
char"s to get all the bits. If this is used to copy (e.g.) 65536
bytes from buffer A to buffer B, the loop runs 65536 times.

Next, consider the following non-portable variant, intended for a
machine with today's common 8-bit-bytes and 32-bit ints:

void *mc1(void *dst, const void *src, size_t len) {
char *d = dst;
const char *s = src;

while (len >= sizeof(int)) {
*(int *)d = *(int *)s;
d += sizeof(int);
s += sizeof(int);
len -= sizeof(int);
}
while (len--)
*d++ = *s++;
return dst;
}

Code like this might be used on x86-style CPUs, where misaligned
moves are permitted, to move four bytes at a time from (int *)src
to (int *)dst. (In practice we might even use "cld", put len>>2
into %ecx, and use a "loop" instruction with lodsl or stosl combined
with regular movl/increment, although such instructions do not
pipeline well in some Intel CPUs.) On average, this code might
copy memory approximately four times faster than the byte-at-a-time
copy in mc0() -- copying 65536 8-bit bytes from buffer A to buffer
B runs the first loop only 16384 times, after which len==0.

But suppose we were to do this:

char buf[N];
buf[0] = 'x';
mc0(buf + 1, buf, N - 1);

In C, the effect of this call is well-defined. Before calling
mc0(), we set buf[0] to 'x'. Then, inside mc0(), the first trip
through the loop copies buf[0] to buf[1], so that it too is 'x';
the next trip copies buf[1] to buf[2], setting it to 'x'; and so
on. We could also write:

buf[0] = 'x';
buf[1] = 'y';
buf[2] = 'z';
mc0(buf + 3, buf, N - 3);

to repeat the sequence "xyz" throughout the buffer.

If we call mc1(), on the other hand, it will read all four bytes
from buf[0] through buf[3] inclusive *before* writing any of the
bytes at buf[1] (in the "set everything to 'x'" case) or buf[3]
(in the "fill with 'xyz' case"). This will fail to fill the buffer
with the desired pattern. That, in turn, means that a C compiler
*must not* automatically generate code like that in mc1() for
function mc0() -- even though, in the usual case, it runs four
times faster. The optimization is incorrect because in mc0(),
s names the same object -- the same "char" in the buf[] array
-- as d[i+1] or d[i+3], for valid values of i. Thus, any write
operation to d[i+1] or d[i+3] must be complete before any read
operation on s.

If we use the new "restrict" qualifier in mc0(), however, a C
compiler is now allowed to assume -- whether it is correct or not
-- that the memory to which the restrict-qualified pointer points
is disjoint from the memory to which any other pointer points. In
other words, we (as C programmers) can now promise to the compiler
that s and d[j] are distinct, no matter which valid values i
and j take. The compiler can then automatically generate the
faster mc1()-style code.

The "restrict" qualifier basically makes the same guarantee that
Fortran makes for *all* its subroutine and function parameters.
This enables all the optimizations the Fortran compiler folks have
come up with over the years. On machines like Crays and Convexes,
such optimizations can make functions run anywhere from three to
300 times faster. This makes them quite desirable, at least to
certain groups of programmers -- but at the same time, qualifying
pointers in this way is rather dangerous, since the programmer can
get it wrong, and in general, the compiler cannot diagnose such
mistakes.

(I happen to think it would be better to use a more limited
declaration, in which one might explicitly declare two pointers or
objects -- including array objects -- as "disjoint". In contrast
with blanket "this pointer points to something I will never access
in *any* other way during this code section" decrees, this is at
least somewhat less likely to be gotten wrong. Moreover, a
sequence like:

void f(int n, double A[n], double B[n], double C[n]) {
_Pragma(disjoint(A, B));
_Pragma(disjoint(A, C));
_Pragma(disjoint(B, C));
...
}

could actually be tested at runtime, so that an incorrect call to
f() would trap into the debugger, rather than blithely producing
"impossible" results.)

 

[Sheldon Simms]

Really!

void *memcpy(void *restrict dest,
const void *restrict src, size_t n) {
// Please show us how you you would know
// when dest and src overlap.
return dest;
}

At this point:

...
mytype1 * dstptr;
mytype2 * srcptr;
size_t copy_size;
...
--> memcpy(dstptr, srcptr, copy_size);
...

 

[gc]

The data pointed to by a pointer declared with the restrict
qualifier may not be pointed to by any other pointer. This
allows for more effective optimization.

Thanks!

Does this mean that code of the following type is disallowed too:

void
test(char * restrict s)
{
char *p=s;/* p points at s*/
..........
}


regards,
gc

 

[Peter Nilsson]

No.

The restrict keyword does *not* provide any extra information
to the compiler.

Yes it does. You say so yourself, below.

It simple allows the programmer to *lie* to the C compiler.

There are many ways to lie to a compiler. Most competent programmers
choose not to, at least not knowingly.

It tells the C compiler to *assume* that
source and destination arrays are disjoint

This is new information to the compiler.

even though there is no way for either the programmer
or the C compiler to ensure that
source and destination arrays do *not* overlap.

There is *always* a way for the programmer to ensure that. Whether a
programmer *cares* to or not is up to them.

And the whole purpose of restrict is give that assurance to the
compiler. In that way, the compiler doesn't *need* to ensure the
condition for itself.