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
which 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 which takes very little token space, whereas {(0)} isn't  and  so  can  be
compared 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