Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!uakari.primate.wisc.edu!aplcen!haven!adm!cmcl2!lanl!jlg
From: jlg@lanl.gov (Jim Giles)
Newsgroups: comp.lang.misc
Subject: Re: Answers, Chapter 1: TeX
Message-ID: <5488@lanl.gov>
Date: 9 Nov 90 21:27:24 GMT
References: <24149:Nov905:42:0990@kramden.acf.nyu.edu>
Organization: Los Alamos Natl Lab, Los Alamos, N.M.
Lines: 66

From article <24149:Nov905:42:0990@kramden.acf.nyu.edu>, by brnstnd@kramden.acf.nyu.edu (Dan Bernstein):
> [...]
> As a matter of fact, most of my responses to this article are contained
> in that article back from April, which you never responded to. How about
> giving it a try? It's quoted below. Pay attention to the last paragraph.

Actually I _did_ respond to that article.  I didn't respond to the
_next_ one you sent on the same thread. (The one where you claimed
that there were linear sorting techniques.  There are indeed: radix
sorts - which I assume are what you are refering to.  Unfortunately,
these are linear in _both_ the number of elements to be sorted N
_and_ the number of radix B digits in the keys D.  Note that if the
keys are distinct, Nlog(N) is less than (or equal to) ND.  This is
because D is the log base B of the size of the keyspace and N - at
most - fills the keyspace.  That's why I didn't bother to answer
your next post - you didn't seem to realize that an Nlog(N) sort is
_faster_ than a 'linear' radix sort when the keyspace is sparcely
filled.)

> [...]
>> > 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.
>   [ implying that the number of versions is 2^(N choose 2), not 2^N ]

I will point out that, at the time, the subject of the conversation
was the computational complexity of testing passed parameters to
determine whether they are aliased (at least, that's what I was
discussing at that time - if you thought the discussion was something
else, you should have explicitly said so,instead of claiming my
math was wrong).  It can be seen that the number of combinations
to test is indeed N choose 2.  I pointed out that this might be
trimmed a little by doing a sort of the parameter addresses before
testing: hence the side-discussion about the speed of sort algorithms.

> [...]
> Hmmm, this doesn't sound right. After all, if A and B could be aliased,
> and B and C could be aliased, then A and C could be aliased. (This is
> why the natural keyword is ``alias,'' not ``noalias.'')
> 
> I count 2 for 2, 5 for 3, 15 for 4, 52 for 5, 218 for 6. Go figure.
> 
> Anyway, this is all irrelevant, because as Jim loves to remind us,
> aliasing is rarely useful. (It can't be---otherwise Fortran would allow
> it.) Therefore you only need two versions: the amazingly fast one for no
> aliasing, and the slow one for the rare cases. Right, Jim?

But, one of the things I've consistently insisted upon is _not_ to
have the slow one on those rare occasions, but to have a slightly
slower one which compromises on speed only for those variables which
are _actually_ going to be aliased.  This leaves either one of us
with an exponential problem (at least - I still don't have a closed
form solution - so I don't make promises about the size being _just_
exponential).

I solve the problem by doing a call chain analysis and failing to
load if the propagated aliasing constraints don't match.  This keeps
incorrect optimizations from being done _and_ provides feedback to
the user allowing him to correct the aliasing in whatever way he
considers appropriate (even by explicitly allowing it).  As far as I
can tell, Dan doesn't solve (or even address) the problem.

J. Giles