NOBOX
This file contains facilities for compile-time suppression of
unnecessary allocation and collection of cons cells, large integer
boxes, and floating boxes. It also provides access fields that can
be used to speed up boxing and unboxing in arithmetic operations.
The trick for managing storage allocation is basically to allocate
the memory for temporary results (e.g. a list that will be thrown
away or a floating number that will not exist outside a local
computational context) at compile-time or load-time. This "static"
storage will be re-used whenever the given line of code is
re-executed. Compiled functions need no run-time support for these
facilities, so that NOBOX need not be loaded to execute compiled
code.
CONS CELLS.
The function CBOX may be used to suppress allocation of cons cells.
It operates like the function CONS, except that the cons-cell
returned is constructed at compile/load time. New values for CAR and
CDR are smashed into the cell at each execution. When run
interpreted, CBOX is exactly equivalent to CONS.
The function LBOX is to LIST and CBOX is to CONS. Thus, (LBOX A B C)
will cause a 3-element static list to be included with a compiled
function's literals. Each time the line of code is executed, those
three cells will be returned containing the current values of the
variables A, B, and C. When run interpreted, LBOX is exactly
equivalent to LIST.
LBOX allocates cells according to the number of its arguments. There
is also a mechanism for suppressing new conses when the length of a
list is not known at compile-time. This is accomplished by the
iterative statement operator SCRATCHCOLLECT. This can be used in
iterative statements exactly as COLLECT. Each time it is executed,
however, it re-uses the cells that it returned on previous
executions, which it has remembered as an internal scratch list.
This scratch list will always be the length of the maximum value that
was ever returned; new cells will be allocated whenever the scratch
list runs out, and they will be permanently remembered.
CBOX, LBOX, and SCRATCHCOLLECT, like the arithmetic facilities
described below, must be used carefully. They should only be used
for processing temporary values, since the static cells will be
smashed if the line of code is re-executed. See Note 2 below.
NUMBER BOXES.
There are 3 functions and 2 record declarations for improving the
efficiency of arithmetic computations. They permit information to be
given to the PDP-10 compiler (not the byte-compiler) that will
improve access time to variable-values that are known to be large
integers or floating point numbers, and that will inhibit the
allocation (and subsequent collection) of number boxes needed for
holding temporary results of numeric computations. In the latter
respect, these duplicate some of what SETN does, except that they are
more convenient to use and are executed more efficiently.
The records declared in this file (IBOX and FBOX) describe the
structure of large-number and floating-point boxes. IBOX has a
single field, called I, by which the user can cause the bits of a
large-integer box to be extracted. The use can create a large
integer box containing a given value by saying
(SETQ X (create IBOX I ← (FOO)))
Even if (FOO) evaluates to a small integer, the result will be stored
in a new large-number box. Why is this seeming ineffeciency
important? Because if some values of (FOO) might be large, making
all values large means that the compiler can be told exactly how to
treat future references to X without generating run-time tests to
discover how to do the unboxing. Thus, wherever the value of X is to
be referenced, the user can simply write X:I (or (fetch I of X). The
compiler will generate a single MOVE instruction without any
type-testing whatsoever. Furthermore, given that X is guaranteed to
be bound to a large integer, the user can re-use that number box by
saying X:I←(FUM), which is equivalent but much more efficent than
(SETN X (FUM)). In other words, once it is known that X is bound to
a large integer, the suffix :I can be used in all number-contexts to
inform the compiler of that fact.
The record FBOX and the field F act in the same way for
floating-point boxes. Note, however, that the (create FBOX --)
construction isn't that useful for floating point numbers, since
there is no distinction between small and large to be erased. The :F
suffix can still be used to improve accesses to the values, however.
The facilities described so far do nothing to suppress the creation
of unnecessary boxes; indeed, the (create IBOX --) will produces
boxes for small numbers that would not be allocated otherwise. The
functions (not records) IBOX, FBOX, and NBOX are used to suppress
unnecessary boxing of temporaries. Effectively, they cause
"constant" or "static" boxes of the appropriate type to be allocated
and stored in a functions literals when a function is compiled or
loaded. Those boxes can be used (and reused) to hold temporary
results.
IBOX and FBOX can appear with 0 or 1 arguments. If no arguments are
specified (which is different than having a single argument evaluate
to NIL), then the value of the function is a large-integer or
floating number box, respectively, which is allocated statically.
These might be used to construct an initial binding for a variable
into which temporary values will be stored using the :I or :F
assignments. For example
(PROG ((X (IBOX)))
(x:I←(FOO)) ...).
If an argument is specified for IBOX or FBOX, then again a static box
of the appropriate type will be allocated at compile- or load-time,
but the value of the argument will be stored in that box whenever the
IBOX statement is executed. For example, suppose you wanted to set a
file pointer to 1 past a given byte position. If you said
(SETFILEPTR FILE (ADD1 POS))
and POS happened to be large, you would get a new number box
allocated on each execution. That box would be passed into
SETFILEPTR and then returned as its value. Since the value is not
saved, the box would be thrown away, to be collected later. If you
said
(SETFILEPTR FILE (IBOX (ADD1 POS)))
the desired position would be stored in a constant box--no
allocations would take place. For another example, suppose that you
have a complicated integer expression whose value must be saved in a
variable to be used a little further down in your code:
(X←(IPLUS 2000 (ITIMES FOO (IQUOTIENT FUM 5))))
...
(Z←(IPLUS X (GETFILEPTR FILE)))
The PDP-10 compiler is smart enough to suppress the boxing inside the
X expression tree, but it will generate a box when it comes to do the
SETQ (←). This can be suppressed by writing
(X←(IBOX (IPLUS 2000 (ITIMES FOO (IQUOTIENT FUM 5)))))
Furthermore, it is now known that X is bound to a large-integer, so
the
Z assignment can be speeded up by writing
(Z←(IPLUS X:I (GETFILEPTR FILE)))
In effect, the function IBOX suppresses boxing at the root of an
arithmetic expression tree; the field I can be used to speed access
at the leaves of such a tree. The compiler knows how to generate
efficient code between the root and the leaves.
The function FBOX behaves the same as IBOX, except that it traffics
in constant floating boxes. Note that if the argument of IBOX is
FLOATP, then it will be FIXed; if the argument of FBOX is FIXP, it
will be FLOATed.
The function NBOX is a generic function for copying unknown values
into constant number boxes. It allocates 2 constant boxes, one
integer and one floating, and stores the value of its argument in the
one compatible with the value's type. This is of limited utility,
since it does not suppress the explicit boxing that might result from
evaluation of its argument. It is useful only if the argument value
is a constant number box (of unknown type) that needs to be copied
(see caution 2 below).
CAUTIONS
There are some dangers in using these facilities, just as there are
with SETN, FRPLACA, and any other function that smashes structures.
The user of this package should be particularly aware of the
following:
1. The F and I fields aim at efficiency more than validity. This
means that they DO NOT CHECK THE TYPE of the pointer that they smash
into. If you say, for example, X:I←2, and X is bound to NIL, then
you will have clobbered CAR and CDR of NIL! You must be very careful
that the arguments that you give for replacing do indeed point to
cells that unboxed numbers can be smashed into. (These need not be
explicit number boxes--it is legal to store into the unboxed region
of an array, for example, by presenting a pointer to the array cell
in the replace statement.) Note: the DECLTRAN package can be used
to generate the replaces, IBOXes, FBOXes automatically in a safe and
efficient way.
2. CBOX, LBOX, SCRATHCOLLECT, IBOX, and FBOX allocate constant
boxes, and those boxes will be reused (i.e. smashed with new values)
every time the line containing the function call is executed. If you
save that box in a variable or data-structure (e.g. by a SETQ) as a
way of preserving the value it contains, and then re-execute that
line of code, the saved value will be smashed. Thus you must beware
of using the constant boxes to save information in loops or
recursions that can get you back to the same statement. In these
situations, you must copy the value into other cells, perhaps a
constant associated with some other line of code, or perhaps you must
simply allow lisp to allocate the box to copy into in the ordinary
way. The first approach can be realized by SCRATCHCOLLECT, IBOX,
FBOX or NBOX:
(for V in X SCRATCHCOLLECT V), if X is the value of an LBOX, or
(SETQ Y (IBOX X:I], if X was the result of a previous IBOX,
will copy the value into new constants. The second approach can be
obtained by APPEND for LBOX, or by simply referencing X:I for IBOX
(:F for FBOX): (SETQ Y X:I]. You must also be careful about
returning a constant box as the value of a function, since the caller
might unknowingly save the value and re-invoke the box-returner.
----------------
These facilities were implemented by Ron Kaplan, with help from
Martin Kay and Beau Sheil.