bytes ← ##.wsreq expr ⍝ WS required to execute expression ⍵.
[wsreq] reports how many bytes of workspace are required to execute character
vector expression ⍵. It relies on trapping WS FULL errors and doing a "binary
chop" to find the minimum amount of available workspace that does not produce
the 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 expr ⍵.
⍺←0 ∇'64⍴32768' ⍝ version calibration.
cc←¯272××⍺ ⍝ calibration constant (see notes).
wd←⍕0.25×⍬⍴⎕SIZE'cc' ⍝ word size.
{1::0 ⋄ ⍵⍴⍨⎕WA}'?': ⍝ force initial WS FULL to set ⎕DM.
try←{} ⍝ make local function name.
⎕WA-⍺+cc+try 0 ⎕WA{⍺}⎕FX⌽{ ⍝ fix 'n run test fn.
⍵,⊂' try←{ '}wd{ ⍝ initial range; calibrated result.
⍵,⊂' mid←',⍺,'×⌊(+/⍵÷2)÷',⍺}{ ⍝ mid point of range.
⍵,⊂' mid∊⍵:⍬⍴⍵ '}{ ⍝ convergence: bytes reqd for expr.
⍵,⊂' lo hi←⍵ '}{ ⍝ lower and upper bounds.
⍵,⊂' 1::∇ lo mid '}{ ⍝ ws full: explore lower range.
⍵,⊂' fill←mid⍴'' '' '}⍵{ ⍝ fill all but mid's-worth of WS.
⍵,⊂' {0}',⍺,': '}{ ⍝ attempt to execute expr.
⍵,⊂' ∇ mid hi '}{ ⍝ success: explore upper range.
⍵,⊂' } '}⍬ ⍝ test function.
}
[wsreq] employs the same binary search technique as operator →bsearch←. It fixes
a local function "try" that embodies the subject expression. Within try, local
vector [fill] is packed with varying numbers of blanks to determine at which
point WS FULL occurs when executing the subject expression ⍵.
Details:
[1] ⍺←0 ∇'64⍴32768' ⍝ version calibration.
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. The line runs the test once on an expression
with a known space requirement and then uses the result in conjunction with the
fixed calibration constant:
[2] cc←¯272××⍺ ⍝ calibration constant.
The fixed calibration constant ¯272 (also known as a "fudge factor") compensates
for space taken to execute function [try]. The value of the constant was determ-
ined by executing an expression with a known memory requirement.
[4] {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.
To watch [wsreq] working, we could append a fragment of code that displays ⍞← to
each of the two recursive calls:
1::∇ lo mid{⍺}⍞←'<' ⍝ ws full: explore lower range.
¯¯¯¯¯¯¯¯
∇ mid hi{⍺}⍞←'>' ⍝ success: explore upper range.
then: ¯¯¯¯¯¯¯¯
wsreq'⍳1000' ⍝ show binary search.
>>>>>>>>>>>>>><><><>>><><>><
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
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:
···
⍵,⊂' mid←',⍺,'×⌊(+/⍵÷2)÷',⍺}{ ⍝ mid point of range.
⍵,⊂' ⎕←⍺ '}{ ⍝ SHOW LIMITS
⍵,⊂' mid∊⍵:⍬⍴⍵ '}{ ⍝ convergence: bytes reqd for expr.
···
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.
364
wsreq'(1000⍴7)+1000⍴8' ⍝ workspace for more complex expression.
10048
wsreq'2+2+2+2+2+1000⍴2' ⍝ multiple temporary space allocations.
8032
See also: pack nspack Data_compression bsearch
Back to: contents
Back to: Dyalog APL
Trouble seeing APL font?