Does bootstrapping limit the achievable speed of the new compiler?

Question

I have a good grasp on how the C compiler was bootstrapped from itself and how that must have been very efficient, since the first pre-bootstrapping version was written in assembler, which is as low level as you can get.

BUT today we have a very different situation, with languages first written on other relatively high-level languages (e.g. Clojure).

Question 1: I have a hard time imagining that the bootstrapped compiler could be faster in anything than its non-bootstrapped counterpart. Is this possible?

Question 2: Especially once you take the step in which you write then new version of your compiler in your new language: Can any inefficiencies that existed in the non-bootstrapped code be fixed or is the code generation of the new compiler haunted by those forever? That matters even more since you can’t easily go back and fix those afterwards!

Answer 1

I think the easiest way to fix this problem, mentally, is just to realize that it all ends up back as machine code anyway. How it ended up as machine code is the story, and the story certainly has meaning to us as people, but computers don't care what the history of the machine code is. They just do what the lowest-level instruction set tells them to do.

Mentally, we might think like this:

1. Someone wrote the appropriate machine code to allow, say, C.
2. C was used to write C-Plus-Classes
3. C++ gets used to create an implementation of, say, Java.

Therefore, we justify a belief that anything in Java must be slower than anything in, say, Assembler. But...that's not how it really works!

How It Really Works Nowadays

1. Computer runs machine code.

Or, for those who want bytecode considered:

1. Machine code (JIT) turns bytecode into machine code. (slower startup time caused, maybe)
2. Computer runs machine code.

All the code ends up the same place, so the long path it took to get there doesn't necessarily effect how it runs.

Sometimes there is an extra layer, like with JavaScript that never gets compiled to machine code before being run, but then machine code turns that stuff into machine code too. It all ends up the same place, in the CPU and the RAM. Some machine code isn't as efficient as other machine code, but how that code came to be written doesn't really matter: sometimes machine code writes the best machine code, and sometimes a human hand-writing it would have done it differently and that way would have been better. Now adays, thanks to some very clever humans, that's a rare feat indeed, and the differences are usually too small to care about.

So, whether or not the compiler was bootstrapped or not, and whether or not compilation happens late, or early, or just in time, or only via mail service with a SASE to Bangladesh, the result is not necessarily limited by the path it took to the same destination.

Answer 2

1. Modern compilers (especially JITs) have optimization algorithms that exist outside the domain of the source languages. This invalidates your original premise, which is that a bootstrapped compiler can't be faster than a "native" compiler because it is built on top of a subset of the source language.

2. Programmers are notoriously bad at predicting where code will perform suboptimally. The only good way to know is to measure performance with a profiler.

3. Nowadays, a good optimizing compiler can often produce object or binary code that is faster than hand-coded assembly, provided the source code is written in a way that doesn't defeat the compiler's optimizations.

Answer 3

1. Design language A.
2. Write first A-compiler in language B.
3. Compile first A-compiler using any B-compiler.
4. Write second A-compiler in language A.
5. Compile second A-compiler using the executable obtained in step 3.
6. Compile second A-compiler using the executable obtained in step 5.

Assume that all compilers involved (the B-compiler and both A-compilers) are correct. Then the executables obtained in step 5 and 6 both match the source code written in step 3 - in particular, they parse A code, optimize it, and generate code for it exactly as specified during step 4, regardless of what happened during step 2.

In addition, the executable from step 6 contains exactly the code the second compiler ought to emit, regardless of what kind of code the first compiler emitted during step 5 (again, as long as it was correct given the source code).

Repeat this process as necessary. Any compiler, no matter how complicated its ancestry and bootstrapping process are, can be made to both

1. run as fast as it possible can with the best A- or B-compiler.
2. emits code that is as efficient as the most efficient code any A-compiler.

Note that these are two quite different metrics, I included both because it wasn't clear which one you were talking about.

Answer 4

One reason why they (the bootstrapped compilers) may be faster because in low-level language, you make things work, but you probably won't bother to implement complex behaviour. In high-level language it's much easier. IOW, optimizations (at algorithm and data structure level) is often easier to do in higher language than in assembler.

Answer 5

We first assume that the language A which you want to have a compiler for is suitable for writing compilers. If not (say the language is FORTRAN, or zsh shell scripts), then you won't ever write a compiler for A in the language A, so there will be no bootstrapping.

Otherwise, since you don't have a compiler for A, you can't write an A-compiler in the language A because you can't compile the compiler, and therefore can't compile any A programs including the compiler. That's where bootstrapping comes in: You write a compiler for the A-language in language B, which is suitable for writing compilers. When you are done, you have an A-compiler of unknown quality. Then you can write an A-compiler in the A-language and compile it with the A-compiler written in the B-language. Once you have that, you can forget about B completely.

You improve your A-compiler written in the A language by adding any missing features that the compiler written in B didn't support. When your compiler supports a new feature, then it can use the new feature. Then you can improve the compiler by making it generate faster code. Once you've done that, you compile your A compiler with the version that generates faster code, and you get an A compiler that runs faster.

Since generating faster code can cost time, you may add a switch to the compiler to either generate code as quickly as possible, or to generate the fastest possible code. Once you have this, you can compile the A compiler with a setting "generate the fastest possible code". Compiling the compiler may take a while, but you now have a compiler that runs at the highest possible speed, and generates the fastest possible code. But while you develop the compiler, you will use the setting that generates code as quickly as possible, so you can produce new compiler versions quickly. These compiler versions will be able to compile quickly or to generate good code, but will take longer to do so. But once you have a compiler you want to ship, you compile it with the option to produce the fastest possible code.

So the end result will be a compiler that runs as fast as possible, and can generate slow code quickly, or can generate fast code more slowly. So there is no cost from the fact that you used bootstrapping.

Now there might be the situation that your language A is inherently more complicated than language B. For example by having extra overhead because variables have no type. In that case, a compiler written in A might be slower than one written in B. But that means we are back to the first case, where language A is not as suitable for writing compilers as language B.

Another problem is that A might be very suitable for writing compilers, but you already have B compilers for various languages X, Y and Z, and it is easier to create a compiler for A by modifying a compiler for X, Y or Z. So you will have to do less work by creating A in language B by modifying one of the available compilers and end up with four compilers for X, Y, Z and A written in the B language.