Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   Problem with "restrict" (http://www.velocityreviews.com/forums/t958528-problem-with-restrict.html)

diegotorquemada@gmail.com 03-09-2013 11:11 PM

Problem with "restrict"
 
Hello all!

I am trying to learn to use the reserved word restrict. However, it seems that it is not working. The code with and without that keyword have the same size and running time, even though I am inducing pointer aliasing.

Can somebody please check my minimal example?

Thanks and kind regards!

Diego

/*
gcc -std=c99 -O3 -Wall -D USE_RESTRICT -o 08_restrict 08_restrict.c
ls -l
time -p ./08_restrict
*/

#include<stdio.h>
#include<stdlib.h>

#ifdef USE_RESTRICT
#else
#define restrict
#endif

const int N = 100000;

int *restrict x, *restrict y, *restrict z;

void fun(int *restrict a, int *restrict b, int *restrict c, int n);

int main()
{
x = malloc(N * sizeof(int));
y = malloc(N * sizeof(int));
z = malloc(N * sizeof(int));
if (x==NULL || y==NULL || z==NULL)
{
fprintf(stderr, "Error with malloc()!\n");
return EXIT_FAILURE;
}

// run this several times in order to have some average time
for (int i=0; i<10000; i++)
{
for (int j=0; j<N; j++) x[j] = y[j] = z[j] = j;
fun(x, y, z, N);
// fun(x, x, x, N);
}

free(x);
free(y);
free(z);

return EXIT_SUCCESS;
}

void fun(int *restrict a, int *restrict b, int *restrict c, int n)
{
for (int i=n; i<n; i++)
{
// The compiler has to read c in the second line because
// it may happen that either b points to a or c.
b[i] = b[i] + c[i];
a[i] = a[i] + b[i]*c[i];
}

return;
}

Ike Naar 03-09-2013 11:55 PM

Re: Problem with "restrict"
 
On 2013-03-09, diegotorquemada@gmail.com <diegotorquemada@gmail.com> wrote:
> void fun(int *restrict a, int *restrict b, int *restrict c, int n)
> {
> for (int i=n; i<n; i++)


Did you really mean 'i=n' here, or should that be 'i=0' ?
As written, the loop body is never executed because the initial condition
'i==n' implies the termination condition 'i>=n'.

> {
> // The compiler has to read c in the second line because
> // it may happen that either b points to a or c.
> b[i] = b[i] + c[i];
> a[i] = a[i] + b[i]*c[i];
> }
>
> return;


This statement is harmless but redundant.

> }


diegotorquemada@gmail.com 03-10-2013 12:17 AM

Re: Problem with "restrict"
 
On Saturday, March 9, 2013 6:55:52 PM UTC-5, Ike Naar wrote:
> On 2013-03-09, diegotorquemada@gmail.com <diegotorquemada@gmail.com> wrote:
>
> > void fun(int *restrict a, int *restrict b, int *restrict c, int n)

>
> > {

>
> > for (int i=n; i<n; i++)

>
>
>
> Did you really mean 'i=n' here, or should that be 'i=0' ?
>

Ups Ike, I didn't see that mistake. However correcting to i=0, the code still does not work.

> As written, the loop body is never executed because the initial condition
>
> 'i==n' implies the termination condition 'i>=n'.
>
>
>
> > {

>
> > // The compiler has to read c in the second line because

>
> > // it may happen that either b points to a or c.

>
> > b[i] = b[i] + c[i];

>
> > a[i] = a[i] + b[i]*c[i];

>
> > }

>
> >

>
> > return;

>
>
>
> This statement is harmless but redundant.
>
>
>
> > }



Shao Miller 03-10-2013 03:47 AM

Re: Problem with "restrict"
 
On 3/9/2013 18:55, Ike Naar wrote:
> On 2013-03-09, diegotorquemada@gmail.com <diegotorquemada@gmail.com> wrote:
>>
>> return;

>
> This statement is harmless but redundant.
>


It can also be handy as a habit if you ever wish to override 'return'
with a macro, so that something special can happen at each place it
appears... Same with a 'continue' as an entire loop body or just before
the end of a loop body's compound statement.

while (stuff())
continue;

while (stuff())
{
continue;
}

--
- Shao Miller
--
"Thank you for the kind words; those are the kind of words I like to hear.

Cheerily," -- Richard Harter

Joe Pfeiffer 03-10-2013 06:12 AM

Re: Problem with "restrict"
 
diegotorquemada@gmail.com writes:

> void fun(int *restrict a, int *restrict b, int *restrict c, int n)
> {
> for (int i=n; i<n; i++)
> {


I hadn't encountered the restrict keyword before, but my understanding
after a bit of reading is that in using it you are promising that a, b,
and c *won't* point to the same object.

> // The compiler has to read c in the second line because
> // it may happen that either b points to a or c.
> b[i] = b[i] + c[i];
> a[i] = a[i] + b[i]*c[i];
> }
>
> return;
> }



James Kuyper 03-10-2013 01:03 PM

Re: Problem with "restrict"
 
On 03/10/2013 01:12 AM, Joe Pfeiffer wrote:
> diegotorquemada@gmail.com writes:
>
>> void fun(int *restrict a, int *restrict b, int *restrict c, int n)
>> {
>> for (int i=n; i<n; i++)
>> {

>
> I hadn't encountered the restrict keyword before, but my understanding
> after a bit of reading is that in using it you are promising that a, b,
> and c *won't* point to the same object.
>
>> // The compiler has to read c in the second line because
>> // it may happen that either b points to a or c.
>> b[i] = b[i] + c[i];
>> a[i] = a[i] + b[i]*c[i];
>> }
>>
>> return;
>> }


The rules that apply to restrict-qualified pointers are substantially
more complicated, and I could easily construct examples where your
description would be wrong. However, you've got the right basic idea.
The point is, that because 'restrict' makes that promise, it enables a
compiler to optimize the code on the assumption that the promise will
not be broken. This only matters if there is such an optimization
possible. In this case, there is. If c[i] will never refer to the same
object as b[i], then it's value need only be retrieved once per pass
through the loop; without 'restrict', it would have to be retrieved twice.
Note, however, that 'restrict' doesn't mandate performance of such
optimizations, it only allows them.
--
James Kuyper

Tiib 03-10-2013 03:03 PM

Re: Problem with "restrict"
 
On Sunday, 10 March 2013 01:11:30 UTC+2, diegoto...@gmail.com wrote:
> I am trying to learn to use the reserved word restrict. However, it seems
> that it is not working. The code with and without that keyword have the
> same size and running time, even though I am inducing pointer aliasing.


The example does not contain function without restrict.

The function with restrict is equivalent to nop on most optimizing compilers
so the size is ZERO I presume?

There are no code that measures anything. There are no compiler
options in example.

Those few things are usually done wrongly when someone
"measures performance" and gets "seemingly surprising results".
So I bet it is between chair and keyboard what is not working.


88888 Dihedral 03-10-2013 09:36 PM

Re: Problem with "restrict"
 
diegoto...@gmail.com於 2013年3月10日星期日UTC+8上午7時11分30秒 寫道:
> Hello all!
>
>
>
> I am trying to learn to use the reserved word restrict. However, it seemsthat it is not working. The code with and without that keyword have the same size and running time, even though I am inducing pointer aliasing.
>
>
>
> Can somebody please check my minimal example?
>
>
>
> Thanks and kind regards!
>
>
>
> Diego
>
>
>
> /*
>
> gcc -std=c99 -O3 -Wall -D USE_RESTRICT -o 08_restrict 08_restrict.c
>
> ls -l
>
> time -p ./08_restrict
>
> */
>
>
>
> #include<stdio.h>
>
> #include<stdlib.h>
>
>
>
> #ifdef USE_RESTRICT
>
> #else
>
> #define restrict
>
> #endif
>
>
>
> const int N = 100000;
>
>
>
> int *restrict x, *restrict y, *restrict z;
>
>
>
> void fun(int *restrict a, int *restrict b, int *restrict c, int n);
>
>
>
> int main()
>
> {
>
> x = malloc(N * sizeof(int));
>
> y = malloc(N * sizeof(int));
>
> z = malloc(N * sizeof(int));
>
> if (x==NULL || y==NULL || z==NULL)
>
> {
>
> fprintf(stderr, "Error with malloc()!\n");
>
> return EXIT_FAILURE;
>
> }
>
>
>
> // run this several times in order to have some average time
>
> for (int i=0; i<10000; i++)
>
> {
>
> for (int j=0; j<N; j++) x[j] = y[j] = z[j] = j;
>
> fun(x, y, z, N);
>
> // fun(x, x, x, N);
>
> }
>
>
>
> free(x);
>
> free(y);
>
> free(z);
>
>
>
> return EXIT_SUCCESS;
>


//====
If you are programming short scripts , then nothing does matter
in your way of EXITING the real time running conditions.


But if you are programming for a library to be used by others in this
way, then the story might be quite different in your career.



> }
>
>
>
> void fun(int *restrict a, int *restrict b, int *restrict c, int n)
>
> {
>
> for (int i=n; i<n; i++)
>
> {
>
> // The compiler has to read c in the second line because
>
> // it may happen that either b points to a or c.
>
> b[i] = b[i] + c[i];
>
> a[i] = a[i] + b[i]*c[i];
>
> }
>
>
>
> return;
>
> }



Keith Thompson 03-11-2013 05:14 AM

Re: Problem with "restrict"
 
diegotorquemada@gmail.com writes:
> I am trying to learn to use the reserved word restrict. However, it
> seems that it is not working. The code with and without that keyword
> have the same size and running time, even though I am inducing pointer
> aliasing.
>
> Can somebody please check my minimal example?

[snip]

The fact that you get the same code with and without restrict doesn't
mean much.

The use of the "restrict" keyword is a promise (from the programmer
to the compiler) that certain restrictions are not violated.
The compiler is permitted, but not required, to take advantage
of that promise to enable optimizations. An implementation that
ignores "restrict" entirely (other than checking its syntax)
could be conforming. A program that uses "restrict" but violates
the restrictions is in effect lying to the compiler, making the
program's behavior undefined.

The "restrict" keyword can make a program's behavior undefined when it
would be well defined without it. That's pretty much all it does. That
has the side effect of enabling optimizations.

--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Noob 03-11-2013 10:28 AM

Re: Problem with "restrict"
 
diego wrote:

> I am trying to learn to use the reserved word restrict. However, it
> seems that it is not working. The code with and without that keyword
> have the same size and running time, even though I am inducing
> pointer aliasing.


As Robert said, it's best to look at the generated code.

$ cat restrict.c
#ifndef USE_RESTRICT
#define restrict
#endif

void fun(int *restrict a, int *restrict b, int *restrict c)
{
*a = *c;
*b = *c;
}
$ gcc -std=c99 -pedantic -Wall -Wextra -O3 -S restrict.c -o v1.s
$ gcc -std=c99 -pedantic -Wall -Wextra -O3 -S -DUSE_RESTRICT restrict.c -o v2.s

Without restrict:
movl 12(%esp), %eax ; eax <- c
movl 4(%esp), %edx ; edx <- a
movl (%eax), %ecx ; ecx <- *c
movl %ecx, (%edx) ; *a = *c
movl (%eax), %edx ; edx <- *c
movl 8(%esp), %eax ; eax <- b
movl %edx, (%eax) ; *b = *c
ret

NB: *c is loaded twice.

With restrict:
movl 12(%esp), %eax ; eax <- c
movl 4(%esp), %edx ; edx <- a
movl (%eax), %eax ; eax <- *c
movl %eax, (%edx) ; *a = *c
movl 8(%esp), %edx ; edx <- b
movl %eax, (%edx) ; *b = *c
ret

NB: *c is loaded only once.

Regards.



All times are GMT. The time now is 08:59 AM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.