Commute with other operators

[Phil Last]

A couple of years ago in dyalogusers it was pointed out that:

combining commute with each:

for all a, f and w where a and w are arrays and f if a function

      a f⍨¨ w ←→ a f¨⍨ w
and
      f⍨¨ w ←→ f¨⍨ w

The difference being that the former expression in each equivalence requires that an item of the argument(s) be switched at each iteration while the switching is done once only in the latter. In other words we run commute itself n times instead of once for a &/or w of count n.

For a large number of items the latter can therefore be significantly quicker.

Similarly for commute with power:

for all a, f, w & n where n is an integer scalar

      a (f⍨⍣n) w ←→ a (f⍣n)⍨ w
and
      (f⍨⍣n) w ←→ (f⍣n)⍨ w

the former of each pair will switch the arguments n times rather than once only in the latter.

No such equivalences exist for reduction, scan or inner or outer product.

[Phil Last]

My apologies for doing insufficient testing.

Now I can't even find the case where I had used this and found the above to be true.

Please ignore the above posting.

I suppose there's no way I can delete the thread?

[JohnS|Dyalog]

Phil, I think what you say is true:
Here is a comparison of ¨⍨ vs ⍨¨ on a thousand-item vector:

Code: Select all

Dyalog APL/W Version 12.1.1
Serial No : 000000
Unicode Edition
Fri Jan 08 09:56:05 2010
clear ws

      )copy dfns cmpx
u:\ws\dfns saved Thu Jan 07 21:37:02 2010

      0⍴⎕wa⍴42   ⍝ stretch the WS to avoid compactions during test.

      v←⍳1e3

      cmpx '1+⍨¨v' '1+¨⍨v'
  1+⍨¨v → 5.6E¯4 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  1+¨⍨v → 3.8E¯4 | -33% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕             

⍝ Note that applying compose umpteen times also has a cost:

      cmpx'1 1∘⍴¨v' '(⊂1 1)⍴¨v'
  1 1∘⍴¨v   → 7.6E¯4 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  (⊂1 1)⍴¨v → 5.6E¯4 | -27% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕         



[giangiquario]

John,
please explain what's happening here:
0⍴⎕wa⍴42 ⍝ stretch the WS to avoid compactions during test.

Nor do I understand why we do not obtain:
WS FULL

[JohnS|Dyalog]

A new Dyalog process starts small and expands on demand up to your configured MAXWS (Options->Configure->Workspace->Maximum workspace size (KB)).

At each expansion (when the heap manager can't satisfy a request for contiguous memory), the interpreter: garbage collects; demotes integer arrays where possible; compacts the heap; and expands the Dyalog process size. This all takes a not insignificant time and so could pollute benchmark timings.

There are two ways to ameliorate this effect:

[1] run the benchmark a number of times and choose one of the later results, when the heap has "warmed up".

[2] to pre-expand the heap by filling it with a large array, which is then discarded.

The expression:

0 ⍴ ⎕WA ⍴ 42

just succeeds because 42 is a 1-byte integer, and so there is just enough space to accommodate a vector of size ⎕WA bytes.

That's the short answer, but you're probably thinking: that can't be true because an n-byte vector would require slightly more than n bytes of heap-space, because it would need an array header and we would also need a small additional amount of space for the result of the 0⍴.

Well, we get lucky because niladic system functions, such as ⎕WA, push a little "environment" stack frame on to the state-indicator and release it again on return. This freed-up stack frame gives us just enough free space to accommodate the two extra array headers.

Hurrah!