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.
See for example this quick investigation and look at the number of branches for what's not a very big program https://bnikolic.co.uk/blog/hpc-perf-branchprediction
Only branches that capture exceptional events, e.g. error checks, show 99% hit rate.
Branches that are part of an algorithm are driven by the data you feed to them. For example in a classical binary search, the prediction is right only 50% of the time.
If we have an instruction that will conditionally load one of two pointers from memory, the left or right traversal can be made branch-free.
The only reason we need to switch between two code paths in the binary tree descent is that we have two different pieces of code for loading the left or right pointer to the different offsets used in the load instruction.
If we use a two element array for left and right, the indices [0] and [1] select between them. We make the comparison condition calculate a 0 or 1 result and use it as an index.
Because newlines are relatively common and unpredictable a state machine is likely better. But on a long file with no new lines and no spaces the branching one should be slightly faster. (All reasoning from first principles; I have not done any benchmarking!)
wc2 and wc might be compiled with different flags / use a different strategy for IO, which makes it hard to compare speeds directly. The theoretical speedup of branches is tiny compared potential speedup of changing your compiler flags!
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.
To handle illegal chars, it would need a 4th class but also a 5th state, so that's not the reason.
Can it be to replace a 'modulo' operation with an 'and' in the access to table?
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.
It's especially obvious in the Unicode case where it first takes 1-4 bytes to get a Unicode character and then checks this character with another function to see if it's whitespace
But even with with naive ASCII approach, if you don't hand roll a state machine you are checking multiple conditions on each byte (is it a space and am I leaving a word etc)
Using a dfa has fixed compute per byte
An actual sampled profile showing the two approaches would be interesting. Naively it seems like it's just because it has faster UTF8 handling and nothing to do with being a state machine exactly
Personally, I'd expect SIMD to win over all of these. wc sounds like kind of challenge that's very easy to partition and process in chunks, though UTF-8 might ruin that.
Which counters to increment at each byte depends on the previous bytes, though. You could probably succeed using overlapping chunks, but I wouldn't call it very easy.
It's framed in the context of programming-language tokenization, but the principles are the same.
A project with all code working with special magic reminds me of another project that some attention a while back (XZ lib - supposed improvements with packages containing clever system back doors).
Edit: The code is likely harmless but the more opaqueness is in a system, the easier it is for malevolent opaqueness to hide.
[1] https://github.com/angea/pocorgtfo/blob/master/contents/arti... [2] https://twitter.com/ErrataRob/status/1494009849427992576
For starters you need to know what the states the values represent (you should remember this from k&r)
0 we are out of a word, but not via newline (lets call this character type "a one").
1 we are out of a word, via a newline ("a two" or "a newline").
2 we entered a word ("a zero").
3 we are in a word ("a zero").
So we know we need 4 rows in the table
{} {} {} {}
lets fill the 0th row first, we aren't in a word so the only states we can enter are 0,1 and 2. That's helpful cause we can fill out the 1st element
{,0,} {} {} {} (a one sends us to the first row)
{[12],0,[12]} {} {} {}(we know 3 isn't a possible destination as we are out of a word)
{1,0,2} {} {} {} (actually we have a choice of {1,0,2} or {2,0,1} I'll show 1,0,2 but this swaps the first 2 args of print at the end)
{1,0,2} {} {1,0,2} {} (since newline is also out of a word we have the same options)
{1,0,2} {3,0,2} {1,0,2} {} (now 3 is a possible destination if we get zero. A one will take us to state 0 and a newline to state 2 as before)
{1,0,2} {3,0,2} {1,0,2} {3,0,2} (now 0,2, and 3 are our only possible states)
As you can see, there is nothing magic about it.
The parent seems to be using the term "magic numbers" incorrectly.
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, but even there the comments are largely describing what things do and not why, so I feel you need to have some understanding of the algorithm in question. For example, the parts where the state table gets constructed rather unhelpful comments to the uninformed:
Even `wc2o.c` doesn't delve into the magic numbers it has chosen. I was hoping this repo would be more educational and explain how the state table works and why it's constructed the way it is.Does anyone have a good resource for learning more about asynchronous state-machine parsers, that also could hopefully help explain why this is better than just iterating over characters? I'm guessing maybe it's the lack of branching?