Dense Arena Interning: The Engine of Compiler Performance

A collection of thoughts I had while reading the article:

0. Overall, a nice article.

1. There are several places where the (LLM assisted?) writing is a bit odd. For example, the code for hash table insertion is irrelevant. The "“Un-freeable” Nature of Arenas" paragraph sets up a problem that I expect the next section to resolve, but the next section goes in a different direction.

2. It feels like the author is on the verge of rediscovering some classic PL concepts. E.g. tries or regular expressions for faster lexing (why would you ever do strcmp in a loop in a lexer?); de Bruijn indices for disambiguating lexically scoped variables; strong normalization in type systems to canonicalize types.

3. I was expecting some benchmark results.

Interning can be really helpful.

In the early noughties I worked in a compiler in Java, and using String.intern() at the lexical level helped a lot with compiling speed and garbage generation.

It can be a neat trick, since you do it at lexing time and you speed up any subsequent String.equals() call.

It was particularly important for us because we called it very often in an IDE in the editor for error highlighting and auto completion and you want sub-300ms responses or it feels extremely slow.

Machines at the time were under 1GB of RAM and fairly slow

So, it's like converting to symbols in lisps. EQ on symbols is also a single word comparison.

An interesting part is where you want to have maps from these.

Common python strings are interned to speed things up as well. Maybe this way of interning could benefit cpython.