Graydon Hoare: 21 compilers and 3 orders of magnitude in 60 minutes

In 2019, Graydon Hoare gave a talk to undergraduates (PDF of slides) trying to communicate a sense of what compilers looked like from the perspective of people who did it for a living.

I've been aware of this talk for over a year and meant to submit a story here, but was overcome by the sheer number of excellent observations. I'll just summarise the groups he uses:

  • The giants: by which he means the big compilers that are built the old-fashioned way that throw massive resources at attaining efficiency
  • The variants, which use tricks to avoid being so massive:
    1. Fewer optimisations: be traditional, but be selective and only the optimisations that really pay off
    2. Use compiler-friendly languages, by which he is really taking about languages that are good for implementing compilers, like Lisp and ML
    3. Theory-driven meta-languages, esp. how something like yacc allows a traditional Dragon-book style compiler to be written more easily
    4. Base compiler on a carefully designed IR that is either easy to compile or reasonable to bytecode-interpret
    5. Exercise discretion to have the object code be a mix of compiled and interpreted
    6. Use sophisticated partial evaluation
    7. Forget tradition and implement everything directly by hand

I really recommend spending time working through these slides. While much of the material I was familiar with, enough was new, and I really appreciated the well-made points, shout-outs to projects that deserve more visibility, such as Nanopass compilers and CakeML, and the presentation of the Futamura projections, a famously tricky concept, at the undergraduate level.