Making `wc` 20x faster with parallel state machines - aarol.dev
Making `wc` 20x faster with parallel state machines
Published 20.07.2026
A few years back, I came across Robert Graham’s wc2 repository on GitHub. wc2 is an implementation of the Unix wc command that is significantly faster than the existing GNU and BSD wc implementations. It achieves its speed by using something called a state machine. The repo contains a nice write-up that explains some things, but doesn’t explain how the program actually works. I wrote this post to explain all of that.
I’ll also show how I made it even faster by parallelizing the word-counting across many threads. On sufficiently large inputs, zwc is 5-20 times faster than GNU or BSD wc.
Preface
wc, short for “word count”, is a command that calculates the number of lines, words, and bytes contained in the given input file(s). A word as “a string of characters delimited by white space characters”.
For example, to count the number of words in a file, you simply type:
$ wc -w file.txt<br>598 file.txt<br>You can also display the number of lines, words and bytes together (the default behaviour):
$ wc -lwc file.txt<br>167 598 4614 file.txt<br>Calculating the byte count is easy: just keep track of the number of bytes processed. The line count is also trivial, just count the number of \n characters, but what about the word count? We can’t just count the number of whitespace characters, since a words may be delimited by more than one whitespace.
The simple solution is to keep track of whether the previous character was a whitespace character. If a non-whitespace character is encountered after a whitespace character, it means that a new word was entered.
Basic implementation
Here is a simple, plain ASCII word count implementation in Zig 0.15:
pub fn wc_ref(reader: *std.Io.Reader) Result {<br>var line_count: usize = 0;<br>var word_count: usize = 0;<br>var byte_count: usize = 0;
var in_word: bool = false;
while (true) {<br>const b = reader.takeByte() catch break;<br>byte_count += 1;<br>switch (b) {<br>'\n' => {<br>line_count += 1;<br>in_word = false;<br>},<br>'\r', '\t', ' ' => {<br>in_word = false;<br>},<br>else => {<br>if (!in_word) {<br>word_count += 1;<br>in_word = true;<br>},<br>return .{<br>.line_count = line_count,<br>.word_count = word_count,<br>.byte_count = byte_count,<br>};<br>Anytime a whitespace (carriage return, tab, space or newline) character is encountered, in_word is set to false. If the next character is not whitespace but the previous character was, then a new word is entered and word_count is incremented.
This is the basic idea behind the macOS wc, GNU wc and uutils wc (Rust port of GNU Coreutils) implementations.
In this post, we’re going to take a different approach: modeling the program flow as a state machine. The benefits of this approach will be clear later on.
State machines
A state machine is a mathematical model that consists of a number of unique states, an initial state, and a series of transitions from one state to another depending on the input character. Here is the wc program represented as a state machine:
WhitespaceNew wordChWsIn wordChNewlineNlNlChWsWsNlChNlWsLegendNl: Newline characterWs: Whitespace characterCh: Character (non-whitespace)
When executing the state machine, it starts off in the “Whitespace” state and reads the input one character at a time, transitioning into the next state depending on the type of that character.
The important thing to recognize in this graph is the distinction between “New word” and “In word”. If the previous state was “Newline” or “Whitespace”, then a non-whitespace character will always transition to “New word” first. This is how we can count the number of words: just keep count of how many times each state has been visited.
If we visit the state “New word” a total of 5 times, it means that there were 5 words in the input.
State machine in Zig
Let’s try converting this into a state machine in Zig. First, we’ll define all of the states and also the possible character types.
const State = struct {<br>whitespace: usize = 0,<br>newline: usize = 1,<br>word: usize = 2,<br>in_word: usize = 3,<br>}{};<br>const CharType = struct {<br>character: usize = 0,<br>whitespace: usize = 1,<br>newline: usize = 2,<br>}{};
I’m not using a Zig enum here because enum members are not integer-typed but enum-typed. This means that in order to access the integer value, one needs to wrap it in @intFromEnum(State.foo), which would add a lot of visual clutter.
Now, we can define the transition table. It’s basically a 2-dimensional table that answers
for each state,
for each type of input character,
what state should I transition to?
pub fn gen_transition_table() [4][3]u8 {<br>var table: [4][3]u8 = undefined;
table[State.whitespace][CharType.character] = State.word;<br>table[State.whitespace][CharType.whitespace] =...