Alex Rivera | Logout

What are the key design choices to make a wicked fast compiler?

Asked 2010-09-13T19:35:55.553
10

I want to know how to design a compiler that compiles very, very quickly.

First, let me head off some obvious misunderstandings of my question:

  1. I am not talking about the speed of the code produced by the compiler. There are already many resources available for learning how to optimize generated code. What I'm having trouble finding is information on making the compiler fast.

  2. I'm also not interested in a discussion of why C++ compilers are generally slower than Java compilers (for example). I'm interested in what techniques can be used to be speed up the compiler for any given language.

  3. I also don't want to hear about distributed compilation systems like Microsoft's Incredibuild or Unix's distcc. Those systems don't give you faster compilers, they just give you more compilers. Which is certainly useful, but that's not the question I'm asking. I want to know how to design a fast compiler for a single CPU.

  4. Nor is ccache the answer I'm looking for. That's a system that allows you to avoid using the compiler at all, but it doesn't make the compiler faster. Again, that's useful; again, that's not the question I'm asking.

I hope my question is now crystal clear. But perhaps some history will make it even clearer.

C compilers used to be really slow. Then, in 1986, THINK Technologies introduced Lightspeed C for Macintosh, and it compiled programs almost instantaneously. Lightspeed C was so much faster than all the other C compilers that there was hardly any comparison. (Perhaps Lightspeed C wasn't the first of the new generation of lightning-fast compilers, but it was the first in my experience. Turbo Pascal came earlier [1983] but I had no experience with it, so I don't know how it compared, speed-wise.)

Since then, many fast compilers have been available. It seems that there was some

design-patterns performance compiler-theory
Edit
Report

1 Answer

4
  • Simple syntax that can be parsed in a single pass.
  • Simple target code. If you don't target machine code directly you can get away with many things.
  • Not compiling at all. If you don't need fast execution or design mostly for one off scripts, you don't need to waste time analyzing the code.
  • Don't, I repeat, do not try to out-smart your OS disk/cache management. Mmap the whole damn file and read it as if you read it from RAM. If you don't have a virtual memory, fast compilation is the least of your worries.
  • Avoid creating XML DOM like bloated data structures for AST. You don't need to animate your operator precedences. Keep pointers to the mmaped data instead of copying stuff around.
  • Profile your code if you want it fast. Always.

Addition:

  • Learn different ways to parse. If you are not extremely confident of your parser writing skills, use proven parser/lexer generator tools like antlr, lemon etc.
answered 2010-09-13T20:06:41.080

Your Answer