Benefits of compiling a language vs Executing an AST as soon as it is built

Question

What are the advantages / disadvantages of compiling a program for machine code instead of simply building an AST from the source code and performing operations while moving the tree?

Are there certain reasons why you would like to make one on top of the other?

Answer 1

Interpreting AST is usually much slower than running machine code that does the same. Typical is a factor of 20.

The advantage is that AST is faster to produce, so it takes less time to generate code than most compilers. AST interpreters are also simpler than compilers, because the entire phase of code generation can be ignored.

So, if you have a program that does not perform heavy calculations, it will work faster and faster with the help of an interpreter. On the other hand, if you have code that runs frequently or continuously in an environment where loops are limited, it is best to compile.

In some programming environments (for example, many lisps) there is an interpreter for developing code, since it supports fast debugging cycles and a compiler for creating fast code at the end of development. Some of these systems allow you to freely mix interpreted and compiled code, which is interesting in itself.

Compilation into bytecode is an intermediate environment: it is faster to compile than machine code, but faster to execute than AST. However, modern bytecode interpreters often compile their own code “just in time” as your program launches. This, for example, is the name source for the Sun HotSpot JVM. It compiles the "hot spots" in Java bytecode into native code to speed up programs at runtime.

Answer questions in the comments

The question arose about the multiplier 20 mentioned above. The support links for this issue are old, because few modern language systems use pure AST interpreters. (Shells are a notable exception, but most of them have been developed for a long time, and test speeds are not normal.) They are too slow. My context is lisp interpreters. I implemented a couple. Here, for example, is one Scheme test suite . Columns corresponding to AST interpreters are fairly easy to select. If there is demand, I can publish more and similar from the archive of the digital library ACM.

Another example: Perl uses the highly optimized AST interpreter. It takes about 7 seconds to add 10 million floats to a tight loop on my machine. Compiled C (gcc-O1) takes about 1/20 of a second.

As an example, the commentator introduced the addition of 4 variables. Analysis forgot the cost of the search. One clear dividing line between the interpreter and the compiler is pre-calculated addresses or frame offsets for characters. In the "pure" interpreter, they are not. Thus, adding 4 numbers requires 4 search queries in the runtime, usually a hash table - at least 100 instructions. In a good compiled code, adding 4 integers on x86 requires 2 instructions and one more to save the result.

There are many shades between “clean” AST meters and compiled machine code. Depending on the language, it may be possible to compile character offsets in the AST. This is sometimes called "quick links." Technique usually speeds up work two or more times. Then there are byte code compilation and transition systems such as Python, PHP, Perl, Ruby 1.9+. Their bytecode is effectively a stream code (opcodes can cause very complex things), so they are closer to AST than machine code. Then there are the JIT bytecode interpreters that I mentioned above.

The fact is that the coefficient of 20 pure interpreters of AST is one book, and machine code is another. In the middle there are many options, each of which has advantages and disadvantages.

Answer 2

Another advantage of compilation, not mentioned yet, is that it is often much simpler than a direct special interpretation. Often the raw source language is not very suitable for direct interpretation, and lowering it to a simpler language will facilitate a much more efficient and understandable interpretation.

For example, a language may contain a lexical region for which a name search is required for each time a variable or function argument is dereferenced. But a simple conversion pass, which will enumerate variables and embed implicit storage management structures, will make interpretation much easier and more efficient - access to the array is much faster than a hash table with a text key. Another such example is lid handling — going through a lambda lift is a lot easier than any ad hoc approach possible.

It is also much easier to interpret a flat "bytecode" than a tree. There are many well-known optimization methods (for example, threaded code ) for bytecode interpreters, while the AST hosting interpreter is doomed to slow down.

And, if you do not need to do some heavy optimization (for example, deleting dead code, constantly folding, register allocation, efficient command scheduling), compilation is extremely trivial and can be divided into ridiculously obvious small steps . On the other hand, a simple interpretation of any non-trivial language is always complex and cannot be divided into something simple and obvious.