Optimise `surface::pretty`

[Kmeakin]

Fixes very high heap utilization when rendering surface AST to Doc for pretty printing.

Problem was in surface::pretty::sequence, in particular the use of FlatAlt. FlatAlt requires allocating two AST nodes, one for the single line situation and one for the multi line situation. When used recursively, this will lead to exponential space and time complexity! Fortunately, we can push FlatAlt down into the leaves: it is only necessary when deciding whether to emit a separator (eg ,) or nil at the end of the item in the list.

[Kmeakin]

Benchmark results

Before

Peak memory usage, as measured by heaptrack ./target/release/fathom data --module formats/opentype.fathom /usr/share/fonts/liberation/LiberationMono-Bold.ttf: 142.9MB

Runtime, as measured by hyperfine -w 1 -r 10 "./target/release/fathom data --module formats/opentype.fathom /usr/share/fonts/liberation/LiberationMono-Bold.ttf":

  Time (mean ± σ):     341.7 ms ±   3.3 ms    [User: 315.4 ms, System: 25.9 ms]
  Range (min … max):   337.2 ms … 347.1 ms    10 runs

After

Peak memory usage, as measured by heaptrack ./target/release/fathom data --module formats/opentype.fathom /usr/share/fonts/liberation/LiberationMono-Bold.ttf: 14.2MB

Runtime, as measured by hyperfine -w 1 -r 10 "./target/release/fathom data --module formats/opentype.fathom /usr/share/fonts/liberation/LiberationMono-Bold.ttf":

  Time (mean ± σ):      38.0 ms ±   1.0 ms    [User: 33.9 ms, System: 4.2 ms]
  Range (min … max):    37.1 ms …  39.7 ms    10 runs

[brendanzab]

The initial win was good, but I’m not sure about the later micro-optimsations. I think I’d prefer to hold off on these to another PR. I’m somewhat uncomfortable with the interner optimisation: while it looks tempting it I think I’d prefer it if we could properly encapsulate the unsafe code around the string interner.