2

I have a good grasp on how the C compiler was boostrapped 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!

  • 1
    Assembler is not as low as you can get. Machine code is lower. ;-) – herby Jan 15 '14 at 18:38
  • 2
    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 '14 at 18:38
  • 2
    @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 '14 at 18:40
  • 4
    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. – Robert Harvey Jan 15 '14 at 18:42
  • It's hard to guess what are you actually talking about, but, take a look at Tachyon and PyPy. – SK-logic Jan 16 '14 at 10:03
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.

  • That kind of missed my questions. I changed the OP a bit to make them obvious. Sorry for the misunderstanding. – Profpatsch Jan 16 '14 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 '14 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.

  • 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 '14 at 10:54
2
  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.

  • 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 '14 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 '15 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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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