bytes ← ##.wsreq expr ⍝ WS required to execute expression ⍵.
[wsreq] reports how many bytes of workspace are required to execute its charact-
er vector argument [expr]ession. It relies on trapping WS FULL errors and doing
a "binary chop" to find the minimum amount of free workspace needed to evaluate
the expression without error.
NB: Some primitive functions use a different algorithm, depending on the amount
of workspace available. In this case, [wsreq] forces the choice of the more
frugal and thus slower method.
Technical notes:
wsreq←{ ⍝ WS required to execute expression ⍵.
-/{ ⍝ max padding difference for exprs '⍬' and ⍵
(⍎'{(',⍵,')}'){ ⍝ subject expr ⍵ embedded in dfn operand
⎕SIGNAL 0: ⍝ clear previous ⎕DM
1::(1↑⍵),⍺ ⍝ wsfull:: explore lower range (lo .. mid)
(⍺,1↓⍵)⊣⍺⍺ ⍺⍴' ' ⍝ eval ok: explore upper range (mid .. hi)
}{ ⍝ binary search for WS FULL failure point:
mid←⌊+/⍵÷2 ⍝ mid point of range
mid=1↑⍵:mid ⍝ convergence: maximum packing value
∇ mid ⍺⍺ ⍵ ⍝ explore upper else lower range
}0 ⎕WA ⍝ starting with maximum range
}¨'⍬'⍵ ⍝ calibration and subject expressions.
}
The first inner function:
-/{ ⍝ diff in max padding for exprs '⍬' and ⍵
...
}¨'⍬'⍵ ⍝ calibration and subject expressions.
reports the difference in the maximum amount of padding that can be used before
either the calibration '⍬' or subject expression ⍵ cause WS FULL.
Within this, the second inner function:
(⍎'{(',⍵,')}'){ ⍝ subject expr ⍵ embedded in dfn operand
...
}{ ⍝ binary search for WS FULL failure point:
...
}0 ⎕WA ⍝ starting with maximum range
fixes the subject expression as the operand of an operator, to derive a function
that is itself the operand of the main binary search operator. Fixing the func-
tion in this way (as opposed to, say, executing (⍎) the subject vector directly)
means that space used for tokenisation if removed from the calculation. This is
better as it reflects more accurately the normal usage of code, which has gener-
ally already been tokenised at function edit time.
The lower of the two innermost operators:
{ ⍝ binary search for WS FULL failure point:
mid←⌊+/⍵÷2 ⍝ mid point of range
mid=1↑⍵:mid ⍝ convergence: maximum packing value
∇ mid ⍺⍺ ⍵ ⍝ explore upper else lower range
}
is a classic "binary chop", which calls its operand function ⍺⍺ with the current
range and, as a convenience its midpoint "mid". The evaluation of the subject
expression itself is separated into the upper innermost operator, in order to
avoid any name-conflicts (lo hi mid) with the working of the binary search:
{ ⍝ subject expr ⍵ embedded in dfn operand
⎕SIGNAL 0: ⍝ clear previous ⎕DM
1::(1↑⍵),⍺ ⍝ wsfull:: explore lower range (lo .. mid)
(⍺,1↓⍵)⊣⍺⍺ ⍺⍴' ' ⍝ eval ok: explore upper range (mid .. hi)
}
The first line clears the previous error, so that any workspaces used to hold
its state does not interfere with the calculation. The second line traps WS
FULL to return the lower half of the range, and try again with reduced padding.
The last line pads the workspace with ⍺ blanks and attempts to evaluate the sub-
ject expression in its pre-fixed dfn ⍺⍺. If this succeeds, the lower part of the
range is returned.
Note the reliance on the error guard's being _dynamically_ in scope when the
subject operand expression is being evaluated.
The error-guarded code is separated from the binary search code, in order that
the latter's tail recursion is not disabled by the presence of an error-guard.
Note the parenthesising of the subject expression ⍎'{(',⍵,')}'. This is so that
expressions, such as 0, fail to form an idiom when embedded in braces. {0} is an
idiom that takes very little token space, whereas {(0)} isn't and so can be com-
pared fairly with the calibration expression {(⍬)}.
Temporary results
-----------------
Remember that an APL function requires enough workspace for its argument(s) as
well as for its result. Temporary results are released only when they are no
longer referenced. For example, if [vec] is a 1,000-item character vector:
vec←1000⍴'abc' ⍝ 1,016-byte vector.
then successive catenations:
vec←vec,vec,vec
require an additional 2,016 bytes for the first (rightmost) catenation to store
a temporary 2,000-item vector. This temporary vector must remain in the work-
space for the duration of the second (leftmost) catenation, which requires a
further 3,016 bytes for its 3,000-item result. During the second catenation, the
total workspace required is:
named vector [vec]: 1,016
result of rightmost cat: 2,016
result of leftmost cat: 3,016
-----
6,048 bytes
-----
as the second catenation completes, its temporary right argument is released
leaving:
named vector [vec]: 1,016
result of leftmost cat: 3,016
-----
4,032 bytes
-----
and the final assignment releases the original array leaving:
named vector [vec]: 3,016
-----
3,016 bytes
-----
Given the presence of a 1,000-item character vector [vec], the additional space
needed to do the above catenations is 2016 + 3016:
vec←1000⍴'abc'
wsreq'vec,vec,vec'
5032
NB: wsreq may report a little more WS usage than above, as it includes space
taken for symbols and code tokens, etc.
NB: In 32-bit versions of the interpreter, each floating-point (645=⎕dr ⍵) array
is padded with either 0 or 4 bytes in order to align its IEEE floating-point
numbers. This _may_ affect the result of wsreq by 4 bytes for each simple float-
ing point array generated by the subject expression.
Examples:
⍝ reset ⎕DM, etc:
)reset
wsreq'⍳1000' ⍝ workspace used to generate index sequence.
2016
3000 wsreq'⍳1000' ⍝ ... with explicit reservation (quicker).
2016
wsreq'⎕a[⍳⍴⎕a]' ⍝ workspace used for indexing.
680
wsreq'(1000⍴7)+1000⍴8' ⍝ workspace for more complex expression.
30068
wsreq'2+2+2+2+2+1000⍴2' ⍝ multiple temporary space allocations.
8056
See also: pack nspack Data_compression bsearch
Back to: contents
Back to: Workspaces