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:
c1 iff a “selfie”, i.e. the left and right arguments are equal as C pointerseq1 if∘.≡; 0 if∘.≢r1 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.
Follow