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

Destroying C with 20 lines of Haskell: wc

0xd34df00d.me

Post reply on HN
Print view View original

51–60 of 74 posts

Re: Destroying C with 20 lines of Haskell: wc

#51

Post by felixge »

ColinWright wrote: post #33

So I just wrote the most naive version of wc I could think of in C, matching the capability of this Haskell version, and I smoked the system wc ... my code, unoptimised, was over twice as fast. $ time wc Backups/Tera2/files.txt 1123699 2283439 161361844 Backups/Tera2/files.txt real 0m2.010s user 0m1.964s sys 0m0.020s $ time naive Backups/Tera2/files.txt L: 1123699 W: 2283439 C: 161361844 real 0m0.864s user 0m0.835s s…

Just put together a naive version of wc in Go and got similar perf gains over the wc that ships with macOS.

That being said, unlike the OP, I don't think it means anything as wc is likely supporting more features than my program.

    $ time wc test.txt
     16500000 49252094 2059004431 test.txt

    real 0m5.930s
    user 0m5.491s
    sys 0m0.374s

    $ go build wc.go && time ./wc test.txt
    16500000 49252094 2059004431

    real 0m2.947s
    user 0m2.620s
    sys 0m0.299s
https://gist.github.com/felixge/aa70fc97e893a7eb0bd4c801f8f5...

Re: Destroying C with 20 lines of Haskell: wc

#52

Post by AnIdiotOnTheNet »

pinkfoot wrote: post #25
jstimpfle wrote: post #23

> So we’ve managed to just smash a C program that was looked at by thousands of eyes of quite hardcore low-level Unix hackers over a few decades. We did this with a handful of lines of pure, mutation-less, idiomatic Haskell, achieving about 4 to 5 times of throughput of the C version and spending less than an hour on all the optimizations. I've done many very arrogant things in my life, because I've been a strange gu…

Perhaps - just possibly maybe perhaps - he was suggesting its is his superior tool and technology that allowed his team to do this. Do you think you took the most generous possible interpretation possible?

> he was suggesting its is his superior tool and technology that allowed his team to do this

He really thinks it makes sense that a "C program that was looked at by thousands of eyes of quite hardcore low-level Unix hackers over a few decades" is that much slower than something he threw together? That's like doing some back of the napkin math in a bar and declaring relativity wrong (while also not being Edward Witten). Any reasonable person would suspect that this isn't a very likely outcome and dig deeper to figure out if that's really true or not. My guess is he just implemented a very trivial and naive version of the C code and that's why it is faster.

Re: Destroying C with 20 lines of Haskell: wc

#54

Post by jstimpfle »

0xd34df00d wrote: post #43
jstimpfle wrote: post #23

> So we’ve managed to just smash a C program that was looked at by thousands of eyes of quite hardcore low-level Unix hackers over a few decades. We did this with a handful of lines of pure, mutation-less, idiomatic Haskell, achieving about 4 to 5 times of throughput of the C version and spending less than an hour on all the optimizations. I've done many very arrogant things in my life, because I've been a strange gu…

Those are fairly trivial and well-known optimizations that I did (and I by no means am an expert in writing high-performant code), so all the honors go to GHC authors.

Thanks for replying. I want to tell you that I feel deep regret for my impulse to publically shame you - even though I've gotten a lot of points for this comment, and did not really receive criticism for it.

Hey - if you make performance optimizations and compare implementations, it's probably best not to jump to quick conclusions. I would advise to brush up on C to get a feel for performance. Or, in times where it's popular to shit on C, and claim that it's not really a low-level language anymore, I would advise to write some assembler (which I've barely done). In practice it's unlikely that you find yourself in a situation where you can write code in a high-level language that runs considerably faster than what you could realistically write in C. The only situation where that can happen that I can see, is when the program does something that is so complicated but seems so arbitrary that you simply can't bring yourself to invest more time than what you need to hack together a quick Python script, and what you would be willing to write in C would be not even the asymptotically best approach that you can see.

For a simple program like wc, that situation does not apply, and if you find surprising results, it's best to first check for other possible reasons than "thousands of graybeards were wrong".

Re: Destroying C with 20 lines of Haskell: wc

#55

Post by zzzcpan »

ColinWright wrote: post #33

So I just wrote the most naive version of wc I could think of in C, matching the capability of this Haskell version, and I smoked the system wc ... my code, unoptimised, was over twice as fast. $ time wc Backups/Tera2/files.txt 1123699 2283439 161361844 Backups/Tera2/files.txt real 0m2.010s user 0m1.964s sys 0m0.020s $ time naive Backups/Tera2/files.txt L: 1123699 W: 2283439 C: 161361844 real 0m0.864s user 0m0.835s s…

I got 5.6x speedup on just wc alone with:

  export LANG=C
(obviously in both cases with prewarmed filesystem cache)

Re: Destroying C with 20 lines of Haskell: wc

#56

Post by quadrifoliate »

I would really like to see fewer of these clickbait post titles. The author honestly admits here (props!) https://news.ycombinator.com/item?id=22235536 that they only used the title because it encourages discussion.

In that case, I would say that it's up to the community to not take clickbait titles like this seriously if we want to encourage reasoned, detailed content rather than borderline flaming with words like "destroy" and "smash". I personally don't enjoy this new Buzzfeed style of technical post at all.

Therefore, I have some comments about the actual code here, but going to keep them to myself so I don't encourage more people to follow OP's example.

Re: Destroying C with 20 lines of Haskell: wc

#57

Post by hnlmorg »

notacoward wrote: post #5

This doesn't seem to be comparing anything like the same thing. Does the Haskell version really do the same thing as the C version? Does it handle all of the same error cases, providing the same quality of error messages if they occur? Does it handle localization? If not, that makes the comparison very skewed, as unhammer already pointed out. Sure, if you strip out all of the things that the people who wrote wc actua…

He's not handling unicode and it's been well demonstrated in the past that unicode handling adds a lot to computation time in tests like these (it often comes up in grep benchmarks too).

I'd be interested to see the same tests but with a non-unicode local set, IIRC:

    LC_ALL=C
I'd wager the C version would perform much better in that test.

Re: Destroying C with 20 lines of Haskell: wc

#58

Post by ColinWright »

0xd34df00d wrote: post #49
ColinWright wrote: post #44

Earlier quoted context omitted.

Reproducing what your code does in the most simple, naive C program possible, I can beat the existing wc utility, taking only around 40% of the time that wc takes. So until you put in locale handling, alternate line endings, option handling, and error handling, I don't see that your post is at all convincing. Quite the opposite. So I look forward to a Haskell version that supports everything the wc has so we can get…

> So until you put in locale handling, alternate line endings, option handling, and error handling, I don't see that your post is at all convincing. That's precisely what the second part would be about. And, if I succeed, IMO, that's where Haskell would really shine (because composability and local reasoning), and where I would be able to claim to achieve something — the stuff in the post we're discussing is indeed t…

FWIW, my version, now compiled with -O3, is 8 times faster than wc. And I haven't even tried to optimise it.

I look forward to your results.

Re: Destroying C with 20 lines of Haskell: wc

#59

Post by zzzcpan »

0xd34df00d wrote: post #45
mkup wrote: post #7

But how would Haskell version of wc compare with C version of wc running with LC_ALL=C environment variable? UTF-8 locale is much slower than C locale in coreutils, it's a well-known fact, and their Haskell version of wc is already using fixed 8-bit characters.

wc was actually slower with LC_ALL=C as opposed to ru_RU.UTF-8 that my system normally runs with (about 10 s against 7.2 s). Which actually raises a good question of whether I should have been comparing with that one — but that'd probably raise more questions and lead to more people accusing me of cheating in favour of Haskell.

The only way I can think of this could be true is if you made a mistake in setting an env var.

Re: Destroying C with 20 lines of Haskell: wc

#60

Post by jstimpfle »

hnlmorg wrote: post #57
notacoward wrote: post #5

This doesn't seem to be comparing anything like the same thing. Does the Haskell version really do the same thing as the C version? Does it handle all of the same error cases, providing the same quality of error messages if they occur? Does it handle localization? If not, that makes the comparison very skewed, as unhammer already pointed out. Sure, if you strip out all of the things that the people who wrote wc actua…

He's not handling unicode and it's been well demonstrated in the past that unicode handling adds a lot to computation time in tests like these (it often comes up in grep benchmarks too). I'd be interested to see the same tests but with a non-unicode local set, IIRC: LC_ALL=C I'd wager the C version would perform much better in that test.

Don't forget to export the variable, or run like "LC_ALL=C wc ...", or otherwise the locale won't apply.
Post reply on HN