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

he is talking in context of same-sized files (counted in bytes)

I wanted to take a peek the state diagram (ASCII version). But I was feeling lazy, so apologies for having ChatGPT do the work for me. I wasn't going for correctness and didn't check it. If you're like me, here you go:

https://dreampuf.github.io/GraphvizOnline/#digraph%20StateMa...

digraph StateMachine { rankdir=LR; size="8,5"; node [shape = circle];

    LookingForWord -> InsideWord [label="Non-space"];
    LookingForWord -> LookingForWord [label="Space"];
    LookingForWord -> Newline [label="Newline"];
    LookingForWord -> LookingForWord [label="Other"];
    
    Newline -> InsideWord [label="Non-space"];
    Newline -> LookingForWord [label="Space"];
    Newline -> Newline [label="Newline"];
    Newline -> LookingForWord [label="Other"];
    
    InsideWord -> ContinueWord [label="Non-space"];
    InsideWord -> LookingForWord [label="Space"];
    InsideWord -> Newline [label="Newline"];
    InsideWord -> LookingForWord [label="Other"];
    
    ContinueWord -> ContinueWord [label="Non-space"];
    ContinueWord -> LookingForWord [label="Space"];
    ContinueWord -> Newline [label="Newline"];
    ContinueWord -> LookingForWord [label="Other"];

}

EDIT: Under peer pressure, I checked it and it correctly reflects the code apart from being designed for one specific line ending sequence (as it should, being an example optimized for brevity).

As for the replies, as opposed to my approach, I'm sure when you're browsing research papers, you're doing a full reproducibility study for each one. I'm sorry I commented, I should have waited for you to post your results.

I’m with you. It appears to be a fairly bog-standard DFA, but divining that from 4x4 `int`s and a 256 `char` array feels like I’d just be doing all of the heavy lifting, intellectually. However… it does look like it’s trying to detect spaces (that’s the array of 256 `char`, as `char` is self-indexing). I can’t be bothered to remember how `wc` works, but my guess is that the state-machine has transition states for `sp->sp`, `sp->wd`, `wd->wd`, and `wd-sp`. It’d also need error modes. I suppose it doesn’t contain states for escapes?

> This is analogous to NFA and DFA regular-expressions. If you use the NFA approach, you need to buffer the entire chunk of data, so that the regex can backtrack. Using the DFA approach, input can be provided as a stream

Sorry, no, this is completely wrong. There are other reasons NFAs or DFAs might be preferable, and there are other performance considerations as far as backtracking is concerned, but NFA implementations do not backtrack. I mean, they could, but they don’t, and in common usage a “NFA regex implementation” means a non-backtracking one (that goes through all input once with a bag of states in hand and advances each one of them on each step), whereas a “backtracking regex implementation” means one that doesn’t use automata at all (and is usually worst-case exponential in the input).

What this is actually talking about is a streaming parser. Just call it like it is, it’s an OK term that sees plenty of usage.

[What you could mention here is PEG parsers, because even linear PEG implementations may need to keep O(input) state and thus are essentially incapable of streaming, unlike LL or LR ones; and GLR et al. can be even worse, for what it’s worth. But this is a much more obscure topic.]

They definitely do in simple cases (e.g. a simple for loop). In more complex cases, especially when the index/pointer escapes a function then the code will be different.