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

101–110 of 157 posts

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

#101

Post by roetlich »

JackSlateur wrote: post #56

Reading the code to help me understand how things are I got the wc_lines from coreutils: https://github.com/coreutils/coreutils/blob/master/src/wc.c#... And I thought "damn, I understand nothing about the state-machine stuff, how did they made this faster ?" Truth is: they did not Of course, this is just the "count line" part. Other parts are indeed faster. Coreutils 9.4: 0.67 [jack:/tmp] /usr/bin/time -v wc -l debia…

From looking at the code, the clever bit is how this is doing word count. (and word & line count at the same time). So yeah, it makes -l isn't better.

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

#102

Post by joe_the_user »

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…

Hmm,

A project with all code working with special magic reminds me of another project that some attention a while back (XZ lib - supposed improvements with packages containing clever system back doors).

Edit: The code is likely harmless but the more opaqueness is in a system, the easier it is for malevolent opaqueness to hide.

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

#103

Post by 1vuio0pswjnm7 »

"The wc program included with macOS and Linux are completely different. Therefore, the following table shows them benchmarked against each other on the same hardware."

Appears BSD wc ("the macOS program") is much faster than the GNU coreutils wc ("the Linux program").

It certainly illustrates a point about people rewriting wc in newer languages to demonstrate alleged speed against C.

Which wc are they using for comparison.

Pehaps they should use wc2 or wc2o.

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

#104

Post by mytec »

1vuio0pswjnm7 wrote: post #103

"The wc program included with macOS and Linux are completely different. Therefore, the following table shows them benchmarked against each other on the same hardware." Appears BSD wc ("the macOS program") is much faster than the GNU coreutils wc ("the Linux program"). It certainly illustrates a point about people rewriting wc in newer languages to demonstrate alleged speed against C. Which wc are they using for compa…

That's a really good point. I'm using macOS and I tested -w option against a CSV file that is about 430MB in size and has about 18,000,000 words in it. The time was 0.989. When I ran wc2 on the same file, it clocked in at 0.943.

I wondered what I was doing wrong and came back to the comments section and found your comment. Ah.

Edit: interestingly, the newline count time was 0.458 with the macOS version and 0.943 with wc2.

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

#107

Post by lmm »

lesuorac wrote: post #2

State machines are an underrated approached. 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…

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

You don't want a state machine for that, you want sum types. Using state machines give you the worse problem of not being able to tell how you got into to a given state, not being able to take meaningful stack traces, which is generally an even worse problem.

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

#108

Post by tkhattra »

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…

rob graham wrote an article on this wc program in the humorously titled PoC||GTFO journal - see [1]. he also tweeted about it a few years ago [2].

[1] https://github.com/angea/pocorgtfo/blob/master/contents/arti... [2] https://twitter.com/ErrataRob/status/1494009849427992576

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

#109

Post by Dylan16807 »

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

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

#110

Post by kllrnohj »

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?

Run a profiler on your code sometime and see how many branches it reports taking. You can easily get millions of branches per second, so 1% events happen hundreds of thousands of times.

See for example this quick investigation and look at the number of branches for what's not a very big program https://bnikolic.co.uk/blog/hpc-perf-branchprediction

Post reply on HN