What is this noalias thing Dennis Ritchie is railing about ?

[Spiros Bousbouras]

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 ?

[Ben Pfaff]

Spiros Bousbouras <sp****@gmail.comwrites:

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

[Guy Macon]

Ben Pfaff wrote:

>
Spiros Bousbouras <sp****@gmail.comwrites:

>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...66_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...n-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/>

[christian.bau]

On Sep 7, 3:33 pm, Spiros Bousbouras <[e-mail]:

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.

[Guy Macon]

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...66_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 ]

[christian.bau]

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...6_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.

[Malcolm McLean]

"christian.bau" <ch***********@cbau.wanadoo.co.ukwrote in message
news:11*********************@k79g2000hse.googlegro ups.com...

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

[CBFalconer]

Malcolm McLean wrote:

"christian.bau" <ch***********@cbau.wanadoo.co.ukwrote 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

[Malcolm McLean]

"CBFalconer" <cb********@yahoo.comwrote in message
news:46***************@yahoo.com...

Malcolm McLean wrote:

>"christian.bau" <ch***********@cbau.wanadoo.co.ukwrote 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

[Martin Wells]

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

[Richard]

Martin Wells <wa****@eircom.netwrites:

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.

[pete]

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

[Keith Thompson]

Martin Wells <wa****@eircom.netwrites:

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) ks***@mib.org <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"

[Flash Gordon]

Richard wrote, On 10/09/07 23:46:

Martin Wells <wa****@eircom.netwrites:

>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

[Francine.Neary]

On Sep 11, 12:19 am, pete <[e-mail]:

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

[Keith Thompson]

Fr************@googlemail.com 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) ks***@mib.org <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"

[CBFalconer]

Malcolm McLean wrote:

"CBFalconer" <cb********@yahoo.comwrote in message

>Malcolm McLean wrote:

>>"christian.bau" <ch***********@cbau.wanadoo.co.ukwrote 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]

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

[James Dow Allen]

On Sep 7, 7:43 am, "christian.bau" <[e-mail]>
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

[Richard Bos]

Fr************@googlemail.com wrote:

On Sep 11, 12:19 am, pete <[e-mail]:

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

[Malcolm McLean]

"James Dow Allen" <jd*********@yahoo.comwrote in message
news:11**********************@w3g2000hsg.googlegro ups.com...

On Sep 7, 7:43 am, "christian.bau" <[e-mail]>
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.

Mr Ritchie has desinged a successful language whilst the committees has
proposed an unsuccessful standard, so I've give his opinion more weight.

const would have been a good idea, had it been designed in right from the
start of the language. However it doesn't fit C as she is spoke. C++ has
even added a "mutable" keyword. All problems can be solved by adding another
layer of indirection.

On "volatile" I think he is wrong. It doesn't have a place in programs
written in pure C, of course. However I cannot think of any better solution
to the problems of threads and interrupt routines.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

[Malcolm McLean]

<Fr************@googlemail.comwrote in message
news:11**********************@k79g2000hse.googlegr oups.com...

On Sep 11, 12:19 am, pete <[e-mail]:

>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!

I propose a new syntax

)ptr(

a restricted pointer.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm