Build a compiler that compiles just before (or during) runtime to get benefits of both compilers and interpreters. [Architectural Pattern]
Context
Language implementation.
Forces
- An interpreter has advantages over a compiler:
- It’s usually the fastest, easiest way to implement a language.
- The representation used by the interpreter can be space-efficient.
- The representation used by the interpreter can be portable.
- A compiler has an important advantage over an interpreter: the code runs 5-10x faster.
Resolution
Build an interpreter first, and then integrate a just-in-time (JIT) compiler. The JIT can either compile the code all at once when it’s first ready to “interpret”, or it can compile classes or methods on an as-needed basis.
Discussion
It’s easier to implement an interpreter than a compiler. Providing the interpreter first gives us early access to a language implementation. (For many languages, it is desirable to write the compiler in that language itself, so an interpreter provides a way to bootstrap that process.) You can develop an intermediate language that is customized to the programming language – space-efficient and portable. (Java uses “JVM” code for just such a reason: Java code should be small when shipped across the network, and portable because there are many machines on the net.)
Once the interpreter framework is in place, you can build the compiler around it. (Perhaps even one construct at a time, if you like.)
The resulting system will not have code as fast as a pure compiler (which has more time and usually more code to look at while compiling). The system will usually beat a pure interpreter though. Instead of
n * interpret_time(x)
for n statements, you pay
compile_time(x) + n * run_time(x)
(Note that if compile_time(x)+run_time(x) is longer than interpret_time(x), the JIT can actually run slower than an interpreter: there must be enough executions of the run-time to amortize the cost of the compile-time.)
Examples
- P-code Interpreter. [Bowles, Wirth – refs?] Some Pascal systems used a similar approach, using P-code as a portable Pascal intermediate representation.
- Java and the JVM. [Sun] Java uses JVM “machine code” to deliver portable software. In the Java world, there are pure interpreters, pure compilers, interpreter + JIT compiler, and probably other combinations as well.
- BLIT code. [ref?] You can carry the compiler idea down to just the subroutine level. The BLIT (block transfer) method is used in graphical displays to handle the move of screen bytes for e.g., scrolling. The fastest way to do the BLIT depends on the actual parameters. For instance, data aligned on an 8-byte boundary might allow for a faster copy; it may be faster if an even number of bytes are copied, etc. Some systems generate code on the fly. The generated code can take the actual parameters into account. It can use faster addressing modes. For instance, it might be able to replace indexed access by hard-coded addresses.
Caveats
Processors have rules about creating code in an existing process. They may require that an instruction cache be flushed before the generated code is executed. (Failure to do this may result in strange errors.) Unfortunately, this adds “hidden” slow-downs before new code is first executed.
[Written 7-20-98]