Wc2: Investigates optimizing 'wc', the Unix word count program

The "asynchronous state machine" name here is a bit strange, when searching for this term used elsewhere I couldn't find any formal definition what it is. Reading further in the README it looks like the author implies that it really just means a DFA? Not entirely sure.

I'd also like to add the Plan 9 implementation[0], which also uses the properties of utf8 as part of its state machine and anecdotally has been quite performant when I've used it.

[0] http://git.9front.org/plan9front/plan9front/107a7ba9717429ae...

I don't get that either.

It feels like they compare the asynchronous-ness of their algorithm to Nginx being asynchronous ("asynchronous web-servers like Nginx use a state-machine parser. They parse the bytes as they arrive, and discard them."), but I don't see how that relates. The way web-servers handle requests (multiple threads vs multiple processes vs asynchronous event-driven in one thread) is completely orthogonal to how they parse headers.

The impression I have is that their algorithm works in a streaming way, without having to allocate memory buffers, and that they call that asynchronous (wrongly, as far as I can see).

I also don't really see what they mean by their algorithm being more scalable.

You can figure it out by just looking at the table and output. It prints the number of lines, then words, then characters. Since the lines count is counts[1], you can conclude that when a newline is encountered, the machine will transition to state 1, hence why the newline is the only 2 entry in the character table and all 2 entries in the state machine point to state 1. From the character table, we can see that characters are split between classes 0, 1, 2 which are word, space, and newline characters.

To get the definitions of all other states, by working back from the fact that state 2 is the word count, it must be entered when a word character (class 0) is hit after some space/newline characters. Hence state 0 represents the machine being in the middle of a sequence of whitespace, state 1 is when the machine is in a sequences of newlines, state 2 is the first letter of a word, and state 3 is any subsequent letter of a word. You can then verify that the machine transitions to the correct state from those by checking what it does in case of a word, space, or newline character. But I'm not sure why the table is 4×4. The fourth transition from every state is unreachable since the symbols are all in [0, 2].

As for why the approach is better, I think it's because it avoids branching. If you think about the length of a word, it's quite short compared to a CPU pipeline, so on a branching version of this you're going to be stuck spending most of your execution time on branch miss-prediction.

> Just remember, if you're ever debugging something and some values in a Class/Object/Group of them are set and others are unset the state machine avoids that issue.

Better yet, switch to a language that supports discriminated unions to avoid invalid state without having to write a low-level state machine. Each case in the union represents one of the valid states of the type. This is one of the many benefits of functional programming.

At search time, the principle difference between an NFA and a DFA is that, in an NFA, you can be in more than one state at the same time. There's no problem with implementing your transition function to advance all states you are in simultaneously for each character of input. You'll get `O(m * n)` time, where `m` is proportional to the number of states in the NFA and `n` is proportional to the length of the input.

The GP is remarking on a confusable term, "NFA algorithm," that has come to mean something different from its underlying theory. The PCRE2 documentation itself, for example[1], remarks about how it uses the "NFA algorithm" as its standard approach to matching. But of course, PCRE2 supports way more than the theoretical model of non-deterministic finite automata (NFA) actually supports. PCRE2 is much more expressive. Yet, the implementation approach is still called "NFA algorithm." Presumably the reason for this is that an NFA can be simulated by doing backtracking, but if you don't keep track of where you've visited, the worst case runtime of this is superlinear, possibly catastrophically so[2]. The problem is that the backtracking regex engines have evolved well beyond what an NFA actually supports. But the name stuck.

To make things even more confusing, as I mentioned above, an NFA can be used to execute a search in O(m * n) time. (We typically call that "linear in the size of the input" since the NFA itself can usually, but not always, be regarded as a constant factor. i.e., A literal regex string in your program source code.) So when you say something like, "a finite automata regex engine uses NFAs to guarantee linear time," you might be really confused if your background is in backtracking engines which... also use an "NFA," but of course cannot guarantee linear search time.

So what we have is ambiguous terminology, not unlike "regex" itself, which could perhaps mean a real theoretical "regular expression" (in the case of Hyperscan, RE2, Go's regexp package and Rust's regex crate) or it could mean "a very expressive DSL for pattern matching that supports more than what regular languages can describe" (in the case of PCRE2, ECMAScript's regex engine, Ruby's Oniguruma, Python's `re` module, and more). I've made my peace with "regex" being ambiguous, but the fact that "NFA algorithm" is itself ambiguous despite "non-deterministic finite automata" being a somewhat baroque and specific technical term, is very unfortunate.

To make things even worse---and I shit you not, I am not joking---the backtracking people seem to have taken to calling a linear time NFA search the "DFA algorithm."[3] (At least the PCRE2 docs mention it's not a "traditional" finite state machine...) But... it's not a DFA. The backtracking folks have effectively elevated the terms "NFA" and "DFA" to mean something very different from their theoretical underpinnings.

So when you have people that are only aware of one meaning of "NFA algorithm" talking to other people only aware of the other meaning of "NFA algorithm," chaos ensues.

[1]: https://www.pcre.org/current/doc/html/pcre2matching.html

[2]: https://github.com/BurntSushi/rebar?tab=readme-ov-file#cloud...

[3]: https://www.pcre.org/current/doc/html/pcre2matching.html#TOC...