Commute with other operators

APL-related discussions - a stream of APL consciousness.
Not sure where to start a discussion ? Here's the place to be
Forum rules
This forum is for discussing APL-related issues. If you think that the subject is off-topic, then the Chat forum is probably a better place for your thoughts !

Commute with other operators

Postby Phil Last on Thu Jan 07, 2010 12:43 pm

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.
User avatar
Phil Last
 
Posts: 557
Joined: Thu Jun 18, 2009 6:29 pm

Re: Commute with other operators

Postby Phil Last on Thu Jan 07, 2010 2:02 pm

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?
User avatar
Phil Last
 
Posts: 557
Joined: Thu Jun 18, 2009 6:29 pm

Re: Commute with other operators

Postby JohnS|Dyalog on Fri Jan 08, 2010 10:16 am

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% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕         

JohnS|Dyalog
 

Re: Commute with other operators

Postby giangiquario on Fri Jan 08, 2010 1:38 pm

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
User avatar
giangiquario
 
Posts: 46
Joined: Thu Nov 26, 2009 8:55 am
Location: Milano, Italia

Re: Commute with other operators

Postby JohnS|Dyalog on Fri Jan 08, 2010 4:38 pm

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!
JohnS|Dyalog
 


Return to APL Chat

Who is online

Users browsing this forum: No registered users and 1 guest