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.

This kind of tradeoff shows up in many places and levels.

André DeHon