What does 'restrict' mean?

N

Niu Xiao

I see a lot of use in function declarations, such as

size_t fread(void* restrict ptr, size_t size, size_t nobj, FILE*
restrict fp);

but what does the keyword 'restrict' mean? there is no definition found
in K&R 2nd.
 
N

Niu Xiao

Burton said:
I see a lot of use in function declarations, such as

size_t fread(void* restrict ptr, size_t size, size_t nobj, FILE*
restrict fp);

but what does the keyword 'restrict' mean? there is no definition
found in K&R 2nd.


restrict keyword

C99 supports the restrict keyword, which allows for certain
optimizations involving pointers. For example:

void copy(int *restrict d, const int *restrict s, int n)
{
while (n-- > 0)
*d++ = *s++;
}

C++ does not recognize this keyword.

A simple work-around for code that is meant to be compiled as
either C or C++ is to use a macro for the restrict keyword:

#ifdef __cplusplus
#define restrict /* nothing */
#endif

(This feature is likely to be provided as an extension by many
C++ compilers. If it is, it is also likely to be allowed as a
reference modifier as well as a pointer modifier.)

[C99: §6.2.5, 6.4.1, 6.7.3, 6.7.3.1, 7, A.1.2, J.2]
[C++98: §2.11]



from http://david.tribble.com/text/cdiffs.htm#C99-restrict

but what optimizations invoving pointers?
 
R

Richard Bos

Burton Samograd said:
restrict keyword

C99 supports the restrict keyword,

And note that the reason you won't find it in K&R 2 is that that book
covers C(almost-)89, not C99.

Richard
 
P

pete

Niu said:
I see a lot of use in function declarations, such as

size_t fread(void* restrict ptr, size_t size, size_t nobj, FILE*
restrict fp);

but what does the keyword 'restrict' mean?
there is no definition found
in K&R 2nd.

Consider the types of memcpy and memmove:

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

The reason that memcpy has the restrict keyword and memmove doesn't
is because the parameters don't overlap in memcpy,
but they are allowed to, in memmove.

What it means is that in memcpy,
all accesses to the object pointed by s1,
will be made from s1 or pointers derived from s1
and that all accesses to the object pointed to by s2
will be made from s2 or pointers derived from s2.
There may or may not be optimizations available
because of that. Bear in mind that standard library functions
can be written in assembley langauge or any language.

In memmove, because the objects may overlap,
it's possible to be accessing both objects at the same time
with the same pointer.
 
M

Michael Mair

Niu said:
Burton said:
Niu Xiao said:
I see a lot of use in function declarations, such as

size_t fread(void* restrict ptr, size_t size, size_t nobj, FILE*
restrict fp);

but what does the keyword 'restrict' mean? there is no definition
found in K&R 2nd.

restrict keyword
C99 supports the restrict keyword, which allows for certain
optimizations involving pointers. For example:
void copy(int *restrict d, const int *restrict s, int n)
{
while (n-- > 0)
*d++ = *s++;
} C++ does not recognize this keyword.
A simple work-around for code that is meant to be compiled as
either C or C++ is to use a macro for the restrict keyword:
#ifdef __cplusplus
#define restrict /* nothing */
#endif (This feature is likely to be provided as an
extension by many
C++ compilers. If it is, it is also likely to be allowed as a
reference modifier as well as a pointer modifier.)
[C99: §6.2.5, 6.4.1, 6.7.3, 6.7.3.1, 7, A.1.2, J.2]
[C++98: §2.11]
•

from http://david.tribble.com/text/cdiffs.htm#C99-restrict

but what optimizations invoving pointers?

If you know that two pointers do not point to the same object,
then you can leave out some kinds of sanity checks, can change
loops (e.g. make a while (a!=b) loop into a do--while(a != b)
loop), can work directly without intermediate copy.
Think of memcpy() and memmove(). If you had to implement
memmove() portably and had no way of checking whether the source
and destination pointers belong to the same object, you were
not allowed to compare the pointers with < or >, thus you cannot
take care of overlapping objects flexibly. This means that you
have to do something along the lines of

void *MemMove (void *pDest, void *pSrc, size_t size)
{
if (pDest == pSrc) {
return pDest;
}
void *pTemp = malloc(size);
if (pTemp) {
unsigned char * pMDest = pTemp;
unsigned char * pMSrc = pSrc;
for (size_t i = 0; i < size; i++) {
*pMDest++ = *pMSrc++;
}
pMDest = pDest;
pMSrc = pTemp;
for (size_t i = 0; i < size; i++) {
*pMDest++ = *pMSrc++;
}
free(pTemp);
pTemp = pDest;
}
return pTemp;
}

which may be pretty wasteful of memory. For MemCopy(), you
can do

void *MemCopy (void * restrict pDest,
void * restrict pSrc, size_t size)
{
unsigned char * restrict pCDest = pDest;
unsigned char * restrict pCSrc = pSrc;
for (size_t i = 0; i < size; i++) {
*pCDest++ = *pCSrc++;
}
return pDest;
}

That is quite a difference, I'd say.
Now, imagine for a moment we were an optimizing compiler and
would optimize the following function

1)
void *MemFoo (void * restrict pDest,
void * restrict pSrc, size_t size)
{
/* Never true: Can be thrown away */
if (pDest == pSrc) {
return pDest;
}
void *pTemp = malloc(size);
if (pTemp) {
unsigned char * pMDest = pTemp;
unsigned char * pMSrc = pSrc;
/* Loops can be merged if auxiliary variable is introduced */
for (size_t i = 0; i < size; i++) {
*pMDest++ = *pMSrc++;
}
pMDest = pDest;
pMSrc = pTemp;
for (size_t i = 0; i < size; i++) {
*pMDest++ = *pMSrc++;
}
free(pTemp);
pTemp = pDest;
}
return pTemp;
}

2)
void *MemFoo (void * restrict pDest,
void * restrict pSrc, size_t size)
{
void *pTemp = malloc(size);
if (pTemp) {
unsigned char * pMDest = pTemp;
unsigned char * restrict pMSrc = pSrc;
unsigned char * restrict pAux = pDest;
for (size_t i = 0; i < size; i++) {
/* pMDest is only used to change the object pointed to by pTemp */
*pMDest++ = *pMSrc++;
*pAux++ = *pMDest++;
}
/* The object pointed to by pTemp is not used after the redefinition */
free(pTemp);
pTemp = pDest;
}
return pTemp;
}

3)
void *MemFoo (void * restrict pDest,
void * restrict pSrc, size_t size)
{
unsigned char *pTemp = malloc(size);
if (pTemp) {
unsigned char * restrict pMSrc = pSrc;
unsigned char * restrict pAux = pDest;
for (size_t i = 0; i < size; i++) {
*pAux++ = *pMSrc++;
}
/* Code could be rescheduled to sooner free resources */
free(pTemp);
pTemp = pDest;
}
return pTemp;
}

4)
void *MemFoo (void * restrict pDest,
void * restrict pSrc, size_t size)
{
unsigned char *pTemp = malloc(size);
if (pTemp) {
free(pTemp);
pTemp = pDest;
unsigned char * restrict pMSrc = pSrc;
unsigned char * restrict pAux = pDest;
for (size_t i = 0; i < size; i++) {
*pAux++ = *pMSrc++;
}
}
return pTemp;
}

Not the optimum. If we imagine for a moment a compiler that
can do truly wondrous things, then we could eliminate the
calls to malloc() and free() as there is only a use of pTemp
in a Boolean context in between.

5->7)
void *MemFoo (void * restrict pDest,
void * restrict pSrc, size_t size)
{
unsigned char *pTemp;
if (size <= __MAX_MALLOC) {
pTemp = pDest;
unsigned char * restrict pMSrc = pSrc;
unsigned char * restrict pAux = pDest;
for (size_t i = 0; i < size; i++) {
*pAux++ = *pMSrc++;
}
}
else {
pTemp = NULL;
}
return pTemp;
}

where __MAX_MALLOC may be an implementation dependent constant
defining the maximal number of bytes that can be allocated by
one call to malloc().
If __MAX_MALLOC does not exist, we arrive at MemCpy(), otherwise
we arrive at

void *MemFoo (void * restrict pDest,
void * restrict pSrc, size_t size)
{
if (size <= __MAX_MALLOC) {
unsigned char * restrict pMSrc = pSrc;
unsigned char * restrict pAux = pDest;
for (size_t i = 0; i < size; i++) {
*pAux++ = *pMSrc++;
}
return pDest;
}
return NULL;
}

Nice, huh?


Cheers
Michael
 
B

Burton Samograd

Niu Xiao said:
I see a lot of use in function declarations, such as

size_t fread(void* restrict ptr, size_t size, size_t nobj, FILE*
restrict fp);

but what does the keyword 'restrict' mean? there is no definition
found in K&R 2nd.

restrict keyword

C99 supports the restrict keyword, which allows for certain
optimizations involving pointers. For example:

void copy(int *restrict d, const int *restrict s, int n)
{
while (n-- > 0)
*d++ = *s++;
}

C++ does not recognize this keyword.

A simple work-around for code that is meant to be compiled as
either C or C++ is to use a macro for the restrict keyword:

#ifdef __cplusplus
#define restrict /* nothing */
#endif

(This feature is likely to be provided as an extension by many
C++ compilers. If it is, it is also likely to be allowed as a
reference modifier as well as a pointer modifier.)

[C99: §6.2.5, 6.4.1, 6.7.3, 6.7.3.1, 7, A.1.2, J.2]
[C++98: §2.11]

•

from http://david.tribble.com/text/cdiffs.htm#C99-restrict
 
M

Michael Mair

Michael said:
Now, imagine for a moment we were an optimizing compiler and
would optimize the following function

1)
void *MemFoo (void * restrict pDest,
void * restrict pSrc, size_t size)
{
/* Never true: Can be thrown away */
if (pDest == pSrc) {
return pDest;
}
void *pTemp = malloc(size);
if (pTemp) {
unsigned char * pMDest = pTemp;
unsigned char * pMSrc = pSrc;
/* Loops can be merged if auxiliary variable is introduced */
for (size_t i = 0; i < size; i++) {
*pMDest++ = *pMSrc++;
}
pMDest = pDest;
pMSrc = pTemp;
for (size_t i = 0; i < size; i++) {
*pMDest++ = *pMSrc++;
}

Note that this is the crucial step: We only may merge the loops
without further thought if pDest and pSrc are guarantueed to not
point to the same object.
I failed to make this clear originally.
free(pTemp);
pTemp = pDest;
}
return pTemp;
}

Cheers
Michael
 
N

Niu Xiao

Niu said:
I see a lot of use in function declarations, such as

size_t fread(void* restrict ptr, size_t size, size_t nobj, FILE*
restrict fp);

but what does the keyword 'restrict' mean? there is no definition found
in K&R 2nd.


thanks for ur help :)
 
M

Me

Michael said:
void *MemFoo (void * restrict pDest,
void * restrict pSrc, size_t size)
{
/* Never true: Can be thrown away */
if (pDest == pSrc) {
return pDest;
}

I don't think that's true.
 
F

Flash Gordon

pete said:
Do you think it's OK to call memcpy
with the first two arguments being equal?

I don't, since if they are equal the regions obviously overlap so the
behaviour is undefined.
 
M

Me

pete said:
Do you think it's OK to call memcpy
with the first two arguments being equal?

I think it's ok but it ultimately depends on if the committee considers
[p,p+0) and [p,p+0) overlapping or not. If they don't for the same
object then they should at least consider it not overlapping for the
end+1 and beginning of another object that just happens to compare
equal.

In any event, take a look at 6.7.3.1/10 as to why memcpy's semantics
looks irrelevant in this case.
 
C

CBFalconer

pete said:
Do you think it's OK to call memcpy
with the first two arguments being equal?

Doesn't the restrict by itself forbid those arguments from being
equal?

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>
 
M

Michael Mair

Me said:
I don't think that's true.

I forgot to make sure that neither pDest nor pSrc is a null
pointer -- this part should have been excluded beforehand;
if we assume that we know that neither is a null pointer,
then -- if I have understood restrict right -- this means
that pDest cannot be equal to pSrc.
Is this what you are getting at?


Cheers
Michael
 
K

Keith Thompson

CBFalconer said:
Doesn't the restrict by itself forbid those arguments from being
equal?

It doesn't forbid anything. It causes undefined behavior if they
overlap (which includes the case where they're equal) -- which means
the compiler could legally replace "if (pDest == pSrc)" with "if (0)".
 
C

CBFalconer

Keith said:
.... snip ...

It doesn't forbid anything. It causes undefined behavior if they
overlap (which includes the case where they're equal) -- which means
the compiler could legally replace "if (pDest == pSrc)" with "if (0)".

Oh very well. It forbids the programmer, on pain of undefined
behaviour, from supplying equal arguments.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>
 
M

Me

Michael said:
I forgot to make sure that neither pDest nor pSrc is a null
pointer -- this part should have been excluded beforehand;
if we assume that we know that neither is a null pointer,
then -- if I have understood restrict right -- this means
that pDest cannot be equal to pSrc.
Is this what you are getting at?

No, I'm saying that just because a pointer is marked as restrict
doesn't give the compiler any information at all to say if it overlaps
with another object or not. It has to examine the use of the pointer
expressions inside a block to determine this information, hence the
comparison of the pointers in MemFoo cannot be eliminated as is.
Christian Bau's post about restrict is a pretty good approximation to
what the standard says:

http://groups.google.com/group/comp.std.c/msg/7f4409dea7e43736

just be careful when reading it because he uses "const restrict
pointer" to mean "const T * restrict".

http://www.lysator.liu.se/c/restrict.html

Is also a good (outdated) reference. The most important piece of
information to glean from it is 3.9 which describes how return values
and typecasts with restrict are meaningless.


To summarize what's ok and what isn't with just the minimum amount of
information:

void f(int *restrict, int *restrict){}

/* ok */
int a;
f(&a, &a);

/* also ok */
int a;
int *restrict pa = &a;
int *restrict pb = &a;
f(pa, pb);

/* undefined */
int a;
int *restrict pa = &a;
f(pa, pa);
 
R

Richard Bos

Me said:
No, I'm saying that just because a pointer is marked as restrict
doesn't give the compiler any information at all to say if it overlaps
with another object or not.

It gives the compiler no information whether it _does_ overlap, but it
does tell it that it may _assume_ there is no overlap, and hang the
consequences if the programmer bunged the job.
void f(int *restrict, int *restrict){}

/* ok */
int a;
f(&a, &a);

/* also ok */
int a;
int *restrict pa = &a;
int *restrict pb = &a;
f(pa, pb);

Not OK, and not OK, except for the quibble that your function body is
empty (and the declaration incomplete). To quote the Standard:

# In what follows, a pointer expression E is said to be based on object
# P if (at some sequence point in the execution of B prior to the
# evaluation of E)

Note: in the execution _of the block associated with the declaration_.
Not anywhere previously; in the block itself. You cannot use a
restricted pointer if it corresponds to another restricted pointer,
_except_ in cases like this:

int func(int * restrict ptr)
{
int * restrict ptr2 = ptr;
return ptr;
}

That's because the second restricted pointer was based on the first,
_inside_ the block which the restricted declaration belongs to.

Richard
 
M

Michael Mair

Me said:
No, I'm saying that just because a pointer is marked as restrict
doesn't give the compiler any information at all to say if it overlaps
with another object or not. It has to examine the use of the pointer
expressions inside a block to determine this information, hence the
comparison of the pointers in MemFoo cannot be eliminated as is.

I think you are wrong there -- restrict does not say straight
out "does not overlap" but it says the compiler may assume that
the pointers are used like this. I expect a compiler to utilise
this information as if a full alias analysis said "these pointers
never point to overlapping objects". These are the steps I performed
but for the omission of making sure that no null pointers are
involved.
I understand that there are no guarantees for restrict but that
there is a permission to act as if there were such guarantees --
which is quite enough for a compiler.
Christian Bau's post about restrict is a pretty good approximation to
what the standard says:

http://groups.google.com/group/comp.std.c/msg/7f4409dea7e43736

Thanks for the link.
just be careful when reading it because he uses "const restrict
pointer" to mean "const T * restrict".

http://www.lysator.liu.se/c/restrict.html

Is also a good (outdated) reference. The most important piece of
information to glean from it is 3.9 which describes how return values
and typecasts with restrict are meaningless.

Which is consistent.

To summarize what's ok and what isn't with just the minimum amount of
information:

void f(int *restrict, int *restrict){}

/* ok */
int a;
f(&a, &a);

I'd expect at least a warning from a good compiler in this case.

/* also ok */
int a;
int *restrict pa = &a;
int *restrict pb = &a;
f(pa, pb);

The same. The only reason why I see this and the above as safe is
that f()'s body is empty.
/* undefined */
int a;
int *restrict pa = &a;
f(pa, pa);

Here we agree.

I do not know if there are compilers who actually use the
information gleaned from restrict or who even use it aggressively;
I really would welcome a compiler writer's point of view for this
case as it may clarify potential and actual uses as well as less
obvious defects in the specification of restrict.


Cheers
Michael
 

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,484
Members
44,904
Latest member
HealthyVisionsCBDPrice

Latest Threads

Top