Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!cmcl2!lanl!lambda!jlg
From: jlg@lambda.UUCP (Jim Giles)
Newsgroups: comp.lang.misc
Subject: Re: Pointers as 3-tuples
Message-ID: <14332@lambda.UUCP>
Date: 11 Apr 90 05:43:17 GMT
References: <20080@megaron.cs.arizona.edu>
Lines: 23

From article <20080@megaron.cs.arizona.edu>, by gudeman@cs.arizona.edu (David Gudeman):
> [...]
> Actually, it increases exponentially with the number of aliasing
> patterns in the arguments of the functions.  For a function of 3
> array arguments, the maximum number of versions needed is 2^3 = 8.

No, the number increases combinatorially.  Aliasing occurs pairwise
between arguments (an/or global data).  So, the number of potentially
aliased pairs is N choose 2, ie. a binomial coefficient.  Here, N is the
number of variables in the pool of potentially aliased objects.

> Just how many array arguments do your functions have?  And I wouldn't
> even consider trying to compile a seperate function for _every_
> possibility.  Just 2 or so, maybe a worst case and an average case.

Actually, the procedures which are required to be fast may have lots
of parameters (like the RKF differential equation solver).  You give
me the choice of alias free performance or very _worst_ case.  I'll
take the first and skip the second by not allowing _any_ aliasing
(at least until the tools required for interprocedural analysis
are cheap and widely available).

J. Giles