3.2 Compilation Strategies

As we discovered in our experiments, the execution time of a program using the continuous compiler is strongly affected by the order in which the routines are translated into native code. Seven different compilation strategies were examined. Each is described below.

Three of the strategies, shortest-first, largest-first, and random, are static and use fixed information about the routines to determine the translation order before any translation begins. Two of the strategies, longest-so-far and most-frequently-executed-so-far, are dynamic and use information gleaned from monitoring the execution of the program to determine the order of translation; the next module to translate is picked at the time of translation.

The remaining two strategies, longest-overall and most-frequently-executed-overall, are hybrid. The order of translation is determined upon start-up, before any translation begins; however, they require knowledge about the execution of the program, gained from a previous run.

The three static strategies have the advantage of low overhead; the order of translation is fully determined before translation begins and is based only on easily determined static properties of the source modules. The two dynamic strategies have the disadvantage of a higher overhead; more processing is required at each step to determine the next module to translate. The order of translation cannot be fully determined at start-up, and in fact changes as the program is executed. The final two strategies have low overhead, but they have the disadvantage of requiring information from a previous run of the program, which is not always available.

Shortest-first

The shortest-first strategy is based on the size of the source modules. The modules are simply sorted from smallest to largest and then translated in that order.

Largest-first

The largest-first strategy is the opposite of the shortest-first strategy: the modules are translated in order from largest to smallest.

Random

In the random strategy, the source modules are simply translated in random order. The main purpose of this strategy is to emulate the nondeterminism that might be caused by the transmission of source files over a network, when the files might not arrive in the order sent.

Most-frequently-executed-so-far

In this strategy, the Monitor module keeps track of how often each routine is called. When the next source module to translate needs to be picked, the Compiler picks the untranslated routine that has accumulated the most calls up to that point in the execution of the program.

Longest-so-far

This strategy is similar to most-frequently-executed-so-far, except that the next module for translation is chosen based on the current accumulated time spent in executing the routines in each module rather than a call count. The accumulated time for a function does not include time spent in other functions on behalf of this function.

Most-frequently-executed-overall

This strategy uses information gained during a previous execution of the program to determine which routines were called the most over the entire execution. The untranslated source module which received the most calls during the previous execution is the one that is chosen for translation.

Longest-overall

This strategy is the same as the most-frequently-executed-overall, except that the next module chosen for translation is the one that accumulated the most run-time during the previous execution instead of the one with the most calls.

An important point to note is that compilation takes place on a file-based level of granularity, not on the routine level. If each source file contains only one routine then these are of course identical, but that is not often the case. Section 6.7 describes some experiments run to determine how strong an effect the density of routines per source file has on the performance of the continuous compiler.

When choosing which file to translate next, our system looks at the statistics for the file as a whole, not at the individual routines. For example, the most-frequently-executed-so-far strategy picks the file with the largest number of calls made to all of the routines defined in each file, which is not necessarily the file which contains the single most called routine. All of our compilation strategies work in this manner. Picking the files based on individual routines is, of course, also a valid method, but was not examined in these experiments.

The shortest-first strategy deserves closer attention. If the assumption can be made that the time required for compilation of a file is a monotonically nondecreasing function of file size, then the shortest-first strategy maximizes the throughput (files translated per minute) of the Compiler module. It is analogous to the shortest processing time scheduling algorithm [6]. However, it is important to note that maximizing the throughput of the Compiler module is not the same as maximizing the performance of the continuous compilation system as a whole. In fact, we found through our experiments (see Chapter 6) that, while the shortest-first strategy usually gave fairly good results, it did not usually give the best results.