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):

expression factor version
⍋i 2-18 12.1
⎕DR 1-3.8 14.1
⍳⍨x 2-4 14.1
⍳⍨i 3-6 14.1
↑x 5-12 15.0
⊂[a]x 1-1.75 15.0
b⊂[⎕IO]x 1.3-42 14.1

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):

If it is to be effective as a tool of thought, a notation must allow convenient expression not only of notions arising directly from a problem, but also of those arising in subsequent analysis, generalization, and specialization.

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:

⍕b
x⍕b
float ⍳ b
float ⍳ int8
scalar×b and b×scalar
scalar*b

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.

In Praise of Magic Functions: Part I

A magic function is an APL-coded (dfn) computation in the C source of the interpreter. For example, some cases of ∧.= are coded as MAGIC("(≢⍺)(↑∘.=↓)⍺⍳⍺⍪⍉⍵"). The rubric “magic function” includes magic functions and magic operators.

Acknowledgments. Magic functions in Dyalog are made possible due to work done by John Scholes and Richard Smith.

Development Speed

A magic function implementation takes an order of magnitude less time to write than a C-coded implementation. A case in point is ∘.≡ (and ∘.≢) on enclosed character vectors, as recounted in the blog post A Speed-Up Story. The chronology is recovered from the G-mail, Mantis and SVN systems.

2014-10-27 04:24 Nicolas initial e-mail describing the problem
2014-10-27 07:33 Roger proposes i∘.=i←a⍳a as a solution
2014-10-27 07:36 Jay objects that solution should check ⎕CT
2014-10-27 07:40 Roger responds to objection
2014-10-27 10:29 Roger creates Mantis issue
2014-10-27 13:57 Roger SVN commit
2014-10-27 18:12 Roger reports factor 6-64 speed-up and submits blog post
2014-10-28 16:33 Roger SVN commit to fix a bug

After checking that ⎕CT is not required, the main processing in the C source is as follows:

  • 1 iff a “selfie”, i.e. the left and right arguments are equal as C pointers
  • eq 1 if ∘.≡ ; 0 if ∘.≢
  • 1 iff the right argument has rank 1
#define CASE(x,y,z)  ((x<<2)+(y<<1)+(z))

switch(CASE(c,eq,r))
{
  case CASE(0,0,0): MAGIC("((,⍺)⍳⍺)∘.≠((,⍺)⍳⍵)"); break;
  case CASE(0,0,1): MAGIC("(  ⍺ ⍳⍺)∘.≠(  ⍺ ⍳⍵)"); break;
  case CASE(0,1,0): MAGIC("((,⍺)⍳⍺)∘.=((,⍺)⍳⍵)"); break;
  case CASE(0,1,1): MAGIC("(  ⍺ ⍳⍺)∘.=(  ⍺ ⍳⍵)"); break;
  case CASE(1,0,0): MAGIC("∘.≠⍨(,⍵)⍳⍵");          break;
  case CASE(1,0,1): MAGIC("∘.≠⍨  ⍵ ⍳⍵");          break;
  case CASE(1,1,0): MAGIC("∘.=⍨(,⍵)⍳⍵");          break;
  case CASE(1,1,1): MAGIC("∘.=⍨  ⍵ ⍳⍵");          break;
}

Execution Speed

Development speed for a magic function need not be at the expense of execution speed. As indicated above, ∘.≡ is 6 to 64 times faster than the previous (C coded) implementation. Factors for a few other magic function implementations:

expression factor version
x∘.≡y and x∘.≢y 6-64 14.1
x∧.=y and x∨.≠y 1.5-4 14.1
,/y 1-∞ 15.0
x⊥y 1-26 15.0
x⊤y 1-3.3 15.0

One can always make a magic function faster by hand-translating it from APL into C, and in so doing save on the tokenizing (scanning) and parsing costs. However, the effort increases the development time and the code size (see Special Cases below) for (I argue) not much reduction in execution time. I also expect that such translation can be done automatically by the APL compiler in the future.

Accurate estimates for the amount of speed up obtain readily from APL benchmarks. For example, x⍕b where x is a scalar or 2-element vector and b is a Boolean array, is a candidate for a magic function implementation, and:

   f←{((¯1↓s),(⊃⌽⍴t)×⊃⌽s←⍴⍵)⍴(t←⍺⍕⍪0 1)[⍵;]}

   b←1=?10⍴2     ⍝ small argument
   cmpx '2 f b' '2⍕b'
 2 f b → 5.83E¯6 |    0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
 2⍕b   → 1.23E¯5 | +110% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

   b←1=?1e6⍴2    ⍝ large argument
   cmpx '8 2 f b' '8 2⍕b'
 8 2 f b → 9.75E¯3 |     0% ⎕
 8 2⍕b   → 3.35E¯1 | +3339% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

We can say with confidence that x⍕b can be made 2 to 34 times faster before actually proceeding with the implementation.

Magic functions can be used when execution speed is not paramount. For example a problem was reported with !∘y⍣¯1:

   !∘25⍣¯1 ⊢ 1e4
DOMAIN ERROR
   !∘25⍣¯1⊢10000
  ∧

The problem can be solved readily with an APL function using Newton iteration, with a relatively complicated computation for the initial estimate:

   f←{-∘⍵∘⍺⍺{⍵-(⊃t)ׯ0.01÷-/t←⍺⍺ ⍵×1 1.01}⍣≡⊃⍋|⍵-(⍳!⊢)⌊0.5+⍺⍺ 1}
   ⎕←x←!∘25 f 1e4
3.85142
   x!25
10000

General Case vs. Special Cases

Magic functions are well-suited for implementing operators. An operator has potentially tens or hundreds of cases, and it would be onerous, not cost-effective and unnecessary to write code for each case. Instead, the general case can be implemented quickly and succinctly by a magic function, and the saved effort can be devoted to cases deemed worthy of attention. The rank and key operators are done this way. The magic function for the general case of key:

MAGIC(
  "0=⎕nc'⍺':⍵ ∇ ⍳≢⍵    ⋄"  // monadic case: f⌸ x ←→ x f⌸ ⍳≢x
  "⍺ ⍺⍺{⍺ ⍺⍺ ⍵}{        "
  "  ⎕ml←1             ⋄"  // needed by ↑⍵ and ⍺⊂⍵ 
  "  j←⍋i⊣⎕dr i←⍳⍨⍺    ⋄"
  "  ↑ (⊂[1↓⍳⍴⍴⍺]((⍳≢i)=⍳⍨i)⌿⍺) ⍺⍺¨ (2≠/¯1,i[j])⊂[⎕io]⍵⌷⍨⊂j"
  "}⍵                   "
);

Before execution reaches the general case, special cases are detected and are implemented by special code, usually in C. These special cases are:

operand version comment
{f⌿⍵} and ⊢∘(f⌿) 14.0 for f one of + ⌈ ⌊ or (for Boolean right arguments) one of ∧ ∨ = ≠; also / instead of for vector right arguments
{⍺(f⌿⍵)} 15.0 for f as above
{⍺,f⌿⍵} 15.0 for f as above and numeric left arguments
{≢⍵} and ⊢∘≢ 14.0
{⍺(≢⍵)} 14.1
{⍺,≢⍵} 14.1 for numeric left arguments
{≢∪⍵} 14.1
{⍺(≢∪⍵)} 14.1
{⍺,≢∪⍵} 14.1 for numeric left arguments
{⊂⍵} and ⊢∘⊂ 14.0
{⍺⍵} 14.1
{⍺} and 14.1 ⊣⌸x ←→ ∪x if were extended like

Additional special cases can be implemented as required.

Special Cases

Since magic functions are so terse, sometimes it is worthwhile to make special cases which would not be made special cases if the implementation were more verbose and/or require more effort. The implementation of ∘.≡ (in the Development Speed section above) illustrates the point. In general, x∘.≡y ←→ ((,⍺)⍳⍺)∘.=((,⍺)⍳⍵). However, if x is a vector, the two ravels can be elided; moreover, if x and y are equal as C pointers, the two uses of can be reduced to one use (not only that, but to a “selfie” ⍵⍳⍵ if a vector). So instead of the one case:

MAGIC("((,⍺)⍳⍺)∘.=((,⍺)⍳⍵)");

we have

switch(CASE(c,eq,r))
{
    …
  case CASE(0,1,0): MAGIC("((,⍺)⍳⍺)∘.=((,⍺)⍳⍵)"); break;
  case CASE(0,1,1): MAGIC("(  ⍺ ⍳⍺)∘.=(  ⍺ ⍳⍵)"); break;
    …
  case CASE(1,1,0): MAGIC("∘.=⍨(,⍵)⍳⍵");          break;
  case CASE(1,1,1): MAGIC("∘.=⍨  ⍵ ⍳⍵");          break;
}

The extra cases are not too burdensome, and their detection is done in scalar code at which C is better than APL. The following benchmarks illustrate the difference that the special cases make:

   t ←' zero one two three four five six seven eight nine'
   t,←' zéro un deux trois quatre cinq six sept huit neuf'
   t,←' zero eins zwei drei vier fünf sechs sieben acht neun'
   u←1↓¨(' '=t)⊂t

   x←u[?300⍴≢u]    ⍝ vector selfie vs. non-selfie
   y←(⍴x)⍴x
   cmpx 'x∘.≡x' 'x∘.≡y'
 x∘.≡x → 1.48E¯4 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
 x∘.≡y → 1.93E¯4 | +30% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

   x1←(1,⍴x)⍴x     ⍝ matrix selfie vs. non-selfie
   y1←(⍴x1)⍴x1
   cmpx 'x1∘.≡x1' 'x1∘.≡y1'
 x1∘.≡x1 → 1.50E¯4 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
 x1∘.≡y1 → 1.97E¯4 | +31% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

To be continued…Part II will describe the benefits from future improvements and APL as a tool of implementation.

Response to Name Colouring for Dfns

This post contains comments to John Scholes’ post on name colouring; please continue to post any further comments with the original post.

This is a very interesting topic – as the discussion has already showed, there are many different needs. It seems to me that some of the suggestions that have been made are forms of highlighting that you would want to turn on briefly in order to search for something specific or highlight structures while editing code. For example:

  • to verify the structure (highlight the matching parenthesis or bracket, or rainbow colouring of parentheses/brackets)
  • highlight all uses of a particular name or small group of names.

I don’t think I would really want any of these enabled for any length of time; some of them can probably work very well if they are turned on and off as the cursor moves through the text (when on a parenthesis, highlight the other half of the pair, when on a name, highlight all uses of that name, etc).

Making it easier to read statements through highlighting of “kinds” feels more like something that I might well want to have enabled all the time. However, I find colouring to be quite distracting – it breaks the flow for me. I would certainly want the colours to be as calm as possible for the most common kinds, getting more exciting for the “exotic ones”. So I would suggest:

 Array
 Function
 MonOp
 DyOp

For example:

   r←(foo dop 1 2 3) mat hoo mop vec

I find that syntax colouring is much more effective in a bold font:

   r←(foo dop 1 2 3) mat hoo mop vec 

But…looking at the above, I personally find the colours to be quite distracting; they make it hard for me to read the expression as a “sentence”. How about if we experiment with emphasis instead, for example we could make functions italic, monadic operators bold, and dyadic operators both.

   r←(foo dop 1 2 3) mat hoo mop vec

This is very subjective of course, but this is much more readable to me than the coloured version.

Further comments with the original post please.