Making `wc` 20x faster with parallel state machines

This explains how to speed up the classic wc word/line/byte counter by modeling its control flow as a deterministic finite automaton (DFA) and then parallelizing that DFA. The core idea replaces the usual boolean in_word check and branching with a small state machine: classify each input byte as newline, whitespace, or character, use a 4×3 transition table (or a 4×256 table mapping bytes directly) to pick the next state, and increment per-state counters. A compact Zig implementation demonstrates that almost all work occurs in a three-line loop reading from a 64 KiB buffered reader, and shows small optimizations such as combining tables for faster indexing and keeping the buffer size cache-friendly.

Benchmarks show the tradeoffs: a straight DFA for ASCII can be competitive but initially ran slower than GNU wc on a 165 MB dataset because DFA execution replaces predictable branches (good for CPU branch prediction) with data-dependent memory accesses that are harder to predict. Extending the approach to real-world UTF-8 requires handling multibyte sequences and a larger whitespace classification (25 code points), which inflates the state space and transition logic. The crucial finding is that by parallelizing the DFA across multiple threads for large inputs, the implementation (zwc) achieves substantial wins - on big files it becomes roughly 5-20× faster than GNU/BSD wc - demonstrating a practical performance engineering path from simple DFA modeling to scalable parallel execution.