I didn't know you were allowed to use a language other than Rust for something like this.
Wc2: Investigates optimizing 'wc', the Unix word count program
71–80 of 157 posts
Re: Wc2: Investigates optimizing 'wc', the Unix word count program
#72The "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…
"Asynchronous" isn't part of the name of some really cool state machine :-) Its just an adjective and means the same as when you put it in front of any other noun. A synchronous state machine is one where the incoming stream of events is always "in sync" with the state transitions, in the following sense: 1. When an event happens, the state machine can transition to the next state and perform any necessary actions be…
I was not treating "asynchronous state machine" as a noun, even if taken as a generic adjective it doesn't make sense in this context. What "other things" is this wc2.c doing while the state machine is churning? There is no multi threading or multi processing going on here. So I find it hard to believe that this use of "asynchronous" is inside of what I would generally see it used as. As such I thought perhaps it referred to a specific methodology for designing the code, something akin to how the "lock free" adjective implies a certain design sensibility.
Re: Wc2: Investigates optimizing 'wc', the Unix word count program
#73> No, you aren't suppose to be able to see how the word-count works by looking at this code. The complexity happens elsewhere, setting up the state-machine. This is like most of the reason I opened this article. I wish they'd spend more time talking about this. In fact, most of the README covers details that are important, but, irrelevant to their algorithmic improvements. Maybe they expect you to open up the code, b…
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 char…
> 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].
I think the fourth transition represents illegal Unicode. From there it stays in the illegal state until it hits legal UTF-8, then goes back to counting.
Re: Wc2: Investigates optimizing 'wc', the Unix word count program
#74The primary reason their code is faster as they've made incorrect code that assumes you always have a UTF-8 locale. The normal isspace does not assume this:
> The real programs spend most of their time in functions like mbrtowc() to parse multi-byte characters and iswspace() to test if they are spaces
This will produce bad results in the real world. People have previously posted about bugs related to this on Hacker News: https://news.ycombinator.com/item?id=36216389
Re: Wc2: Investigates optimizing 'wc', the Unix word count program
#75Earlier quoted context omitted.
How do you implement a non-backtracking NFA other than converting it to a DFA?
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. Th…
Yeah, it’s vexing. This backtracking / NFA / DFA confusion originally came from Jeffrey Friedl’s book “mastering regular expressions” (O’Reilly, 1997) — at least, that’s the first place I saw the mistake in print. Philip Hazel relied a lot on Friedl’s book when writing PCRE, which is why the PCRE docs get it wrong. (I spoke to Philip about this many years ago when we worked together.)
Re: Wc2: Investigates optimizing 'wc', the Unix word count program
#76Earlier quoted context omitted.
> why this is better than just iterating over characters? The explanation it provides regarding Apache vs Ngnix seemed to me to imply that Apache requires memory allocation to read headers into buffers and Ngnix uses a state machine to avoid memory allocation. Memory allocation is slower than most people realise.
Why is this better for wc, though? wc is not doing memory allocation in the hot loop.
I think it keeps wc simple if an algorithm is introduced not directly related to count words it becomes more complicated to debug. I see this a an example of the Unix philosophy of do one thing well.
Re: Wc2: Investigates optimizing 'wc', the Unix word count program
#77> The algorithm is known as an "asynchronous state-machine parser". It's a technique for parsing that you don't learn in college. The mapping from regular and context free languages to state machines and their table-based implementations was covered in depth in the Compilers course I took. A table based state machine is literally the textbook algorithm for parsing these classes of languages, and implementing them has…
For example, see Chapter 3 of the Dragon Book, Compilers: Principles, Techniques, and Tools by Aho, Ullman, et al. Or probably any other compilers text book.
Re: Wc2: Investigates optimizing 'wc', the Unix word count program
#78I was a bit surprised by the macos/linux speed differential here: > The difference in macOS and Linux speed is actually the difference in clang and gcc speed. The LLVM clang compiler is doing better optimizations for x86 processors here. I know GCC has been getting much, much more aggressive as of late, but there have been some complaints that it is now much, much less safe (checks intended for security getting optim…
I'd assume the difference between Linux's GNU and macOS's BSD implementations would be much more significant.
Exactly. MacOS (really BSD) grep sucks, 5-10x slower than GNU Grep for simple searches on the same hardware, but MacOS/BSD wc is fast.
Re: Wc2: Investigates optimizing 'wc', the Unix word count program
#79Earlier quoted context omitted.
> 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 funct…
This comes down to "Make Invalid States Unrepresentable" Notably Go's choice here is instead "Make Representable States Valid". So for example in Go it's not possible for a type not to have a default value - every type must have a value you get by default, you could name this unwanted default value FUCK_OFF or DO_NOT_USE if you like, but in a larger system (where Go is supposed to thrive) you can be certain you'll fi…
> This is one of the few things the C++ type system almost gets right. You really can say for your C++ type no, it doesn't have a default.
Rust does even better here, I think, for fairly subtle reasons:
- Exceptions are replaced by Result, with explicitly-marked return points. They're far less magic. ("panic!" is still magic, but it's allowed to be a call to "abort", so you only use it when the world is burning.)
- "Move semantics" by default makes a lot of edge cases cleaner. If you move out of an object by default, it gets consumed, not set to a default value. Similarly, moving values into a newly-constructed object can't fail, because it's just memmove.
- Object construction is atomic from the programmer's perspective.
- Default initialization only works if you implement "Default". Which is actually just a normal trait with no magic.
- If you discover that you have a state machine, you can switch to discriminated unions ("enum") to make your states mutually exclusive and clearly represented.
This whole area is one of the better parts of Rust's design.
Re: Wc2: Investigates optimizing 'wc', the Unix word count program
#80I love state machines and every time I use one my workers think I invented it because they’ve never seen them before. The data for state machine in this article might be best prepared by generating it from a program. That generator program doesn’t need to care (too much) about performance since it is run during the build process. I like the idea of doing a lot of work now to save time in the future.
Do you have any accessible references on state machines? I’ve just read about them a bit but never coded one in a project. Seems like a useful concept for testable, reliable code.
A finite state machine has a set of input symbols, a set of states, and a transition function, which maps the current state and current input to the next state (and, when programming it, it doesn't have to be a literal function; for example, it could be a 2D array). It also has a start state, and a set of accept states.
It's also common for state machines to have some sort of output; otherwise, all an FSM can do is recognize whether an input string is "good." So, there's also an output function, so that the FSM actually does something while processing the input string. There are two types of FSMs: a Mealy Machine, and a Moore machine. In a Mealy machine, the output function maps the current state and the current input to an output; so, one state could be associated with multiple outputs. In a Moore machine, the output is purely a function of the current state, no matter the input. Usually, a Moore machine has more states than the equivalent Mealy machine. In practice, Moore machines are a lot rarer than Mealy machines.
You can model FSMs in a variety of ways. You could use the state pattern [0]. You could have a table-based state machine; examples in C here [1] [2]. It's also common to model them using a loop and a switch statement with integers to represent the current state - or just use "goto" to go to the next state, if it's available in your language.
Also, this is tangential, but something nice about coroutines is that they save can you from writing an explicit state machine, as the state is implicit in your code. One example of this is how it's easier to write iterators as coroutines that yield results as they run, rather than as structures that update themselves based on their current state, transition to the next state, and yield a result.
So far, what I've covered is basically a deterministic finite automaton (DFA). There are also non-deterministic finite automata (NDFAs), which are used to implement regular expressions (at least when regular expressions aren't extended to require more powerful recognizers) [3], as well as pushdown automata (PDAs), which are basically finite automata with a stack, and can parse e.g. programming languages. Finally, there are Turing machines.
For theory on that, I'd recommend reading Sipser's Introduction to the Theory of Computation. If you look up the book on Google, it's not difficult to find a PDF of it.
[0]: https://refactoring.guru/design-patterns/state
[1]: https://nullprogram.com/blog/2020/12/31
[2]: https://ideone.com/94U6aJ (this one removes C-style comments from source code - I didn't make it)