Writing a Fast Compiler
12 points by abhin4v
12 points by abhin4v
I was hoping for a bit more substance, rather than just a list of somewhat vague things to do. For example, there's a decent portion dedicated to lexical analysis and parsing and yet that's usually the least time consuming process of a compiler (unless you're implementing a dump source-to-source compiler). It's also a stage that's pretty easy to speed up dramatically by performing the work in parallel.
To illustrate, a non-incremental debug build of Inko's entire test suite (which effectively also means it includes the entire standard library, and clocks in at somewhere between 50 000 and 100 000 LOC) takes about 4.2 seconds in total on my desktop, of which only 2% is spent in lexing and parsing while 73% is spent in lowering to and compiling the LLVM IR to machine code.
I did recently spend some time looking into optimizing the lexer and parser by doing fewer string allocations in a bunch of places where they are technically redundant. My findings were that the resulting code wasn't something I was happy with, and there was no measurable difference in performance.
The areas where things are more interesting to optimize (and to discuss on how to do that) would be type checking. This stage typically involves a lot of mutations of shared data structures such that you can't just slap a bunch of threads on it and call it a day. You'll likely also end up producing a lot of garbage that needs to be cleaned up, such as when you specialize generic types and functions as the original version has to be kept around until this stage is done.
Another time consuming stage is inlining, which suffers from the same issues: lots of mutations, difficult to parallelize, and lots of copying (and thus an increase in memory usage). In fact, the inliner is probably the most time consuming part of Inko's compiler apart from the LLVM stage. It's also the most memory hungry because of all the copying it needs to do.
I'd love to read more about those stages, yet there's sadly not a lot available on it. My best guess is that most writing their own compiler either give up before reaching a point where they need to implement this themselves, or they just never do and defer to some underlying library/compiler (e.g. LLVM) to do all the work for them.
Yeah, my experience has been that the hard parts of building a compiler intended for serious use (as opposed to e.g. a hobby project created primarily for fun and/or the author's learning) get glossed over by learning materials about compilers. For example, the article includes this diagram:
Lexical Analysis ---> Syntax Analysis ---> Build ---> Code Generation
Everything I would categorize as "the hard parts" of building a compiler all live in that step labeled "Build" - type-checking, optimizing, and lowering to an A-normal form (or something similarly primitive) representation. Those are the hard parts, and I'd guess maybe 90% of the time spent on a production compiler is spent on them. Everything up through and including parsing is so much easier it's closer to "trivial" than "comparable." I'd say code generation, including to x64, ARM, wasm, and LLVM IR, is only somewhat harder than parsing.
Those hard parts also account for ~all of the time spent in compilation, with the two exceptions of LLVM and linking. LLVM is famously slow to do anything, including to emit completely unoptimized code, and even modern linkers like mold and lld can be a big source of build time. This has been not only my personal experience, but also what I've heard from other authors of production compilers that emit machine code. So unless you're doing your own low-level optimizations and/or linking, making compilation faster also usually means spending ~all your time on things in that "Build" step.
That said, I'm not surprised the article focuses on the easy parts - the harder stuff is not only hard, it takes a lot more time to explain! When I taught a 1-day workshop on implementing a type checker with type inference (https://master.dev/courses/type-compiler/) the challenge was fitting all the necessary background info into the time slot of a single day. Compilers are a deep topic!
I strongly recommend looking at the other projects from this author while you’re there. Every single one is beautiful.