next up previous contents
Next: Quasistatic Parameters and Up: Quasistatic Constructs Previous: Quasistatic Constructs

Quasistatic Variables and qif-qelse Statements

A quasistatic qif-qelse statement (hereafter referred generically to as qif) is resolved at compile-time to one of its clauses. I.e., it differs from the C if statement in that no selection between the clauses is done at run-time; also, only a single quasistatic variable may appear as the test expression. It differs from the C preprocessor directives #if defined(...)gif, #elseif defined(...), and #endif, which are sometimes used by programmers to delineate ``alternative'' code, in that it is the clever compiler which selects one of the qif clauses to execute at run-time; by contrast, preprocessor directives are explicitly resolved by the programmer when he or she indicates which symbols are to be considered defined by the compiler.

This new syntax allows the programmer to easily provide arbitrary alternative pieces of code, when he or she is uncertain which implementation will provide better performance. Below, I provide some examples to help to define the semantics of the construct; these examples also demonstrate the kinds of situations where the ability to easily specify alternative code might be useful.

Sorting

  
Figure: qif example: sorting.

In Figure gif, the programmer thinks that the FOOBAR sort implementation might perform better than the Quicksort implementation, but isn't positive. That uncertainty translates into writing a qif statement.

Note although SPECIAL_SORT_INPUT, the name of the quasistatic variable used in the qif statement in Figure gif, does not bear any semantic meaning to the clever compiler,gif the compiler does use it as an unique tag. At other places in the program where the programmer wishes to indicates the choice between the two sorts, the programmer can either use the same tag to force the selection to be the same; or, the programmer can use a different taggif to allow the clever compiler to make the selection separately.

Separate optimization decisions might be useful, for example, if one call site is expected to sort nearly random order data, but another call site is expected sort nearly sorted data --- the net effect in this example would be a variation of call site specialization. However, whether these a priori expectations were correct or not, the clever compiler can still make the right selection for each site so long as the decisions are decoupled at the two sites; thus, decoupled tags are generally preferable. So why should the programmer have the ability to force the clever compiler to couple decisions by using the same tag? A simple example where coupling is necessary is a function that needs to be initialized. Sorting routines generally don't need need initialization, but other kinds of routines may need initialization; if, however, the quasistatic decision is not to use that routine after all, then initialization should not be unnecessarily performed --- it might be expensive in terms of computation time (e.g., set-up) or money (e.g., a third-party library if initialized might grab a floating license for the duration of program execution).

Coupling the clever compiler's decisions can be used for more than initialization, however. For example, the ability to force the compiler to couple decisions makes it possible for the programmer to provide different implementations of abstract data structures, but to be manipulated in-line at points of use in the program rather than strictly through an abstraction layer of library function calls. For example, an abstract set might be represented as either an unsorted linked list or as a b-tree (slower insertions, but faster deletions and lookups than the linked list); an abstract complex number might be represented either as in Cartesian form as a pair of real and imaginary numbers, or in polar form as radius and angle (slower additions and subtractions, but faster multiplications and divisions than the Cartesian form). (Note no single implementation of these or other abstract data types is likely to be the best-performing for all possible programs.) It is vital that the quasistatic decisions between alternative code fragments accessing the internals of different representations from different places in the program are coupled, i.e., made consistently, or else an alternative code fragment might end up trying to manipulate data in a b-tree as a linked list, for example.gif

Hardware Assist

As another example, in Figure gif, the programmer is uncertain sure how effective the available graphics accelerator will be at rendering this particular application's display list (e.g., CAD). Hence the programmer decides to let the clever compiler quasistatically choose between having the graphics accelerator do all, some, or none of the work.

  
Figure: qif example: graphics hardware assist.

The figure demonstrates how the programmer can specify more than two alternatives by adding a qelse qif(QVAR) clause. A final qelse clause which does not specify a quasistatic variable is optional; therefore, for any particular qif statement, no matter how long the chain of clauses it contains, either exactly one (no final qelse clause) or zero (final qelse clause exists) of all the quasistatic variables used must resolve to true, so that in either case exactly one of the clauses in the statement will be selected.

In this example, the code alternatives trade off between doing work locally on the CPU and doing work on the graphics accelerator. It might be the case, for example, that on a workstation model with a slow CPU the FULL_HW_ASSIST alternative performs best, whereas on a workstation model with a fast CPU, it's faster to let the CPU take on a larger share of the computation; the sophistication of the graphics subsystem installed on any given machine is of course also a major factor in the quasistatic decision.



next up previous contents
Next: Quasistatic Parameters and Up: Quasistatic Constructs Previous: Quasistatic Constructs



Reinventing Computing, MIT AI Lab. Author: pshuang@ai.mit.edu (Ping Huang)