From: andrew@rentec.com (Andrew Mullhaupt)
Newsgroups: comp.lang.apl
Subject: Re: APL execution efficiency revisited
Date: 6 Apr 92 22:36:54 GMT
Organization: Renaissance Technologies Corp., Setauket, NY.

In article <1992Apr5.180150.41@yrloc.ipsa.reuter.COM> rbe@yrloc.ipsa.reuter.COM (Robert Bernecky) writes:
>In article <783@kepler1.rentec.com> andrew@rentec.com (Andrew Mullhaupt) writes:
>>In article <1992Mar30.203818.15221@yrloc.ipsa.reuter.COM> rbe@yrloc.ipsa.reuter.COM (Robert Bernecky) writes:
>>>>Now for the particular case  of +.x / (A B C D ...) you will be able to

>The point I am STILL trying to make (and will give up if this iteration
>fails...) is that APL already HAS all the information at hand to 
>optimally (from the standpoint of ordering the matrix products to 
>minimize ops) determine the best ordering. 

Yes. If you are doing +.x / you can optimize this. It is much harder to
say something about 'on-line' matrix chain product, where you are supposed
to compute the partial product as you go along, as in the case of a loop.

>Furthermore, the application, or lack of application of said optimization
>can be done without ANY changes to the application, so that relatively
>inexperienced programmers obtain the benefit of such optimizations with
>no work on their part.

In the simple cases, yes. If a program can be transformed from one which
accumulates its matrix product in a loop to one which uses +.x /, then
experience may be helpful.

>A. A posting by a single programmer is not necessarily optimal for any
>   language.

Yes, but that posting was claimed to be optimal for APL2. I have reason
to believe that it is very fast in APL2, and nobody seems to have posted
better, so maybe I'll just claim "best known", although you might want
to be conservative about it and say that it's hard enough to do better
that nobody is motivated to post better...

>B. Predicting the speed of an idiom is walking on thin ice: Many
>   APL (and other) systems detect idioms and produce special purpose 
>   code to handle them efficiently. This is no different from Fortran
>   compilers which stare at 5 lines of DO loop code, and pump out a
>   matrix product.

Yes, and it is also sometimes necessary to foil idiom detection because
APL doesn't always get it right. In APL2 it was necessary for a while to
put a 'harmless' ravel in the unique idiom to _prevent_ the interpreter
from recognizing it, because it had special code, but the dyadic iota
which was being avoided, was actually faster. Then IBM fixed this by taking
out the idiom but you'll still see the extra comma in some people's code.

On the other hand, I like to use matrix bandwidth as an example which is
as fast as you can go in many APL interpreters, but still slow compared
to good compiled language. I have in mind the APL line:

	1 + max / B x T jot.- T <- iota rho B <- 0 unequal M

which computes the bandwidth of a matrix M. I have not seen interpreted
APL which significantly outperforms this, and I think that you won't
be able to cut much off this. I am aware of some of the differences between
different APL systems, but I don't see any which would make this much less
than optimal in practice. In "theory" you might do better by looping over
rows, or recursive subdivision of the matrix, but not without a _giant_
workspace.

>>      c) Some people said 'nobody's forcing you to use APL'. That's not true.
>>         When you have to optimize an APL function, you normally have to call
>>         it from APL. This has recently been fixed in APL2 but not in most
>>         APL's yet. 
>
>Don't make assertions about products about which you are ignorant.
>I am not aware of any APL which has been released in the last several years
>which does not have call-in call-out capabilities.

You're right. I should have said something other than most. Although almost
all APL interpreters I used have call-out, very few supported call-in. 
I used APL2 (which now has it) and STSC and Sharpe APL. One of our resident
APL programmers here doesn't think you can do it with Dyalog. Maybe we're
not talking about the same thing.

By call-in, I mean the ablilty to invoke APL code by calling a function in a
compiled program, not the ability to communicate over a pipe. If people are
putting call-in in interpreters, it raises some interesting issues. (Is it
re-entrant? Can you call in and out and in and out... etc.?) Is it a 'full
bandwidth' interface? (An example of a practical 'full-bandwidth' interface
is the dynamic loading / call-back in the Splus interpreter, where the overhead
of calling in or out is essentially the same as the overhead of calling a
compiled function from within a compiled program. Note that you have to
have called out in order to call back in in Splus...)


Later,
Andrew Mullhaupt
Newsgroups: comp.lang.apl