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 ⍵.
⍺←¯700+0 ∇'⍬' ⍝ ⍺ is calibration constant.
{1::0 ⋄ ⍵⍴' '}⎕WA: ⍝ force initial WS FULL to set ⎕DM.
⎕WA-⍺+⍵{ ⍝ WS required.
1::1 1 0/⍵ ⍝ WS FULL:: explore lower range (lo mid).
(0 1 1/⍵){⍺}⍺⍺{⍎⍺}⍺⍴' ' ⍝ execute subject expr with restricted WA.
}{ ⍝ binary search for WS FULL failure point:
mid←⌊+/⍵÷2 ⍝ mid point of range.
mid∊⍵:⍬⍴⍵ ⍝ convergence: maximum packing value.
lo hi←⍵ ⍝ lower and upper bounds.
∇ mid ⍺⍺ lo mid hi ⍝ explore lower or upper range.
}0 ⎕WA ⍝ starting with maximum range.
}
[wsreq] employs the same binary search technique as operator →bsearch←. The
workspace is packed with varying numbers of blanks in order to determine the
minimum amount of available workspace in which the expression may be executed.
Notice that the expression is executed (⍎) within an operand function outside
the binary search operator. This is to avoid the possibility of a name clash
between names used in the subject expression and those (mid lo hi) used in the
search. Within the operand function, no local names are in scope.
Details:
[1] ⍺←¯700+0 ∇'⍬' ⍝ ⍺ is calibration constant.
This line calibrates the particular version of the interpreter that is running
the test. Different interpreter versions have differing memory requirements for
structures such as stack frames and code and symbol representations. The line
calls [wsreq] recursively with a calibration constant (⍺) of 0 and subject expr-
ession '⍬', which is known not to consume additional workspace in its evaluat-
ion.
The calibration is to some extent arbitrary, as we need to decide how much of
the space taken by ancilliary structures, such as tokens and symbol references,
to include. The additional fixed calibration constant ¯700 (termed a "fudge
factor" in some circles) is chosen simply so as to report a value of 2016 for
expression '⍳1000'.
[2] {1::0 ⋄ ⍵⍴' '}⎕WA: ⍝ force initial WS FULL to set ⎕DM.
This forced WS FULL is used to set ⎕DM to a predetermined value. Otherwise, the
first WS FULL sustained in the body of the test can spoil the results by retain-
ing pointers to error structures.
[3] ⎕WA-⍺+⍵{ ⍝ WS required.
[4] 1::1 1 0/⍵ ⍝ WS FULL:: explore lower range (lo mid).
[5] (0 1 1/⍵){⍺}⍺⍺{⍎⍺}⍺⍴' ' ⍝ execute subject expr with restricted WA.
[6] }{ ⍝ initial range; calibrated result.
The operand function traps (1::) WS FULL on line[4] before attempting to execute
the subject expression (⍺⍺) on line[5], after packing (⍺⍴' ') the workspace with
⍺ blanks. The function is passed the three items of the range (lo mid hi) as a
right argument, and returns which range to examine next (1 1 0/⍵) or (0 1 1/⍵),
depending on whether the execution sustains a WS FULL error or not.
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.
Delay
-----
[wsreq] might take a significant time to execute as it involves repeatedly pack-
ing the workspace until a WS FULL occurs. Many iterations precipitate a work-
space compaction and garbage collection. To view progress, add a first line to
the inner dfn:
···
}{ ⍝ initial range; calibrated result.
⎕←⍵ ⍝ SHOW LIMITS
mid←⌊+/⍵÷2 ⍝ mid point of range.
···
For repeated testing, we can save time by reducing the amount of initial work-
space available to [wsreq] using a temporary variable. For example, if we think
that the workspace requirement for our expressions might be no more than a mega-
byte, we can pre-fill most of the WS:
junk ← (⎕wa-1e6)⍴'junk' ⍝ fill all but a megabyte or so.
wsreq'2+3+4' ⍝ test workspace requirements for expressions.
760
wsreq'1+2+3+4' ⍝ ...
780
⎕ex'junk' ⍝ remember to remove filler variable.
Examples:
⍝ reset ⎕DM, etc:
)reset
wsreq'⍳1000' ⍝ workspace used to generate index sequence.
2016
wsreq'⎕a[⍳⍴⎕a]' ⍝ workspace used for indexing.
680
wsreq'(1000⍴7)+1000⍴8' ⍝ workspace for more complex expression.
10068
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
Trouble seeing APL font?