From: andrew@rentec.com (Andrew Mullhaupt)
Newsgroups: comp.lang.apl
Subject: Re: What does that FORTRAN code  _do_?
Date: 6 Apr 92 21:02:26 GMT
Organization: Renaissance Technologies Corp., Setauket, NY.

In article <920404100728_70530.1226_CHC22-1@CompuServe.COM> 70530.1226@CompuServe.COM (Mike Kent) writes:
>In article <ROCKWELL.92apr2194843@socrates.umd.edu>
>rowkwell@socrates.umd.edu (Raul Deluth Miller-Rockwell) asks:
>Calling
>
>               partsum(count1, count2, lenvec, itmvec, result)
>
>produces a partitioned sum of the integer vector <itmvec> in <result>,
>that is, a sum of the <count1> consecutive subvectors of respective
>lengths <lenvec>.  It does this a bit more quickly than the usual APL
>+\ , compress, first differences idiom with a partitioning bit vector
>marking the partitions of <itmvec> when <count1> is very small, and
>considerably more _slowly_ when <count1> modest to large (modest == 50).

The reason for this is that you have smaller inner loops. You can
beat this one by copying the array and summing 'in place', then
differencing. I probably would have tried this first. On the other
hand, Mike's post was a reasonable attempt. His point that when you
can express an algorithm in APL which doesn't use much flow of control
or a lot of excess memory that it will be pretty fast. You have a
right to expect this from your interpreter vendor. I must admit that
Mike's FORTRAN is reasonable. However, FORTRAN certainly allows for
an algorithm which would compete with the APL, so I don't think it's
fair to use this partition sum as an example where APL is faster than
FORTRAN. It _is_ an example of where good APL is faster than a reasonable
FORTRAN program, and I guess this is what Mike's focus is.

I am more interested in the limits of the language, and to determine these
you need to be prepared to use the _best_ possible algorithm for the
programming system. Recently I posted an APL2 intersection idiom which
I think is about as fast as APL2 can go. If I can go faster using C
or FORTRAN, I interpret this as evidence that APL2 is "not as fast" as
FORTRAN or C, since I gave APL2 its best shot. If someone can find a much
faster APL2 intersection, then I have to reconsider.


I like to use the bandwidth as a good example of an APL limit. In APL2,
a fast way to determine the bandwidth of a matrix M is:

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

It works by forming a boolean matrix B which indicates the nonzero elements
of M, then it forms a matrix (abs T jot.-T) which labels the diagonals
then it takes the maximum value of this bandwidth matrix which corresponds
to a nonzero element of M.

It is interesting to speculate that an supersmart APL interpreter could
avoid creating a full B matrix by looking at the entire line, but in
reality, B will be fully computed by most APLs. Now on a vector machine,
you are still in contention since APL is going to get pretty long vectors.
Now (abs T jot.- T) will also be formed. This is where you start to get
beat by compiled algorithms. The extra memory for this matrix will cost
you, and then you're going to go through it again to multply by B. Then
we assume the ravel is free, but the max reduce does cost you a full set
of comparisons. It is pretty easy to see how this algorithm is not space
or time efficient compared to fairly simple C or FORTRAN, and it is not
so easy to see how to improve it. (Obviously, I'm interested in any faster
approach, but I don't think you can gain much...)

 

>still think, that { first +.x / } is not an especially compelling 
>candidate for a new primitive, or []MATCHAINPROD, or idiom recognition 

Actually, I think that {}MATCHAINPROD would be totally uncalled for.
If the only thing you can do in APL is expand the system to include
bad examples, then you'll end up with PL/I with funny characters.
The value of discussing hard examples in APL is not so much to argue
for expanding APL, but to raise our consciousness about APL as an
expressive language. On the blackboard, there is essentially _nothing_
wrong with using an inefficient APL expression. It's often only when you
want to solve large problems that you find the limits of 'thinking in APL
terms'.

Now I take the point of view that a language which wants to be thought
of as expressive needs to take seriously _any_ algorithm with performance
advantages, not so much because you can make a million bucks because you
have this fast implementation, but because 'expressiveness' in a
performance vacuum is meaningless. Prolog is a great example of a 
language which is _tremendously_ expressive in some directions, but it
is also possible to write Prolog programs which do not terminate at all
merely because you put the desired clauses in a different order.


> ... On the other hand,
>if the idiom recognized were { first f.g / } with identification of the
>cases where the pair f::g has an associative inner product and shape-
>based ordering of the reduction so that that { and . = / } and a personal
>favorite { or . and / } also benefitted for example, THAT would be a real
>good candidate for incorporation into the system software, i.e., the APl
>interpreter. 

Such is actually the case, but I'd rather be able to write the algorithms
in APL rather than have every clever twist turn up as a new primitive.

>Mike Kent [ who would just as soon _not_ flog the mouldering corpse of
>            this dead horse any further ]

Later,
Andrew Mullhaupt
Newsgroups: comp.lang.apl