3.3 Replacement Strategies

The strategy used by the Interpreter in replacing interpreted source code with translated native code can also have a profound effect on execution time. In this study, two strategies were considered: replace-at-call and replace-preemptive.

Replace-at-call

In this strategy, the switch from interpreting source code to running native code occurs only at function calls. When a function call occurs, a jump is made to the native code, if it is available; otherwise, the function is interpreted. And when a function returns, execution of the calling function continues in whatever mode it was in prior to when the call occurred. That is, if routine A, which is being interpreted, calls routine B, which is available in native-code form, then when routine B exits and control is returned to routine A, A continues to be interpreted, even if the native code for A became available during execution of B. In other words, function invocations active on the stack are not replaced. However, if a recursive call is made to a routine that is now available in native form, then the native-code version of the routine is used for the new call, regardless of whether or not an interpreted instantiation of the function is on the call stack.

Replace-preemptive

In this strategy, execution of a routine is switched from interpreting source code to running native code as soon as the native code is available, even if it is while the routine is being executed. Also, if the native-code version of a function is available when that function is popped off the activation stack to resume execution, then a jump is made to the native code, even if the function was originally being interpreted when it was pushed on the stack.

The replace-at-call strategy has the advantage of low overhead and relative ease of implementation. The only processing required by the Interpreter to implement replace-at-call occurs at function calls. When the Interpreter reaches a call instruction, it simply checks the program state information to see if the function is available in native-code form. If it is available, it simply jumps to the compiled code; if not, it continues interpreting. The processing required by the Compiler module is also fairly minimal. When the Compiler translates a function that contains calls to functions that have not yet been translated, the functions calls are implemented as jumps to the Interpreter.

The replace-preemptive strategy is more difficult to implement and has a higher overhead, but it also has the possibility of greatly improving performance. In addition to the processing required by replace-at-call, the replace-preemptive strategy requires that the Interpreter check for newly available native code whenever it removes an activation record from the stack to continue execution. The Interpreter would also need to know where to jump in the native-code version of the function to continue execution where it left off interpreting. In a fully replace-preemptive system, the Compiler would need to be able to interrupt the Interpreter if it happens to finish translating the function that the Interpreter is currently processing so that the Interpreter can jump to the compiled code. However, the cost of implementation would most likely be prohibitive. A "mostly" replace-preemptive system, which did not include the interruption of the Interpreter, could be implemented instead. Jumps to compiled code would only occur at function calls and returns, but as function calls occur with a fairly large frequency in most well-structured programs, performance is not likely to be impacted much. The main advantage over the replace-at-call method still exists; we do not have to wait for a particular function to complete before replacing it with native code. The replacement can occur when execution of the function resumes after returning from a function call. Nevertheless, for the purposes of these experiments our simulator emulates the fully replace-preemptive method.