Problem with "restrict"

Discussion in 'C Programming' started by diegotorquemada@gmail.com, Mar 9, 2013.

  1. Guest

    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 = b + c;
    a = a + b*c;
    }

    return;
    }
     
    , Mar 9, 2013
    #1
    1. Advertising

  2. Ike Naar Guest

    On 2013-03-09, <> 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 = b + c;
    > a = a + b*c;
    > }
    >
    > return;


    This statement is harmless but redundant.

    > }
     
    Ike Naar, Mar 9, 2013
    #2
    1. Advertising

  3. Guest

    On Saturday, March 9, 2013 6:55:52 PM UTC-5, Ike Naar wrote:
    > On 2013-03-09, <> 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 = b + c;

    >
    > > a = a + b*c;

    >
    > > }

    >
    > >

    >
    > > return;

    >
    >
    >
    > This statement is harmless but redundant.
    >
    >
    >
    > > }
     
    , Mar 10, 2013
    #3
  4. Shao Miller Guest

    On 3/9/2013 18:55, Ike Naar wrote:
    > On 2013-03-09, <> 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
     
    Shao Miller, Mar 10, 2013
    #4
  5. Joe Pfeiffer Guest

    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 = b + c;
    > a = a + b*c;
    > }
    >
    > return;
    > }
     
    Joe Pfeiffer, Mar 10, 2013
    #5
  6. James Kuyper Guest

    On 03/10/2013 01:12 AM, Joe Pfeiffer wrote:
    > 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 = b + c;
    >> a = a + b*c;
    >> }
    >>
    >> 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 will never refer to the same
    object as b, 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
     
    James Kuyper, Mar 10, 2013
    #6
  7. Öö Tiib Guest

    On Sunday, 10 March 2013 01:11:30 UTC+2, 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.
     
    Öö Tiib, Mar 10, 2013
    #7
  8. æ–¼ 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 = b + c;
    >
    > a = a + b*c;
    >
    > }
    >
    >
    >
    > return;
    >
    > }
     
    88888 Dihedral, Mar 10, 2013
    #8
  9. 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) <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"
     
    Keith Thompson, Mar 11, 2013
    #9
  10. Noob Guest

    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.
     
    Noob, Mar 11, 2013
    #10
  11. In article <>,
    David Brown <> wrote:
    >
    >That's the "problem" here. The compiler knows that "malloc" returns
    >non-overlapping memory areas (unless it returns 0), and because it has
    >the definition of "fun" on hand it can put two and two together and see
    >that there are no possible overlaps between the arrays, and thus
    >generate better code using that assumption.
    >
    >Try putting the definition of "fun" in an external C file and compiling
    >the two files separately.


    Since fun() is a global, the compiler can't assume that main() is the only
    thing that ever calls it, so I don't think the compiler can make that
    particular assumption/optimization.

    At this point, I can only assume either that the compiler isn't making
    an optimization w.r.t. c that it could be making, or that the
    optimization isn't making enough of a difference time-wise to be
    detectable to OP.

    We really need to see the generated code at this point to be sure.

    --
    -Ed Falk,
    http://thespamdiaries.blogspot.com/
     
    Edward A. Falk, Mar 11, 2013
    #11
  12. In article <>,
    David Brown <> wrote:
    >
    >"fun" is not a nop. The compiler may, however, figure out that the
    >entire code ("main" and "fun") does nothing.


    D'oh! Of course. I'll bet the entire outer loop was optimized
    out of existance. If the compiler knows that fun() has no
    side effects, it could do that.

    OP, try adding a function call at the end of main() that
    references your inputs. That would force the compiler to
    keep the outer loop.

    --
    -Ed Falk,
    http://thespamdiaries.blogspot.com/
     
    Edward A. Falk, Mar 11, 2013
    #12
  13. James Kuyper Guest

    On 03/11/2013 12:20 PM, David Brown wrote:
    ....
    > The compiler may still make some assumptions and optimisations here.
    > First, if the compiler knows that the function cannot be accessed
    > externally, then it can be treated as "static". ...


    In the context of function definitions, "static" means "cannot be
    accessed externally (by name)" (a pointer to a function with internal
    linkage can be passed to code in a different translation unit, and
    dereferenced there, which is the reason for the "by name" exception). If
    a function is not actually static, it can be accessed externally, so it
    seems to me that your exception would never apply. Could you give an
    example of a context where it would?

    > ... I don't know the
    > details of Linux compilation here (most of my work is embedded systems),
    > but if there is no way for anything to access the "fun" function as a
    > sort of shared library, then since the compiler knows it is generating
    > an executable rather than a linkable object file, it could make that
    > assumption and then do the alias analysis.


    If some aspects of code generation are delayed until link time, the
    linker can know that a function with external linkage is only used in
    contexts that enable that optimization. Otherwise, I don't see any way
    for that to work.

    A function which doesn't have any objects with static storage duration,
    and which doesn't access any global variables can be in-lined, whether
    or not it's declared inline, and such optimizations could be performed
    on the in-lined version. But unless the function has internal linkage,
    there must also be an external definition, for which such optimization
    cannot be performed until all translation units that make up the program
    have been processed and are being linked together.
     
    James Kuyper, Mar 11, 2013
    #13
  14. James Kuyper Guest

    On 03/13/2013 05:08 AM, christian.bau wrote:
    > On Mar 11, 10:28�am, Noob <r...@127.0.0.1> wrote:
    >
    >> 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.

    >
    > In this case, the compiler could have optimised the second load away,
    > even without restrict. Even if a and c are the same pointer, it makes
    > no difference whether the same value is reloaded or not. If you used
    > non-aligned pointer so writing to *a changes some bytes of *c, then
    > you have undefined behaviour.


    a, b, and c all have the type int*, and therefore must all be correctly
    aligned for an int. Where do unaligned pointers enter into this?

    Diego's original code sets b to a different value than c, so if
    b==c, it makes a big difference whether c is retrieved a second time
    for it's second usage (as required without 'restrict') or only once (as
    allowed by the use of 'restrict'). Noob's simplified version not only
    reorders the assignments, so that it's now an issue whether a==c, rather
    than b==c; he also simplified it by setting *a to the same value as *c.
    As a result, it doesn't make any difference whether a==c, thereby
    missing the whole point of Diego's code.
    --
    James Kuyper
     
    James Kuyper, Mar 13, 2013
    #14
  15. Noob Guest

    James Kuyper wrote:

    > As a result, it doesn't make any difference whether a==c,
    > thereby missing the whole point of Diego's code.


    I most certainly DID NOT "miss the whole point of Diego's code"
    as you so undiplomatically put it.

    I was just trying to illustrate the effect of the restrict
    keyword, using as simple an example as possible. Obviously,
    I over-simplified.
     
    Noob, Mar 13, 2013
    #15
  16. James Kuyper Guest

    On 03/13/2013 10:21 AM, Noob wrote:
    > James Kuyper wrote:
    >
    >> As a result, it doesn't make any difference whether a==c,
    >> thereby missing the whole point of Diego's code.

    >
    > I most certainly DID NOT "miss the whole point of Diego's code"
    > as you so undiplomatically put it.
    >
    > I was just trying to illustrate the effect of the restrict
    > keyword, using as simple an example as possible. Obviously,
    > I over-simplified.


    Illustrating the effect of the restrict keyword requires writing code
    where it makes a difference whether or not 'restrict' is present. What I
    so undiplomatically pointed out was the fact that you over-simplified
    the code because you missed the importance of one feature of the
    original code that was necessary in order to make 'restrict' relevant.

    If you can suggest a more diplomatic way I could have used to describe
    the problem, I'm willing to learn. However, it seems to me that any
    annoyance I caused you was inherent in what I was saying; nothing I
    could do to sugar-coat my description of the problem would change that.
     
    James Kuyper, Mar 13, 2013
    #16
  17. Noob Guest

    James Kuyper wrote:
    > On 03/13/2013 10:21 AM, Noob wrote:
    >> James Kuyper wrote:
    >>
    >>> As a result, it doesn't make any difference whether a==c,
    >>> thereby missing the whole point of Diego's code.

    >>
    >> I most certainly DID NOT "miss the whole point of Diego's code"
    >> as you so undiplomatically put it.
    >>
    >> I was just trying to illustrate the effect of the restrict
    >> keyword, using as simple an example as possible. Obviously,
    >> I over-simplified.

    >
    > Illustrating the effect of the restrict keyword requires writing code
    > where it makes a difference whether or not 'restrict' is present.


    Please note that the presence/absence of 'restrict' in my
    (admittedly over-simplified) example did make a difference,
    as far as gcc-4.6.3 -O3 was concerned.

    But thanks to you and Christian for pointing out that an
    aggressively optimizing compiler may determine that after
    *a = *c, *a and *c must have the same contents, therefore
    it is not necessary to reload *c.

    In hindsight, I should have commented on

    void fun(int *restrict a, int *restrict b, int *restrict c)
    {
    *a = *c+1;
    *b = *c+1;
    }
     
    Noob, Mar 13, 2013
    #17
  18. Guest

    On Saturday, March 9, 2013 6:11:30 PM UTC-5, wrote:
    > 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
    >
    >
    >


    Probably my example was not the best because, from the discussion I deduce that the compiler was "clever" enough to find the pointer alignment I was inducing in the code.

    Does somebody has any other example with the restrict keyword that could be helpful in order to see the power of that reserved word?

    Thanks,

    Diego
     
    , Mar 13, 2013
    #18
  19. Shao Miller Guest

    On 3/13/2013 14:41, wrote:
    >
    > Probably my example was not the best because, from the discussion I deduce that the compiler was "clever" enough to find the pointer alignment I was inducing in the code.
    >
    > Does somebody has any other example with the restrict keyword that could be helpful in order to see the power of that reserved word?
    >


    Maybe have a read of this:

    http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1520.htm

    With particular attention to the examples.

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

    Cheerily," -- Richard Harter
     
    Shao Miller, Mar 13, 2013
    #19
  20. In article <>,
    christian.bau <> wrote:
    >On Mar 11, 3:23 pm, (Edward A. Falk) wrote:
    >
    >> Since fun() is a global, the compiler can't assume that main() is the only
    >> thing that ever calls it, so I don't think the compiler can make that
    >> particular assumption/optimization.

    >
    >The compiler can make an inlined copy of fun () and optimize that.


    Hmmm; very good point. (I've often wondered what the compiler
    does with an "inline" function that isn't declared static.)

    That brings back to the same conclusion: we need to see the
    generated code.

    Obviously, this is all an exercise in pedantry anyway; knowing
    what one compiler did in one particular case doesn't really
    teach us much about programming in C.

    --
    -Ed Falk,
    http://thespamdiaries.blogspot.com/
     
    Edward A. Falk, Mar 14, 2013
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Prasad
    Replies:
    1
    Views:
    645
    Kelly Leahy
    Jan 16, 2004
  2. Paras Wadehra
    Replies:
    1
    Views:
    1,843
    =?Utf-8?B?U2F1cmFiaCBOYW5kdQ==?=
    Aug 15, 2004
  3. Lawrance
    Replies:
    1
    Views:
    388
    Bhaskardeep Khaund
    Nov 30, 2003
  4. Replies:
    0
    Views:
    796
  5. Paul

    Restrict Access Problem

    Paul, Apr 6, 2005, in forum: ASP General
    Replies:
    3
    Views:
    284
    Christopher Williams
    Apr 6, 2005
Loading...

Share This Page