Good to see effort to speed up wc, its been taking way too many cycles away from my 1.5GiB electron chat program
Wc2: Investigates optimizing 'wc', the Unix word count program
151–157 of 157 posts
Re: Wc2: Investigates optimizing 'wc', the Unix word count program
#152Earlier quoted context omitted.
An ASCII SIMD wc would likely be much more than 4× faster. The 320 MB/s is speed TFA quotes is good for a byte-at-a-time solution, but pitiful as far as the capabilities of modern machines are concerned. A decent SSD is an order of magnitude faster than that. Around 1 GB/s (i.e. ~100 cycles/fetch) is table stakes for a task of this complexity. (TFA almost nerd-sniped me into writing a SIMD implementation already, and…
Remember exploring the simd fizz-buzz solution[0] and forgot just how fast computers can be [0] https://codegolf.stackexchange.com/questions/215216/high-thr...
There are degrees to this kind of thing, and this is far far away from that one (exercise: find one instruction in the code that can be deleted without changing anything else). On my (Ryzen 7x40) laptop it does run around two times faster than its SSD can supply data (11 GB/s vs 6 GB/s), and—to my great surprise—gets four times(!) slower if you feed it via (GNU) cat(1) instead of shell redirection (slowdown from piping from pv is below 1.5× though).
Yet it’s nowhere near being bottlenecked on memory bandwidth (theoretical at 80 GB/s, sequential-read actual at 55 GB/s, memset at 45 GB/s, or—probably most realistically given we’re not using zero-copy I/O—memcpy at 25 GB/s). As Daniel Lemire put it, “Data engineering at the speed of your disk”[1].
Unfortunately, to get that speed out of your computer, you end up needing to program any transformations you may need in strange, target-dependent, and most importantly nearly noncomposable ways. Compiler engineers have been working on the problem for more than two decades, but I don’t think we’re putting away our intrinsic references and latency tables any time soon. One good way[2] to explain the problem is that a single core of the CPU mentioned above (for example) has about as much memory it can access essentially instantly as the original IBM PC without addons: about 64 KB (then it was called “RAM”, now we call it “physical registers” and “L1 cache”).
Re: Wc2: Investigates optimizing 'wc', the Unix word count program
#153Earlier quoted context omitted.
Even something as simple as wc calling a libc function for parsing utf-8, that doesn't get inlined, would destroy its performance relative to anything optimized. 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.
> very easy to partition and process in chunks 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.
That sort of "find the correct chunk boundary" logic was very common with all the mapreduce processing that was done when people still used the phrase big data.
Re: Wc2: Investigates optimizing 'wc', the Unix word count program
#154Earlier quoted context omitted.
Here's how the table is made 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 fir…
"As you can see, there is nothing magic about it." The parent seems to be using the term "magic numbers" incorrectly. https://en.wikipedia.org/wiki/Magic_number_(programming)
[deleted]
Re: Wc2: Investigates optimizing 'wc', the Unix word count program
#155From 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
It's funny that you call that the standard algorithm, because, although it intuitively makes sense, this is the first time I've seen that word-counting algorithm. The first implementation of wc I ever saw was the one from The C Programming Language , which has this written at the beginning of the book (except instead of "(isspace(c))" they wrote "(c == ' ' || c == '\n' || c == '\t')"): state = OUT; nl = nw = nc = 0;…
[deleted]
Re: Wc2: Investigates optimizing 'wc', the Unix word count program
#156Re: Wc2: Investigates optimizing 'wc', the Unix word count program
#157Earlier quoted context omitted.
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 ambiguit…
Thanks for the detailed explanation to grok the whole landscape.