In Praise of Magic Functions: Part II

Part I of this post was concerned with the development speed and execution speed of magic functions and should be read before this post.

Benefitting from Future and Past Improvements

Looking at the magic function for key in Part I, we see that its performance depends on the following APL primitives, listed with information on when they were last improved (or when they will be improved):

Key was introduced in version 14.0 and x{⍺,f⌿⍵}⌸y is currently computed by the general case. Comparing the speed in version 14.0 to 15.0 as of June 2015:

   x←?1e6⍴5e4
   y←?1e6⍴0

   1 1 cmpx 'x{⍺,+/⍵}⌸y'    ⍝ 14.0
0.1735

   1 1 cmpx 'x{⍺,+/⍵}⌸y'    ⍝ 15.0
0.12855

   0.1735 ÷ 0.12855
1.34967

a factor of 1.3 improvement without touching the key code. Special code had been planned for {⍺,f/⍵}⌸, and we can get an idea of the amount of speed up:

   cmpx 'x{⍺,+/⍵}⌸y' '(∪x),⍤0⊢x{+/⍵}⌸y'    ⍝ 15.0
 x{⍺,+/⍵}⌸y       → 1.25E¯1 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
 (∪x),⍤0⊢x{+/⍵}⌸y → 1.16E¯2 | -91% ⎕⎕⎕

Perhaps the special code for {⍺,f/⍵}⌸ can be a magic function?

Magic functions also benefit from past improvements. The primitive ⍕b (in the Suggestivity subsection below) has a magic function implementation: MAGIC("(¯1+2×≢⍵)⍴(2 2⍴'0 1 ')[⍵;]⊣⎕io←0"). Then I thought, why not get an extra level of performance by doing it in native C? Benchmarks done after that work showed that the native C implementation was faster by a factor of 25 but the magic function was faster by a factor of 40. What happened? On reflection, the speed of the code depends crucially on the speed of x[b;…;] and it turned out that x[b;…;] was previously sped up (version 13.2). Apparently the x[b;…;] code is faster than a casually-written C program.

Finally, I expect magic functions are prime candidates for being fed to the APL compiler when it becomes possible to do so.

APL as a Tool of Implementation

Being APL code, magic functions have the characteristic terseness of APL and all that that entails. K.E. Iverson’s 1979 Turing Lecture Notation as a Tool of Thought lists five important characteristics of notation. We examine how they play out in this context.

Ease of Expression
Notation as a Tool of Thought entitles this characteristic as “ease of expressing constructs arising in problems”, explicated as follows (§1.1):

For magic functions, the analogous concept would be facility in program development, debugging, tracing, profiling, benchmarking, and other activities required in implementation. Dyalog APL has these in spades.

Suggestivity
It was first identified that ⍕b can be sped up by doing (¯1+2×≢⍵)⍴(2 2⍴'0 1 ')[⍵;]⊣⎕io←0, the idea being that if f is an expensive function and x is from a small domain D, then f x can be computed by (f D)[⍵;]. (A similar idea is described in §4.3 of Notation as a Tool of Thought.) For the idea to be effective, f does not have to be very expensive, just more expensive than indexing, and x is sufficiently large. A few speed-ups in the pattern have been identified:

All of these can be implemented by magic functions. As well, the utility of the pattern (f D)[i;] motivates extra attention on x[i;…;]. Fortuitously, x[b;…;] has previously been made fast.

Subordination of Detail
Writing in APL means not having to deal with many details involved in writing in C in the interpreter, including:

• workspace compaction
• arrays changing their internal datatype
• call by name
• allocating and releasing memory
• index errors AKA memory read and write exceptions
• different numeric types
• different character types
• loops and nested loops
• declarations
• etc.

Economy
Economy refers to the size of the vocabulary and the complexity of the grammar. Here, the comparison is not just between APL and C (in which comparison APL wins), but between APL and the collection of programs, utilities, macros, data structures, typedefs, calling conventions, …, accumulated by the C source code over the years. These have not been as rigorously defined and executed as APL.

Amenability to Formal Manipulation
The opening paragraph of the present text had a different magic function for ∧.= in a previous version. In repeated readings of the MSS and in meditation on the ideas I realized that the line of code can be made simpler:

MAGIC("((≢⍺)↑i)∘.=(≢⍺)↓i←⍺⍳⍺⍪⍉⍵");    ⍝ old version
MAGIC("(≢⍺)(↑∘.=↓)⍺⍳⍺⍪⍉⍵");           ⍝ current version

I daresay that such simplification would be harder to conceive with a more verbose statement of the algorithm.

Follow