3

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!

6
  • 1
    Assembler is not as low as you can get. Machine code is lower. ;-)
    – herby
    Jan 15, 2014 at 18:38
  • 3
    Are you talking about the speed at which the compiler runs, or the speed at which code generated by the compiler runs?
    – user7043
    Jan 15, 2014 at 18:38
  • 3
    @herby Assembly is essentially a different spelling for machine code in that you can make the assembler generate pretty much any machine code possible.
    – user7043
    Jan 15, 2014 at 18:40
  • 5
    Yeah, assembly language is essentially machine language. There's a one-to-one mapping between the instructions in assembly language source and the underlying machine instructions. Jan 15, 2014 at 18:42
  • 1
    It's hard to guess what are you actually talking about, but, take a look at Tachyon and PyPy.
    – SK-logic
    Jan 16, 2014 at 10:03

5 Answers 5

8

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.

2
  • 1
    That kind of missed my questions. I changed the OP a bit to make them obvious. Sorry for the misunderstanding.
    – Profpatsch
    Jan 16, 2014 at 10:51
  • @Profpatsch I'm afraid I'm still not entirely sure how what you are asking is terribly different? I see how question 1 might be more about comparing bootstrapped to non-strapped implementations, and 2 is about the result of problems with the "Genesis Compiler", if you will, but I think my answer is somewhat the same even then. The compiler itself could potentially be slower if it must go through various logical hoops to get to the end generation of code, but the code that results doesn't necessarily depend on any of those steps. So I'm not sure even how I would change my answer after the edit.
    – BrianH
    Jan 16, 2014 at 21:34
7
  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.

1
  • The question was more on a computational theory level. But bullet point 1) would be a good fit to be considered in delnan’s answer.
    – Profpatsch
    Jan 16, 2014 at 10:54
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.

2
  • That was enlightning. I fixed my OP up a bit to outline the questions, but based on this answer I’d assume Q1:no, Q2:Yes.
    – Profpatsch
    Jan 16, 2014 at 10:50
  • If compilers were deterministic, this approach could be used to guard against some compiler-bootstrapping attacks; if a version of trustworthy compiler X is available in source-code form, compiling it with two or more other compilers of independent vintage and then using the resulting executables to bootstrap X with itself should produce two (or more) identical executables for X, regardless of what compilers were used initially. If at least one of the original compilers couldn't plausibly contain a compiler-bootstrapping attack against X, that would imply the executable couldn't either.
    – supercat
    Feb 20, 2015 at 18:19
0

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.

0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.