Path: utzoo!utgpu!water!watmath!clyde!cbosgd!ihnp4!cuuxb!mmengel
From: mmengel@cuuxb.ATT.COM (Marc W. Mengel)
Newsgroups: comp.lang.c
Subject: Re: some objections to 'noalias'
Message-ID: <1486@cuuxb.ATT.COM>
Date: 13 Jan 88 00:17:43 GMT
References: <485@cresswell.quintus.UUCP> <1453@cuuxb.ATT.COM> <6971@brl-smoke.ARPA> <512@cresswell.quintus.UUCP>
Reply-To: mmengel@cuuxb.UUCP (Marc W. Mengel)
Organization: AT&T-DSD, System Engineering for Resellers, Lisle IL
Lines: 117

In article <512@cresswell.quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes:
>In article <6971@brl-smoke.ARPA>, gwyn@brl-smoke.ARPA (Doug Gwyn ) writes:
>> In article <1469@cuuxb.ATT.COM> mmengel@cuuxb.UUCP (Marc W. Mengel) writes:
>> 
>> >	Aliasing is not a problem in C. Ensuring that it is not a problem is
>> >	expensive.  People want to be able to turn off this expensive behavior
>> >	in specific cases where they know that it won't make a difference.
>> 
>> (This is such a beautiful statement of what "noalias" is all about that
>> I wanted to make sure everyone noticed it.  Please excuse the reposting.)
>
>This is such a CONFUSING statement that I too want to make sure everyone
>notices it.  Is he talking about the compile-time cost of checking whether
>something is aliased or not, or about the usually small run-time cost of
>picking up another copy of something from memory just in case it was
>aliased?  

Actually, I was referring to BOTH sets of costs -- run time and compile
time; at compile time there are lots of headaches about synchronizing
whats in registers with whats in memory every time code for a pointer 
indirection is generated; and at run time, the cost of performing
the "usually small" costs of picking up another copy of something from
memory can add up quite a bit.

>[If someone has an example of a real program where adding 'noalias'
>to fewer than 10% of the variables makes a factor of 2 difference to run
>time, let's see it!]  If whatever-it-is is so expensive, shouldn't the
>cheap version be the default (as it is in Fortran, Pascal, COBOL, ADA,
>BASIC, Euclid, and so on) and the expensive version be the one you have
>to say explicitly?

Lets say I agree with you on your assumption that the best I can
get with noalias is a factor of 2 difference in run time... are you
claiming that optimizations that halve my run time are not worth
putting in???  Next, lets look at a nice piece of code...

vecadd( v1, v2, v3 , n)
	noalias int *v1, *v2, *v3;
	int n;
{
	register int i;

	for( i = 0; i < n ; i++, v1++, v2++, v3++  ){
		*v3 = *v2 + *v1;
	}
}

On certain machines like CDC Cyber 205's or other vector processors,
I could encode this as 1 instruction *if* i know that my 3 vectors
don't overlap.  noalias is the only way to efficiently tell the 
compiler this. (you may note in this example the compiler could
generate code that tests for vector overlap and branch to do either the
single vector instruction or the loop, in practice the logic needed
to make that kind of decision in the general case is arbitrarily complex
and may involve solving the (insoluble) halting problem...)

The noalias==cheap-version as a default will break existing code 
so that is *not* an option.

>    What we need at this point is a CLEAR description of exactly what
>    the difference is between
>	volatile int x;
>		 int x;
>	noalias  int x;
>Are they points on a scale:
>	volatile:	may change at any time
Right...

>	{plain}:	may change in any *procedure call*
or through *any* pointer indirection if the plain item  is not a 
register variable and the address of it is taken *anywhere*...  
It can only change in procedure calls that indirect pointers or 
use it directly (if it's global), if your compiler wants to keep 
that kind of bookkeeping, you can restrict your statement about 
procedure calls more.

>	noalias:	may only change by explicit assignment
right.

>If I say
>	cat >>foo.h <<'EOF'
>	extern noalias int x;
>	extern void set_x(int i);
>	EOF
>	cat >>foo.c <<'EOF'
>	noalias int x;
>
>	void set_x(int i) { x = i; }
>	EOF
>	cat >>main.c <<'EOF'
>	#include <stdio.h>
>	#include "foo.h"
>	main() {
>	    x = 0;
>	    set_x(1);
>	    printf("x = %d\n", x);
>	}
>	EOF
>	cc main.c foo.c
>	a.out
>is the output
>	x = 0
>legal?  {Presumably such a program is non-conforming, but is a conforming
>compiler allowed to do this to it?}

I don't see any aliasing in the code you have written...  The global
variable x is everywhere refered to as x, this causes no problems of
any sort that I can see, noalias or not.  The program you list will
output "x = 1\n" on stdout.

It sounds like you misunderstand what aliasing is, and hence miss seeing
when noalias would allow a valuable optimaztion...
-- 
 Marc Mengel	

 attmail!mmengel
 ...!{moss|lll-crg|mtune|ihnp4}!cuuxb!mmengel