Destroying C with 20 lines of Haskell: wc(0xd34df00d.me) |
Destroying C with 20 lines of Haskell: wc(0xd34df00d.me) |
> Does the Haskell version really do the same thing as the C version?
It counts bytes, words and lines and, modulo intended Unicode space handling and unintended bugs, does the same thing.
Indeed, it does not count things like max line length or char count, but those can be plugged in without significant performance overhead (and that's what the second part is gonna be about).
> Does it handle all of the same error cases, providing the same quality of error messages if they occur?
There are no error messages at this point. Although I don't really see how this should affect performance.
> Does it handle localization?
If you mean counting multi-byte characters, then not yet. Although I'm pretty convinced it does not require doing something much more complicated — but maybe I'm wrong, we'll see in the next part.
Also, thanks for the feedback, those are important questions! Something to keep in mind when writing subsequent posts.
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 a fair comparison.
I will wait for what the next article presents, as the end of this article states:
> Stay tuned for a second part, where we will investigate shaping all this into an actual wc substitute, where different statistics can be turned on or off, all while not computing what the user hasn’t requested.
This is a fair point, and I believe this whole series of 'Beating C with foo' posts could have been better named.
But I'm of the opinion that the whole series is about showcasing various language's strengths and weaknesses, while using GNU wc as a benchmark.
From this perspective, I've learnt a bit about several languages I knew nothing about, so I rather like these articles, despite the fact that their titles might be a bit misleading.
Everyone remembers being a brash know-nothing teenager, so just by the headline "DESTROYING C" you get that vibe.
I remember having a blog about Haskell circa 2002 where I would smugly enumerate the ways in which Guido van Rossum was wrong. "GUIDO IS WRONG! PART 4" my post titles would say.
I'd be interested to see the same tests but with a non-unicode local set, IIRC:
LC_ALL=C
Anyway, destroying Haskell with 100 lines of C :-)
https://raw.githubusercontent.com/gdevic/minix1/master/comma...
https://www.ioccc.org/2019/burton/prog.c
It is the Burton entry from The International Obfuscated C Code Contest, but seems like only handling ascii
https://www.ioccc.org/years-spoiler.html
Limits:
"Requires the C locale and ASCII character set. Input should be less than ten million octets to avoid this problem."
wc:{sum (({1};ceiling 0.5*sum differ " "=;{1+count x})@\:) peach read0 x}[0]: https://old.reddit.com/r/dataisbeautiful/comments/eyevca/my_...
[1]: https://old.reddit.com/r/dataisbeautiful/comments/eyevca/my_...
Like yourself, I think any reader could understand that this is meant to be a toy implementation. The author even says so in the very first paragraph and at several points in the article thereafter. How is that dishonest?
Apples smash Oranges, etc.
$ time wc Backups/Tera2/files.txt
1123699 2283439 161361844 Backups/Tera2/files.txt
real 0m2.010s
user 0m1.964s
sys 0m0.020s
L: 1123699
W: 2283439
C: 161361844
real 0m0.864s
user 0m0.835s
sys 0m0.028s
(See my comment elsewhere[0] for a more sensible comment)
[0] https://news.ycombinator.com/item?id=22234673
--------
Update: I just compiled with -O3 and got user time of 0.24 secs. This version is 8 times faster than the system wc.
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
* Does this cope with different whitespace, such as tabs?
* Does this cope with different settings of locale?
* Does this include the option of the "longest line"?
* Does this perform the character counts?
I'm pretty sure wc does all these, and that stripping them out would make it faster. If this Haskell version doesn't do that, and yet still compares against a fully-featured version of wc, the comparison hardly seems fair.
* Looking at a single byte at a time, it presumably only handles the "C" locale :) They don't say what locale GNU wc was tested with (if it's not LANG=C, that benchmark should be re-run)
* --max-line-length? no. But I'm guessing GNU wc isn't benchmarked with that option on (can't find the invocation in the blog post though)
* data State { ws, bs, ls } keeps count of words, bytes (more honest than calling it characters) and lines.
> ... further down, they rip out the remains of unicode handling ...
Ah. Well, that makes it a little unfair, surely.
> Looking at a single byte at a time, it presumably only handles the "C" locale ...
Again.
> --max-line-length? no. But I'm guessing GNU wc isn't benchmarked with that option on
I wonder if wc does the work anyway, and only reports it if asked, or if it actually changes the code path if it's not needed.
So this entire post feels ... intellectually dishonest. personally I'm all in favour of Haskell, and I wish I had the chance to use it "in anger" rather than just doing the occasional toy thingie that I do. But this post doesn't do it or its community any favours.
Disappointing.
https://github.com/coreutils/coreutils/blob/master/src/wc.c
The word counting algorithm does seem to be much more complex.
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.
Then I'll consider C destroyed.
Like the other said, the second article will probably be more interesting.
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.
Also, I was trying to make a reverence to the original post that was "beating C", with the connotation of further improving on that. I'm not a native speaker so my language model might be terribly flawed.
I don't understand why LOC was even brought up. You can put all your code on a single line in most languages. The Github code linked even has 26 lines of Haskell which makes this even more nonsense.
"...There’s also a parallel version that relies on the monoidal structure of the problem a lot, and that one actually beats C"
coreutils wc is single-threaded, just checked.
But that post left me wondering: is it possible to do better without resorting to parallel processing?
Turns out the answer is yes.
Average time for wc on the same test file: 0.8 seconds
average time: 0.8 seconds
I've done many very arrogant things in my life, because I've been a strange guy with lack of self-esteem who doesn't have a clue how many things he doesn't know. I hope I've never been this arrogant, though.
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".
> wc implemented in Haskell (significantly faster than GNU coreutils version — oops I did it again
For reference, I'm referring to the "oops I did it again" part. It's really hard to take that comment as "honours go to GHC authors".
Also, I suggest you try running the GNU wc with unicode turned off because unicode is computationally expensive and you're deliberately disabling unicode support in your own code anyway. I appreciate you said you'd add in the edge cases that GNU does in your next blog post but disabling unicode in GNU for this benchmark would show good faith that you're at least trying to compare like for like. And if GHC still out performs then you can at least legitimately say:
> My code outperforms GNU for non-unicode strings
Which currently you cannot because your claim is based on incorrect benchmarks.
Do you think you took the most generous possible interpretation possible?
The most generous possible interpretation is to say that he's not being intentionally misleading but actually believes what he writes. I fail to see how that improves matters.
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.
Once I've wrung every last drop of performance out of wc, I can move on to the next largest limiting factor in GNU performance, 'tail' :-)
Was overly excited when I created the repo after obtaining the first results. Childish indeed, thanks for reminding, fixed.
> Also, I suggest you try running the GNU wc with unicode turned off because unicode is computationally expensive and you're deliberately disabling unicode support in your own code anyway.
I tried running wc as `LC_ALL=C wc file.txt`, and it (surprisingly for me) resulted in worse run time for wc (my default locale is ru_RU.UTF-8 for comparison). This reproduced on two machines of mine and also on a machine of a friend of mine who also gave my code a shot.
My bad for omitting this in the post, I'll update it accordingly.
> 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.
I do way more C++ (in fact, I don't do pure C at all), and aliasing has bitten me and my code performance more often than I'd like. While there are workarounds, I'd probably consider spending time and effort on them as rather unrealistic in a sense. So it surely doesn't contradict my world model if a language with a stricter type system (Haskell? Rust? ATS anyone?) achieves better results on at least some of the tasks with less effort and less dependence on implementation details.
Although ironically I'm going to write something low-level for the Haskell bytestrings library today evening, in C with intrinsics (so almost assembly modulo stuff like register allocation).
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 trivial (I didn't want to say that in the post itself though as I think it'll look like I'm belittling the guy who did the original post), while modularizing this is _fun_.
I look forward to your results.
It's easy to see that it's not the result of 10+ years of low-level optimizations to eek out the most performance.
Your test code probably hits the MB_CUR_MAX>1 path at line 361. (Check your locale setting!)
The main loop is:
402 if (!in_shift && is_basic (*p))
403 {
404 /* Handle most ASCII characters quickly, without calling
405 mbrtowc(). */
406 n = 1;
407 wide_char = *p;
408 wide = false;
409 }
...
443 switch (wide_char)
444 {
445 case '\n':
446 lines++;
447 FALLTHROUGH;
448 case '\r':
449 case '\f':
450 if (linepos > linelength)
451 linelength = linepos;
452 linepos = 0;
453 goto mb_word_separator;
454 case '\t':
455 linepos += 8 - (linepos % 8);
456 goto mb_word_separator;
457 case ' ':
458 linepos++;
459 FALLTHROUGH;
460 case '\v':
461 mb_word_separator:
462 words += in_word;
463 in_word = false;
464 break;
465 default:
466 if (wide && iswprint (wide_char))
....
480 else if (!wide && isprint (to_uchar (*p)))
481 {
482 linepos++;
483 if (isspace (to_uchar (*p)))
484 goto mb_word_separator;
485 in_word = true;
486 }
487 break;
488 }
Even in when character = byte, the main loop uses the same logic:
555 default:
556 if (isprint (to_uchar (p[-1])))
557 {
558 linepos++;
559 if (isspace (to_uchar (p[-1]))
560 || isnbspace (to_uchar (p[-1])))
561 goto word_separator;
562 in_word = true;
563 }
564 break;
565 }
"\n\r ',-./0123456789ABCDEFGHIJKLMNOPQRSTUVYZabcdefghijklmnopqrstuvwxyz"
The following should be a more difficult test set to reproduce wc's output. I create the test set with Python:
with open("testset.dat", "wb") as f:
for b1 in range(256):
for b2 in range(256):
for b3 in range(256):
_ = f.write(bytes((b1, b2, b3)))
% env LANG=en_US.UTF-8 wc testset.dat
196608 1523713 50331648 testset.dat
% env LANG=C wc testset.dat
196608 1152001 50331648 testset.datI ask because the essay and your comments until now show no insight from reading the code.
I find it difficult to understand how anyone could miss that (rather significant) part of the core algorithm, and then assert the differences are due to only "modulo intended Unicode space handling" and the like.
Until now I had assumed you had a lay understanding of wc, and had not read the code.
On a meta level, I wasn't even considering that the notion of a word might be different from "a sequence of characters that aren't space characters".
Live and learn indeed.