next up previous contents index
Next: Cheating Up: Extending HLSIM Previous: carrier-sense? procedure

Efficiency trade-offs

A Gunk simulation is only a model of a clump of amorphous computers. As with any other model, trade-offs have been made between the faithfulness of the model and complexity and efficiency of the model. It is important to be aware of this fact.

HLSIM is capable of a reasonable degree of accuracy in its model of Scheme program execution. For `ordinary' programs, a Gunk program will execute in a number of clock ticks that is roughly proportional to the time the original Scheme program would take. The degree of accuracy is probably similar in predictive power to using an interpreter to predict compiled code performance. You might predict ``40 times faster than the interpreter'' but some of the compiled code would be only slightly faster (e.g. input/output) and other parts might benefit a lot from compiler optimizations and be a several hundred times faster. However, the thinking of so-many-times faster is adequate for most purposes. The program, whether intepreted or compiled (or, run on different machines), is executing the same algorithm.

Problems can arise from two sources. These sources can be categorized into timing dependent and non-linear timing.

If the correctness of the program depends on the relative speed of different program segments then is it timing dependent. A program is also timing dependent if its correctness depends on the relative speed of the program to communications. The communications parameters can be adjusted to compensate for problems with program/communications timing problems.

Non-linear timing problems occur when the simulation accounts a program fragment as requiring an amount of time that is not plausably linearly related to the time it would take a `real' program to perform the same operations. The main reason this might occur is that the simulator will use standard Scheme procedures if no Gunk version is defined. It assumes that the ordinary Scheme versions take a fixed, small amount of time.

Consider the following three procedures: car, * and assq. One might assume that car always completes within a fixed amount of time. Calling * is usually is pretty fast too, but there are exceptions, for example, when operating on very large exact integers. Assq is usually expected to take time proportional to the length of the list.

It is often reasonable to use the standard Scheme version of procedures like assq because the timing behaviour should not affect correctness. One might argue this is reasonable usage because the alist is always quite small, or that a hash table would turn the operation into a constant time operation.

For the purposes of speeding up the simulation, it is almost always faster to call the standard Scheme procedure.

next up previous contents index
Next: Cheating Up: Extending HLSIM Previous: carrier-sense? procedure

Erik Rauch
Sat May 8 16:42:57 EDT 1999