explicit <-> tacit, space/time usage on prime numbers

Johann Mitloehner

unread,

Oct 30, 1992, 5:55:15 AM10/30/92

to

Here are some experiments (by T. Kolarik and myself) with the
well-known primes-idiom on several machines, comparing tacit and
explicit definition of the verb:

On an HP 9000/720 (HP-UX):

0!:2 <'ta-ex.js'
eprimes =. '(i.y.)#~2=+/0=|/~i.y.':'' NB. explicit def
tprimes =. (=&2 @ (+/ @ (=&0 @ |/~ @ i.))) # i. NB. tacit def
time =. 6!:2
space =. 7!:2
ts =. (time, space)
ts 'tprimes 100'
2.71 2528
ts 'eprimes 100'
0.15 464

On a Mac Quadra:

0!:2 <'users:j-bench'
eprimes =. '(i.y.)#~2=+/0=|/~i.y.':'' NB. explicit def
tprimes =. (=&2 @ (+/ @ (=&0 @ |/~ @ i.))) # i. NB. tacit def
time =. 6!:2
space =. 7!:2
ts =. (time, space)
ts 'tprimes 100'
5.23333 28
ts 'eprimes 100'
0.166667 28

On a Mac IIx:

eprimes =. '(i.y.)#~2=+/0=|/~i.y.':'' NB. explicit def
tprimes =. (=&2 @ (+/ @ (=&0 @ |/~ @ i.))) # i. NB. tacit def
time =. 6!:2
space =. 7!:2
ts =. (time, space)
ts 'tprimes 100'
33.4667 28
ts 'eprimes 100'
1.05 28

Result: explicit definition is much faster.

I have done a similar thing on a Mac Classic with J 5.1a; interestingly,
tacit was slightly faster (the difference being very small; I did no space measure).

But tacitly defined
verbs are supposed to be (much?) faster, aren't they?
Or is this just a bad example? (Or is our tacit version so bad :-(

(Note: we used J 4.1 in the first example because we have not yet
succeeded in compiling J5.1a for the HP 9000/720 and 730.)

Sam Sirlin

unread,

Nov 4, 1992, 2:33:52 PM11/4/92

to

...

|> Result: explicit definition is much faster.

Using J6 on a sun sparcstation 1:
ts 'tprimes 100'
4.53315 24
ts 'eprimes 100'
0.099996 24
ts 'eprimes 100'
0.116662 24

teprimes=. '(i.y.)#~2=+/0=|/~i.y.' : 11 NB. tacitize eprimes
ts 'teprimes 100'
0.116662 24

So not all tacit definitions are equal.
--
Sam Sirlin
Jet Propulsion Laboratory s...@kalessin.jpl.nasa.gov

Roger Hui

unread,

Nov 7, 1992, 6:38:13 PM11/7/92

to

Johann Mitloehner writes:

> Here are some experiments (by T. Kolarik and myself) with the
> well-known primes-idiom on several machines, comparing tacit and
> explicit definition of the verb:
>
> On an HP 9000/720 (HP-UX):
> J 4.1 Copyright (c) 1990-1992, Iverson Software Inc. All Rights Reserved.
>
> 0!:2 <'ta-ex.js'
> eprimes =. '(i.y.)#~2=+/0=|/~i.y.':'' NB. explicit def
> tprimes =. (=&2 @ (+/ @ (=&0 @ |/~ @ i.))) # i. NB. tacit def
> time =. 6!:2
> space =. 7!:2
> ts =. (time, space)
> ts 'tprimes 100'
> 2.71 2528
> ts 'eprimes 100'
> 0.15 464

> ...

>
> Result: explicit definition is much faster.
>

> But tacitly defined verbs are supposed to be (much?) faster, aren't they?
> Or is this just a bad example? (Or is our tacit version so bad :-(

In July 1990, at the APL90 Conference in Copenhagen, Eugene McDonnell
presented timings indicating that a tacitly defined nub was faster
than an explicitly defined nub, and was as fast as the primitive ~. .
I was in the audience and was surprised by this result. Tacit defns
arise from the use of adverbs and conjunctions, function assignment,
and forks; that they happen to be faster is an unexpected benefit.

The slower times for "tprimes" obtained above can be accounted for by
the difference between =&0@|/ vs. =&0@(|/). I applied the tacit
translator to the explicit defn, and obtained the following time/space
results (J6 on a PC486/33):

ts 'tprimes 100'
2.86 24692
ts 'eprimes 100'
0.05 53420
f0 =. '(i.y.)#~2=+/0=|/~i.y.': 11
ts 'f0 100'
0.05 50312
lr =. 5!:5
lr <'f0'
i.@] #~ 2&=@(+/@(0&=@(|/~@(i.@]))))

This shows that tacit defn is at least no slower than explicit defn.
The following table shows that it is in fact faster. All times are
obtained using 100 time 'f n' on J6 PC486/33.

200 100 10 5 1
tprimes 11.0334 2.8456 0.0341 0.0109 0.0033
eprimes 0.2230 0.0582 0.0049 0.0044 0.0044
f0 0.2213 0.0565 0.0032 0.0027 0.0027
f1 0.2208 0.0566 0.0033 0.0027 0.0026
f2 0.2208 0.0566 0.0033 0.0027 0.0027
f3 0.0193 0.0138 0.0038 0.0033 0.0038
f4 0.0143 0.0088 0.0017 0.0016 0.0016

"f0" is faster than "eprime" by a fixed amount, 0.0017. This is
consistent with the explanation of why tacit is faster than explicit:
a tacit defn is not reparsed on execution, and 0.0017 is the time it takes
to parse "eprimes". The relative advantage of tacit over explicit is thus
greatest for small vectors, when parsing time dominates, and diminishes as
vector size increases. This fact is of interest to compiler writers.

"f1" is an attempt to see how much better or worse a "hand-written" tacit
defn may be. f0=.i.@] #~ 2&=@(+/@(0&=@(|/~@(i.@])))) , the defn produced
by the translator, is periphrastic. It is easy to see that the two uses
of @] are unnecessary, and the use of passive can be eliminated by
rearranging the tines of the fork. As well, I tend to shy away from
deeply right-nested compositions. Putting it all together:

f1 =. 2&=@(+/)@(0&=)@(|/~)@i. # i.

The timings in the table indicate that "f1" is slightly faster than "f0".
Not too surprising, as "f1" is only slightly different from "f0".

As indicated at the start, speed is not the main point of tacit defn.
Some of the advantages of tacit defn were outlined in a msg two weeks ago:

0) The tacit form encourages the use of components, primitive and
user-defined. Use of components is one of the few effective ways of
dealing with complexity.
1) The tacit form focuses on how components are combined, i.e. it focuses
on the interface between components, where errors tend to occur.
2) Tacit expressions are algebraic, i.e. they are amenable to proof
and other formal manipulations.
3) Tacit expressions are constructed using operators (adverbs and
conjunctions), ideas debugged in mathematics over hundreds of years.

Even for something as small as this primes problem, it is possible to
see how these benefits may be applicable. "f1" can be redefined to
use a sub-function, of interest in its own right:
sieve =. 2&=@(+/)@(0&=)@(|/~)@i.
f2 =. sieve # i.

"f2" is slightly clearer than the others, in bringing into sharper relief the
structure of the computation. It is about as fast as the others (see table).

I'd previously written a recursive version of "primes" which avoids
generating the n^2 table:
t=.i. 0 0
t=.t,'$.=.1+30<y.'
t=.t,'y.(>: # ])2 3 5 7 11 13 17 19 23 29'
t=.t,'p,(*./0~:p|/s)#s=.k+i.>:y.-k=.{:p=.f3 <.%:y.'
f3 =. t :''

A hand-translated tacit version of same:
basis =. (>: # ])&2 3 5 7 11 13 17 19 23 29
sieve =. *./@(0&~:)@(|/)
suffix =. {:@[ ([ + i.@-.@-) ]
extend =. [ , [ (sieve # ]) suffix
f4 =. ($:@<.@%: extend ])`basis @. (30&>)

The time and space complexity of "f3" and "f4" are of a lesser order
than the others, so that the advantage shown in the table increases with
argument size:

100 time 'f0 500' 100 time 'f0 1000'
1.3583 ws full
100 time 'f3 500' 100 time 'f3 1000'
0.038 0.09
100 time 'f4 500' 100 time 'f4 1000'
0.0335 0.0829

Finally, 2) speaks of tacit expressions as being more amenable
to proof and other formal manipulations. Optimization is a class of
formal manipulation, and in the future the implementation may exploit
formal properties of tacit defns to effect faster execution. I described
some possible approaches at the Minnowbrook '92 conference in mid September.

> (Note: we used J 4.1 in the first example because we have not yet
> succeeded in compiling J5.1a for the HP 9000/720 and 730.)

J6 is now available. When compiling for the HP9000/7x0, try setting
SYS_DOUBLE in js.h to 1.

------------------------------------
Roger Hui, Iverson Software Inc., 33 Major Street, Toronto, Ontario M5S 2K9
Phone: (416) 925 6096; Fax: (416) 488 7559