What is this noalias thing Dennis Ritchie is railing about ?

  • Thread starter Spiros Bousbouras
  • Start date
B

Ben Pfaff

G

Guy Macon

Ben said:
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 ]
 
C

christian.bau

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.
 
G

Guy Macon

christian.bau said:
"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 ]
 
C

christian.bau

christian.bau said:
"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.
 
M

Malcolm McLean

christian.bau said:
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.
 
C

CBFalconer

Malcolm said:
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.
 
M

Malcolm McLean

CBFalconer said:
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.
 
M

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
 
R

Richard

Martin Wells said:
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.
 
P

pete

Martin said:
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.
 
K

Keith Thompson

Martin Wells said:
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.
 
F

Flash Gordon

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

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?
 
F

Francine.Neary

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

Keith Thompson

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.
 
C

CBFalconer

Malcolm said:
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.
 
C

CBFalconer

Martin said:
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.
 
J

James Dow Allen

"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
 
R

Richard Bos

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
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,755
Messages
2,569,536
Members
45,014
Latest member
BiancaFix3

Latest Threads

Top