Strategies for Optimising the API Problem

Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 7

Strategies for Optimising the API Problem¶

From: Robert Bernecky, March 6 1997

Reading Roger Stokes’ letter about "Nick Cox’s Antecedent Precipitation Index" problem, (Vector 13.3 p.8) I realized that the problem is simply solved by using the recurrence relationship function that APLers have known and loved (or hated) for years:

    ∇ sequence←addend recurrence multiplier;t
[1]  ⍝ sequence[i]←addend[i]+multiplier[i]×sequence[i-1]
[2]  ⍝ sequence[⎕IO]←addend[⎕IO]
[3]  ⍝ 0∊multiplier ←→ 0.  ⎕IO-independent.
[4]  ⍝ (sauce/recurrence.1 from the sharp apl utility library)
[5]   t←×\multiplier
[6]   sequence←1/t×+\addend÷t
    ∇

To get the effect of 0.5 api1 1 2 3 4, you would use the expression 1 2 3 4 recurrence 0.5 0.5 0.5 0.5. This works fine (I naively thought) and is substantially faster than any of the functions presented by Stokes, taking 110 milliseconds for a 1000-element argument on my 486/DX4-100 running APL+Win V1.3.00 under Windows 3.1.

Unfortunately, this function breaks down just at 1024 elements, because the ×\ in line 5 starts producing zeros, which in turn causes the divide in line 6 to fail. This sort of failure is typical of APL algorithms that attempt to mimic iterative algorithms by the use of scan. The partitioned scan utility functions are also prone to this sort of data sensitivity.

Daunted, I returned to iterative solutions, observing that api1 builds its result by repeated catenation. Here is the version of api1 that I used:

r←x api1 y;p;api;i;k
⍝ antecedent precipitation index NJC 15 April 1996
⍝ Rewritten in APL+Win 1997-02-24
⍝ Robert Bernecky
⍝ Repetitive catenate version (slow)
⍝
⍝ dcl double scalar x
⍝ dcl double vector y
k←x
p←y
api←,0.0
:for i :in ⍳⍴y
 api←api,p[i]+k×api[i]
:endfor
r←1↓api

This approach to iterative construction of a result is almost always a bad idea in APL and J. It results in a non-linear amount of work being done, instead of a linear amount. To see why this is, note that iteration I copies I elements of the old value of api to generate the new value. Thus, N iterations will copy (N×(N-1))÷2 array elements to generate an N-element result.

To eliminate this extra work, I rewrote api1 as api3, preallocating result space and using index assign to reduce the amount of array copying:

r←x api3 y;p;api;i;k
⍝ antecedent precipitation index NJC 15 April 1996
⍝ Rewritten in APL+Win 1997-02-24
⍝ Robert Bernecky
⍝ This version avoids repetitive catenation,
⍝ by preallocating result and using indexed assign.
⍝
⍝ dcl double scalar x
⍝ dcl double vector y
k←x
p←y
api←(1+⍴y)⍴0.0
:for i :in ⍳⍴y
 api[i+1]←p[i]+k×api[i]
:endfor
r←1↓api

api3 =. 3 : 0
NB. antecedent precipitation index NJC 15 April 1996
NB. k api p
NB. This preallocates result and uses
NB. indexed assign. Robert Bernecky 1997-02-24
:
k =. x.
p =. y.
api =. (1+#y.)# 0.0
i =. 0
while. i< #y. do.
api =. ((i{p)+k* i{api) (i+1)} api
i=. i+1
end.
}. api
)

These functions compute the final result shape, preallocate a result of the appropriate shape, then perform indexed assign or merge to insert the partial results into the final result, thereby performing work proportional to the shape of the result.

The results of this rather simple optimization were enlightening. On an argument size of 10000 elements (shorter arguments ran too fast to measure on my system), I observed mean execution times in seconds as follows:

The performance of api1 confirms benchmarks done by others, suggesting that J tends to execute slightly faster than APL on many codes. In the APL version of api3, we see that performance has improved significantly, due entirely to elimination of the repetitive array copy operations. APL application programmers should be aware that they can often make substantial improvements to programs through such preallocation techniques in any algorithm that builds its result by aggregation.

Even if the final result size is unknown, it is often possible to obtain most of the benefit of preallocation by the following method: first, allocate a large intermediate result, TMP. On each iteration, if the new data for this iteration fits within TMP, use indexed assign to amend TMP. If it does not fit, catenate a generous amount of filler onto TMP and try again. At the end, drop off any remaining filler. Thus, we see that applying a bit of craft to the problem results in a dramatic performance improvement.

Turning to the J version of api3, I was surprised to see that performance is, in fact, worse than it was for api1. It is evident that the J merge operation did not detect the ability to work in place and avoid the copy operation. During execution, it copied the entire merged array over and over again. This resulted in N*N array elements being copied, explaining the degraded performance.

I reported this bug to Roger Hui, the implementor of J. He was also puzzled, as we both knew that this case of merge should work in place, which would make its performance roughly equivalent to that of the APL version of api3. When I get a fix, I will report updated figures for this benchmark.

So, we now have a real-world application that can not be solved, in general, using non-obvious, non-iterative algorithms, such as recurrence, due to loss of numerical precision. Incorrect results aside, the non-obvious nature of these algorithms makes it hard for naive programmers to design and use them. It is time for APLers to admit that iteration has its place in a programmer’s toolkit.

In order to use iteration effectively, the APL programmer must have the confidence that execution times for iterative code are similar to those written in C or FORTRAN. This can only be done with adoption of compiler methodology, such as that provided by APEX (Bernecky: apl93, apl95, MSc Thesis in press). The APEX compiler is able to take iterative APL code and translate to C code suitable for execution on multiprocessor or uniprocessor systems. I used APEX to compile api1 and api3, and obtained the following results on 10000-element arguments, using Linux (Slackware’96) and gcc on the same hardware platform used above:

Note that the api1 code compiled with APEX is running about 80 times faster than the interpreted code. However, the api3 timings are so low that they are being affected by timer precision on the PC. When I reran the api3 APEX benchmark with a 800000-element argument, it took 1.68 seconds, about the same as the interpreter with a 10000-element argument. Thus, it also obtains an 80-fold speedup over the interpreter.

Since the performance of api3 compiled with APEX is within 20% of the same program written in FORTRAN and compiled with g77 (compiler options were: g77 -O2 -m486 -dalign), it is clear that APL programmers no longer need to fear iteration.

Robert Bernecky
Snake Island Research Inc

APL or J Association?¶

From: Norman Thomson, 20 February 1997

Don Mattern’s letter on the above subject in Vector 13.3 contains enough factual error, prejudice and misjudgement to demand a reply.

First the bulk of Vector is not on J. A rough survey of the technical contents pages over the last few years shows the following percentages of APL/J:

1992 : 69/31, 1993 : 76/24, 1994 : 77/23,
1995 : 59/41, 1996 : 67/33, 1997 (one issue):58/42.

Secondly, the APL character set may look like Greek but in fact they have only four symbols in common. Arguably the need for a special character set has greatly hindered APL’s progress in the programming world. Although it is true that the iconic properties of some of the APL characters is lost by using ASCII characters, whether programs are intuitive or not is a matter for the stylistic skills of the writer combined with the effort expended by the reader in mastering the specific meanings which J imposes on these symbols in context. For those who are not prepared to make this effort to say that J looks like "comic book invective" is no more valid a criticism than that of those castigators of APL who scorn it because it "looks like Greek". Thirdly, Adrian Smith among others will, I am sure, be happy to provide instances of current commercial applications of J.

Fourthly, try as I will, I can find nothing on J in past numbers of Vector which can be described as "theoretical"; as for its being academic, APL itself began as an academic project prior to its commercial success, and J represents in many respects the continuation of the pursuit of innovation which APL began. Perhaps it is worth quoting Richard Procter’s conference report on APL96 (see Vector 13.2, pp.80-81) — "J has a great future with its superior approach to array handling … It is being embraced by APL people as a potentially useful array processing language, and seen by some as better than APL". Fifthly, Mr Mattern says that "IBM has never endorsed J". Subsequent to the introduction of APL, IBM has not been in the business of inventing new languages, so it is hard to see why IBM’s endorsement (or not) is of any more significance than that of any other large commercial IT user or supplier. Sixthly, APL has nearly thirty years of published history behind it in the form of magazines, technical reports, books and conference papers. Admittedly this material is not always as accessible as one would like it to be but at least it represents at least a twenty year start over J, — the surprising thing is surely that Vector contains so little of the latter.

Mr. Mattern says that he subscribed to Vector to receive APL information — let him if he wishes tear out the thirty-odd or so percent of pages of J, and he still has just that, at a subscription which is roughly equal to the "voluntary" ACM donation which accompanies the dues for the corresponding American publication. That all this is so is a tribute to the enormous amount of voluntary effort on the part of the Vector production team (to mention names would be invidious) whose untiring efforts have ensured that Vector has appeared regularly, informatively and uninterruptedly for thirteen years, a record of which no other APL publication can come within striking distance.

From: A J Wilson, 11th February 1997

I am writing to concur with Don Mattern’s letter about J in the January edition of the Vector. The number of articles about J seems disproportionate to its usage.

I do not believe Vector is serving the best interests of its APL users.

From: Stefano Lanzavecchia, 9th March 1997

Personally I like the attitude of "Vector" regarding J. I don’t find the amount of papers about J as a language and about applications written in J excessive at all. On the contrary, I, as an APLer and as programming language freak, find it very stimulating and very valuable: trying to dive into the mind of a J programmer can give a completely new perspective when looking back at problems to be solved in APL. Notice that, due the quantity of work I have to do, I don’t actually have time to play with J in front of a keyboard, and without Vector, that I can read lost in the sofa while sipping a cup of hot tea on a rainy Sunday morning, I would simply not have the possibility of improving my knowledge in that fascinating world.

P.S. in Vector Vol.13 No.3 Page 131 the definition of the verb w should be:

   w =. ~. ^ #/.~

Please note the last "Reflex" that gives a completely different meaning to the train #/. .