From: Jim Weigang <jimw@chilton.com>
Newsgroups: comp.lang.apl
Date: Fri, 05 Jun 1998 17:52:38 -0400
Subject: Beware selective assignment
Here's an example of an aspect of interpreter internals that APL users
should be aware of. Given the understandable reluctance of vendors to
reveal proprietary implementation details (especially unfavorable ones),
it's up to users to discover and publicize this type of information.
The topic is selective assignment, statements like (3{take}V){<-}4 5 6.
In some APL systems, these statements are apparently implemented by
replacing the target variable V with {iota}{rho}V (for vector V),
applying the selection expression, and then using the resulting indices
to decide which elements of V to replace. One consequence of this
behavior is slow execution time when replacing elements in a large
array. APL has to materialize all of {iota}{rho}V even if you're
replacing just a few elements. In contrast, the execution time for
simple indexed assignment (e.g., V[1 2 3]{<-}4 5 6) depends only on how
much data you're replacing, not on how big V is. Another consequence is
that the index array takes memory, and materializing it can result in a
WS FULL. Indexed assignment doesn't usually require extra memory
(unless the target is a synonym of another variable or has the wrong
datatype).
It doesn't matter what selection expression you use, (1{pick}V){<-}4,
(1{rho}V){<-}4, or (1{take}V){<-}4; they all use the same technique.
Both Dyalog APLW (v7) and APL+ seem to use this algorithm for selective
assignment. I suspect that APL2 does also, but this is based solely on
the observation that TryAPL2 crashes if there isn't enough memory to
materialize the index array.
You can confirm this behavior in your APL by creating a V that nearly
fills the workspace. Then try executing V[1]{<-}3. It should work
just fine. Try (1{take}V){<-}3. It'll probably give a WS FULL. You
can also try timing these expressions, preferably using some precise
timing tools such as #MF and the RESTIME program supplied with APL+DOS.
The speed differences can be quite dramatic. When replacing a single
element in a 1000-by-1000 integer matrix, selective assignment is about
12,000 times slower than indexed assignment.
Selective assignment isn't a useless feature, but you have to be
cautious about using it. If you're replacing items in a relatively
small array, the cost of materializing {iota}{rho}V will be modest and
there's no reason to avoid selective assignment. But for large arrays,
you should stick with indexed assignment.
The behavior when setting items in a nested array is somewhat more
complicated. The APL+ systems that I use apparently don't materialize
the entire per-recursive index array all the way down to the simple
leaves. Instead, the index arrays seem to be generated as needed on a
level-by-level basis. For example, if N is 3 4 (1000000{rho}5), doing
(1{take}N){<-}30 takes about the same amount of time as N[1]{<-}30.
When working on the blob finder program (see my c.l.a posting from May
24), I discovered something I wasn't previously aware of. Indexed
assignment with nested indices (e.g., M[{enclose}5 10]{<-}20, which is
equivalent to M[5;10]{<-}20) apparently uses the same technique as
selective assignment and suffers from the same problems. (I suspect
that M[N]{<-}B for nested N is implemented as (N{pick}{each}M){<-}B.)
I found this initially by observing that line of [42] of BLOBS, which
does M[T]{<-}U, was consuming far more time than the entire rest of the
program. I also got unexpected WS FULL errors when trying this
statement with large arrays. Simply replacing the statement with
M[1{pick}{disclose}T;2{pick}{disclose}T]{<-}U made the program run a LOT
faster. Not surprising--the original version forced the program to
generate a million-element index array for every 1 in the Boolean
argument!
Indexed reference with nested indices doesn't suffer from the same
problems. This is to be expected. Even if Z{<-}M[N] is implemented as
Z{<-}N{pick}{each}M, APL doesn't have to generate the index array; that
happens only when the expression is an assignment target. So you don't
have to worry about indexing with nested indices to the right of the
assignment arrow, only to the left.
The slow execution speed for M[N]{<-}B seems quite unnecessary. (And,
indeed, Dyalog APL doesn't have this problem.) The user has already
provided the indices of the items to replace. Using the indices as a
selection expression to produce the very same indices is obviously
redundant. Perhaps this will be sped up in a future release of the APL+
systems.
Jim
 JimW's Home Page |