Making `wc` 20x faster with parallel state machines

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
	598 file.txt

You can also display the number of lines, words and bytes together (the default behaviour):

$ wc -lwc file.txt
	167     598    4614 file.txt

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 {
    var line_count: usize = 0;
    var word_count: usize = 0;
    var byte_count: usize = 0;

    var in_word: bool = false;

    while (true) {
        const b = reader.takeByte() catch break;
        byte_count += 1;
        switch (b) {
            '\n' => {
                line_count += 1;
                in_word = false;
            },
            '\r', '\t', ' ' => {
                in_word = false;
            },
            else => {
                if (!in_word) {
                    word_count += 1;
                }
                in_word = true;
            },
        }
    }
    return .{
        .line_count = line_count,
        .word_count = word_count,
        .byte_count = byte_count,
    };
}

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:

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 {
    whitespace: usize = 0,
    newline: usize = 1,
    word: usize = 2,
    in_word: usize = 3,
}{};
const CharType = struct {
    character: usize = 0,
    whitespace: usize = 1,
    newline: usize = 2,
}{};

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 {
    var table: [4][3]u8 = undefined;

    table[State.whitespace][CharType.character] = State.word;
    table[State.whitespace][CharType.whitespace] = State.whitespace;
    table[State.whitespace][CharType.newline] = State.newline;

    table[State.newline][CharType.character] = State.word;
    table[State.newline][CharType.whitespace] = State.whitespace;
    table[State.newline][CharType.newline] = State.newline;

    table[State.word][CharType.character] = State.in_word;
    table[State.word][CharType.whitespace] = State.whitespace;
    table[State.word][CharType.newline] = State.newline;

    table[State.in_word][CharType.character] = State.in_word;
    table[State.in_word][CharType.whitespace] = State.whitespace;
    table[State.in_word][CharType.newline] = State.newline;

    return table;
}

These transitions map 1-to-1 with the diagram above. Effectively, the result is a 2-dimensional array {{2,0,1}, {2,0,1}, {3,0,1}, {3,0,1}} identical to Robert’s original wc2o.c.

Let us also define a character type table that maps each ascii character into its corresponding CharType.

fn gen_char_type_table() [256]u8 {
	// set to character type by default
    var column: [256]u8 = [_]u8{CharType.character} ** 256;
    // now we just have to find all whitespace and newline characters 
    // and mark them
    for (0..256) |b| {
        if (std.ascii.isWhitespace(@intCast(b))) {
            column[b] = CharType.whitespace;
        }
        if (b == '\n') {
            column[b] = CharType.newline;
        }
    }
    return column;
}

Most of the work is done now. Now it’s just a matter of processing the input and returning the result:

pub fn wc_dfa(reader: *std.Io.Reader) Result {
    const table = gen_transition_table();
    const column = gen_char_type_table();

    var counts = [4]usize{ 0, 0, 0, 0 };
    var state: usize = State.whitespace;
    while (true) {
        const b = reader.takeByte() catch break;
        state = table[state][column[b]];
        counts[state] += 1;
    }
    return .{
        .line_count = counts[State.newline],
        .word_count = counts[State.word],
        // For byte count, sum all of them
        .byte_count = counts[0] + counts[1] + counts[2] + counts[3],
    };
}

99% of the program execution time happens inside that 3-line while loop. I think that’s very neat!

It’s also possible to combine column and table by turning table into a [4][256]u8 where the input byte b can be used directly. It generates slightly more efficient than using two tables.

while (true) {
	const b = reader.takeByte() catch break;
	state = table[state][b];
	counts[state] += 1;
}

You may notice that we only read one byte from the input at a time using reader.takeByte(). This seems really wasteful. What if every single call to takeByte() is reading one byte from a file individually?

Well, you would be correct if there was no buffering, but I’ve explicitly defined the buffer size in processFile like this:

const BUF_SIZE = 65536;

fn processFile(file: *std.fs.File) !Result {
  var buf: [BUF_SIZE]u8 = undefined;
  var file_reader = file.reader(&buf);
  const reader = &file_reader.interface;
  return wc_dfa(reader);
}

Here buf is allocated on the stack. 2^16=65536 is a nice number because it fits in L1-L2 CPU cache and is also not big enough to blow up the stack.

Zig doesn’t have real interfaces, so file.reader(&buf) returns a std.fs.File.Reader struct. This struct defines a field interface of type std.Io.Reader. A pointer to this interface can then be passed around as an *std.Io.Reader. Reader is an abstraction for anything that can be read from, and has a bunch of useful methods on it like takeByte. Checkout out this great post by Joel Mckay if you want to know more.

Benchmarks #

In order to compare zwc against other implementations, I am going to use hyperfine to measure execution time from processing 165 MB of English wikipedia titles. I ran these tests on my M4 MacBook Air laptop.

Benchmark 1: ./zwc -lwc enwiki-20260301-all-titles
  Time (mean ± σ):     276.0 ms ±   1.9 ms    [User: 264.9 ms, System: 10.5 ms]
  Range (min … max):   274.3 ms … 279.5 ms    10 runs

Benchmark 2: wc -lwc enwiki-20260301-all-titles
  Time (mean ± σ):     225.3 ms ±   0.3 ms    [User: 214.5 ms, System: 9.9 ms]
  Range (min … max):   225.0 ms … 226.1 ms    13 runs

Summary
  wc -lwc enwiki-20260301-all-titles ran
    1.22 ± 0.01 times faster than ./zwc -lwc enwiki-20260301-all-titles

What? wc was faster?

The difference comes from the fact that even though both programs produce the same result, they use very different instructions. The regular wc uses branching jmp instructions depending on if in_word is true or not. That is fine though, as modern CPUs read far ahead of the currently executing instruction and make guesses for which execution branches the program is going to take. It can then start speculatively executing instructions in those branches before it even evaluates the branch condition. This is called branch prediciton, and as it turns out, the CPU is pretty good at predicting those branches. If it happens to guess wrong, it can just discard the speculative instructions and start again from the correct branch.

The state of our state machine however directly depends on the previous state. It’s not using any branches or jump tables, which removes the CPU’s ability execute things ahead of time. By using a state machine like this, we’re trading away unpredictable control flow for unpredictable data access.

I’ve written more about the actual assembly code in appendix A, if you’re curious.

Now, things can be made simple and fast when we’re only concerned with ASCII input. But *real* wc implementations support UTF-8. It adds a lot of overhead into the word-counting process, as we’ll see next.

Understanding UTF-8 is important for the next part. If you’re not sure what it is or how it works, I’ve written a quick explanation below in Appendix B.

UTF-8 in practice #

Most modern systems use a UTF-8 locale such as en_US.UTF-8. Even though the locales might have different capitalization or folding rules, all of them have the same classification of whitespace characters. There are 25 characters in the whitespace category, consistent across all locales. You can find them on Wikipedia here.

In the standard C library, “wide characters” are typically¹ unsigned 32-bit integers so that they can hold all 2^21 Unicode code points. mbrtowc can be used to convert multibyte sequences to wide characters. iswspace can then be used to check if the given wide character is a white-space character.

These functions are what existing wc programs use. For example, this is what the Apple’s wc implementation – based on FreeBSD – looks like:

	uintmax_t wordct = 0, charct = 0, linect = 0;
	const char *p = buf; // pointer to buffer
	wchar_t wch; // current wide char
	bool gotsp = false; // got whitespace?
	mbstate_t mbs; // multibyte conversion state (not important)
	while (len > 0) {
		int clen = 1;
		if(!domulti) {
			wch = (unsigned char)*p;
		} else { // parse multibyte characters
			clen = mbrtowc(&wch, p, len, &mbs);
		}
		charct++;
		if (wch != L'\n')
			tmpll++;
		len -= char_len;
		p += char_len;
		if (wch == L'\n') {
			++linect;
		}
		if (iswspace(wch)) {
			gotsp = true;
		} else if (gotsp) {
			gotsp = false;
			++wordct;
		}
	}

It parses characters into a wide char and checks if that code point is a whitespace character using iswspace.

Let’s measure wc in non-multibyte mode (with -c) and multibyte mode (with the -m flag). Multibyte mode means that instead of counting the number of bytes, it counts the number of characters as defined by the locale. In UTF-8, it is the number of code points.

$ echo -n "Hei äiti" | wc -c
       9
$ echo -n "Hei äiti" | wc -m
       8

The ‘ä’ character is represented with 2 bytes in UTF-8, so the total is 1 smaller than the number of bytes.

Here is a benchmark comparing -lwc and -lwm modes on the same English wikipedia titles:

Benchmark 1: wc -lwc enwiki-20260301-all-titles
  Time (mean ± σ):     223.5 ms ±   0.5 ms    [User: 212.7 ms, System: 9.8 ms]
  Range (min … max):   222.9 ms … 224.2 ms    13 runs
 
Benchmark 2: wc -lwm enwiki-20260301-all-titles
  Time (mean ± σ):     610.9 ms ±  16.8 ms    [User: 599.7 ms, System: 10.2 ms]
  Range (min … max):   588.9 ms … 629.5 ms    10 runs
 
Summary
  wc -lwc enwiki-20260301-all-titles ran
    2.73 ± 0.08 times faster than wc -lwm enwiki-20260301-all-titles

It’s a lot slower. That call to mbrtowc really has a big impact on performance.

What if we used text with a lot of multibyte characters? Here is a benchmark with a similarly sized 165 MB file of Chinese Wikipedia titles.

Benchmark 1: wc -lwc zhwiki-latest-all-titles
  Time (mean ± σ):     343.2 ms ±  10.2 ms    [User: 328.8 ms, System: 12.6 ms]
  Range (min … max):   335.9 ms … 370.9 ms    10 runs
 
Benchmark 2: wc -lwm zhwiki-latest-all-titles
  Time (mean ± σ):     933.3 ms ± 116.5 ms    [User: 915.6 ms, System: 16.2 ms]
  Range (min … max):   823.7 ms … 1131.9 ms    10 runs
 
Summary
  wc -lwc zhwiki-latest-all-titles ran
    2.72 ± 0.35 times faster than wc -lwm zhwiki-latest-all-titles

It’s a further 50% slower. It’s taking almost a second to parse. For a 165 MB file, we get a throughput of ~170 MBPS. For reference, gzip can decompress files at ~1.7 GBPS. Clearly there’s room for improvement here.

Can we do better with a state machine? Yes! A lot better. Let’s look at the state machine again:

while (true) {
	const b = reader.takeByte() catch break;
	state = table[state][b];
	counts[state] += 1;
}

Internally, this loop is just a couple mov and add instructions which operate on indices into table and counts. The cost of these operations is independent of the number of states², so each character is processed in the exact same amount of time.

This means that if we can support UTF-8 by just adding more states, it’s going to be exactly as fast as the ASCII version.

UTF-8 state machine #

In order to make this work, we need process the input one byte at a time. Since UTF-8 is a multibyte, variable-length encoding, we need to add states to represent characters in the middle of being parsed.

Take for example the lightning ⚡️ emoji, which is 11100010 10011010 10100001 in UTF-8. After reading the first byte 11100010, we transition into the state TRI2_0A, which means that we’re in the second byte of a 3-byte character, the value of the previous byte being 0x0A in hex or 0010 in binary (the last 4 bits of the first byte). After reading the second byte 10011010 we transition into TRI3_0A_1A. After reading the third byte 10100001, we transition into either NEWWORD, INWORD, depending on what state we started at.

The UTF-8 state space, one byte at a time #

Constructing the transition table is a lot of work. Thankfully Robert Graham already did that work for us in his wc2 code. I’ll do my best to explain how it works.

Recall that there are only 25 whitespace characters in the entirety of Unicode. Therefore we really only need to care about the cases where the current character could be a whitespace character. This reduces the number of required states significantly.

const Utf8State = struct {
    DUO2_xx: u8 = 0,
    DUO2_C2: u8 = 1,
    TRI2_E0: u8 = 2,
    TRI2_E1: u8 = 3,
    TRI2_E2: u8 = 4,
    TRI2_E3: u8 = 5,
    TRI2_ED: u8 = 6,
    TRI2_EE: u8 = 7,
    TRI2_xx: u8 = 8,
    TRI3_E0_xx: u8 = 9,
    TRI3_E1_xx: u8 = 10,
    TRI3_E1_9a: u8 = 11,
    TRI3_E2_80: u8 = 12,
    TRI3_E2_81: u8 = 13,
    TRI3_E2_xx: u8 = 14,
    TRI3_E3_80: u8 = 15,
    TRI3_E3_81: u8 = 16,
    TRI3_E3_xx: u8 = 17,
    TRI3_Ed_xx: u8 = 18,
    TRI3_Ee_xx: u8 = 19,
    TRI3_xx_xx: u8 = 20,
    QUAD2_xx: u8 = 21,
    QUAD2_F0: u8 = 22,
    QUAD2_F4: u8 = 23,
    QUAD3_xx_xx: u8 = 24,
    QUAD3_F0_xx: u8 = 25,
    QUAD3_F4_xx: u8 = 26,
    QUAD4_xx_xx_xx: u8 = 27,
    QUAD4_F0_xx_xx: u8 = 28,
    QUAD4_F4_xx_xx: u8 = 29,
    ILLEGAL: u8 = 30,
}{};

Here you can see every possible multibyte sequence we’re interested in. For example, in TRI3_E2_81 , the only possible whitespace character at this state is the Narrow No-Break Space ’ ‘.

All of the states with xx in them are states that will always turn into a non-whitespace character. We don’t care about the specific characters, just consume the required number of bytes and transition into the desired base state.

A much bigger state space #

With Utf8State done, here is the full updated State:

pub const State = struct {
    WASSPACE: usize = 0,
    NEWLINE: usize = 1,
    NEWWORD: usize = 2,
    WASWORD: usize = 3,
    USPACE: usize = 4,
    UWORD: usize = 35, // State.USPACE + Utf8State.ILLEGAL + 1
    STATE_MAX: usize = 66, //  State.UWORD + Utf8State.ILLEGAL + 1,
}{};

The first 4 are the same “base states”, but after that there are actually 62 more states, they are just not shown explicitly.

If we’re in the middle of a multibyte sequence and the character is not whitespace, we need to know if we started from the WASSPACE or WASWORD state. Since we don’t want to have any conditional logic for that, we can to encode that information in the state space instead. USPACE and UWORD are not actually states that we can transition into, but they are markers for parts of the state space. There is a DUO2_xx state in UWORD and in USPACE both.

Generating the transition table #

The transition table code is much more complex now, but we can start from the top, gen_table():

pub const Table = [State.STATE_MAX][256]u8;

pub fn gen_table() Table {
    var table: Table = undefined;
    // Params are Row, base state, word state
    // In WASSPACE and NEWLINE states, non-whitespace ASCII goes to NEWWORD
    build_first_byte_states(&table[State.WASSPACE], State.USPACE, State.NEWWORD);
    build_first_byte_states(&table[State.NEWLINE], State.USPACE, State.NEWWORD);
    
    // In WASWORD and NEWWORD states, non-whitespace ASCII goes to WASWORD
    build_first_byte_states(&table[State.WASWORD], State.UWORD, State.WASWORD);
    build_first_byte_states(&table[State.NEWWORD], State.UWORD, State.WASWORD);
    
    // Unicode multi-byte sequences get their own states,
    // "USPACE" being multi-bytes sequences that started in WASSPACE or NEWLINE,
    // and "UWORD" being multi-byte sequences that started in WASWORD or NEWWORD.
    build_unicode(&table, State.USPACE, State.NEWWORD);
    build_unicode(&table, State.UWORD, State.WASWORD);
    return table;
}

This is the top-level function that creates the table. The table is only 66*256*1 ≈ 17 KB in size, small enough to be passed around on the stack.

It calls two types of functions: build_first_byte_states and build_unicode. The former one is quite straight-forward as it’s only tasked with adding transitions from the first byte of a character to its corresponding state.

pub fn build_first_byte_states(row: *[256]u8, base_state: u8, word_state: u8) void {
    for (0..256) |i| {
        const b: u8 = @intCast(i);
        if ((b & 0x80) != 0) {
            if ((b & 0xE0) == 0xC0) {
                // 110x xxxx - unicode 2 byte sequence
                if (b < 0xC2) {
                    row[b] = base_state + Utf8State.ILLEGAL;
                } else if (b == 0xC2) {
                    row[b] = base_state + Utf8State.DUO2_C2;
                } else {
                    row[b] = base_state + Utf8State.DUO2_xx;
                }
            } else if ((b & 0xF0) == 0xE0) {
                // 1110 xxxx - unicode 3 byte sequence
                switch (b) {
                    0xE0 => row[b] = base_state + Utf8State.TRI2_E0,
                    0xE1 => row[b] = base_state + Utf8State.TRI2_E1,
                    0xE2 => row[b] = base_state + Utf8State.TRI2_E2,
                    0xE3 => row[b] = base_state + Utf8State.TRI2_E3,
                    0xED => row[b] = base_state + Utf8State.TRI2_ED,
                    0xEE => row[b] = base_state + Utf8State.TRI2_EE,
                    else => row[b] = base_state + Utf8State.TRI2_xx,
                }
            } else if ((b & 0xF8) == 0xF0) {
                // 1111 0xxx - unicode 4 byte sequence
                if (b >= 0xF5) {
                    row[b] = base_state + Utf8State.ILLEGAL;
                } else if (b == 0xF0) {
                    row[b] = base_state + Utf8State.QUAD2_F0;
                } else if (b == 0xF4) {
                    row[b] = base_state + Utf8State.QUAD2_F4;
                } else {
                    row[b] = base_state + Utf8State.QUAD2_xx;
                }
            } else {
                row[b] = base_state + Utf8State.ILLEGAL;
            }
            // Unicode 1 byte sequences
        } else if (b == '\n') {
            row[b] = State.NEWLINE;
        } else if (std.ascii.isWhitespace(b)) {
            row[b] = State.WASSPACE;
        } else {
            row[b] = word_state;
        }
    }
}

base_state refers to the starting state of the character (USPACE or UWORD). word_state refers to the state to go to when encountering a word (NEWWORD or INWORD).

This function covers all of the cases where the byte starts with 0xxx, 110, 1110 or 1111 0. Notably, it doesn’t cover the case where the byte is a continuation byte (starting with 10). That is the job of build_unicode.

I’ve left the body of build_unicode() out of this post as it’s a lot of repetitive code, but the idea is the same: from a given state, wire up transition to the next states.

You can view it on GitHub here.

With the gen_table function done, here is the updated wc_dfa function.

pub fn wc_dfa(reader: *std.Io.Reader) Result {
    const table = gen_table();
    var counts = [_]usize{0} ** State.STATE_MAX;
    var state: usize = State.WASSPACE;
    while (true) {
        const b = reader.takeByte() catch break;
        state = table[state][b];
        counts[state] += 1;
    }

    var byte_count: usize = 0;
    for (0..State.STATE_MAX) |i| {
        byte_count += counts[i];
    }

    return .{
        .line_count = counts[State.NEWLINE],
        .word_count = counts[State.NEWWORD],
        .char_count = counts[0] + counts[1] + counts[2] + counts[3],
        .byte_count = byte_count,
    };
}

It’s really similar to the wc_simple version, except that we count how many UTF-8 multibyte characters we read. Since every character starts from one of the first 4 states and ends in them, it’s really easy to calculate the total amount.

Benchmarks #

Benchmark 1: ./zwc -lwc enwiki-20260301-all-titles
  Time (mean ± σ):     275.6 ms ±   0.2 ms    [User: 263.8 ms, System: 11.5 ms]
  Range (min … max):   275.4 ms … 275.9 ms    10 runs
 
Benchmark 2: wc -lwc enwiki-20260301-all-titles
  Time (mean ± σ):     227.2 ms ±   0.4 ms    [User: 215.5 ms, System: 10.7 ms]
  Range (min … max):   226.6 ms … 227.9 ms    13 runs
 
Summary
  wc -lwc enwiki-20260301-all-titles ran
    1.21 ± 0.00 times faster than ./zwc -lwc enwiki-20260301-all-titles

When processing ascii text in non-multibyte mode, it’s still around 20% slower like before. This depends a lot on the hardware and wc implementation though: GNU wc is very close to the same speed.

Benchmark 1: ./zwc -lwc enwiki-20260301-all-titles
  Time (mean ± σ):     275.2 ms ±   0.3 ms    [User: 263.4 ms, System: 11.4 ms]
  Range (min … max):   274.8 ms … 275.8 ms    10 runs
 
Benchmark 2: gwc -lwc enwiki-20260301-all-titles
  Time (mean ± σ):     268.5 ms ±   1.4 ms    [User: 256.5 ms, System: 11.1 ms]
  Range (min … max):   266.7 ms … 270.7 ms    11 runs
 
Summary
  gwc -lwc enwiki-20260301-all-titles ran
    1.02 ± 0.01 times faster than ./zwc -lwc enwiki-20260301-all-titles

On my desktop CPU (AMD Ryzen 5 3600X), zwc is around 20% faster than GNU wc.

Things change though when processing more multibyte-heavy text.

Benchmark 1: ./zwc -lwm zhwiki-latest-all-titles
  Time (mean ± σ):     266.3 ms ±   0.2 ms    [User: 255.5 ms, System: 10.4 ms]
  Range (min … max):   266.1 ms … 266.6 ms    11 runs
 
Benchmark 2: wc -lwm zhwiki-latest-all-titles
  Time (mean ± σ):     813.1 ms ±  18.5 ms    [User: 801.8 ms, System: 10.3 ms]
  Range (min … max):   802.1 ms … 864.8 ms    10 runs
 
Summary
  ./zwc -lwm zhwiki-latest-all-titles ran
    3.05 ± 0.07 times faster than wc -lwm zhwiki-latest-all-titles

It’s 3× faster! Here is zwc compared against gwc and uutils-wc too.

Benchmark 1: ./zwc -lwm zhwiki-latest-all-titles
  Time (mean ± σ):     266.6 ms ±   0.1 ms    [User: 255.5 ms, System: 10.6 ms]
  Range (min … max):   266.4 ms … 266.8 ms    11 runs
 
Benchmark 2: gwc -lwm zhwiki-latest-all-titles
  Time (mean ± σ):     684.3 ms ±   3.7 ms    [User: 672.1 ms, System: 11.3 ms]
  Range (min … max):   678.3 ms … 689.4 ms    10 runs
 
Benchmark 3: uutils-wc -lwm zhwiki-latest-all-titles
  Time (mean ± σ):     271.4 ms ±   8.0 ms    [User: 253.7 ms, System: 16.8 ms]
  Range (min … max):   259.6 ms … 280.2 ms    10 runs
 
Summary
  ./zwc -lwm zhwiki-latest-all-titles ran
    1.02 ± 0.03 times faster than uutils-wc -lwm zhwiki-latest-all-titles
    2.57 ± 0.01 times faster than gwc -lwm zhwiki-latest-all-titles

uutils-wc is impressively close though. One reason for this is that assumes that the input is always UTF-8 and doesn’t use the mbrtowc type functions at all. The same is true for zwc as well.

When writing this, I was often getting slightly different results from zwc compared to Apple’s wc. It was not until I looked at the source code that I discovered a quirk (or a bug?) in Apple’s wc: it parses the input as UTF-8 (or any other non-ASCII format) only if the -m flag is used. It means that the word count is likely wrong if the input used any of the non-ASCII whitespace characters. Every other implementation does this right, treating the input as possibly multibyte even in non-multibyte mode. I believe that this is the reason behind the performance difference in wc and gwc in non-multibyte mode.

Parallelizing the state machine #

Looking at the benchmark results, they seem pretty great. The code is pretty much as fast as it could be, but it’s only using one thread. Could we go even faster by somehow doing stuff in parallel?

As it turns out, it is possible! We can split the input into large chunks and process those chunks in parallel. Here is the process:

1. Set initial starting state to STATE_WASSPACE.
2. Read chunk A. Start processing A.
3. Set starting state for next chunk to STATE_WASSPACE or STATE_WASWORD depending on if chunk A ended in a whitespace character or not.
4. Read chunk B. Start processing B.
5. Repeat from 3

There is one extra detail to consider though: what if the chunk ends right in the middle of a multibyte UTF-8 sequence? The next chunk would start in a continuation byte 10xx..., which would not be valid UTF-8, giving the wrong result. The solution is to check if the last character continues past the chunk and then read a couple extra bytes (at most 3) into the chunk so that it ends in a valid state.

For the parallelization part, we have to be careful about memory usage. If we were to split a 1 GB input file into 1 MB chunks and allocate memory for each chunk, we would need to allocate 1 GB of memory, which is not great. Since every thread can only process one chunk at a time, a better idea would be to allocate n chunks, where nis the number of threads, and reuse the chunk’s memory when it has been processed. This way, the memory usage remains bounded.

The main thread is going to read the input data into chunks and distribute them among all available threads. If every chunk is being processed at the same time, the main thread also has to wait for a chunk to be free before filling it with data again.

This type of problem is called the producer-consumer problem, originally formulated by Edsger W. Dijkstra in the 1960’s.

There are many solutions to this, but my solution is one that uses two queues: the work queue and the free queue. These queues contain tasks, each task has a pointer to a chunk and also the starting state for the chunk. Initially, all tasks are in the free queue. The main thread takes tasks from the free queue, fills the chunk with data, then adds the task to the work queue. Each worker thread then takes a task from the work queue, processes it and then adds it to the free queue.

Internally, the queues use mutexes and Condition variables to synchronize push/pop operations efficiently. My code was heavily inspired by Andrew Wei’s blog post on the topic.

Why not have each thread read from a computed offset in the file? This way there would be no need for synchronization at all except for the end.

I though about doing this, but ultimately decided against it because of one reason: this does not work with stdin. I would guess that 99% of the time wc is used somewhere in the middle of a bash | pipeline, which wouldn’t benefit from this at all.

Results #

Benchmark 1: ./zwc enwiki-20260301-all-titles
  Time (mean ± σ):      40.4 ms ±   0.6 ms    [User: 332.5 ms, System: 21.3 ms]
  Range (min … max):    39.6 ms …  43.3 ms    71 runs
 
Benchmark 2: wc enwiki-20260301-all-titles
  Time (mean ± σ):     226.7 ms ±   0.5 ms    [User: 215.5 ms, System: 10.3 ms]
  Range (min … max):   225.6 ms … 227.3 ms    13 runs
 
Benchmark 3: gwc enwiki-20260301-all-titles
  Time (mean ± σ):     269.4 ms ±   0.6 ms    [User: 257.9 ms, System: 10.7 ms]
  Range (min … max):   268.5 ms … 270.5 ms    11 runs
 
Benchmark 4: uutils-wc enwiki-20260301-all-titles
  Time (mean ± σ):     249.7 ms ±  11.9 ms    [User: 232.0 ms, System: 16.9 ms]
  Range (min … max):   223.8 ms … 259.4 ms    11 runs
 
Summary
  ./zwc enwiki-20260301-all-titles ran
    5.61 ± 0.08 times faster than wc enwiki-20260301-all-titles
    6.18 ± 0.31 times faster than uutils-wc enwiki-20260301-all-titles
    6.67 ± 0.10 times faster than gwc enwiki-20260301-all-titles

In the typical case of ASCII input text, parallel zwc is ~6x faster than the others, completing the task in 40 ms instead of 250 ms.

The speedup should be ~linear with respect to the amount of CPU cores. My MacBook has 10 cores (4 performance, 6 efficiency).

Now let’s run the same benchmarks with multi-byte UTF-8 text:

Benchmark 1: ./zwc -lwm zhwiki-latest-all-titles
  Time (mean ± σ):      40.8 ms ±   0.5 ms    [User: 326.0 ms, System: 21.1 ms]
  Range (min … max):    39.9 ms …  42.3 ms    73 runs
 
Benchmark 2: wc -lwm zhwiki-latest-all-titles
  Time (mean ± σ):     842.7 ms ±  46.7 ms    [User: 827.3 ms, System: 14.0 ms]
  Range (min … max):   819.1 ms … 974.9 ms    10 runs
 
Benchmark 3: gwc -lwm zhwiki-latest-all-titles
  Time (mean ± σ):     713.1 ms ±  21.3 ms    [User: 698.3 ms, System: 13.7 ms]
  Range (min … max):   697.8 ms … 758.5 ms    10 runs
 
Benchmark 4: uutils-wc -lwm zhwiki-latest-all-titles
  Time (mean ± σ):     282.9 ms ±   9.5 ms    [User: 264.9 ms, System: 17.2 ms]
  Range (min … max):   269.4 ms … 293.4 ms    10 runs
 
Summary
  ./zwc -lwm zhwiki-latest-all-titles ran
    6.94 ± 0.25 times faster than uutils-wc -lwm zhwiki-latest-all-titles
   17.48 ± 0.56 times faster than gwc -lwm zhwiki-latest-all-titles
   20.66 ± 1.17 times faster than wc -lwm zhwiki-latest-all-titles

Even though this is a fairly non-common mode of operation for wc, it’s impressive how much faster it is. Calculating the difference in terms of throughput, we get

>>> 165MB / 842ms to GB/s
    = 0.195962 GB/s    [DataRate]
>>> 165MB / 40ms to GB/s
    = 4.125 GB/s    [DataRate]

My laptop’s SSD has a maximum read speed of 3.1 GB/s, but it’s somehow processing the input faster than that. This is happening because the OS sees that in the benchmarks, the same file is being read hundreds of times, so the whole file is being cached in memory.

This throughput is pretty significant though. It means that in real-world usage, wc is bottlenecked by the CPU while zwc is bottlenecked by the disk.

This is the end. Thanks for reading this far. I’ve put the code on GitHub.

This has been almost 6 months in the making because kept off finishing this blog post. Further ideas for this project would be implementing a special SIMD-accelerated routine for counting newlines (wc -l) and making it support all GNU/BSD wc flags.

Appendix A: Reference wc vs. state machine disassembly #

Here is a link to Godbolt containing disassembly for both versions of the code: https://zig.godbolt.org/z/jhhdWW8Es

The wc_ref version generates two jump tables from the switch statement, one for the case when in_word is false and one for when it is true. Here is the section executed if in_word is false. I’ve added comments above explaining the instructions:

.LBB2_4:
	# set current byte to ecx
	movzx ecx, byte ptr [rcx] # [rcx] = load at address rcx
	# subtract 9 from ecx (ASCII tab = 9, newline=10)
	# the purpose is to make the jump table as small as possible.
	add     ecx, -9
	# compare against ' ' (space character)
	cmp     ecx, 23 
	# if ecx above 23 (space), jump to "else" section
	ja      .LBB2_16 
	# otherwise use jump table. Jump table uses 64-bit addresses,
	# so multiply by 8 bytes to get correct index
	jmp     qword ptr [8*rcx + .LJTI2_0] 

The other section is identical except for the jump table and the “else” section. I’ve only shown a small snippet here, but the important thing here is the two jmp instructions. The branch predictor will choose which jmp instruction to start speculatively executing even before the condition has been tested. This is really good for performance when the right branch is chosen (as it usually is), but can cause branch mispredictions when the chosen path is wrong. In that case, the CPU has to scrap the results and start over from the right branch.

In contrast, here is what the core of wc_dfa looks like:

.LBB0_4:
	# rcx = current byte, r15 = current state, rax = index into buffer
	
	# ecx = column[b]
	movzx   ecx, byte ptr [rcx + .L__unnamed_1]  # .L_unnamed_1 is the column-array
	# rdx = 3*state (each state has 3 transitions)
	lea     rdx, [r15 + 2*r15] 
	# r15 = table[state][column[b]]
	movzx   r15d, byte ptr [rcx + rdx + .L__unnamed_2]
	# counts[state] += 1.	
	#   explanation: rbp is stack base pointer, `counts` starts at rbp - 64,
	#   multiply by 8 bytes to get the correct 64-bit address for this state
	add     qword ptr [rbp + 8*r15 - 64], 1

.LBB0_1:
	# check if we've read past the buffer (r14 is address of std.Io.Reader, r14+32 is reader.buf.len)
	cmp     rax, qword ptr [r14 + 32] 
	# if can still read from buffer, goto start
	jb      .LBB0_4

This code is very different. It basically amounts to reading from two tables with a dynamic offset. This may seem like a bad idea since accessing memory is expensive, but in this case it’s not that bad: even the full UTF-8 transition table fits into the L1 CPU cache quite comfortably. L1 cache access time is 1-4 cycles, so not really different from accessing registers.

You might also notice that the reader.takeByte() function is completely gone from the assembly output. This is because the Zig std.Io.Reader interface is transparent to optimization and the compiler can easily inline the takeByte function. It can also see that the buffer is located on the stack, and effectively turn while(true) { const b = reader.takeByte() } into while(n < buf.len) { const b = buf[n] }.

The compiler can turn the most readable version of the code into the most optimized one. That is amazing.

To see the difference, we can measure the number of branch misses with crap:

Benchmark 1 (10 runs): wc enwiki-20260301-all-titles
  measurement          mean ± σ            min … max           outliers         delta
  wall_time           504ms ± 42.9ms     477ms …  611ms          0 ( 0%)        0%
  peak_rss           2.39MB ± 55.3KB    2.36MB … 2.49MB          0 ( 0%)        0%
  cpu_cycles         1.89G  ± 22.2M     1.86G  … 1.94G           0 ( 0%)        0%
  instructions       5.21G  ±  156      5.21G  … 5.21G           0 ( 0%)        0%
  cache_references   5.85M  ±  296K     5.57M  … 6.55M           0 ( 0%)        0%
  cache_misses        366K  ± 77.1K      290K  …  564K           1 (10%)        0%
  branch_misses      7.65M  ± 12.5K     7.63M  … 7.68M           0 ( 0%)        0%
Benchmark 2 (13 runs): ./zwc enwiki-20260301-all-titles
  measurement          mean ± σ            min … max           outliers         delta
  wall_time           388ms ± 12.0ms     365ms …  409ms          0 ( 0%)        ⚡- 22.9% ±  5.1%
  peak_rss           1.38MB ± 72.9KB    1.27MB … 1.44MB          0 ( 0%)        ⚡- 42.2% ±  2.4%
  cpu_cycles         1.42G  ± 4.23M     1.41G  … 1.43G           0 ( 0%)        ⚡- 24.9% ±  0.7%
  instructions       1.90G  ±  107      1.90G  … 1.90G           0 ( 0%)        ⚡- 63.5% ±  0.0%
  cache_references   4.43M  ±  282K     3.99M  … 4.91M           0 ( 0%)        ⚡- 24.3% ±  4.3%
  cache_misses        214K  ± 46.5K      145K  …  312K           0 ( 0%)        ⚡- 41.6% ± 14.7%
  branch_misses      37.7K  ± 3.47K     31.8K  … 44.7K           0 ( 0%)        ⚡- 99.5% ±  0.1%

This is the single threaded version of zwc running on my old PC with an AMD Ryzen 3600X processor. As you can see, in the GNU wc case there are 7.65M branch misses on average and only 37.7K with our version – a 99.5% reduction!

Appendix A: Quick intro to Unicode #

As you may know, modern text processing depends on something called Unicode. It is a standard that defines a set of code points – integers ranging from 0 to 1 114 111, each identifying a unique character. There are alphabets, emojis, ancient Egyptian hieroglyphs, chess pieces, playing cards, anything that you could possible imagine typing on a keyboard.

There are so many code points that you need an unsigned integer of at least 21 bits to store them all. Because of how computer memory works, it’s better to represent them as 32 bit integers instead. This encode-whole-code-point format is known as UTF-32. It’s the simplest format of them all.

The issue with UTF-32 is that it’s very wasteful. Since Unicode was designed to be backwards compatible with ASCII, all of the basic latin characters are in the range 0-127, representable with 7 bits. Most of the text on the internet is in that small character set (HTML, JSON, Javascript) where those upper 25 bits are always zeroes.

Because ASCII characters always start with a 0-bit followed by 7 bits of actual data, what if you were to define a new format for Unicode that says that if the next byte starts with a 0, it should treat it as ASCII, or otherwise it would be encoded in multiple bytes? That is pretty much what UTF-8 is!

UTF-8 converts those 21-bit code points into a variable-width sequence of 1-4 bytes depending on how many bytes the character takes to represent. This way, some common (mostly latin) characters take up only 1 byte, saving a lot of memory, bandwidth and disk space.

Here is the UTF-8 conversion table from Wikipedia:

Here xyz.. are placeholders for the bits of a given codepoint. As you can see, every character starts with a bit-pattern indicating the length of the character.

For example, the ⚡-emoji is the codepoint U+26A1 in hexadecimal form, which means that it is 9889 in decimal form and 10011010100001 in binary. The binary form is 14 bits long and we can see from the table above that it fits in 3 UTF-8 bytes, with two bits to spare. After padding with two bits on the right, we’re left with 0010011010100001.

Now, encoding it is as simple as taking the bits from left to right and filling in the placeholders in 1110xxxx 10xyyyzz 10zzwwww. We get the result 11100010 10011010 10100001.

Now you know how Unicode and UTF-8 works. Yay!

There is also UTF-16. It was made with the assumption that 2^16=65536 characters would be enough (it wasn’t). Because of this, they had to later add UTF-16 surrogate pairs which are two 16-bit code units that combine to represent a higher-value code point. It’s not a great format because it has all of the disadvantages of UTF-8 (variable-width) while being less space efficient. Nevertheless, it persists because it’s still used in the Windows API, Java, C# and Javascript.