Jeff Hui

This vulnerability is what we call the Filibuster. The Filibuster is a part of the Jefferson spec that allows programs that never halt. In the federal government, it only exists in the Senate, because the House used metaprogramming to reduce the two-thirds rule on the PQ operator to simple majority.

— Jacob Davis-Hanssson, The United States Congress is an elegant stack machine

Elastic Tabstops:

The solution - move tabstops to fit the text between them and align them with matching tabstops on adjacent lines

For as long as we continue to define each tabstop as being a multiple of N characters we will never be able to solve this problem satisfactorily. The problem is that we’re using tabs and spaces to format text for aesthetic reasons rather than treating them semantically - tabs are for indenting and aligning text, spaces are for separating keywords.

What use is an AST without using it? As a test, I took my favorite network protocol and pasted the basic rules from the spec into a file and normalized its specification as a custom grammar:

Then attempted to generate the code parse it. Go isn’t particularly good at large switch statements and string generation (to use the switch statement). The easiest is to transform the AST into a form that a template finds useful, and then use text/template:

It's just a poor implementation of LISP. It would be better if there was a generalized way of traversing the tree. There’s been a handful of attempts of universal abstract syntax trees (UASTs), but they usually are in conflict with performance. It might be worth the trade off to build some generic algorithms (type checking is what first comes to mind). But that requires more thinking.

Also, happy holidays! 😄

A parser combinator gives a lot of flexibility if you need to parse many languages, usually at the cost of performance. Although sacrificing purity can get you an order of magnitude away from a hand-written parser. The most notable parser in Go is actually it’s own compiler, which is written in go itself. So writing a competing implementation is a good way to compare against hand-optimized implementations on a fair playing field since my parser is in go.

It’s roughly 8 times slower. My parser reads around 1.6MB/s (Go’s is blazing away at 12 MB/s).

Go, the language, is actually a pretty good test of a parser combinator:

• It’s a relatively small grammar to write to parse go code.
• It’s grammar doesn’t have ambiguities like C++.
• It has automatic semicolon insertion which requires an unusual step for the lexing phase.
• It has basic inferred typing (which this parser currently does not do).

Obviously the resulting AST is vastly different between both:

• Go’s parser emits structs that conform directly to the struct of Go code (eg - having structs with field names that directly map to the language)
• Go’s parser assumes all file content is static, which allows for some performance optimizations that I don’t want (I want some IDE-like interactivity).
• My parser emits a general AST that require priori knowledge to walk it (since it’s just a list of nodes). For example, there’s a lot of unnecessary curly braces littered in my AST. It’s fixable with annotations in the parser combinator to exclude generation of those tokens, but hasn’t been implemented yet.
• My parser can be repurposed to another language since it’s a parser combinator.
• Go’s parser does not need to assume infinite lookahead. My parser currently assumes all tokens are lex-ed before parsing occurs. Go’s just-time lexes the next token for parsing.
• Auto-semicolon insertion can be implied in Go’s compiler. So far my compiler needs a hook while lexing to insert implied semicolons.

Some other optimizations probably should be a done at some point:

• Use the Go’s technique of using one int instead of two ints to store token positions. It requires assuming all the files being parsed as one contiguous buffer. The gain in parsing may outweigh the cost to set up a group of files for parsing when an edit is made to a file.
• Have my parser not emit unnecessary tokens (eg - emitting open and close parentheses).
• Error reporting and failure recovery can be upwards of 30% of the cost in my parser. I do want meaningful error messages, but I also don’t want to pay the performance cost of tracking enough information to reproduce those error messages.

It would be great if there was a generalized AST walker for common compiler behaviors (eg - type checking), but it seems like once the AST is created, most of the generalizability is lost until another abstract tree is derived from it (like the LLVM AST).

All the optimization needs to be a proper blog post, but here’s a log of various optimization attempts:

Stack-based no pointers:

Lift · (master) ★ ⟩ make bench ~/w/Lift
 go test -benchmem -bench=‘Benchmark.’ -run=‘^$’ . ./assert ./byteconv ./cmd/lift ./parser
 goos: darwin
 goarch: amd64
 BenchmarkGolangParsingFile-8        50000 38515 ns/op 28288 B/op 215 allocs/op
 BenchmarkGolangParsingGrammarFile-8 500 4124223 ns/op 1104208 B/op 23185 allocs/op
 BenchmarkTransformingLisp-8         1000000 1151 ns/op 440 B/op 23 allocs/op
 PASS
 ok _/Users/jeff/workspace/Lift/parser 5.941s


Pointer-based no optimizations:

Lift · (master) ★ ⟩ make bench ~/w/Lift
 go test -benchmem -bench=‘Benchmark.’ -run=‘^$’ . ./assert ./byteconv ./cmd/lift ./parser
 goos: darwin
 goarch: amd64
 BenchmarkGolangParsingFile-8        20000 59981 ns/op 45984 B/op 991 allocs/op
 BenchmarkGolangParsingGrammarFile-8 200 6272572 ns/op 3201888 B/op 111969 allocs/op
 BenchmarkTransformingLisp-8         2000000 892 ns/op 184 B/op 16 allocs/op


Pointer-based with pools:

Lift · (master) ★ ⟩ make bench ~/w/Lift
 go test -benchmem -bench=‘Benchmark.’ -run=‘^$’ . ./assert ./byteconv ./cmd/lift ./parser
 goos: darwin
 goarch: amd64
 BenchmarkGolangParsingFile-8        10000 133741 ns/op 33893 B/op 528 allocs/op
 BenchmarkGolangParsingGrammarFile-8 100 14941902 ns/op 1645023 B/op 60928 allocs/op
 BenchmarkTransformingLisp-8         2000000 898 ns/op 184 B/op 16 allocs/op


Stack-based with no return value (write to shared state):

Lift · (master) ★ ⟩ make bench ~/w/Lift
 go test -benchmem -bench=‘Benchmark.’ -run=‘^$’ . ./assert ./byteconv ./cmd/lift ./parser
 goos: darwin
 goarch: amd64
 BenchmarkGolangParsingFile-8        30000 40670 ns/op 28304 B/op 215 allocs/op
 BenchmarkGolangParsingGrammarFile-8 300 4001636 ns/op 1112160 B/op 23356 allocs/op
 BenchmarkTransformingLisp-8         1000000 1158 ns/op 440 B/op 23 allocs/op


” with ParserContext field reordering:

Lift · (master) ★ ⟩ make bench ~/w/Lift
 go test -benchmem -bench=‘Benchmark.’ -run=‘^$’ . ./assert ./byteconv ./cmd/lift ./parser
 goos: darwin
 goarch: amd64
 BenchmarkGolangParsingFile-8        30000 40436 ns/op 28304 B/op 215 allocs/op
 BenchmarkGolangParsingGrammarFile-8 500 4000211 ns/op 1112160 B/op 23356 allocs/op
 BenchmarkTransformingLisp-8         1000000 1142 ns/op 440 B/op 23 allocs/op
 PASS
 ok _/Users/jeff/workspace/Lift/parser 5.197s

Stack-based with ParserContext field reordering, but restored return value:

Lift · (master) ★ ⟩ make bench ~/w/Lift
 go test -benchmem -bench=‘Benchmark.’ -run=‘^$’ . ./assert ./byteconv ./cmd/lift ./parser
 goos: darwin
 goarch: amd64
 BenchmarkGolangParsingFile-8        30000 40384 ns/op 28272 B/op 215 allocs/op
 BenchmarkGolangParsingGrammarFile-8 500 3934413 ns/op 1104192 B/op 23185 allocs/op
 BenchmarkTransformingLisp-8         1000000 1158 ns/op 440 B/op 23 allocs/op

Stack-based, with reordered fields, and reuse []SyntaxNode (custom pool):

Lift · (master) ★ ⟩ make bench ~/w/Lift
 go test -benchmem -bench=‘Benchmark.’ -run=‘^$’ . ./assert ./byteconv ./cmd/lift ./parser
 goos: darwin
 goarch: amd64
 BenchmarkGolangParsingFile-8        50000 38947 ns/op 28192 B/op 152 allocs/op
 BenchmarkGolangParsingGrammarFile-8 500 3904994 ns/op 1158586 B/op 17155 allocs/op
 BenchmarkTransformingLisp-8         1000000 1166 ns/op 440 B/op 23 allocs/op

Prev + More field reordering:

Lift · (master) ★ ⟩ make bench ~/w/Lift
 go test -benchmem -bench=‘Benchmark.’ -run=‘^$’ . ./assert ./byteconv ./cmd/goparse ./cmd/lift ./parser
 goos: darwin
 goarch: amd64
 BenchmarkGolangParsingFile-8        50000 33827 ns/op 12672 B/op 143 allocs/op
 BenchmarkGolangParsingGrammarFile-8 500 3767218 ns/op 1110288 B/op 16975 allocs/op
 BenchmarkTransformingLisp-8         1000000 1148 ns/op 440 B/op 23 allocs/op

Prev + prealloc + reused SyntaxNode.Children as LexPos:

Lift · (master) ★ ⟩ make bench ~/w/Lift
 go test -benchmem -bench=‘Benchmark.*’ -run=‘^$’ . ./assert ./byteconv ./cmd/goparse ./cmd/lift ./parser
 goos: darwin
 goarch: amd64
 BenchmarkGolangParsingFile-8        50000 32636 ns/op 10880 B/op 144 allocs/op
 BenchmarkGolangParsingGrammarFile-8 500 3846066 ns/op 1070352 B/op 17695 allocs/op
 BenchmarkTransformingLisp-8         1000000 1135 ns/op 440 B/op 23 allocs/op

 

Fast compilers tend to reduce the amount of memory that is generated for ASTs. That can mean simple things like not generating all lever tokens at once. Although trying to have a single representation for an AST node is difficult. Sometimes a c-styled unions is needed. Unfortunately go doesn’t support that. But better or worse, using unsafe pointers can allow us to do so.

I’m not really sure of the implications to the GC, but it can be a clever way to pack more information in the same. It’s nice that go can do this even if it’s significantly uglier. An interface can be built to hide this detail (by returning a pointer).

Not sure if it’s reasonable to do in Swift without exposing UnsafeMutablePointer<T> as it’s API or using classes (which may require more memory overhead?).

As a fun hobby project, I’ve been writing a compiler and trying to optimize it as much as possible (for speed). It's interesting to see the memory allocation breakdown (which has some correlation to perf).

(Turns out error reporting is memory intensive).