Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

github.com

Post reply on HN
Print view View original

81–90 of 157 posts

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

#81

Post by jxndnxu »

loeg wrote: post #39
zadokshi wrote: post #25

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

Because classic wc is not iterating over every byte once, but multiple times.

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

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

#82

Post by jxndnxu »

btown wrote: post #65

State machines are great for complex situations, but when it comes to performance, it's not at all clear to me that they're the most scalable approach with modern systems. The data dependency between a loop iteration for each character might be pipelined really well when executed, and we can assume large enough L1/L2 cache for our lookup tables. But we're still using at least one lookup per character. Projects like h…

My understanding of the article's use of scalable was "fixed overhead more or less regardless of the complexity of the state machine and input" not "fastest implementation available"

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

#83

Post by jxndnxu »

throwaway55533 wrote: post #53

From reading the article, how is this more efficient? Doesn't any word counting algorithm have to iterate through all the characters and count spaces? What makes this better than the standard algorithm of wc = 0 prev = null for ch in charStream: if !isSpace(ch) and isSpace(prev): wc += 1 prev = ch

You have answered your question yourself: your algorithm looks at each byte twice, not once

It's even more obvious in the UTF case where the classic implementation first looks at 1-4 byte to parse a character and only then checks if it's a space

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

#84

Post by jxndnxu »

aftbit wrote: post #24

It would have been nice for the author to label the states and explain how and why they chose the states that they did. Otherwise, it's hard to understand how to apply this sort of thing to larger problems.

How would if have helped? You either design a DFA by hand or use a compiled from a regular language

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

#85

Post by trealira »

mjamil wrote: post #4

"Many programmers think pointer-arithmetic is faster." Don't modern compilers make this statement false (i.e., both approaches are implemented via the same machine instructions)?

Something funny is that GCC may compile your code that uses pointer arithmetic into one that uses an index register, and compile your code that uses an index into an array as pointer arithmetic.

https://godbolt.org/z/9KPnnM7Po

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

#86

Post by anamexis »

tylerhou wrote: post #58
James_K wrote: post #36

Earlier quoted context omitted.

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…

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…

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.

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

#87

Post by d0mine »

GrantMoyer wrote: post #52
pletnes wrote: post #35

Earlier quoted context omitted.

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.

The video Finite State Machines explained by Abelardo Pardo[1] seems like a good introduction (I'm not familiar with the author; I just searched Finite State machine on youtube and found the first result which wasn't a jumbled mess of abstract or misused jargon). It may seem simple, but that's truely all there is to finite state machines, a set of finite states and a set of events which cause transitions between stat…

It could be written as:

    while True:
        ...
        if :
            break

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

#88

Post by scottlamb »

nitwit005 wrote: post #74

The 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 N…

Are we looking at the same thread? Folks there seem to be complaining the old interfaces are anything from outdated to confusing to simply wrong, and I agree.

I think it's totally reasonable for a program designed in 2024 to say it only supports ASCII and UTF-8 encodings. Whether/how it should support the full spectrum of Unicode definitions of characters/graphemes/... is more interesting. For a lot of backend code (processing text-based network protocols, for example), focusing on ASCII is arguably best (e.g. functions like isspace and isdigit only returning true for ASCII characters). For more user-focused stuff, most of the world would say they'd like their native language supported well. Programs written with both use cases in mind should probably have a switch. (Or parallel APIs: e.g. Rust has {u8,char}::is_ascii_digit vs. char::is_numeric, which makes much more sense there than having one that switches behaviors based on an environment variable, as the correct behavior really depends on the call site.)

Of course "say it only supports ASCII and UTF-8 encodings" is mutually exclusive with claiming to be a drop-in replacement for a utility that is specified as having POSIX locale support. This project does not make that claim, or even that it's intended to be actually used rather than illustrative of a performance technique.

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

#89

Post by James_K »

samatman wrote: post #73
James_K wrote: post #36

Earlier quoted context omitted.

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.

That isn't relevant in the ASCII example, and the UTF-8 one uses a 256×256 table.

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

#90

Post by burntsushi »

fanf2 wrote: post #75
burntsushi wrote: post #40

Earlier quoted context omitted.

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

Yeah I didn't mention Friedl because I've dumped on him in the past, and didn't want to belabor it. But Friedl definitely didn't start this. According to him, he was just using what was common vernacular even back then: http://regex.info/blog/2006-09-15/248 (Note that blog is from 2006, but he's actually quoting himself from ~10 years prior to that in 1997.)

But... he is the one who ultimately installed this ambiguity into a classic book that is still read to this day. So I think he can at least be blamed for popularizing the confusion. And especially since the entire book is framed around "NFA" and "DFA" regex engines. It's not like it was just some one-off mention. The mix-up is baked into the conceptual fabric of the book. The landscape also looked different back then. It predated RE2 for example, and RE2 is, I think, principally responsible for bringing "backtracking semantics" to finite automata oriented engines. So Friedl's book is forever stuck in a false dichotomy that only happened to exist back when he wrote it.

Post reply on HN