What is this noalias thing Dennis Ritchie is railing about ?

Discussion in 'C Programming' started by Spiros Bousbouras, Sep 7, 2007.

  1. At http://www.lysator.liu.se/c/dmr-on-noalias.html
    Dennis Ritchie strongly denounces some noalias
    qualifier which was proposed for addition to the language
    at some point. Can someone give me some historical
    background and what it was supposed to do ? Was it
    like restricted pointers ?
    Spiros Bousbouras, Sep 7, 2007
    #1
    1. Advertising

  2. Spiros Bousbouras

    Ben Pfaff Guest

    Spiros Bousbouras <> writes:

    > At http://www.lysator.liu.se/c/dmr-on-noalias.html
    > Dennis Ritchie strongly denounces some noalias
    > qualifier which was proposed for addition to the language
    > at some point. Can someone give me some historical
    > background and what it was supposed to do ? Was it
    > like restricted pointers ?


    A Google search for "c noalias" turned up this page:
    http://www.quut.com/c/noalias-88.html
    The page didn't load for me immediately, but it's in Google's
    cache.
    --
    "All code should be deliberately written for the purposes of instruction.
    If your code isn't readable, it isn't finished yet."
    --Richard Heathfield
    Ben Pfaff, Sep 7, 2007
    #2
    1. Advertising

  3. Spiros Bousbouras

    Guy Macon Guest

    Ben Pfaff wrote:
    >
    >Spiros Bousbouras <> writes:
    >
    >> At http://www.lysator.liu.se/c/dmr-on-noalias.html
    >> Dennis Ritchie strongly denounces some noalias
    >> qualifier which was proposed for addition to the language
    >> at some point. Can someone give me some historical
    >> background and what it was supposed to do ? Was it
    >> like restricted pointers ?

    >
    >A Google search for "c noalias" turned up this page:
    > http://www.quut.com/c/noalias-88.html
    >The page didn't load for me immediately, but it's in Google's
    >cache.


    It appears to be working now.

    The more I read about this sort of thing, the more that
    I agree with the idea that God made machine language and
    all the rest is the work of man... :)

    Here are some additional references:

    Noalias: excerpt from the ANSI C draft of January 1988 -Dennis Ritchie
    [ http://www.quut.com/c/noalias-88.html ]

    Noalias: Official comment to X3J11 -Dennis Ritchie
    [ http://www.quut.com/c/dmr-on-noalias.html ]

    C166 user's Guide: NOALIAS Compiler Directive
    [ http://www.keil.com/support/man/docs/c166/c166_noalias.htm ]

    Restricted Pointers in C: Comparison with Noalias
    Numerical C Extensions Group, Aliasing Subcommittee
    Final Report: Draft 2, X3J11/94-019, WG14/N334
    [ http://www.lysator.liu.se/c/restrict.html#comparison-with-noalias ]

    Gcc Options for Code Generation:
    -falias-check
    -fargument-alias
    -fargument-noalias
    -fno-argument-noalias-global
    [ http://www.delorie.com/gnu/docs/gcc/gcc_13.html ]

    --
    Guy Macon
    <http://www.guymacon.com/>
    Guy Macon, Sep 7, 2007
    #3
  4. On Sep 7, 3:33 pm, Spiros Bousbouras <> wrote:
    > Athttp://www.lysator.liu.se/c/dmr-on-noalias.html
    > Dennis Ritchie strongly denounces some noalias
    > qualifier which was proposed for addition to the language
    > at some point. Can someone give me some historical
    > background and what it was supposed to do ? Was it
    > like restricted pointers ?


    "noalias" was an early proposal to handle aliasing/non-aliasing
    problems in the C language. That proposal turned out to be completely
    broken, as Dennis Ritchie and probably some others recognised. This
    was then replaced with "restrict" pointers which is a sane solution to
    the problem.
    christian.bau, Sep 7, 2007
    #4
  5. Spiros Bousbouras

    Guy Macon Guest

    christian.bau wrote:

    >"noalias" was an early proposal to handle aliasing/non-aliasing
    >problems in the C language. That proposal turned out to be completely
    >broken, as Dennis Ritchie and probably some others recognised. This
    >was then replaced with "restrict" pointers which is a sane solution to
    >the problem.


    It didn't exactly go away:

    C166 user's Guide: NOALIAS Compiler Directive
    [ http://www.keil.com/support/man/docs/c166/c166_noalias.htm ]

    GCC Options for Code Generation:
    -falias-check
    -fargument-alias
    -fargument-noalias
    -fno-argument-noalias-global
    [ http://www.delorie.com/gnu/docs/gcc/gcc_13.html ]
    Guy Macon, Sep 8, 2007
    #5
  6. On Sep 8, 1:19 pm, Guy Macon <http://www.guymacon.com/> wrote:
    > christian.bau wrote:
    > >"noalias" was an early proposal to handle aliasing/non-aliasing
    > >problems in the C language. That proposal turned out to be completely
    > >broken, as Dennis Ritchie and probably some others recognised. This
    > >was then replaced with "restrict" pointers which is a sane solution to
    > >the problem.

    >
    > It didn't exactly go away:
    >
    > C166 user's Guide: NOALIAS Compiler Directive
    > [http://www.keil.com/support/man/docs/c166/c166_noalias.htm]
    >
    > GCC Options for Code Generation:
    > -falias-check
    > -fargument-alias
    > -fargument-noalias
    > -fno-argument-noalias-global
    > [http://www.delorie.com/gnu/docs/gcc/gcc_13.html]


    You misunderstood. It is quite reasonable and useful to be able to
    tell a compiler that certain pointers cannot point to the same object,
    so that it can assume that modifying what one pointer points to
    doesn't change the value that another pointer points to. _How_ exactly
    this is done is critical. I am quite sure that what these gcc options
    do is reasonable. Same with C99 "restrict" pointers; they may be a bit
    hard to understand but in the end they work in a sensible way. The
    "noalias" proposal for the C language and its consequences for the
    language were - after closer examination - just insane.
    christian.bau, Sep 9, 2007
    #6
  7. "christian.bau" <> wrote in message
    news:...
    > The
    > "noalias" proposal for the C language and its consequences for the
    > language were - after closer examination - just insane.
    >

    The problem was that everything touched by "noalias" becomes "noalias". In
    the end it would have clogged up the language horribly, worse than const,
    because const propagates only one const to subroutines, whilst "noalias"
    propagates two or more "no aliases" to the caller.

    --
    Free games and programming goodies.
    http://www.personal.leeds.ac.uk/~bgy1mm
    Malcolm McLean, Sep 9, 2007
    #7
  8. Spiros Bousbouras

    CBFalconer Guest

    Malcolm McLean wrote:
    > "christian.bau" <> wrote in message
    >
    >> The "noalias" proposal for the C language and its consequences for
    >> the language were - after closer examination - just insane.

    >
    > The problem was that everything touched by "noalias" becomes
    > "noalias". In the end it would have clogged up the language
    > horribly, worse than const, because const propagates only one
    > const to subroutines, whilst "noalias" propagates two or more "no
    > aliases" to the caller.


    I see no way that 'const' propagates to functions. If a pointer to
    a const object is passed to a function, that parameter must be
    _declared_ as const, or there is an error. This is simply type
    matching. If that const object is passed, by value, to a function,
    there is no problem, because the function receives a copy, which is
    not const.

    --
    Chuck F (cbfalconer at maineline dot net)
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net>


    --
    Posted via a free Usenet account from http://www.teranews.com
    CBFalconer, Sep 9, 2007
    #8
  9. "CBFalconer" <> wrote in message
    news:...
    > Malcolm McLean wrote:
    >> "christian.bau" <> wrote in message
    >>
    >>> The "noalias" proposal for the C language and its consequences for
    >>> the language were - after closer examination - just insane.

    >>
    >> The problem was that everything touched by "noalias" becomes
    >> "noalias". In the end it would have clogged up the language
    >> horribly, worse than const, because const propagates only one
    >> const to subroutines, whilst "noalias" propagates two or more "no
    >> aliases" to the caller.

    >
    > I see no way that 'const' propagates to functions. If a pointer to
    > a const object is passed to a function, that parameter must be
    > _declared_ as const, or there is an error. This is simply type
    > matching. If that const object is passed, by value, to a function,
    > there is no problem, because the function receives a copy, which is
    > not const.
    >

    void foo(const char *str)
    {
    bar(str);
    }

    void bar( /* must be const*/ const char *str)
    {
    }

    However

    void baz()
    {
    char *input = malloc(100);

    strcpy(input, "Ba ba black sheep");
    /* this is OK */
    foo(input);
    }

    const propagates down, but not up, unless it is in the return type.

    --
    Free games and programming goodies.
    http://www.personal.leeds.ac.uk/~bgy1mm
    Malcolm McLean, Sep 10, 2007
    #9
  10. Spiros Bousbouras

    Martin Wells Guest

    I just wanna ask if I have a decent understanding of how restrict
    pointers work. Here's an example of a function:

    void Func(int *p) /* const I'd usually add has been removed for
    simplicity */
    {
    *p += 7;

    *p += 7;
    }

    Assuming this function is outline (i.e. as opposed to inline), then it
    CANNOT be optimised to "+= 14" because the function is not free to
    assume that what 'p' points to doesn't get changed in the meantime.
    That right?

    And IF it were written as: void Func(int *restrict p), then it WOULD
    be able to perform such an optimisation? That right?

    Martin
    Martin Wells, Sep 10, 2007
    #10
  11. Spiros Bousbouras

    Richard Guest

    Martin Wells <> writes:

    > I just wanna ask if I have a decent understanding of how restrict
    > pointers work. Here's an example of a function:
    >
    > void Func(int *p) /* const I'd usually add has been removed for
    > simplicity */
    > {
    > *p += 7;
    >
    > *p += 7;
    > }
    >
    > Assuming this function is outline (i.e. as opposed to inline), then it
    > CANNOT be optimised to "+= 14" because the function is not free to
    > assume that what 'p' points to doesn't get changed in the meantime.
    > That right?
    >
    > And IF it were written as: void Func(int *restrict p), then it WOULD
    > be able to perform such an optimisation? That right?


    Yes.
    Richard, Sep 10, 2007
    #11
  12. Spiros Bousbouras

    pete Guest

    Martin Wells wrote:
    >
    > I just wanna ask if I have a decent understanding of how restrict
    > pointers work. Here's an example of a function:
    >
    > void Func(int *p) /* const I'd usually add has been removed for
    > simplicity */
    > {
    > *p += 7;
    >
    > *p += 7;
    > }
    >
    > Assuming this function is outline (i.e. as opposed to inline), then it
    > CANNOT be optimised to "+= 14" because the function is not free to
    > assume that what 'p' points to doesn't get changed in the meantime.
    > That right?
    >
    > And IF it were written as: void Func(int *restrict p), then it WOULD
    > be able to perform such an optimisation? That right?


    That's not what restrict is all about.
    Take a look at the C99 prototypes for 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);

    "restrict" means that all accesses to the object pointed to by s1,
    will be made by pointers which were derived from s1.

    In this version of memcpy:

    void *memcpy(void *restrict s1, const void *restrict s2, size_t n)
    {
    unsigned char *p1 = s1;
    const unsigned char *p2 = s2;

    while (n-- != 0) {
    *p1++ = *p2++;
    }
    return s1;
    }

    all accesses to the object pointed to by s1,
    are made through various values of p1, but p1 is derived from s1.

    In memmove, because the objects may overlap,
    It's possible that s1 and/or pointers derived from s1,
    may point to the same addresses
    as pointed to by s2 and/or pointers derived from s2.

    --
    pete
    pete, Sep 11, 2007
    #12
  13. Martin Wells <> writes:
    > I just wanna ask if I have a decent understanding of how restrict
    > pointers work. Here's an example of a function:
    >
    > void Func(int *p) /* const I'd usually add has been removed for
    > simplicity */
    > {
    > *p += 7;
    >
    > *p += 7;
    > }
    >
    > Assuming this function is outline (i.e. as opposed to inline), then it
    > CANNOT be optimised to "+= 14" because the function is not free to
    > assume that what 'p' points to doesn't get changed in the meantime.
    > That right?
    >
    > And IF it were written as: void Func(int *restrict p), then it WOULD
    > be able to perform such an optimisation? That right?


    I don't think so. In the absence of a 'volatile' keyword, nothing can
    happen between the two statements that would affect the value of
    either 'p' or '*p'.

    I think this is a better example of what you're looking for:

    void Func(int *restrict p, int *restrict q)
    {
    *p += 7;
    *q = 0;
    *p += 7;
    }

    The 'restrict' keywords allow the compiler to assume that p and q do
    *not* point to the same object, so it can optimize the code to the
    equivalent of
    *p += 14;
    *q = 42;

    (I'm too lazy to figure out whether both 'restrict' keywords are
    necessary.)

    Note that if you do something like this:

    int x = 0;
    Func(&x, &x);

    you've invoked undefined behavior, and the compiler isn't obligated to
    diagnose the error (though it can do so if it's sufficiently
    clever).

    Without the 'restrict' keywords, the compiler isn't allowed to make
    this assumption; it has to assume that p and q *might* point to the
    same object, and 'Func(&x, &x)' is no longer UB.

    I'm not 100% certain about all this, so please take it with a grain of
    salt until somebody confirms it.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Sep 11, 2007
    #13
  14. Spiros Bousbouras

    Flash Gordon Guest

    Richard wrote, On 10/09/07 23:46:
    > Martin Wells <> writes:
    >
    >> I just wanna ask if I have a decent understanding of how restrict
    >> pointers work. Here's an example of a function:
    >>
    >> void Func(int *p) /* const I'd usually add has been removed for
    >> simplicity */
    >> {
    >> *p += 7;
    >>
    >> *p += 7;
    >> }
    >>
    >> Assuming this function is outline (i.e. as opposed to inline), then it
    >> CANNOT be optimised to "+= 14" because the function is not free to
    >> assume that what 'p' points to doesn't get changed in the meantime.
    >> That right?
    >>
    >> And IF it were written as: void Func(int *restrict p), then it WOULD
    >> be able to perform such an optimisation? That right?

    >
    > Yes.


    Are you sure? I would have said it could perform the optimisation
    without the restrict qualification since there is no intervening code
    that could have any effect on *p. Maybe you were thinking of volatile
    which would have prevented the optimisation?
    --
    Flash Gordon
    Flash Gordon, Sep 11, 2007
    #14
  15. Spiros Bousbouras

    Guest

    On Sep 11, 12:19 am, pete <> wrote:
    > Martin Wells wrote:
    >
    > > I just wanna ask if I have a decent understanding of how restrict
    > > pointers work. Here's an example of a function:

    >
    > > void Func(int *p) /* const I'd usually add has been removed for
    > > simplicity */
    > > {
    > > *p += 7;

    >
    > > *p += 7;
    > > }

    >
    > > Assuming this function is outline (i.e. as opposed to inline), then it
    > > CANNOT be optimised to "+= 14" because the function is not free to
    > > assume that what 'p' points to doesn't get changed in the meantime.
    > > That right?

    >
    > > And IF it were written as: void Func(int *restrict p), then it WOULD
    > > be able to perform such an optimisation? That right?

    >
    > That's not what restrict is all about.
    > Take a look at the C99 prototypes for 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);
    >
    > "restrict" means that all accesses to the object pointed to by s1,
    > will be made by pointers which were derived from s1.
    >
    > In this version of memcpy:
    >
    > void *memcpy(void *restrict s1, const void *restrict s2, size_t n)
    > {
    > unsigned char *p1 = s1;
    > const unsigned char *p2 = s2;
    >
    > while (n-- != 0) {
    > *p1++ = *p2++;
    > }
    > return s1;
    >
    > }
    >
    > all accesses to the object pointed to by s1,
    > are made through various values of p1, but p1 is derived from s1.
    >
    > In memmove, because the objects may overlap,
    > It's possible that s1 and/or pointers derived from s1,
    > may point to the same addresses
    > as pointed to by s2 and/or pointers derived from s2.


    Wow, what a pig's breakfast! I also find "restrict" is often a useful
    name for a variable - one more reason to stick with C90!

    >
    > --
    > pete
    , Sep 11, 2007
    #15
  16. writes:
    [...]
    > Wow, what a pig's breakfast! I also find "restrict" is often a useful
    > name for a variable - one more reason to stick with C90!


    By doing so, you also restrict (ahem) anyone trying to compile your
    code to using C90 compilers.

    If you want to avoid C99, I recomend programming in the intersection
    of C90 and C99. That mostly means avoiding the new keywords and
    implicit int.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Sep 11, 2007
    #16
  17. Spiros Bousbouras

    CBFalconer Guest

    Malcolm McLean wrote:
    > "CBFalconer" <> wrote in message
    >> Malcolm McLean wrote:
    >>> "christian.bau" <> wrote in message
    >>>
    >>>> The "noalias" proposal for the C language and its consequences for
    >>>> the language were - after closer examination - just insane.
    >>>
    >>> The problem was that everything touched by "noalias" becomes
    >>> "noalias". In the end it would have clogged up the language
    >>> horribly, worse than const, because const propagates only one
    >>> const to subroutines, whilst "noalias" propagates two or more "no
    >>> aliases" to the caller.

    >>
    >> I see no way that 'const' propagates to functions. If a pointer to
    >> a const object is passed to a function, that parameter must be
    >> _declared_ as const, or there is an error. This is simply type
    >> matching. If that const object is passed, by value, to a function,
    >> there is no problem, because the function receives a copy, which is
    >> not const.

    >
    > void foo(const char *str) {
    > bar(str);
    > }
    >
    > void bar( /* must be const*/ const char *str) {
    > }
    >
    > However
    >
    > void baz() {
    > char *input = malloc(100);
    >
    > strcpy(input, "Ba ba black sheep");
    > /* this is OK */
    > foo(input);
    > }
    >
    > const propagates down, but not up, unless it is in the return type.


    This isn't 'propagation', just insistance on proper type matching,
    and preventing writing on a read-only object. Things are much
    clearer if you define functions before they are called, which
    avoids most prototypes, except for external functions and recursive
    groups.

    --
    Chuck F (cbfalconer at maineline dot net)
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net>



    --
    Posted via a free Usenet account from http://www.teranews.com
    CBFalconer, Sep 11, 2007
    #17
  18. Spiros Bousbouras

    CBFalconer Guest

    Martin Wells wrote:
    >
    > I just wanna ask if I have a decent understanding of how restrict
    > pointers work. Here's an example of a function:
    >
    > void Func(int *p) {
    > *p += 7;
    > *p += 7;
    > }
    >
    > Assuming this function is outline (i.e. as opposed to inline), then
    > it CANNOT be optimised to "+= 14" because the function is not free
    > to assume that what 'p' points to doesn't get changed in the
    > meantime. That right?
    >
    > And IF it were written as: void Func(int *restrict p), then it WOULD
    > be able to perform such an optimisation? That right?


    No, no, no.

    void foo(int *p, int *q) {

    if (8 == (*p += 3)) {
    *q++;
    /* now you can no longer assume p to be 8 */
    /* because p and q have no 'restrict' */
    }
    }

    (the call that shows this)
    int a[22];
    ...
    foo(a+4, a);

    or something like that. The restrict is not on the function, but
    on the caller, who must ensure the arguments are independant.

    --
    Chuck F (cbfalconer at maineline dot net)
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net>



    --
    Posted via a free Usenet account from http://www.teranews.com
    CBFalconer, Sep 11, 2007
    #18
  19. On Sep 7, 7:43 am, "christian.bau" <>
    wrote:
    > "noalias" was an early proposal to handle
    > aliasing/non-aliasing problems in the C language.
    > That proposal turned out to be completely
    > broken, as Dennis Ritchie ... recognised.


    Here's the relevant Dennis Ritchie Usenet post:
    //groups.google.com/group/comp.lang.c/msg/991b9116ffa83c60?
    dmode=source

    Although Dennis obviously disapproved of
    "broken" proposals, his comment goes further:
    > Let me begin by saying that I'm not convinced
    > that even the pre-December qualifiers (`const'
    > and `volatile') carry their weight; I suspect
    > that what they add to the cost of learning
    > and using the language is not repaid in
    > greater expressiveness.


    Dennis' comment seems like a good antidote
    to the frequently-heard assumption that
    adding a feature to a language automatically
    makes it better.

    James Dow Allen
    James Dow Allen, Sep 11, 2007
    #19
  20. Spiros Bousbouras

    Richard Bos Guest

    wrote:

    > On Sep 11, 12:19 am, pete <> wrote:
    > > That's not what restrict is all about.
    > > Take a look at the C99 prototypes for 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);
    > >
    > > "restrict" means that all accesses to the object pointed to by s1,
    > > will be made by pointers which were derived from s1.
    > >
    > > In this version of memcpy:
    > >
    > > void *memcpy(void *restrict s1, const void *restrict s2, size_t n)
    > > {
    > > unsigned char *p1 = s1;
    > > const unsigned char *p2 = s2;
    > >
    > > while (n-- != 0) {
    > > *p1++ = *p2++;
    > > }
    > > return s1;
    > >
    > > }
    > >
    > > all accesses to the object pointed to by s1,
    > > are made through various values of p1, but p1 is derived from s1.
    > >
    > > In memmove, because the objects may overlap,
    > > It's possible that s1 and/or pointers derived from s1,
    > > may point to the same addresses
    > > as pointed to by s2 and/or pointers derived from s2.

    >
    > Wow, what a pig's breakfast!


    Why a pig's breakfast? This allows restrict to specify exactly what was
    written in words in the previous Standard: that the two pointers to
    memcpy() must not point to overlapping areas, and that those to
    memmove() may. This is actually the most useful application of restrict
    I've found in the Standard.

    Richard
    Richard Bos, Sep 12, 2007
    #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. Ioannis Vranos
    Replies:
    4
    Views:
    359
    Ioannis Vranos
    May 16, 2009
  2. C learner

    Query from Dennis Ritchie

    C learner, Mar 29, 2011, in forum: C Programming
    Replies:
    6
    Views:
    360
    James Harris
    Apr 4, 2011
  3. Bradley K. Sherman

    Dennis Ritchie Has Died

    Bradley K. Sherman, Oct 13, 2011, in forum: C Programming
    Replies:
    28
    Views:
    943
    luser- -droog
    Oct 18, 2011
  4. Lynn McGuire

    Re: RIP Dennis Ritchie

    Lynn McGuire, Oct 13, 2011, in forum: C++
    Replies:
    12
    Views:
    698
    Markus Wichmann
    Oct 18, 2011
  5. markspace

    [OT] Dennis Ritchie dies at 70

    markspace, Oct 13, 2011, in forum: Java
    Replies:
    37
    Views:
    971
    B1ll Gat3s
    Nov 7, 2011
Loading...

Share This Page