Efficiency in APL
Vector 4:4, page 111
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 111
Introduction¶
This article is based on a presentation with the same title given at a meeting of the British APL Association in 1987. It is by no means intended to be an exhaustive study of the topic of efficiency in the APL environment, but rather a collection of ideas from many sources suffused with some recent work experience optimising APL systems. I apologise for any mistakes or omissions, and welcome any correspondence on this subject, either through the pages of this journal or personally at the Cocking and Drury London office.
First, let me briefly review the contents of this article, so that you can decide now if you want to read it or not; we will be covering a number of areas: after a brief look at what ‘efficiency’ could possibly mean, and why it is relevant, a review will be made of the tools available for locating problem areas in APL systems. We will then look at some sample techniques that can be used to optimise those systems. I also hope to demonstrate the value of ‘knowing your interpreter’ in the optimisation effort.
What is Efficiency?¶
When I was asked to give this talk, it seemed clear what the subject matter was, but then of course I started to think about it, and all was lost. In a vague attempt to regain my footing I reached for a pocket dictionary (not Ken Iverson’s); apparently ‘efficiency’ is the ‘ratio of useful work done to energy expended’. First we have to decide what the object of efficiency is. It could be the development of a software system, the operation of the system, the execution of the system and probably others too. For the purpose of this article let us take the restricted view, and agree that what we are primarily interested in here is program execution efficiency.
We should also assume that the program does in fact do ‘useful work’, although as we will see later the removal of redundancy is a valid optimisation technique. What ‘energies’ are expended then, during program execution? Certainly electricity is consumed, and possibly also such human resources as are required by the program’s interaction with its environment. Again, let us take a restricted view; most of us do not concern ourselves with the quantity of electricity that our beloved programs consume (although there were rumours that during the early days of development of STSC’s APL compiler the lights went dim all over Rockville). What we are concerned with are the time and space opportunities which once lost are gone forever. In APL application terms we are talking about:
- CPU time
- Workspace storage
- Elapsed time
- External storage
We are probably all familiar with the CPU time and workspace storage resources. Elapsed time and external file storage considerations can also make or break an APL application – these are often determined by higher-level design choices as well as by questions of run-time efficiency. The main emphasis of this article will be on the first two, and in particular on minimising CPU time.
Why Make Programs Efficient?¶
So now we have arrived at what was probably obvious to you all along – that reducing CPU time increases program efficiency. But before we get stuck into the nitty-gritty of optimisation, it is worth looking briefly at why optimising a program may be worthwhile. Actually, efficiency can be seen as just one out of a whole set of ‘program quality characteristics’, each of which contributes to the overall quality of the program.
Figure 1 puts efficiency into this context.
PROGRAM QUALITY
/\
/ \
/ \
/ \
SUITABILITY MAINTAINABILITY
| |
| |
Reliability Understandability
Correctness Modifiability
Accuracy Testability
Useability Portability
Security
Efficiency
Figure 1: Progam quality characteristics
So increasing efficiency is just one way of increasing the quality of a program. The catch of course, is that many of the quality characteristics compete, i.e. increasing one may cause others to decrease. Your program is probably too efficient once you can no longer understand it. (You may have had the experience of asking a colleague why a particular piece of dense, uncommented APL code was written in such a compact way; the answer probably was “oh yes, well, I had to write it like that to be efficient.”) In fact it is not necessary to sacrifice understandability for efficiency, if the right approach is adopted.
One of the first jobs the application developer should do when extracting the users’ requirements is to gain a clear understanding of which of the quality characteristics are perceived as important. This simple task is often overlooked in the rush to ‘start work’.
How do programs get to be efficient? Either by writing them that way because efficiency was declared to be a critical quality factor, or more usually, by making an existing program more efficient, which we can call optimisation. Ironically of course, it is often harder to do things the second way, especially if storage efficiency is a factor.
Even if you cannot afford the time to directly consider the efficiency issue at the start of a project, there is something you can do at this stage to make life easier later on. Making a program more efficient is merely a kind of program modification, albeit an unusual one which does not change the input or output. Any type of program modification can be made more easily, quickly, cheaply and correctly when the program is highly modifiable, and high modifiability is one of the attributes of a good system design. A system design technique well-suited to APL is described in [1].
So a useful rule is: if you are expecting to make changes to your program, do a good design. It is so much more effective to put early effort into creating a modifiable system than to waste the time later heart-searching about what type of looping construct to use, or whether to truncate variable names to three characters, or other such nonsense.
The fact of the matter is, however, that most of the code people want to optimise has already been written, and so we do need to consider alternative coding techniques, about which more later.
Perhaps it is worth briefly reflecting on why efficiency in APL has become more of an issue recently. APL is now expected to compete with packages and languages that it could not have hoped to in the past. Users are not willing to put up with a language that is insular, but expect it to interact with its environment and to take full advantage of external facilities. Consider as an example STSC’s Statgraphics package, which competes very successfully with other PC and mainframe statistical and graphics systems. Although written largely in APL, the performance that users expect can only be delivered by a combination of efficiently-coded APL, C and Assembler. On the mainframe side too, users want to exploit the particular advantages of their environment, access fast Fortran routines and carefully monitor their APL applications, to name just three examples at random, with a view to reducing the CPU loadings on their machines.
Tools for Optimisation¶
Once you have decided to optimise a system, the first thing you have to do is decide what to optimise. It can be very tempting to think that speeding up everything is the best way to proceed, but do not be fooled. It is similarly a waste of time to say ‘OK, I’ll rewrite function XYZ because it uses a really inefficient algorithm’ when function XYZ only accounts for 1% of the total CPU time in a run.
A better approach is to optimise just those areas that need it most. There are two main advantages to this method: first, time is not wasted working on areas which will not yield benefits; and second and perhaps more critical, the overall maintainability of the system is not compromised. The goal is to achieve a large increase in efficiency while retaining the flexibility of an easily readable, modifiable, testable and portable system.
These observations underline the need to carefully and accurately monitor application execution time. You cannot start optimising until you know what to optimise, and you cannot know what to optimise until you know what is slow. So let us review the tools available to the APL optimiser. Figure 2 is a list of execution monitoring tools available to users of different APLs – apologies for any omissions.
APL interpreter Tools available
VS APL - APAT (APL Performance Analysis Tool)
APL2 R1,R2 - Migrate APAT
APL2 R2,R3 - ⎕IB
APL2 R3 - TIME external function
APL*PLUS Mainframe - ⎕MF
APL*PLUS PC R6 - Fastcode monitor
APL*PLUS PC R7 - ⎕MF
SHARP APL (experimental) - ⎕FM
Figure 2: APL execution monitoring tools
IBM’s APAT product is rarely seen; it will give the CPU time for each function line, and list the functions consuming most time in descending order. APAT is itself written in APL, and works by modifying the APL application on which it is used. A review can be found in [14]. Users of APL2 Release 2 or 3 could try to migrate APAT, or use the quad-IB system function, as described in [2]. Correctly used, quad-IB will yield the number of times each line of code is executed, and the CPU time per line. The quad-IB facility actually provides a whole range of useful facilities, of which function execution tracing is but one. (APL veterans may be amused to learn that ‘IB’ apparently stands for ‘I-Beam’.) Release 3 comes with an external function called TIME for measuring the performance of APL2 programs.
Users of APL*PLUS Mainframe or APL*PLUS PC Release 7 can use the built-in monitoring facility accessed via quad-MF. This system function will monitor the execution of all the functions named in its right argument. A typical use is given in Figure 3.
1 ⎕MF ⎕NL 3 ⍝ Monitor ALL functions in ws
RUN ⍝ Run the application to completion
)COPY 3 MFFNS GRPCUMSUM GRPLTIMES
CUMSUM ⎕NL 3 ⍝ Display CPU info for each function
LTIMES 'FOO' ⍝ Display CPU info for each line of FOO
Figure 3: Use of APL*PLUS Mainframe Monitor Facility
This article is not the place for a full description of the outputs of the CUMSUM and LTIMES functions, but a synopsis of the information produced is useful. The CUMSUM function produces a listing which includes the following pieces of information for each function in its argument:
- The function name
- The total CPU time spent in the function
- The function’s CPU time as a % of the whole run
- The cumulative % CPU time
- The number of times the function was called
- The maximum number of times any one line was executed
- The number of lines in the function
- The function size in bytes
The above information is displayed on a single row per function, ordered so that the highest CPU consumer appears at the top of the list. The LTIMES function applies to a single function name, and yields information relating to each line of code in the function. The display includes the function listing with the following data appended to each line of the listing:
- The CPU time spent on the line, excluding sub-functions (HERE)
- The CPU time spent on the line, including all sub-functions (ALL)
- The number of times the line was executed
The HERE time ignores the time spent in any defined sub-functions called by the line, and so identifies code lines which are intrinsically expensive. The ALL time accumulates the time spent in all of the sub-functions invoked as a result of executing the line, and is crucial for identifying CPU-critical ‘function trees’ in the workspace. This encourages the optimiser to recast the algorithm of a function with high ALL time so that it no longer needs the expensive sub-functions.
Optimisation Procedure¶
The process of optimisation involves the following steps:
- Time the application with specific, known inputs
- Make optimising changes
- Re-time the application with the same specific, known inputs
Clearly one can iterate on the last two steps until the objective has been achieved, or until resource limitations preclude further study.
In large, complex APL applications it is especially important to identify the objects of optimisation. It is initially tempting to view the object of optimisation as the entire ws; after all, we want to speed up the slow functions in the workspace don’t we? In fact there may be more than one top-level function in the ws, and in any case there are likely to be many possible ‘execution paths’ in a large system.
So the focus of attention should be a specific ‘theme’ in the workspace, combined with a given set of data. I am using the word theme here to refer to exactly one execution path through the application. This path is determined by all of the inputs to the APL interpreter and the application during the run, which must remain unchanged for the timing runs performed before and after optimising changes have been made. The job of ‘optimising the ws’ may therefore be a larger task involving the optimisation of multiple themes.
Once you know the distribution of CPU time in the application theme under study you can start optimising. Most unoptimised programs obey the apparently ubiquitous 80-20 rule, which says:
- 80% of the CPU time is spent in 20% of the code
In some cases you find an even stronger skew, with over 90% of the time going into a single function or even a single line. Optimised systems usually show a more even spread of CPU time among the CPU intensive functions. In general, the greater the skew, the easier the work of optimisation. The golden rule is:
- Concentrate your effort where it will do most good
Sometimes it can be hard to know when to stop optimising a system. This depends on the original distribution of CPU over the critical functions, but once a reasonable job has been done on the hogs, it is probably time to stop. The point is that it is not usually worth trying to squeeze out an extra few milliseconds once you have halved CPU time. It is interesting to reflect on the fact that:
A speedup factor of 2 saves more CPU time than a subsequent speedup factor of 1000
Optimising changes can be classified according to modifications made at three distinct levels:
- Line level
- Function level
- Function-group level
An example of a line level change is the replacement of one code fragment by another. In a function level change, the whole function is rewritten, or completely replaced by a new one. The last type is more subtle and can often give the most gains. What happens is that a certain function appears high on the CPU-hog list, and one is tempted to immediately concentrate a lot of effort on the function. This may not always be the most successful approach.
In these cases it is useful to look at the calling function – the function that invoked the CPU-hog. Of course, the calling function may not itself be a hog, but it may be possible to rewrite it so that the reference to the offending function is no longer required. Effectively you are rewriting the algorithm, and in doing so replacing one group of functions by a new group. In such cases it is essential to have a clear understanding of what the code is doing, i.e. to understand the application.
Techniques for Optimisation¶
Now that we know what to optimise, we should review the techniques available for effecting the optimisation. This depends on which APL you are using, but the options can be classified by the following categories, in no particular order:
- Recode using APL
- Recode to use fast-functions
- Recode to use an alternative programming language
- Recode to use operating system services
- Modify application to use IBM files more efficiently
- Modify application to use an APL component filing system
- Modify application to use more appropriate data structures
- Use APL compiler
- Upgrade your APL
The first on the list – recode using APL – is one of the most commonly used, and detailed examples will be saved until after the other techniques have been briefly addressed.
The phrase ‘fast-function’ is used here to refer to a function which has the external attributes of an APL function, but is actually implemented using a lower-level language. Generally fast-functions implement commonly used and well-defined APL utilities, e.g. table lookup functions. Many vendors now supply workspaces of fast-functions with their interpreters, while others offer them as add-ons.
Here is a summary of some of the software available for some popular APLs:
APL interpreter Available fast-functions
VS APL - third-party functions
APL2 R2 - supplied external functions
- third-party external functions
- third-party ⎕FMT external function
APL*PLUS Mainframe - supplied FASTFNS worskpace
- extra FASTFNS with APL*PLUS compiler
APL*PLUS PC - supplied ASMFNS workspace
- third-party assembler functions
Dyalog APL - external functions
Figure 4: Available APL fast-functions
The following example shows how the fast-function technique is used in practice. In a recent job, a VS APL system was migrated to APL*PLUS Mainframe with a view to optimising it. (Many of the examples in this article come from the APL*PLUS Mainframe system, because much of my recent work experience has been with that system.) After monitoring the CPU intensive application, which was designed to analyse and print multi-level product-tree information, it was discovered that more than 95% of the total CPU fell on a single line. The offending line was merely doing a table-lookup between two large integer matrices of product code numbers, where all the codes in one table were known to exist in the other. The notoriously CPU intensive ‘and-dot-equals’ method was employed. The line was recoded to use a supplied fast-function for performing numeric table lookup. This simple change yielded a 90% speedup over the whole application theme.
Figure 5 summarises the original and replacement code lines.
⍴MAT
1000 10
⍴CODES
100 10
I←1++⌿~∨⍀MAT∧.=⍉CODES ⍝ Original line
I←MAT MATIOTAN CODES ⍝ Replacement line
Figure 5: Using a fast-function to speed up numeric table lookup
Users of APL*PLUS/PC are well-advised to study the contents of the distributed ASMFNS ws, which contains a host of useful fast-functions. The workspace also contains ‘segmented-string’ fast-functions which permit the processing of delimited character vectors more quickly, and in less space, than when using the traditional character matrix representation. Other good sources af partition-function techniques include [3] and [4].
When the fast-function you need does not exist, and you are feeling particularly brave, you might consider trying your hand at developing your own low-level programs. Figure 6 summarises available foreign language execution facilities for a variety of APL interpreters.
APL interpreter Facility
VS APL CALL/AP
APL2 ⎕NA
APL*PLUS UNX ⎕CALL, ⎕XP1
APL*PLUS VMS ⎕NA
APL*PLUS PC ⎕CALL, APL2C
APL.68000 AP1
Dyalog APL ⎕SH
IBM PC APL ⎕PK, AP2
Figure 6: Foreign language execution facilities from APL
In one VS APL application developed by a colleague before the days of fast-functions, the critical part turned out to be a numeric table lookup similar to the case described above. It was known that the rows of both argument matrices were in sorted order, however. The technique used was to write a small 360 assembly language program which used a fast binary-search algorithm to do the lookup. The assembler program was invoked from VS APL via a shared-variable link to the Interprocess CALL/AP auxiliary processor. The original APL algorithm was never implemented because it would simply have taken too long to run [5].
APL2 users can now write specialised programs in Assembler, Fortran, Rexx, PL/1, (and now even APL2 itself), and interface to them via the quad-NA Name Association facility. A similar facility is available in the APL*PLUS VMS system. APL.68000 foreign language routines can be accessed via the AP1 auxiliary processor via shared variables, and Dyalog APL external functions can be executed via the quad-SH (shell) function.
APL*PLUS PC users can write their own assembler programs and invoke them via the quad-CALL system function. Those interested in developing this skill should review the excellent tutorials [6] and [7]. For jobs too large to attempt writing assembler code, or those involving floating-point arithmetic, the APL2C interface from Lauer Software may prove suitable. A colleague has produced excellent results interfacing in this way to C programs, in the area of processing tabular control-break data prior to producing reports in APL*PLUS PC [8].
The host operating system can sometimes offer a solution to efficiency problems. On mainframes, IBM’s System Sort utility or Computer Associates’ CASORT utility can be used to sort large files more efficiently and easily than an equivalent APL program. At the other end of the scale, DOS commands can be used to great benefit from the PC APL environment. For example, the DOS PRINT command is an asynchronous process, and so when invoked from within APL*PLUS PC, large files may be printed without delaying subsequent APL processing. This is particularly beneficial on 80286/80386 machines.
A good file design is essential for both ordinary IBM files accessed via shared variables, and for APL component filing systems. Techniques for improving IBM file access times usually involve changes that minimise file i/o. For example, this might be done by playing around with file record lengths or by introducing an in-workspace file buffer. (See references [9 10 11]). An APL component filing system can provide excellent opportunities for the efficient processing of APL data, especially when multi-user access is required.
Choosing appropriate structures for the major data objects in an APL system is also crucial, both for time and space efficiency. This will be briefly covered later.
If an APL compiler is available, recoding CPU-intensive functions for compilation is another avenue open to the optimiser.
But for now, we should return to a most popular optimisation technique, the one we will concentrate on most – recoding in APL.
Recoding in APL¶
Four techniques can be identified when using pure APL to recode for efficiency:
- Change the idiom
- Remove redundancy
- Use dynamic function-fixing
- Use a better algorithm
Changing the idiom is a common technique. The use of fast-functions falls into this category. In a recent project a line of code was sped up by 26% by replacing the original idiom by a different one. The original line, which catenated two large numeric matrices (see Figure 7), was buried inside a long loop, where the boolean compresssion vector B had been pre-computed outside the loop.
Z←(B/MAT1),MAT2 ⍝ Original idiom, B pre-computed outside loop
Z←MAT1[;I],MAT2 ⍝ New idiom, I pre-computed from B outside loop
Figure 7: Example change of idiom under APL*PLUS Mainframe
The new idiom uses a pre-computed index vector I to index the columns of MAT1, rather than compress them. This is a faster operation in VS APL and in APL*PLUS Mainframe.
In the same system, the original author was able to rewrite a sub-function in order to avoid transposing the argument and the result, as shown in Figure 8. The new function used a modified algorithm to unpack the un-transposed codes matrix. Removing the transposes saved 29% of the CPU time, and this saving was increased to 47% by using fast-functions. [5].
Figure 8: Avoiding two transposes saved 29%
A good understanding of the application can often allow redundant code to be identified and removed. In one system for example, the line of code in Figure 9 was being used to remove the rows of matrix MAT which were entirely zero. Not only is the inner-product algorithm expensive, but it turned out that the whole line was redundant; the operation had already been performed at an earlier stage of the processing. Removal of the line produced a significant benefit.
Figure 9: Remove expensive redundant code
In the same system it turned out that about 10% of the CPU time was going into the calculation of control totals on the reports. When questioned, the user admitted that he never looked at these totals, and offered the opinion that they were “something the programmers wanted”. Removing the control total calculations entirely might be a bit drastic, but modifying the application to provide the user with an option to omit them was an acceptable solution.
Savings can also be made by ensuring that invariant operations are removed from loops – ‘loop hoisting’. Again, this is only worth doing if the looping function proves to be a large consumer of CPU time. In critical cases a vector of case-statement labels formed by repeated catenations inside a loop can be replaced by a line that uses a pre-computed vector of labels, as in Figure 10.
LP:→(L1,L2,L3,L4,L5,L6)[CASE] ⍝ Old line
...
BRVEC←L1,L2,L3,L4,L5,L6 ⍝ New lines
LP:→BRVEC[CASE]
...
Figure 10: Loop hoisting in critical cases
Redundant operations can also be removed from within interpreter loops. For example, I recently came across a line of code similar to the following one, in which the dyadic-iota was consuming quite a lot of CPU time:
A reduction in processing time was achieved by performing the compression before the expensive lookup, without changing the result:
It is better to apply any selection operations as soon as you can in order to avoid unnecessary processing.
The technique of using quad-FX to dynamically fix a function is a type of ‘compilation’ which all APL users can exploit. I hesitate to mention it however, because it has one very serious drawback. The general idea is to build a character matrix which contains the lines of code that are to be executed, but using run-time knowledge to minimise the processing. The character matrix is then fixed to create the function. The approach may be indicated when the following conditions arise:
- Heavy processing inside a long loop
- Conditional code, much branching
- Execute is being used to execute constructed expressions
The benefit is faster code; there are no conditions, branches, executes or constructed expressions of any kind. The very serious drawback is that the code is usually much more difficult to write, debug, maintain, modify or optimise, because it is harder to understand.
In one VS APL optimisation effort this technique was taken to the limit; no less than 19 functions were dynamically fixed by the system, many of which still appeared at the top of the CPU list. In this particular case, all other avenues had been explored, and only this approach made the application feasible. (This was before the days of fast-functions and compilers.) This is a very rare case – in general the disadvantage far outweighs the benefit for applications programming, and the method should be avoided.
It is easier to justify in APL ‘systems programming’ or for building utilities of a special nature. [13].
Use a Better Algorithm¶
Before you can use a better algorithm you have to know what is wrong with the current one, and how to make improvements.
Because APL is an interpreted language, the efficiency of ‘small array’ problems can be considered distinctly from that of ‘large array’ problems. When applied to small arrays all the APL primitive operations take about the same amount of CPU time, because all the CPU is spent analysing syntax and managing memory. This means that the total CPU time is determined by the total number of distinct operations. On the other hand, for large arrays the interpretive overhead is relatively small compared to the time spent processing the elements, and the CPU time is determined by the type of operation being performed. To summarise:
- SMALL ARRAYS
- All primitives equivalent
- Most CPU in the syntax
- ==> CPU determined by the NUMBER of operations
- LARGE ARRAYS
- Interpretive overhead small
- Per-element time large
- ==> CPU determined by the TYPE of operations
This begs an interesting question; how large is a large array? On the APL*PLUS Mainframe system, the expression V+V takes about 700 machine instructions to analyse the syntax and perform setup operations, and only 7 machine instructions to actually add each pair of elements. This situation is summarised in Figure 11.
V+V
Number of elements in V
1 100 10,000
-------------------------
Overhead 700 700 700
Addition 7 700 70,000
Figure 11: Number of machine instructions to perform V+V on APL*PLUS MF
Notice that for a singleton vector the overhead dwarfs the time for the addition, whereas for 100 elements the CPU spread is balanced between overhead and productive processing. As the array grows larger the percentage of the time spent doing useful work increases, reaching 99% for 10,000 elements. This is why it is generally better to process arrays of data in APL rather than loop round processing scalars.
So, to get back to the subject, when optimising small array problems, the approach is to remove as much syntax and redundant baggage as possible, thereby producing as concise a solution as possible. For large array problems the techniques are different; we must look at the type of the operations being used, and in particular, the ‘order’ of the algorithm.
The ‘order’ of an operation is a way of describing how the processing time is expected to increase as the number of items to be processed increases. All of APL’s scalar functions are order-N, or linear, operations, that is to say the time to complete the operation is linearly proportional to the number of elements processed (N) when the arrays are relatively large. For example, we would expect the time for the expression V+V to double when the number of elements in V is doubled. Other primitives are associated with higher orders, the worst offenders including the inner and outer product, and the cases of index finder and membership where the interpreter performs a naive search.
The order of common APL primitives are listed in Figure 12.
ORDER FUNCTION
N Scalar functions, eg + - × ÷
Some cases of ⍳ and ∊ in advanced systems
NlogN ⍒⍋
Some cases of ⍳ and ∊ in advanced systems
1.5
N Inner products, ⌹
2
N Outer products
Some cases of ⍳ and ∊ in advanced systems
All cases of ⍳ and ∊ in VS APL
Figure 12: The order of some common APL operations
In VS APL the membership and index finder functions are notorious, achieving no better than N-squared time. In fact it is usually possible to write cover functions to these search operations which are actually faster than the primitives themselves. [15 9]. In more advanced APL systems, such as APL*PLUS Mainframe, these functions employ sophisticated algorithms the behaviour of which depends upon multiple factors, so that log and even linear time can be achieved.
The overall order of a complex algorithm may be determined by looking for the highest order of operation in the algorithm. One approach to optimisation could therefore attempt to recast the N-squared operations as lower-order algorithms, with a view to reducing the overall order.
As an example, consider the following example, taken from an STSC Newsletter article by Jim Weigang [12]. Figure 13 shows three variants of the COUNT function, which simply counts the number of 1s in its argument, the number of 2s, etc. COUNT1 uses an obvious APL approach – but the outer product makes it an N-squared algorithm. COUNT2 embodies a more subtle algorithm, using grade-up to sort the argument – this makes it order NlogN. Finally, COUNT3 employs a very naive ‘BASIC-style’ looping solution. No operation in COUNT3 is worse than linear, so the function as a whole is expected to have a linear order.
COUNT1 4 7 7 5 2 1 1 5 1 9
3 1 0 1 2 0 2 0 1
∇ Z←COUNT1 W
[1] ⍝ Outer product makes this an N-squared algorithm
[2] Z←+/(⍳0⌈⌈/W)∘.=W
∇
∇ Z←COUNT2 W;L;I;F
[1] ⍝ Sort, find last occurrence of each number, compute frequencies
[2] ⍝ ⍋ makes this oder NlogN
[3] W←W[⍋W] ⋄ L←W≠1⌽W ⋄ L[(0≠⍴W)/⍴W]←1
[4] I←0,L/⍳⍴L ⋄ F←(1↓I)-¯1↓I
[5] Z←(0⌈⌈/W)⍴0 ⋄ Z[L/W]←F
∇
∇ Z←COUNT3 W;I
[1] ⍝ Uses <W> as an index to increment appropriate result element
[2] ⍝ Scalar operations make this order N, a linear algorithm
[3] Z←(0⌈⌈/W)⍴0 ⋄ I←⍴W ⋄ →(I=0)/0
[4] LP:Z[W[I]]←Z[W[I]]+1
[5] →(0<I←I-1)/LP
∇
Figure 13: The three COUNT functions
The relative APL*PLUS Mainframe CPU timings as reported by Jim are listed in Figure 14. The first column is the number of elements in the argument, and the other columns show the function used. (The last column gives the results obtained for running the COUNT3 function compiled with the STSC APL Compiler.)
The results may surprise those belonging to the parallel-is-always-best school of APL thought. Let’s ignore the compiled function for a moment. For small arguments COUNT1 is the fastest because it uses the fewest operations, however, for larger arguments the order of the operation determines the time taken, and COUNT2 is the fastest. Even though it is linear, COUNT3 cannot hope to beat COUNT2 because it processes scalars. (You could say that COUNT3, although linear, has a very high coefficient of linearity.)
You may be surprised to see that the looping COUNT3 is at least twice as fast as the parallel COUNT1 for anything up to about 1,000 elements. Overall though, the COUNT2 function is probably the best one to store away in your utility workspace.
The high coefficient of linearity can be removed by compiling COUNT3. Freed of the interpretive overhead, the compiled version of COUNT3 reveals the great potential speed of the linear algorithm.
N COUNT1 COUNT2 COUNT3 COUNT3
compiled
1 7 19 14 6
10 10 24 71 8
100 179 50 622 19
1,000 15,740 357 6,327 136
10,000 WS FULL 4,113 62,752 1,490
Order: N-squared NlogN N N
Figure 14: Relative CPU times for the COUNT functions
As another example, consider the Index GENerator utility function IGEN, which produces a vector of index sets catenated together (see Figure 15). The timing results are shown in Figure 16. Also included are the times for IGEN4 compiled, and for the equivalent vendor supplied hand-crafted fast-function OIGEN. Some of the solutions are sensitive to the magnitude of each element, and some to the total number of elements. Timings were therefore performed on two different sets of data which produce the same length of result.
IGEN 3 0 4 2
1 2 3 1 2 3 4 1 2
∇ Z←IGEN1 W;L;B
[1] ⍝ Nested array solution
[2] Z←⊃,/⍳¨W
∇
∇ Z←IGEN2 W;L;B
[1] ⍝ ISO APL solution using outer product
[2] L←⍳⌈/W
[3] B←(W-~⎕IO)∘.≥L
[4] Z←(,B)/,(⍴B)⍴L
∇
∇ Z←IGEN3 W;W1;V
[1] ⍝ ISO APL solution using indexing
[2] W1←(W≠0)/W
[3] Z←(+/W1)⍴1
[4] V←1-¯1↓(~⎕IO),W1
[5] Z[¯1↓+\⎕IO,W1]←V
[6] Z←+\Z
∇
∇ Z←IGEN4 W;I;J;N;C
[1] ⍝ ISO APL solution using looping
[2] Z←(+/W)⍴W
[3] I←⎕IO
[4] J←⎕IO+''⍴⍴W
[5] N←0
[6] LP:→(I=J)/0
[7] C←W[I]
[8] Z[N+⍳C]←⍳C
[9] N←N+C
[10] I←I+1
[11] →LP
∇
Figure 15: The four IGEN functions
To put these timings into some perspective, consider that the nested array approach, when applied to the 1,000-element vector, takes nearly 1 CPU Second. It is of course much easier to write and to read (once you have mastered ‘iota-each’ and ‘catenate-reduction’). As usual, if you are willing to put in a little more effort you can do much better. The preferred solution in the absence of the fast-function or the compiled function, is IGEN3.
In more complex algorithms the overall order is not always as obvious as these examples would imply. ‘Catenate loops’ and ‘take/drop loops’ are good examples of subtle N-squared algorithms, for instance. Consider the code fragment in Figure 17, which shows a simple loop in which records are being appended to the end of a matrix. Maybe the function PROCESS is reading a vector from an IBM file via a shared-variable.
?100⍴100 ?1000⍴10
⍳¨ IGEN1 22 360
∘.≥ IGEN2 9 10
[] IGEN3 5 6
loop IGEN4 14 117
IGEN4 compiled IGEN5 2 8
fast-function ⎕IGEN 1 1.5
Figure 16: Relative CPU times for the IGEN functions
Timed on APL*PLUS Mainframe R5
Each unit = 2.7 Msec.
Figure 17: A typical catenate loop
Every time you go through the loop, a copy of MAT is made, a copy of REC is made, the new result is formed, which is then assigned to MAT again. This is unfortunate for two reasons: firstly a lot of data is moving around. If MAT starts off empty, and ends up with N rows, we can say that the average number of rows of data being moved by the interpreter will be half N. But we will go round the loop N times, so the total amount of data being shunted around will be half-N-squared. Hence we have an N-squared algorithm.
Secondly, this data copying places demands on the interpreter to continually allocate new blocks of storage, which is expensive and may well cause a fragmented workspace. Don’t worry, this is not as painful as it sounds, but it could result in a costly garbage-collection operation when a new block of storage is required each time through the loop.
The problem can be reduced to linear time by replacing the catenate loop by an indexed-assignment loop instead. The simplest case, when you know how many rows there will be in advance, is shown in Figure 18. In other cases it is still possible to use this technique, but you will have to extend the matrix once the available rows have been filled.
Figure 18: An alternative to the catenate loop using indexed assignment
To give you an idea of the saving possible, I recently performed such a replacement in a system which was reading integer vectors via IBM’s AP 110, in a situation where a block-read was not a possible solution. The resulting function ran 21 times faster. (Subsequent compilation gave an overall 50-fold speedup.)
A similar problem occurs in a ‘take/drop’ loop, a template of which is shown in Figure 19.
Figure 19: A typical drop loop
Beneficial results are again obtained by replacing the code by an indexed assignment method. I would like to thank Clark Wiedmann for these examples, taken from his excellent APL*PLUS Compiler course.
The aim is to reduce the overall order of the algorithm as much as possible, hopefully achieving log or even linear time. In many cases you can replace a search type algorithm by a linear indexing operation. For example, suppose that you want to remove the duplicates from a set of integers in a known range. You may use the common utility called DUPSOUT or NUB, shown in Figure 20. The dyadic-iota in NUB can take a lot of time, especially if the vector is a very long one. If you do not mind getting the unique elements in ascending order, then you can use the alternative function SNUBRANGE, which uses a linear indexing operation. You have to know what the largest element in the set will be, and pass it in as the left argument.
∇ Z←NUB W
[1] ⍝ <Z> is the NUB of the elements of the vector <W>
[2]
[3] Z←((W⍳W)=⍳⍴W)/W
∇
∇ Z←A SNUB∆RANGE W;B
[1] ⍝ <Z> is Sorted NUB of integers in set <W>
[2] ⍝ Elements of <W> must be in the RANGE ⎕IO to <A>-~⎕IO
[3]
[4] B←A⍴0
[5] B[W]←1
[6] Z←B/⍳⍴B
∇
⍝ These timings made on APL*PLUS PC R7 on an Olivetti M21
I←?5000⍴10000
Q1←NUB I ⍝ 26.4 Seconds
Q2←10000 SNUB∆RANGE I ⍝ 1.6 Seconds
Q1[⍋Q1]≡Q2 ⍝ SNUB∆RANGE result is sorted
1
Figure 20: Alternative NUB function for integers in a known range
Another example is the use of dyadic grade to replace inner-product table lookup algorithms by equivalent order NlogN code. Figure 21 shows a typical function for removing the duplicate rows from a character matrix. Dyadic grade-up on the character matrix is used to bring matching rows together prior to deleting the duplicates. If your APL system has this facility, you can use it to develop a complete set of fast character matrix manipulation utilities.
∇ Z←MATNUB∆IP W;I;U;B
[1] ⍝ Remove duplicate rows of matrix <W>
[2]
[3] Z←(∨⌿<\W∧.=⍉W)⌿W
∇
∇ Z←MATNUB W;I;U;B
[1] ⍝ Remove duplicate rows of character matrix <W>
[2] ⍝ Uses dyadic grade for speed
[3]
[4] I[I]←+\∨/U≠¯1⊖U←W[I←⎕AV⍋W;]
[5] B←(⍳⍴I)=I⍳I
[6] Z←B⌿W
∇
⍝ These timings made on APL*PLUS PC R7 on an Olivetti M21
A←⎕NL 3
⍴A←A[?100⍴1↑⍴A;]
100 13
⍴Q1←MATNUB∆IP A ⍝ 54.9 Seconds
18 13
⍴Q2←MATNUB A ⍝ 0.9 Seconds
18 13
Q1≡Q2
1
Figure 21: An alternative to inner product in MATNUB
Know your Interpreter¶
The APL philosophy largely protects the user from the idea of data-types, although under the covers APL interpreters are not all the same. Most systems use different internal representations for each type of data.
The more you know about your system the better, especially in terms of the data representations, and how they behave under common operations. How much storage does your APL take to represent an integer? A decimal number? A boolean value? Also, an understanding of the primitives and how they may be used to produce alternative solutions to problems is valuable.
As an example, look at the common problem of selecting records from a large matrix, consisting of many ‘records’ and few ‘fields’. This operation is typically performed prior to special processing on the data, and may even occur within a loop, where the records to be selected have been pre-computed before entering the loop.
The choices before you are whether to use indexing or compression, and what orientation of your matrix to choose, i.e. whether to select rows or columns. To do some timing tests I set up a random 1000 by 20 matrix MDEEP and two boolean vectors BR and BC which can compress rows and columns of MDEEP respectively. From these were computed MWIDE, the equivalent ‘wide’ form of the same matrix, and IR and IC, vectors of indices corresponding to BR and BC, which can be used for indexing. The results for timings under APL*PLUS Mainframe R5 are summarised in Figure 22.
Integer Floating Boolean
MDEEP← ?1000 20⍴10 .9×?1000 20⍴10 1000 20⍴1 0
MWIDE←⍉MDEEP 18.8 32.2 12.7
IR←BR/⍳⍴BR 1.3 1.4 1.4
IC←BC/⍳⍴BC 0.1 0.1 0.2
BR⌿MDEEP 5.6 10.4 5.3
MDEEP[IR;] 16.6 20.9 15.2
BR/MWIDE 22.4 16.4 33.0
MWIDE[;IR] 16.3 21.1 19.1
BC/MDEEP 22.0 25.1 29.9
MDEEP[;IC] 13.2 16.7 14.8
BC⌿MWIDE 2.2 4.3 1.2
MWIDE[IC;] 10.6 14.0 9.5
NB:
BC/MDEEP 21.5
⍉BC⌿MWIDE 15.3 !!
CPU time in Msec. using APL*PLUS Mainframe R5.
Figure 22: Timings for alternative matrix selection expressions using APL*PLUS Mainframe R5.
Similar timings were observed with VS APL, the predecessor to APL*PLUS Mainframe. However, the following list of observations relates to the specific set of timings above, and should not be assumed for other APL systems, or for different environments. APL2 users beware: you may be surprised to find these results reversed. Interesting points to notice include:
- Transpose is expensive
- Compressing rows is faster than indexing them
- Indexing columns is faster than compressing them
- The same pattern is observed when selecting ‘wide’ records
- Selecting rows of the wide matrix is very fast
- No extra surprises with the floating data
- Compressing columns from a boolean matrix is very slow
We can surmise why some of these results pertain. The fast selection of rows, especially long ones, could be caused by the use of a ‘block move’ instruction for transferring contiguous bytes of memory from subject to object matrix, possible because arrays are stored in their ‘ravel’ order.
The comparative slowness of the boolean column selection operations can be explained by realising that the interpreter is engaging in much tedious unpacking and repacking of the 8-to-a-byte bits.
A similar experiment on APL*PLUS/PC R6, with 2-byte integers and 8-byte reals, gave the results in Figure 23. Indexing columns was again faster than compressing them (about 14%), but this time indexing rows was also faster (about 8%) than compressing them.
Integer Floating
MWIDE← ?10 1000⍴99 .5×?10 1000⍴99
I←B/⍳⍴B 0.1 0.1
B/MWIDE 1.0 2.1
MWIDE[;I] 0.9 1.8
MDEEP←⍉MWIDE 0.8 0.9
B⌿MDEEP 1.0 1.9
MDEEP[I;] 1.0 2.1
CPU time in Seconds, using APL*PLUS PC R6 on an Olivetti M21 with
8087 maths coprocessor.
Figure 23: Timings for alternative matrix selection expressions using APL*PLUS PC R6.
Have you ever thought of setting ⎕CT to zero? (All those with virulent ⎕CT phobia should quickly skip the next few paragraphs.)
When performing certain comparison operations APL shows tolerance when deciding whether two quantities are equal. This comparison tolerance usually applies for floating point numbers and large whole numbers, and is controlled by the setting of the system variable ⎕CT. Most APL systems put a limit on the largest value of ⎕CT in order to ensure that no two integers can be tolerantly equal. This allows the interpreter to skip the tolerance calculation for integers, producing the answer more quickly. For floating point numbers however, a tolerant calculation is performed.
But this applies even to whole numbers which are not integers, for example in APL*PLUS/PC, a number which exceeds the 2-byte limit of 32,767. Consider the lookup expression V iota V, performed on a vector V of one thousand 8-byte whole numbers, perhaps a set of packed dates or times. Figure 24 summarises the findings for three APL systems.
Tolerant Comparison
V←?1000⍴1E10
V⍳V V⍳V
Default ⎕CT ⎕CT←0 Speedup
APL*PLUS PC R7 87secs 78secs 10%
APL*PLUS MF R5 25msecs 5msecs 80%
VS APL 792msecs 796msec
Fig24: The effect of ⎕CT←0 when comparing large whole numbers
APL*PLUS PC timing on Olivetti M21 with 8087 co-processor
With the default setting of ⎕CT, APL performs the tolerance calculation. When ⎕CT is set to zero, some systems will skip the calculation (or perhaps some machines perform a hardware multiply-by-zero very quickly). The poor performance of VS APL is due to the naive dyadic-iota algorithm. Savings can often be made, with particular impact in the PC environment.
By the way, do not forget to reset ⎕CT to the default value afterwards, or you might encourage your application to behave differently thereafter. The proper way to restrict the effect of resetting ⎕CT is to localise it in an appropriate sub-function.
I apologise for the absence of results from other systems. I am not attempting to sell the merits of any particular APL in this article – I just make timings on those systems available to me. Perhaps someone will send VECTOR similar results for other systems, particularly APL2.
Perhaps a more common example is the comparison of alternative methods of justifying a character array. The two code fragments of interest are:
Z←(-+/∧\⌽' '=W)⌽W ⍝ Right-justify: rotate booleans
Z←(-+/∧\' '=⌽W)⌽W ⍝ Right-justify: rotate characters
It turns out that VS APL and APL*PLUS MF are faster rotating booleans than characters, whereas APL*PLUS PC is faster rotating characters than booleans (actually 2-byte integers).
It is worth repeating that system-dependent optimisations of this kind should be made with care, since the benefits may not transport between different APL interpreters, or even between different releases of the same interpreter. [9].
Data and File Design¶
This was not supposed to be an article about data design or file efficiency specifically, but the presentation on which it was based included a foil containing these efficiency tips relating to the design of data structures in APL:
- Do a data design for the major data structures
- Keep logically distinct data in separate structures
- Do not mix different data types together in one structure
- it wastes space
- is hard to modify
- it causes the interpreter to work hard packing/unpacking
- a nested array may be effectively used to store logically related data of different type in a single structure
- Consider the orientation of matrices
- Consider data-packing techniques
- using base value/representation (decode/encode)
- by modifying data types
- Imagine you are the interpreter, doing the work
And these relating to efficiency with files:
- Do a file design
- Structure files – have a directory
- Estimate CPU and elapsed time requirements
- Minimise file reads by
- increasing file block sizes
- ‘caching’ data in the workspace
- Use host services where possible
- Accumulate file update requests and apply them at once
- Store frequently accessed data in the file directory
Some aspects of improving file efficiency in the IBM environment are covered in references [10 11].
Efficiency with Nested Arrays¶
No talk on efficiency would be complete without reference to this topical and contentious subject. The foil from the presentation contained the following hard-learned lessons:
- Do a careful data structure design
- Keep logically distinct data in separate arrays
- Use the simplest structure possible
- Avoid using ‘mixed’ arrays for the major data structures
- Use the ‘each’ operator wisely
It is tempting to believe that packing every single piece of data into one great big nested array is somehow ‘efficient’. If you do this you will undoubtedly regret it; it is hard to understand and modify, difficult to write appropriate data access code, and can lead to serious performance problems, in particular with regard to file i/o. It usually results from an inappropriate (or absent) data design.
Similarly, do not get suckered into using a ‘deep’ array when a ‘shallow’ one will do; why use a vector of vectors when a matrix is just as good? (If the ‘inner’ vectors are all the same length then it is certainly inappropriate.)
I learned this the hard way – my first excursion with APL2 resulted in a depth five data structure, each level of which corresponded to one level of corporate consolidation. As the system developed it became harder and harder to traverse the structure and to perform arbitrary operations at the level I wanted. Modification to the structure (e.g. adding a new intermediate consolidation level) became unthinkable. Luckily for me the system was built for demonstration and teaching purposes only (a purpose for which it is now very well suited).
Later on it turned out that the whole lot could be replaced by a depth two matrix. This had a number of advantages: it was simpler, easier to understand, easier to ‘traverse’, much easier to modify (adding a new consolidation level now meant adding a new row to the matrix). In addition it became apparent that an identical structure could be used for another part of the system, and that a common set of access functions could be written.
Last year, a colleague achieved a threefold speedup of a customer’s application by replacing a depth four structure by a depth two structure, and of course modifying the access functions.
For most commercial applications a depth two nested array is deep enough.
This is no reason to shy away from ‘second generation’ APL code however. Nested array facilities can be very effective, rewarding us with excellent productivity gains, in the area of systems programming (testing, debugging, one-off utilities) as well as in applications.
If you do have nested arrays, then use them freely. Part of the system testing phase should include a monitoring exercise; you may well find that the CPU bottleneck is in some nested array code. At that stage you can take the time to recode the offending fragment into traditional APL. In this way the best tradeoff between productivity and efficiency can be obtained. The trick is never to let the real hog code reach the user.
The APL2, APL*PLUS and Dyalog ‘each’ operator can be a rather good little CPU-gobbler if used carelessly, however. It really is just a hidden loop – something that most APLers would normally recognise as undesirable. A small example will demonstrate the perils of ‘each’.
Suppose you have a vector of character matrices, of varying sizes, and you want to left justify each one. You might think “Ah yes, first I have to find where the blanks are”. Fine – so you write on a piece of paper:
“Hmmm, because ‘equals’ is pervasive (you cleverly remember), I now have a vector of boolean matrices, so I need to do an and-scan on each one – I’d better use ‘each’.” So you write:
“Right – now to add up the number of ones in each row of each boolean matrix”, you continue:
“All I need to do now is rotate each matrix by each of the integer vectors I’ve just produced”:
Then you proudly sit back and look at the result. You type it in. It works! (So it must be right.) Maybe you even embed it into a utility function called LJUSTEACH.
What you have just done of course is to commit at least two cardinal APL sins; you looped three times and you re-invented the wheel. The nasty specks all over the screen are what Alan Graham of IBM referred to as ‘pepper’ in a presentation at APL87. They may not make you sneeze, but are just as irritating.
What you should have done of course is to remember the LJUST utility you wrote ages ago. It looked like this:
It works fine on ordinary old character matrices, so you can apply it to each character matrix in the vector of matrices:
This approach has some advantages:
- It exploits an existing utility
- It is easier to write, read and understand
- It is easier to modify
- It executes faster because it uses only one ‘each’
This emerging coding style with ‘each’ can be summarised as follows:
- Solve the problem for SIMPLE arrays first
- Put your simple array solution into a defined function
- Use the defined function with the each operator
Finally, I would like to write about the benefits of using an APL compiler. I would like to, but this article is already overlong (it could certainly do with optimising). If there is interest, this topic rightfully deserves an article of its own.
If I may finish by stealing another Alan Graham line, I should remind you that if your program has not yet been optimised, then it must be pessimised.
References and Bibliography¶
- Glenford J Myers, Reliable Software through Composite Design, Van Nostrand Reinhold Company, N.Y.
- David Piper, Technical Correspondence, VECTOR Vol 3. No 4. p109, April 1987.
- Jonathan Barman, APL and Partitioned Data, VECTOR Vol 1 No 1 p127, May 1984.
- Bob Smith, A Programming Technique for Non-Rectangular Data, APL79 Conference Proceedings p362-367, Rochester N.Y.
- Jonathan Barman, Cocking & Drury Ltd, private communication.
- P Wortham, APL*PLUS PC and Assembler (Part 1), VECTOR Vol 4 No 2 p107, October 1987.
- P Wortham, APL*PLUS PC and Assembler (Part 2), VECTOR Vol 4 No 3 p109, January 1988.
- Romilly Cocking, Cocking & Drury Ltd, private communication.
- Eugene McDonnell, Technical Correspondence, VECTOR Vol 3 No 2 p94, October 1986.
- John Sullivan, Faster File Input in TSO, VECTOR Vol 4 No 1 p99, July 1987.
- Lori D McNichols, Fast I/O – Efficient file Processing, APL88 Conference Proceedings.
- Jim Weigang, Understanding Execution Time, STSC Newsletter, 1987.
- David Piper, Using quad-FX to Facilitate the Use of APs, VECTOR Vol 3 No 2 p123, October 1986, and VECTOR Vol 3 No 3 p130, January 1987.
- Bernard King, APAT: First Impressions, Software Review, VECTOR Vol 1 No 2 p44, October 1984.
- Phil Last, Technical Correspondence, VECTOR Vol 2 No 3 p97, January 1986.
Other Useful References¶
David Piper, Using Name Association for Data Translation, VECTOR Vol 3 No 4 p109, April 1987.
David Piper, A Command Driven Interface for BDAM and QSAM APs using APL2 under TSO, VECTOR Vol 3 No 3 p125, January 1987.
Clark Wiedmann, Efficiency in the APL Environment – A Full Arsenal for Attacking CPU Hogs, APL85 Proceedings, Seattle, Washington.
Jim Lucas, Making APL Cheap – Saving Time and Money, APL88 Conference Proceedings.