restrict

[Andreas Kahari]

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.

 

[Alan Balmer]

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.

 

[E. Robert Tisdale]

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]

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

 

[Mark Gordon]

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.

 

[Christian Bau]

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]

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

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

 

[Tim Prince]

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