Static/Dynamic Tradeoffs
In general, we often have a choice of making something dynamic or
static. A static structure or scheduler is limited by to handling
only a finite set of things of some fixed size since the size must be
selected and planned for as constructed. A dynamic structure or
schedule has the advantage that it can be arbitrarily large. Or
rather, that it only needs to allocate space or time in proportion to
its size rather in proportion to the whole size of the potential
problem. In order to handle cases where the space of things which
might happen is unbounded (but practically finite), we must often go
to this dynamic case since we cannot pre-allocate an unbounded amount
of space or time to represent or plan for a static structure. Dynamic
structures and schedules, however, must carry more information about
what they contain, generally leaving them with more overhead per data
item than the static structures (at least when the static structure is
full). Also, since they are of a size and shape unknown until
runtime, they must be scheduled and managed at runtime at a cost in
time overhead and generally a cost in optimality. The optimality
costs comes because the static case is hoisted before runtime and can
afford to exploit more heavy-weight (time consuming) optimizations
than the dynamic case.
The structure of a computation (or datastructure) can be represented
directly in the instruction stream for computation or described as
data (a separate datastructure) and ``interpreted'' by the computation
stream. Both have their value depending upon the expected form of inputs.
- In with the instruction stream
- the entire set of "possible" things that can happen consume
space and consideration (at least branching around)
- the entire space can be pre-scheduled, offline of computation
- this is good if the usage of cases is high (dense) so that
it's easiest/cheapest to just skip the ones not needed for
a particular instance
- As a separate datastructure
- only the subset of things which are needed at a
particular point are represented
- the structure must be richer to describe need and
consequently more expensive per active item to interpret at runtime
- scheduling must be done at runtime
- this is good if the cases which typically occur are a
small set (sparse) compared to the cases which might occur; here the
larger cost per item and scheduling costs are offset by the ability to
pay attention (spend cycles handling) a much smaller number of events.
This kind of tradeoff shows up in many places and levels.
André DeHon