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