4 ms·

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], y

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.

Vvector 2y ago
I've read recently (here on HN) that branch predictors are right 99% if the time. Is that inaccurate?
- kardos 2y ago
  It may be true in some cases, but not in general. I think of it as an observation that for large swathes of code the branch is predictable. Eg, we usually don't go down the error checking codepath. Faced with flow control that depends on random data, such as "is this random number even", the branch predictor will have a hard time doing better than 50%.
- James_K 2y ago
  This is the 1% of cases. As I understand it, most branches take the same path most of the time. Think of a loop for instance. With purely statistical prediction (go whichever direction the branch takes more often), loops will be predicted with extreme accuracy and the result is a huge number of correct branches. Then think about error handling code which isn't triggered most of the time due to input being valid. Between these two easy cases, I think you cover the majority of branches is programs which is why so many of them are predictable.
- drchickensalad 2y ago
  If you're like me, you need to stop thinking of it as "99% of call sites" and start thinking of it as "99% of iteration loops". I know it's super obvious on the face of it, but the implications is that most call sites can repeatedly fail but are totally overshadowed by insanely high frequency hot loops that it almost always predicts right (it's skewed, just like avg vs median)
- kllrnohj 2y ago
  Run a profiler on your code sometime and see how many branches it reports taking. You can easily get millions of branches per second, so 1% events happen hundreds of thousands of times. 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 https://bnikolic.co.uk/blog/hpc-perf-branchprediction
- teo_zero 2y ago
  That's an over-generalization. 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.
  - ncruces 2y ago
    And any loop that iterates more than 100 times.
  - kazinator 2y ago
    But there's an overall loop which branches backward to the same spot, regardless whether the iteration went left or right. At least that's predictable. 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.
tylerhou 2y ago
There are fewer branches but there is now a data dependency between loop iterations which makes each iteration slightly slower (maybe 1-2 cycles additional latency per iteration). 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!)
- anamexis 2y ago
  The README covers the exact case you describe - the `word.txt` benchmark is just a file with 93MB of the char `x`. The state machine is still faster in this case.
  - tylerhou 2y ago
    wc2 is faster than wc, but unless I am missing something, I can't find an instance where the author benchmarked wc2 with the core state machine loop replaced with branches. 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!
samatman 2y ago
> 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.
- James_K 2y ago
  That isn't relevant in the ASCII example, and the UTF-8 one uses a 256×256 table.
  - samatman 2y ago
    Half of all bytes are illegal ASCII though.
    - James_K 2y ago
      And actually there isn't a state for illegal ASCII so it makes no sense to have a transition to/from it. And it still can never receive a 3 as input and use that transition.
- teo_zero 2y ago
  For handling ASCII, table needs 4 states × 3 classes of chars. Why is it defined as 4×4? 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?

Vvector 2y ago

I've read recently (here on HN) that branch predictors are right 99% if the time. Is that inaccurate?

kardos 2y ago
It may be true in some cases, but not in general. I think of it as an observation that for large swathes of code the branch is predictable. Eg, we usually don't go down the error checking codepath. Faced with flow control that depends on random data, such as "is this random number even", the branch predictor will have a hard time doing better than 50%.
James_K 2y ago
This is the 1% of cases. As I understand it, most branches take the same path most of the time. Think of a loop for instance. With purely statistical prediction (go whichever direction the branch takes more often), loops will be predicted with extreme accuracy and the result is a huge number of correct branches. Then think about error handling code which isn't triggered most of the time due to input being valid. Between these two easy cases, I think you cover the majority of branches is programs which is why so many of them are predictable.
drchickensalad 2y ago
If you're like me, you need to stop thinking of it as "99% of call sites" and start thinking of it as "99% of iteration loops". I know it's super obvious on the face of it, but the implications is that most call sites can repeatedly fail but are totally overshadowed by insanely high frequency hot loops that it almost always predicts right (it's skewed, just like avg vs median)
kllrnohj 2y ago
Run a profiler on your code sometime and see how many branches it reports taking. You can easily get millions of branches per second, so 1% events happen hundreds of thousands of times. 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 https://bnikolic.co.uk/blog/hpc-perf-branchprediction
teo_zero 2y ago
That's an over-generalization. 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.
- ncruces 2y ago
  And any loop that iterates more than 100 times.
- kazinator 2y ago
  But there's an overall loop which branches backward to the same spot, regardless whether the iteration went left or right. At least that's predictable. 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.

tylerhou 2y ago

There are fewer branches but there is now a data dependency between loop iterations which makes each iteration slightly slower (maybe 1-2 cycles additional latency per iteration). 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!)

anamexis 2y ago
The README covers the exact case you describe - the `word.txt` benchmark is just a file with 93MB of the char `x`. The state machine is still faster in this case.
- tylerhou 2y ago
  wc2 is faster than wc, but unless I am missing something, I can't find an instance where the author benchmarked wc2 with the core state machine loop replaced with branches. 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!

samatman 2y ago

> 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.

James_K 2y ago
That isn't relevant in the ASCII example, and the UTF-8 one uses a 256×256 table.
- samatman 2y ago
  Half of all bytes are illegal ASCII though.
  - James_K 2y ago
    And actually there isn't a state for illegal ASCII so it makes no sense to have a transition to/from it. And it still can never receive a 3 as input and use that transition.
teo_zero 2y ago
For handling ASCII, table needs 4 states × 3 classes of chars. Why is it defined as 4×4? 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?