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

121–130 of 157 posts

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

#121

Post by moody__ »

rhelz wrote: post #100
moody__ wrote: post #72

Earlier quoted context omitted.

I was not treating "asynchronous state machine" as a noun, even if taken as a generic adjective it doesn't make sense in this context. What "other things" is this wc2.c doing while the state machine is churning? There is no multi threading or multi processing going on here. So I find it hard to believe that this use of "asynchronous" is inside of what I would generally see it used as. As such I thought perhaps it ref…

// What "other things" is this wc2.c doing... AFAICT, wc2.c isn't written to be an asynchronous state machine. It doesn't ever seem to transfer the control to any other place. // So I find it hard to believe that this use of "asynchronous" is inside of what I would generally see it used as Yeah, you are legitimately confused. The post talks about asynchronous state machines, but w2c.c isn't an example of that. I'm su…

Why would the author of this repository make "wc2 - asynchronous state machine parsing" his header of his README if indeed wc2 was not by his own definition an "asynchronous state machine"? I ask you to consider what is more likely: that your blanket definition of asynchronous is incorrect as applied here or the author is just fucking with us by adding random words as the description of his project.

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

#122

Post by fragmede »

stkdump wrote: post #116
Dylan16807 wrote: post #109

Earlier quoted context omitted.

These benchmarks are on 92 million byte files so we're into the range where bringing a tank is fair (and worth the startup cost).

I doubt that you can make it faster on the GPU than on CPU when utilizing SIMD, reason being that you are actually doing something close to trivial upon looking at each byte in sequence. So you transfer it from CPU memory to GPU memory in order to do almost nothing with it.

I've got it working on a T4 via Google Colab. The PDF takes 178 milliseconds to the 206 listed in the readme for the C version, so 15%?

https://github.com/fragmede/wc-gpu/blob/main/wc_gpu.ipynb

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

#123

Post by teo_zero »

Vvector wrote: post #57
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…

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

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.

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

#124

Post by casey2 »

jmholla wrote: post #8

> No, you aren't suppose to be able to see how the word-count works by looking at this code. The complexity happens elsewhere, setting up the state-machine. 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, b…

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 first, we aren't in a word so the only states we can enter are 0,1 and 2. That's helpful cause we can fill out the 1st element

{,0,} {} {} {} (a one sends us to the first row)

{[12],0,[12]} {} {} {}(we know 3 isn't a possible destination as we are out of a word)

{1,0,2} {} {} {} (actually we have a choice of {1,0,2} or {2,0,1} I'll show 1,0,2 but this swaps the first 2 args of print at the end)

{1,0,2} {} {1,0,2} {} (since newline is also out of a word we have the same options)

{1,0,2} {3,0,2} {1,0,2} {} (now 3 is a possible destination if we get zero. A one will take us to state 0 and a newline to state 2 as before)

{1,0,2} {3,0,2} {1,0,2} {3,0,2} (now 0,2, and 3 are our only possible states)

As you can see, there is nothing magic about it.

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

#125

Post by fragmede »

Dylan16807 wrote: post #109
fragmede wrote: post #106

In the bringing a tank to a knife fight kind of way, could this be optimized to run on a GPU? Load the contents then do an "and" across the whole contents in parallel, and then sum the whitespaces?

These benchmarks are on 92 million byte files so we're into the range where bringing a tank is fair (and worth the startup cost).

I got nerd sniped into doing it. https://github.com/fragmede/wc-gpu

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

#126

Post by 1vuio0pswjnm7 »

casey2 wrote: post #124
jmholla wrote: post #8

> No, you aren't suppose to be able to see how the word-count works by looking at this code. The complexity happens elsewhere, setting up the state-machine. 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, b…

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)

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

#127

Post by 1vuio0pswjnm7 »

rhelz wrote: post #62
moody__ wrote: post #32

The "asynchronous state machine" name here is a bit strange, when searching for this term used elsewhere I couldn't find any formal definition what it is. Reading further in the README it looks like the author implies that it really just means a DFA? Not entirely sure. I'd also like to add the Plan 9 implementation[0], which also uses the properties of utf8 as part of its state machine and anecdotally has been quite…

"Asynchronous" isn't part of the name of some really cool state machine :-) Its just an adjective and means the same as when you put it in front of any other noun. A synchronous state machine is one where the incoming stream of events is always "in sync" with the state transitions, in the following sense: 1. When an event happens, the state machine can transition to the next state and perform any necessary actions be…

"Parallel" seems to be a more popular term in the literature.

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

#128

Post by Maro »

I wrote a clean C++ version of `wc` for fun, and successfully beat the system version by 10-20% iirc. My goal was to make the code much more readable than the GNU/C version, which is a big spaghetti loop, while maintaining the same semantics (ie. return the same counts).

Blog posts:

https://bytepawn.com/tag/wc.html

Code:

https://github.com/mtrencseni/wcpp/

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

#129

Post by ncruces »

teo_zero wrote: post #123
Vvector wrote: post #57

Earlier quoted context omitted.

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

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.

And any loop that iterates more than 100 times.

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

#130

Post by brainwad »

kllrnohj wrote: post #97
jxndnxu wrote: post #81

Earlier quoted context omitted.

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…

Those 1-4 bytes are sitting in a register the entire time and thus basically free to read as often as you want, though. An actual sampled profile showing the two approaches would be interesting. Naively it seems like it's just because it has faster UTF8 handling and nothing to do with being a state machine exactly

According to the authors it's also faster on files full of 'x' or ' ', so there must be more than just better unicode support.
Post reply on HN