restrict

[gc]

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

[Andreas Kahari]

In article <79*************************@posting.google.com> , gc wrote:

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.

--
Andreas Kähäri |
| Make it idiot proof, and someone will wrap it
| in a dysfunctional GUI.

[E. Robert Tisdale]

Andreas Kahari wrote:

gc wrote:

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.

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);

[Andreas Kahari]

In article <3F************@jpl.nasa.gov>, E. Robert Tisdale wrote:

Andreas Kahari wrote:

gc wrote:

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/...ns/memcpy.html

--
Andreas Kähäri |
| Make it idiot proof, and someone will wrap it
| in a dysfunctional GUI.

[E. Robert Tisdale]

Andreas Kahari wrote:

E. Robert Tisdale wrote:

Andreas Kahari wrote:

gc wrote:

What is the purpose of the restrict keyword?

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:

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/...ns/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?"

[j]

"E. Robert Tisdale" <E.**************@jpl.nasa.gov> wrote in message
news:3F**************@jpl.nasa.gov...

Andreas Kahari wrote:

E. Robert Tisdale wrote:

Andreas Kahari wrote:

gc wrote:

>What is the purpose of the restrict keyword?

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:

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/...ns/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?"

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.

[Serve La]

"E. Robert Tisdale" <E.**************@jpl.nasa.gov> wrote in message
news:3F**************@jpl.nasa.gov...

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.

[Mark Gordon]

On Wed, 01 Oct 2003 12:47:43 -0700
"E. Robert Tisdale" <E.**************@jpl.nasa.gov> wrote:

Andreas Kahari wrote:

E. Robert Tisdale wrote:

Andreas Kahari wrote:

gc wrote:

>What is the purpose of the restrict keyword?

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:

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/...ns/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?"

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.
--
Mark Gordon
Paid to be a Geek & a Senior Software Developer
Although my email address says spamtrap, it is real and I read it.

[E. Robert Tisdale]

Mark Gordon wrote:

E. Robert Tisdale wrote:

Andreas Kahari wrote:

E. Robert Tisdale wrote:

Andreas Kahari wrote:

>gc wrote:
>
>>What is the purpose of the restrict keyword?
>
>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:

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/...ns/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?"

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]

On Wed, 1 Oct 2003, E. Robert Tisdale wrote:

Mark Gordon wrote:

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]

On Wed, 01 Oct 2003 12:47:43 -0700, "E. Robert Tisdale"
<E.**************@jpl.nasa.gov> wrote in comp.lang.c:

Andreas Kahari wrote:

E. Robert Tisdale wrote:

Andreas Kahari wrote:

gc wrote:

>What is the purpose of the restrict keyword?

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:
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/...ns/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?"

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]

Jack Klein <ja*******@spamcop.net> writes:

On Wed, 01 Oct 2003 12:47:43 -0700, "E. Robert Tisdale"
<E.**************@jpl.nasa.gov> wrote in comp.lang.c:

[...]

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.

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.)

--
Keith Thompson (The_Other_Keith) ks*@cts.com <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://www.sdsc.edu/~kst>
Schroedinger does Shakespeare: "To be *and* not to be"

[Jeremy Yallop]

E. Robert Tisdale wrote:

Andreas Kahari wrote:

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]

Jeremy Yallop wrote:

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]

On Thu, 02 Oct 2003 15:21:15 -0700, "E. Robert Tisdale"
<E.**************@jpl.nasa.gov> wrote:

Jeremy Yallop wrote:

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.

?

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.

--
Al Balmer
Balmer Consulting
re************************@att.net

[E. Robert Tisdale]

Alan Balmer wrote:

E. Robert Tisdale wrote:

Jeremy Yallop wrote:

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.

?

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[i] 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[i].

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[i] 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.)
--
In-Real-Life: Chris Torek, Wind River Systems (BSD engineering)
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) [phone]
email: forget about it http://67.40.109.61/torek/index.html (for the moment)
Reading email is like searching for food in the garbage, thanks to spammers.

[Sheldon Simms]

On Thu, 02 Oct 2003 16:29:50 -0700, E. Robert Tisdale wrote:

Alan Balmer wrote:

E. Robert Tisdale wrote:

Jeremy Yallop wrote:

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.

?

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;
}

At this point:

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

[gc]

Andreas Kahari <ak*******@freeshell.org> wrote in message

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]

"E. Robert Tisdale" <E.**************@jpl.nasa.gov> wrote in message news:<3F**************@jpl.nasa.gov>...

Jeremy Yallop wrote:

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.

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.

--
Peter

[Andreas Kahari]

In article <79**************************@posting.google.com >, gc wrote:
[cut]

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

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

That is, as far as I understand, not allowed.
--
Andreas Kähäri

[Alan Balmer]

On Thu, 02 Oct 2003 16:29:50 -0700, "E. Robert Tisdale"
<E.**************@jpl.nasa.gov> wrote:

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;
}

I'm not implementing memcpy - that's been done.

When I write

#define BUFSIZE 40

char a[BUFSIZE];
char b[BUFSIZE];
....
memcpy(a, b, BUFSIZE);

I'm reasonably sure the buffers don't overlap.

Perhaps you didn't write what you actually meant, or perhaps I
misread. If the latter, my apologies.

--
Al Balmer
Balmer Consulting
re************************@att.net

[E. Robert Tisdale]

Alan Balmer wrote:

I'm not implementing memcpy - that's been done.

When I write

#define BUFSIZE 40

char a[BUFSIZE];
char b[BUFSIZE];
...
memcpy(a, b, BUFSIZE);

I'm reasonably sure the buffers don't overlap.

Perhaps you didn't write what you actually meant,
or perhaps I misread. If the latter, my apologies.

Notice that the restrict keyword appears nowhere
in the example that you provided.
We have already established that,
int the context of the calling program,
the restrict keyword serves no purpose
except, perhaps, documentation.
The memcpy function could be implemented
in assembler or even Fortran 77 for all we know.

Suppose, instead, that someone modifies your code:

#define BUFSIZE 40

char c[BUFFSIZE + 20];
for (int j = 0; j < BUFFSIZE + 20; ++j)
c[j] = j;
char* a = c + 20;
char* b = c;
. . .
memcpy(a, b, BUFSIZE);

Would you expect your C compiler [or lint] to detect this bug
and issue an appropriate diagnostic message?

[Alan Balmer]

On Fri, 03 Oct 2003 09:50:45 -0700, "E. Robert Tisdale"
<E.**************@jpl.nasa.gov> wrote:

Suppose, instead, that someone modifies your code:

#define BUFSIZE 40

char c[BUFFSIZE + 20];
for (int j = 0; j < BUFFSIZE + 20; ++j)
c[j] = j;
char* a = c + 20;
char* b = c;
. . .
memcpy(a, b, BUFSIZE);

Would you expect your C compiler [or lint] to detect this bug
and issue an appropriate diagnostic message?
No, but I would expect any competent C programmer to recognize it.

Note, once again, that I was only responding to your claim that
there is no way for either the programmer
or the C compiler to ensure that
source and destination arrays do *not* overlap.

--
Al Balmer
Balmer Consulting
re************************@att.net

[Mark Gordon]

On Wed, 01 Oct 2003 15:37:06 -0700
"E. Robert Tisdale" <E.**************@jpl.nasa.gov> wrote:

Mark Gordon wrote:

E. Robert Tisdale wrote:

Andreas Kahari wrote:
<snip>
"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 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)

Well written as always. The maximum value for size_t may be greater than
INT_MAX (and is on some real systems) giving the potential for signed
overflow which is definitely not what you want.
((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;
}
Yes.
Someone else posted one possible optimisation that would only be valid
when restrict is used.
Further, you appear to be saying that
the appearance of the restrict keyword in the
declaration of memcpy (what you call the prototype)
I see lots of mention of prototypes in the standard.
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.

No. I stated three useful purposes the directives serves and you even
quoted them. Admittedly two of them were merely things it *allows* the
implementation to do, not things it requires it to do. However, they are
still useful since it *allows* for the writing of better
implementations.
--
Mark Gordon
Paid to be a Geek & a Senior Software Developer
Although my email address says spamtrap, it is real and I read it.

[Christian Bau]

In article <79**************************@posting.google.com >,
gu**********@yahoo.com (gc) wrote:

Andreas Kahari <ak*******@freeshell.org> wrote in message

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*/
..........
}

No, that is absolutely fine. The pointer assignement is fine anyway, but
also accessing through p is fine.

Remember that most of the time you wouldn't access data through the
pointer s anyway. For example, you might write

s [2] = s [1];

The two pointers used are s+2 and s+1. None of the pointers used is s.
What the C Standard does to handle this: It defines that a pointer can
be "based on s". It roughly means that a pointer value has been created
by a calculation starting with s. In your example, p is clearly "based
on" s.

You are allowed to access data through a pointer "based on s" just as
well as through the pointer s itself. What an optimising compiler will
do is this: It will divide pointers into three classes:

1. The pointer s and pointers based on s.
2. Pointers that are not based on s.
3. Pointers where the compiler doesn't know for sure whether or not
they are based on s.

If pointers are in classes (1) or (2) then optimisations are possible.
For pointers in class (3), restrict doesn't help with optimisations. But
it happens quite often that a compiler definitely knows that p is based
on s or that p is not based on s.

Example:

extern int* f (int* p);

void test (char* restrict s, char* t) {
char* p = s + rand ();
*s = 0;
p = f (s);
*s = 0;
}

t is _not_ based on s. Even if you have a pointer x and call test (x,
x), t is not based on s. After the first assignment, p is based on s.
After the second assignment, the compiler will not know whether or not p
is based on s or not because it doesn't know what the function s does.

So after the first assignment *s = 0; the compiler knows it is possible
that this assignment has changed *p, it is impossible that it has
changed *t. After the second assignment, the compiler doesn't know
anything about *p.

[Daniel Vallstrom]

Chris Torek <no****@elf.eng.bsdi.com> wrote in message news:<bl**********@elf.eng.bsdi.com>...

[snip (an, as usual nice, explanation of restrict)]

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.

What is the current state of compilers when it comes to 'restrict'?
Which compilers actually use it? How much does restrict help current
compiler optimizations? Since the basic situation is the same as the
Fortran case, one would expect that the C compiler writers fairly
easily should be able to incorporate roughly the same optimizations
as in the Fortran case? Is this happening?
Daniel Vallstrom

[Chris Torek]

In article <17**************************@posting.google.com >
Daniel Vallstrom <Da**************@safelogic.se> writes:

What is the current state of compilers when it comes to 'restrict'?
Which compilers actually use it?

I do not know of any that actually use it, but this is more from
not knowing anything about the latest versions of any C compilers,
other than some stuff around the edges of gcc 3.x (just what was
needed to port the existing i386 and PowerPC code generators to
BSD/OS 5.x).
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) [phone]
email: forget about it http://67.40.109.61/torek/index.html (for the moment)
Reading email is like searching for food in the garbage, thanks to spammers.

[Tim Prince]

Daniel Vallstrom wrote:

Chris Torek <no****@elf.eng.bsdi.com> wrote in message
news:<bl**********@elf.eng.bsdi.com>...

[snip (an, as usual nice, explanation of restrict)]

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.

What is the current state of compilers when it comes to 'restrict'?
Which compilers actually use it? How much does restrict help current
compiler optimizations? Since the basic situation is the same as the
Fortran case, one would expect that the C compiler writers fairly
easily should be able to incorporate roughly the same optimizations
as in the Fortran case? Is this happening?
Daniel Vallstrom

Intel C implements restrict. The keyword is ignored by default; there is a
compile command line option to activate it. Likewise, there is an option to
activate optimizations based on assuming code obeys the typed aliasing
rules. It's still quite a bit more work to optimize and test C code.
--
Tim Prince