Technical Correspondence

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

After many years doing APL, followed by fewer years of retained interest in APL, I am still amazed by the abysmal quality of some of the code being published in Vector. One of the major objections to APL in the commercial world is the production of write-only code. The article in Vector 14.2 on Niven Numbers is a perfect exemplar of the coding style that creates such negative reactions. Whilst this article is academic in nature, Vector is a (arguably the) showcase for APL code. All code published here should be of a high quality, or at least ultimately form a contribution to high quality code (maybe as part of a learning exercise). Take the function NIVEN2; it can be criticized for at least the following features:

• use of single character names;
• multiple assignments on a single line;
• complex path analysis (75% of the lines include conditional branches).

The attempt to make the code more efficient (NIVENB) simply exaggerates these features and gives rise to an unrewarding 4% benefit. Clearly the structure of the code is not the source of the performance issue, it is far more likely that the algorithm is to blame. Algorithmically the functions given can be criticized on (at least) two fronts:

• repeated catenation of new result values to the result vector;
• evaluation of only one candidate result at a time.

Below is a version of the algorithm which avoids the repeated catenation issue. This is an easy change to make since we know from the right argument how many result values are required:

∇Z←NIVEND W;candidate;digits;pos
 Z←((W⌈0)⍴0)
 candidate←0
 pos←1
 →(W≤0)/end
next:candidate←candidate+1
 digits←((1+⌊10⍟candidate)⍴10)⊤candidate
 →(0≠(+/digits)|candidate)/next
 Z[pos]←candidate
 pos←pos+1
 →(W≥pos)/again
end:
∇

In performance terms this version shows a significant improvement (here are some relative timings for cases > 1000):

The penalty in performance below 1000 is certainly due to the "style" of the code - this algorithm implemented in the style of NIVEN1 shows a constant improvement of about 10% over the more readable version presented above. For the 100000 case, the saving due to changing the algorithm is 73%, the saving from changing the code style is about 3%.

This illustrates a vitally important point:

as the amount of useful computation increases as a proportion of the total the overheads due to "style" or other factors become less important; in general pursuit of algorithm is more beneficial than sacrificing readability for marginal gains in efficiency.

Despite the effectiveness of the gains made so far, greater gains become available by implementing the algorithm in a way suited to APL. The solutions presented are scalar in nature - each scalar is tested in turn. APL is an array processing language, so an array based solution should be sought. In contrast to the statement made in the original article that …it would be a challenge to find an algorithm… the changes required are fundamentally simple:

∇Z←A NIVENE W;candidates;digits;hits;max
 Z←((W⌈0)⍴0)
 candidates←⍳A
 →(W≤0)/end
next:max←(↑⍴candidates)⊃candidates
 digits←((1+⌊10⍟max)⍴10)⊤candidates
 hits←0=(+/digits)|candidates
 Z←Z,hits/candidates
 candidates←candidates+A
→(W>⍴Z)/again
 Z←W↑Z
end:
∇

The algorithm implemented in this function generates groups of candidates and tests the content of each group in parallel. The size of the group is determined by the left argument to the function. At first sight this algorithm may seem inefficient since it potentially generates too many result values, however the cost of this marginal inefficiency is far outweighed by the gains resulting from the parallelism of the algorithm as a whole. The performance of this improved algorithm is illustrated in the following table:

The performance of the algorithm does depend on the value chosen for chunking size. An optimal choice seems to be a value close to that in the right argument, though the reasons for this are not clear. Re-writing this algorithm in the style of NIVEN1 did not give a noticeable performance benefit (<1% in all cases compared to NIVENE). The function given can be subjected to a criticism made of the original - the use of repeated catenation to form the result. Note, however, that the catenation will be performed far fewer times and a (potentially large) number of results is appended in each operation.

The point is best made by the principle expressed in Normal Thomson’s article in the same edition of Vector - think, reason, express. Once a simple method has been thought up, reason it through to create an algorithm suitable for array processing. Then this can be expressed in a clear and meaningful manner. In my experience, only rarely is there a need to sacrifice clarity for performance.

David Piper