restrict keyword from ISO C99?

Discussion in 'C Programming' started by tweak, Jun 19, 2004.

  1. tweak

    tweak Guest

    Can someone give me a short example as how to best use this keyword in
    your code?

    This is my understanding: by definition restrict sounds like it is
    suppose to restrict access to memory location(s) pointed to, so that
    only one declared pointer can store that address and access the data in
    those memory blocks, where I the data in those location(s) can be changed.

    Is that a correct understanding?

    Thanks,

    Brian

    P.S. I'm slowly making my way through the ISO C99 standard.
     
    tweak, Jun 19, 2004
    #1
    1. Advertising

  2. tweak wrote:

    > Can someone give me a short example
    > as how to best use this keyword in your code?


    #include <string.h>

    void *memcpy(void *restrict dest,
    const void *restrict src, size_t n);

    > This is my understanding: by definition restrict sounds like
    > it is suppose to restrict access to memory location(s) pointed to,
    > so that only one declared pointer
    > can store that address and access the data in those memory blocks,
    > where I the data in those location(s) can be changed.
    >
    > Is that a correct understanding?


    Probably not.

    The restrict keyword is a promise by the programmer to the compiler
    that the destination [dest] array is *not* an alias
    for any part of the source [src] array -- they don't overlap.
    But there is, in general, no way for the compiler to determine
    whether they are actually aliases or not so the programmer can lie.
    The behavior is *undefined*
    if copying takes place between objects that overlap.
     
    E. Robert Tisdale, Jun 19, 2004
    #2
    1. Advertising

  3. tweak

    Tim Prince Guest

    "tweak" <> wrote in message
    news:bdMAc.730$DQ4.264@fed1read05...
    > Can someone give me a short example as how to best use this keyword in
    > your code?
    >
    > This is my understanding: by definition restrict sounds like it is
    > suppose to restrict access to memory location(s) pointed to, so that
    > only one declared pointer can store that address and access the data in
    > those memory blocks, where I the data in those location(s) can be changed.
    >
    > Is that a correct understanding?

    Partly. When you use the keyword, you take responsibility for the pointers
    not interfering with each other, and tell the compiler not to skip any
    optimizations you request which might lead to changes in the order of memory
    access.

    int func(float * restrict a, float * restrict b, int n){
    for(int i=0; i < n; ++i)a += b;
    }

    You tell the compiler not to be concerned that b[] may be changed as a
    result of storing into a[], so it is OK to read as far ahead in a[] and b[]
    as might be needed to generate fast code. Without restrict, it would not be
    OK for the compiler to use parallel instructions, for example. With
    restrict, you rule out cases such as a happening to be equal to b+1, in
    which case each result feeds into the next operation. Should you compile
    this with restrict, and then violate the pledge you made, the results are
    undefined.
    You may be having difficulty distinguishing this from the implications of
    const. const merely tells the compiler to stop you from modifying
    explicitly an object which you said would not be modified. It doesn't tell
    the compiler to perform optimizations on that account, nor would it prevent
    you from running this example with a == b+1. I found it difficult to sort
    these out myself.
    restrict seems to be a parting of the ways which distinguishes C99 from C89
    and C++. No more "C/C++"
     
    Tim Prince, Jun 19, 2004
    #3
  4. tweak

    tweak Guest

    E. Robert Tisdale wrote:
    > tweak wrote:
    >
    >> Can someone give me a short example as how to best use this keyword in
    >> your code?

    >
    >
    > #include <string.h>
    >
    > void *memcpy(void *restrict dest,
    > const void *restrict src, size_t n);
    >
    >> This is my understanding: by definition restrict sounds like
    >> it is suppose to restrict access to memory location(s) pointed to,
    >> so that only one declared pointer
    >> can store that address and access the data in those memory blocks,
    >> where I the data in those location(s) can be changed.
    >>
    >> Is that a correct understanding?

    >
    >
    > Probably not.
    >
    > The restrict keyword is a promise by the programmer to the compiler
    > that the destination [dest] array is *not* an alias
    > for any part of the source [src] array -- they don't overlap.
    > But there is, in general, no way for the compiler to determine
    > whether they are actually aliases or not so the programmer can lie.
    > The behavior is *undefined*
    > if copying takes place between objects that overlap.


    For clarity:

    aliases == variables?
    objects == memory locations (&) ?

    So if an array with four elements (e.g. char name[4]) occupied 0x01
    through 0x05, where 0x05 is '\0', and another array with four elements
    (e.g. char fullname[4]) occupied 0x04 through 0x08, where 0x08 is '\0',
    then overlap would occur. And the restrict keyword specifies that the
    programmer promises to keep the overlapping from occurring, but the
    compiler cannot confirm? Is this a better understanding?

    Thanks,

    Brian
     
    tweak, Jun 19, 2004
    #4
  5. tweak

    tweak Guest

    Tim Prince wrote:
    > "tweak" <> wrote in message
    > news:bdMAc.730$DQ4.264@fed1read05...
    >
    >>Can someone give me a short example as how to best use this keyword in
    >>your code?
    >>
    >>This is my understanding: by definition restrict sounds like it is
    >>suppose to restrict access to memory location(s) pointed to, so that
    >>only one declared pointer can store that address and access the data in
    >>those memory blocks, where I the data in those location(s) can be changed.
    >>
    >>Is that a correct understanding?

    >
    > Partly. When you use the keyword, you take responsibility for the pointers
    > not interfering with each other, and tell the compiler not to skip any
    > optimizations you request which might lead to changes in the order of memory
    > access.
    >
    > int func(float * restrict a, float * restrict b, int n){
    > for(int i=0; i < n; ++i)a += b;
    > }
    >
    > You tell the compiler not to be concerned that b[] may be changed as a
    > result of storing into a[], so it is OK to read as far ahead in a[] and b[]
    > as might be needed to generate fast code. Without restrict, it would not be
    > OK for the compiler to use parallel instructions, for example. With
    > restrict, you rule out cases such as a happening to be equal to b+1, in
    > which case each result feeds into the next operation. Should you compile
    > this with restrict, and then violate the pledge you made, the results are
    > undefined.
    > You may be having difficulty distinguishing this from the implications of
    > const. const merely tells the compiler to stop you from modifying
    > explicitly an object which you said would not be modified. It doesn't tell
    > the compiler to perform optimizations on that account, nor would it prevent
    > you from running this example with a == b+1. I found it difficult to sort
    > these out myself.
    > restrict seems to be a parting of the ways which distinguishes C99 from C89
    > and C++. No more "C/C++"
    >
    >

    So the programmer takes the responsibility to manage the modifyable
    pointers, allowing the compiler to generate faster machine code. But
    because the compiler cannot confirm the programmer did not break his
    promise, there is a possibility of undefined behavior should the
    programmer break his promise. And the result is better machine code,
    so if I disassemble after compiling with optimizations on, I should see
    better assembly code, right?

    And in your example of a == b+1, you have performed pointer math on b
    that you had promised that you would not perform? Is the promise made
    on the memory locations, what's contained in those locations, or both?

    Thanks,

    Brian
     
    tweak, Jun 19, 2004
    #5
  6. tweak

    Tim Prince Guest

    "tweak" <> wrote in message
    news:%HOAc.740$DQ4.283@fed1read05...
    > Tim Prince wrote:
    > > "tweak" <> wrote in message
    > > news:bdMAc.730$DQ4.264@fed1read05...
    > >
    > >>Can someone give me a short example as how to best use this keyword in
    > >>your code?
    > >>
    > >>This is my understanding: by definition restrict sounds like it is
    > >>suppose to restrict access to memory location(s) pointed to, so that
    > >>only one declared pointer can store that address and access the data in
    > >>those memory blocks, where I the data in those location(s) can be

    changed.
    > >>
    > >>Is that a correct understanding?

    > >
    > > Partly. When you use the keyword, you take responsibility for the

    pointers
    > > not interfering with each other, and tell the compiler not to skip any
    > > optimizations you request which might lead to changes in the order of

    memory
    > > access.
    > >
    > > int func(float * restrict a, float * restrict b, int n){
    > > for(int i=0; i < n; ++i)a += b;
    > > }
    > >
    > > You tell the compiler not to be concerned that b[] may be changed as a
    > > result of storing into a[], so it is OK to read as far ahead in a[] and

    b[]
    > > as might be needed to generate fast code. Without restrict, it would

    not be
    > > OK for the compiler to use parallel instructions, for example. With
    > > restrict, you rule out cases such as a happening to be equal to b+1, in
    > > which case each result feeds into the next operation. Should you

    compile
    > > this with restrict, and then violate the pledge you made, the results

    are
    > > undefined.
    > > You may be having difficulty distinguishing this from the implications

    of
    > > const. const merely tells the compiler to stop you from modifying
    > > explicitly an object which you said would not be modified. It doesn't

    tell
    > > the compiler to perform optimizations on that account, nor would it

    prevent
    > > you from running this example with a == b+1. I found it difficult to

    sort
    > > these out myself.
    > > restrict seems to be a parting of the ways which distinguishes C99 from

    C89
    > > and C++. No more "C/C++"
    > >
    > >

    > So the programmer takes the responsibility to manage the modifyable
    > pointers, allowing the compiler to generate faster machine code. But
    > because the compiler cannot confirm the programmer did not break his
    > promise, there is a possibility of undefined behavior should the
    > programmer break his promise. And the result is better machine code,
    > so if I disassemble after compiling with optimizations on, I should see
    > better assembly code, right?

    You have no guarantee of "better" code, but if you use a "vectorizing" or
    pipelining compiler, it should not perform those optimizations without at
    least one of the restricts, or alternatively some option which gives more
    freedom than C allows.
    >
    > And in your example of a == b+1, you have performed pointer math on b
    > that you had promised that you would not perform? Is the promise made
    > on the memory locations, what's contained in those locations, or both?
    >

    It doesn't matter if you violate the restrict to the extent of having
    overlapping read-only ranges of memory locations. What matters is that one
    pointer isn't used to modify data pointed to by another. Strictly, of
    course, you are promising no overlap in memory ranges. It's probably better
    to stick to that from a maintainability point of view, in case you started
    modifying the target of a pointer, and forgot that it overlapped the target
    of another.
     
    Tim Prince, Jun 19, 2004
    #6
  7. In article <bdMAc.730$DQ4.264@fed1read05>, tweak <>
    wrote:

    > Can someone give me a short example as how to best use this keyword in
    > your code?
    >
    > This is my understanding: by definition restrict sounds like it is
    > suppose to restrict access to memory location(s) pointed to, so that
    > only one declared pointer can store that address and access the data in
    > those memory blocks, where I the data in those location(s) can be changed.
    >
    > Is that a correct understanding?


    Two examples why restrict is useful:

    int calc_area (int* width, int* height) {
    *width = 5;
    *height = 6;
    return (*width) * (*height);
    }

    int f (const int* p, int* q) {
    int x = *p;
    *q = x + 1;
    return *p;
    }

    In the first function, you would assume that the function returns 30, so
    an optimising compiler can avoid reading *width and *height and
    multiplying these values. Sadly, this is wrong. If I write

    int x;
    int a = calc_area (&x, &x);

    the result is 36, not 30. An optimising compiler is forced to store 5
    into *width, then store 6 into *height, then read *width, then multiply
    that value by 6 and return the result.

    In the second function, you would assume that the value returned is
    always equal to x. Sadly, this is wrong, too. If I write

    int x = 5;
    int a = f (&x, &x);

    then x will be changed to 6, and the value returned is six, not five.
    "const int* p" only means that you cannot store to the object *p through
    the pointer *p itself, but the same object can be modified by other
    means - for example by storing to *q.

    In both functions, the compiler is forced to produce slow code, to
    handle situations that will never arise in practice. That is what
    "restrict" is for.

    If you declare a restrict pointer object, like

    int* restrict p;

    then all pointer values from then on fall into two categories: Pointer
    values that are derived from p, and pointer values that are not derived
    from p. Roughly speaking, pointer values derived from p are pointer
    values that are calculated by starting with p, and adding or subtracting
    to it in arbitrary complicated way. For example,

    int a [100];
    int* restrict p = &a [0];
    int* q = p + 1;
    int* r = q - 1;
    int* s = &a [0];

    q and r are derived from p. s is not derived from p. Even though r == s,
    one is derived from p, the other is not.

    You promise the compiler two things:

    1. Any object that is modified through a pointer based on p, is not
    accessed or modified through any pointer that is not based on p.
    2. Any object that is modified through a pointer that is not based on p,
    is not accessed or modified through any pointer that is based on p.

    Declaring a "const restrict" pointer object is stronger. If you have

    const int* restrict p = &a[0];

    for example, then your promise to the compiler is:

    Any object that is accessed through a pointer based on p is not modified
    by any means whatsoever.

    What does that mean for the examples above: If you wrote

    int calc_area (int* restrict width, int* restrict height) { ... }

    you promise that assigning to *height does not change *width and vice
    versa (just read the rules above carefully). Actually, using one
    restrict pointer would have had the same effect. As a result, the
    compiler can assume that the result of this function is always 30.

    In the second function, if you wrote

    int f (const int* restrict p, int* q) { ... }

    you would promise to the compiler that *p is not modified in that
    function by any means, so you promse that q does not point to *p. An
    optimising compiler needs to read *p only once and knows that it cannot
    change its value in that function.
     
    Christian Bau, Jun 19, 2004
    #7
  8. tweak

    Dan Pop Guest

    In <bdMAc.730$DQ4.264@fed1read05> tweak <> writes:

    >Can someone give me a short example as how to best use this keyword in
    >your code?
    >
    >This is my understanding: by definition restrict sounds like it is
    >suppose to restrict access to memory location(s) pointed to, so that
    >only one declared pointer can store that address and access the data in
    >those memory blocks, where I the data in those location(s) can be changed.
    >
    >Is that a correct understanding?


    Your description is not very coherent, so it's hard to tell whether your
    understanding is correct or not. This is one of the cases where it's
    better to avoid the normative text of the standard and focus on the
    examples:

    7 EXAMPLE 1 The file scope declarations

    int * restrict a;
    int * restrict b;
    extern int c[];

    assert that if an object is accessed using one of a, b, or c,
    and that object is modified anywhere in the program, then it is
    never accessed using either of the other two.

    Dan
    --
    Dan Pop
    DESY Zeuthen, RZ group
    Email:
     
    Dan Pop, Jun 21, 2004
    #8
    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. Replies:
    13
    Views:
    6,431
    Dave Thompson
    Dec 20, 2004
  2. ISO C89 and ISO C99

    , Dec 10, 2004, in forum: C Programming
    Replies:
    18
    Views:
    545
    Dave Thompson
    Dec 20, 2004
  3. C99 Restrict

    , Apr 20, 2005, in forum: C Programming
    Replies:
    1
    Views:
    537
    Christian Bau
    Apr 21, 2005
  4. Replies:
    6
    Views:
    374
    Army1987
    Sep 24, 2007
  5. Sune

    C99 restrict and function parameters?

    Sune, Feb 15, 2008, in forum: C Programming
    Replies:
    2
    Views:
    280
Loading...

Share This Page