A Coroutine-Style Lexer vs. the State-Machine Approach
Rob Pike's 2011 talk on lexical scanning in Go presented an elegant technique: implement a lexer as a goroutine that communicates tokens over a channel, switching between states by returning the next state function. It's a design that reads beautifully in theory—no explicit state machine, no flags to check at every step. But how does it hold up under a benchmark?
To find out, I reimplemented my TableGen lexer using this coroutine style and compared it against my earlier, faster state-machine version. The exercise started with transcribing Pike's original template lexer and then adapting it to TableGen, a language without the clean two-state oscillation between text and actions that makes the coroutine approach so appealing for templates.
The public API stayed identical to my previous lexers. The same Token type is used, and the NextToken method has the same signature:
func (l *Lexer) NextToken() Token {
return <-l.tokens
}
Under the hood, the constructor launches a goroutine and a channel:
// Lex creates a new Lexer
func Lex(input string) *Lexer {
l := &Lexer{
input: input,
tokens: make(chan Token),
}
go l.run()
return l
}
A run method serves as a trampoline between state functions, each of which can emit tokens into the channel:
type stateFn func(*Lexer) stateFn
func (l *Lexer) run() {
for state := lexText; state != nil; {
state = state(l)
}
close(l.tokens) // no more tokens will be delivered
}
Structurally, it's a faithful port of Pike's design. The state management is indeed simpler—no explicit state variable to maintain. But the performance story is more complex.
The Big Performance Hit
Running the same benchmark as in my previous work—the same input file, the same invocation, the same GOGC=1600 setting—the coroutine-style lexer finished in about 70 ms. That's over ten times slower than the 6 ms achieved by the fastest previous Go lexer.
The source of the slowdown isn't hard to pinpoint. In the state-machine lexer, each call to NextLexer skips whitespace, inspects the current rune, lexes a token, and returns. In the coroutine version, each call to NextLexer is essentially a channel receive. Meanwhile, the lexing goroutine does the real work and then performs a channel send.
Channels are fully synchronized in Go, meaning each send and receive involves locking. Worse, the runtime has to suspend and later wake goroutines when the channel is not immediately available. Those operations are highly optimized, but placed inside the inner loop of a scanner, the relative cost is enormous.
A pprof profile makes this obvious. Where the previous lexer's "fetch next rune" method dominated execution time, it now accounts for just 5.8%. Instead, the runtime functions chansend1 and chanrecv1 take up the bulk, along with the goroutine management code that supports them.
A Partial Fix: Buffered Channels
Go's make creates an unbuffered channel by default, so every send blocks until a receive occurs. That forces constant goroutine switching. Using a buffered channel should let the lexing goroutine run ahead, reducing suspensions. I tested buffer sizes from 1 to 16384, stepping by factors of four:
As expected, buffering helps considerably. Timing levels out around 24 ms for a buffer of 1024 or more. That's a major improvement over the 70 ms unbuffered case, but still four times slower than the 6 ms of the ordinary, non-concurrent lexer.
Buffering isn't a universal remedy. Channels are often used for synchronization, where large buffers defeat the purpose. For a lexer, running ahead is generally harmless—but there are grammars, like those of C, where a lexer may need feedback from the parser, which would complicate things.
Interestingly, the template lexer in the standard library, derived from Pike's talk, still uses an unbuffered channel. A modest buffer could speed it up, a point raised in a Go issue proposing exactly that change.
Should You Care?
For many use cases, no. The coroutine-style lexer is still fast in absolute terms—far quicker than the regex-based lexers I've written in higher-level languages. Template parsing, the standard library's main consumer of this technique, typically handles small inputs parsed once at startup; the parsing time rarely matters.
Where it could matter is in a frontend for a nontrivial language, especially one powering an interpreter where the lexer runs continuously. In such a performance-sensitive setting, the elegance of a coroutine design may not justify the runtime cost; a straightforward state machine remains the faster choice.
