Go’s lexer gets faster with time—and with a string-based API
A TableGen lexer written in Go back in 2014 took roughly 20 ms to process 1 MiB of source. Running the same code today with Go 1.18 cuts that to about 9.6 ms—more than a 2× improvement. The gains are mostly thanks to improvements in the garbage collector rather than the compiler itself.
$ TDINPUT=input.td go test -bench=Preall -benchtime=5s
Results across Go versions show little change between 1.2 and 1.5, a significant jump by 1.10, and further gains in later releases. By Go 1.18, the code is more than twice as fast as the original.
Where the time goes
Profiling with Go’s standard tooling on Go 1.18 points to the expected hot spots. The next function—which pulls characters from the input stream—dominates the profile, similar to how text/scanner works internally.
$ TDINPUT=input.td go test -cpuprofile cpu.out -bench=Preall -benchtime=5s ... # --nodefraction tells pprof to ignore nodes that take less than 5% of the # total time - this significantly reduces the clutter in the produced graph $ go tool pprof --nodefraction=0.05 ./example.com.test cpu.out ... (pprof) web
The bigger surprise is that 16.5% of CPU time lands in slicebytetostring. That’s the allocation and copy triggered when a []byte slice is converted to a string—an operation that appears throughout the scan* methods:
func (lex *Lexer) next() {
if lex.nextpos < len(lex.buf) {
lex.rpos = lex.nextpos
// r is the current rune, w is its width. We start by assuming the
// common case - that the current rune is ASCII (and thus has width=1).
r, w := rune(lex.buf[lex.nextpos]), 1
if r >= utf8.RuneSelf {
// The current rune is not actually ASCII, so we have to decode it
// properly.
r, w = utf8.DecodeRune(lex.buf[lex.nextpos:])
}
lex.nextpos += w
lex.r = r
} else {
lex.rpos = len(lex.buf)
lex.r = -1 // EOF
}
}
return Token{IDENTIFIER, string(lex.buf[startpos:lex.rpos]), startpos}
Go cannot safely alias a mutable []byte with an immutable string, so string(b) always allocates a new backing array. Memory profiling confirms the allocations come from that line. Since much of the CPU cost is in mallocgc, the dramatic speedups seen since Go 1.2 are less about compiler improvements—even with the register-based ABI in 1.17—and more about the garbage collector handling all those allocations far more efficiently.
Substring APIs remove the copies
The lexer’s API takes a []byte and returns tokens with string values:
func NewLexer(buf []byte) *Lexer
type Token struct {
Name TokenName
Val string
Pos int
}
Switching the input to a string changes the picture. Strings are immutable, so subslices share the same underlying byte buffer and creating one is just a new two-word header—no allocation involved:
s := "hello there" s2 := s[6:]
Rewriting the lexer around this principle is straightforward. The scanIdentifier method no longer needs a string(...) cast; it can return a substring directly:
func (lex *Lexer) scanIdentifier() Token {
startpos := lex.rpos
for isAlpha(lex.r) || isDigit(lex.r) {
lex.next()
}
return Token{IDENTIFIER, lex.buf[startpos:lex.rpos], startpos}
}
The benchmark drops to 7.7 ms, roughly 20% faster.
API trade-offs
Whether a string-based API is practical depends on the input source. If the data is already in memory—say from a text box—a string input is natural. But data often comes from an io.Reader, where input is read incrementally and the full slice isn’t available up front. In that case, the substring optimization doesn’t apply.
Go’s own text/scanner takes that route. Its TokenText method internally does what amounts to string(buffer), with the accompanying allocation:
func (s *Scanner) Init(src io.Reader) *Scanner
The Go compiler’s scanner does the same—it reads from an io.Reader and copies literal values into string fields.
The GC still matters
Even with all layout-visible allocations removed, profiling the string-based version shows GC activity still consuming a noticeable share of CPU:
That’s partly an artifact of the benchmark. The test loops over tokenizeAllPrealloc, which pre-allocates a slice of 200,000 tokens—each 32 bytes—then discards it. Over a 5-second run, that’s hundreds of cycles and several gigabytes of heap churn, each cycle triggering collection at the default GOGC=100 setting.
Raising GOGC reduces that overhead. With GOGC=1600, the run completes in about 6 ms—a 37% gain over the original 9.6 ms result—with the collector invoked only ~50 times instead of 700+. Disabling GC entirely with GOGC=off lands slightly slower at 6.5 ms.
These micro-optimizations only matter if the whole application lifecycle is tuned. Still, the trend is clear: the Go GC keeps improving. An accepted proposal adds a GOMEMLIMIT variable, and a longer-term plan explores arenas for programs like compilers that allocate in distinct phases.
Even without any tuning, the original scan-and-copy lexer processes over 100 MiB/sec—often at or beyond the speed of reading the source from storage. With an API change and GC tweaks, that improves further, though real gains depend on the broader application context.
Update (2022-05-24): Go 1.19 in development runs the benchmark at 5.6 ms with GOGC=1600.
Update (2023-06-02): The in-development Go 1.21 brings that down to 4.5 ms under the same settings.
