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

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. When you go to transition between states check that the future state will be valid and if-not go to an error state with that information. The amount of time I've seen spent debugging where spurious `null`s came from completely dwarfs the time it would've taken just to write that class/algorithm as a state machine.

Kinda surprised WC wasn't a state machine to beginning with. Isn't it effectively a special characters counter where if you see a charactered followed by a space bump up the word count? I'm judging by the repos comment of "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 -- which re-implementations of wc skip." that the big improvement is removing unnecessary work of those methods. mbrtowc [1] appears to re-create the provided substring which isn't necessary to count.

[1]: https://en.cppreference.com/w/cpp/string/multibyte/mbrtowc

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.

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:

    /**
     * Build an ASCII row. This configures low-order 7-bits, which should
     * be roughly the same for all states
     */
    static void
    build_basic(unsigned char *row, unsigned char default_state, unsigned char ubase)
    
    ...
    
    /**
     * This function compiles a DFA-style state-machine for parsing UTF-8
     * variable-length byte sequences.
     */
    static void
    compile_utf8_statemachine(int is_multibyte)

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?

This is strange to me, shouldn't it be O(N) with the size of the input ? Or maybe in this benchmark the inputs are small enough that the difference isn't measurable ?