33 ms·
Beating Decades of Optimized C with 80 Lines of Haskell
- olliej 7y agoDuplicate of https://news.ycombinator.com/item?id=21261004 https://news.ycombinator.com/item?id=21261004
- _bxg1 7y agoVery interesting, and a simple enough use-case that a Haskell novice can get the gist of it. It's very informative of how real Haskell development works; it's a brass-tacks kind of example which you don't necessarily see a lot of in the Haskell world.
- djmips 7y agoIs this code that they are beating actually 'hand-optimized C'? Because the C code at a glance I didn't get that impression.
- deleted 7y ago[deleted]
- jdc 7y agoWhere would your hand-optimized C differ?
- rini17 7y agoFor a start, getc() isn't a simple macro accessing read buffer anymore, but a function which always acquires/releases a lock (even in single-threaded program). Changing it into getc_unlocked() usually makes big difference. http://man7.org/linux/man-pages/man3/unlocked_stdio.3.html http://man7.org/linux/man-pages/man3/unlocked_stdio.3.html
- bonzini 7y agoThe linked code uses read(), not getc().
- yxhuvud 7y agoYes, the C is much too readable. Also I wonder how fresh it is - the Macs have been known to run some really old versions of GPL tools due to license issues with newer versions.
- saagarjha 7y ago2008, and I'll have you know that it's Copyright (c) 1980, 1987, 1991, 1993 The Regents of the University of California. All rights reserved.
- verisimilitudes 7y agoThis is interesting and also unsurprising. Haskell is an abstract and high-level language and so doesn't dictate irrelevant machine details as C does. The only reason C's considered efficient at all is due to what was effectively a meme from forty years ago; there have been lifetimes of human effort wasted making C fast, only to trivially be beaten by someone using better tools. A proper analogy would be beating the world's faste runner in a mile-long dash by using a bicycle or perhaps using a cart being more efficient than carrying items on one's head; the main difference is people haven't been deluded to think that humans are faster or better at carrying cargo than a creation of mankind.
- Sysreq1 7y agoThrowing multiple cores at the problem is not what I would call beating decades of optimized C. The author only utilizes multiple cores when he realizes the overhead of Haskell will not allow him to actually win. Author even admits the C program was more efficient. You can multi thread a C program as well, at which point it would retake the title.
- bonzini 7y agoAlso, when counting words the C code is actually handling multibyte sequences, which is one of the biggest sources of improvement for the Haskell code (8s to 3.5s). Having to use a syntax extension explicitly to forgo laziness feels like cheating to me... But then I have never used Haskell so perhaps that's actually normal.
- unhammer 7y agoIf you're talking about BANGPATTERNS, that is completely normal in Haskell. Pretty much any non-trivial Haskell program (and many trivial ones too) will have !'s in various places to force something to be strict, and to use the ! syntax you do need to add a pragma. Those pragmas are what let Haskell evolve new features without breaking backward compatibility, so Haskell programs tend to have a lot of them. Perhaps one day we'll have a new standard (it's been 19 years since the last one) which will include some of the pragmas by default. In the meanwhile, it's possible to turn the common ones on project-wide and just forget about them.
- tome 7y ago
- loosetypes 7y agoReminded me of the following paper, Using Coq to Write Fast and Correct Haskell. https://www.cs.purdue.edu/homes/bendy/Fiat/FiatByteString.html https://www.cs.purdue.edu/homes/bendy/Fiat/FiatByteString.ht...
- Matthias247 7y agoTo be fair for the C version: The linked code [1] doesn't really look like "decades of optimized C" to me. More like a straightforward implementation of this, which had been likely had not seen many updates for decades. It could probably gain performance by playing around with input buffer sizes and trying to make use of vectorized instructions (the compiler might try to auto-vectorize the lops, but there is no guarantee). [1] https://opensource.apple.com/source/text_cmds/text_cmds-68/wc/wc.c.auto.html https://opensource.apple.com/source/text_cmds/text_cmds-68/w...
- saagarjha 7y ago> the compiler might try to auto-vectorize the lops It does on my computer! The wc binary on my machine has movaps instructions.
- abainbridge 7y agoExactly this. I see this as "Simplest possible C code beats carefully hand optimized Haskell".
- test9753 7y agoBeating Decades of Optimized C with 27 Lines of Ocaml: type t = { mutable words: int; mutable chars: int; mutable lines: int; mutable in_word: bool ; mutable finished: bool};; let () = match Core.Sys.argv with | [| prog_name |] -> Core.Printf.eprintf "Usage: %s file1 file2 ...\n" prog_name | _ -> ( let args = Core.Array.slice Core.Sys.argv 1 @@ Core.Array.length Core.Sys.argv in let buf_size = 65536 in (* 64 KB -> Caml IO buffer size *) let buf = Core.Bytes.create buf_size in Core.Array.fold args ~init:() ~f:(fun _ file -> Core.In_channel.with_file file ~f:(fun in_ch -> let c = { words = 0; chars = 0; lines = 0; in_word = false; finished = false } in let set_words () = if c.in_word then c.words <- c.words + 1 in while not c.finished do let len = Core.In_channel.input in_ch ~buf ~pos:0 ~len:buf_size |> Core.Int.to_int in if len > 0 then ( for i = 0 to (len - 1) do match (Core.Caml.Bytes.get buf i) with | ' ' | '\t' | '\r' -> (c.chars <- c.chars + 1; set_words (); c.in_word <- false) | '\n' -> (c.chars <- c.chars + 1; set_words (); c.in_word <- false; c.lines <- c.lines + 1) | _ -> (c.chars <- c.chars + 1; c.in_word <- true) done ) else ( c.finished <- true ) done; set_words (); Core.Printf.printf "%s -> lines: %d, words: %d, characters: %d\n" file c.lines c.words c.chars))) ;; Testing: $ ls -lh test_file.txt -rw-r--r-- 1 user group 508M Oct 16 12:01 test_file.txt $ time wc test_file.txt 4863460 54621760 532480000 test_file.txt real 0m3.368s user 0m3.137s sys 0m0.195s #Ocaml version: $ time ./wcl.native test_file.txt test_file.txt -> lines: 4863460, words: 54621760, characters: 532480000 real 0m2.480s user 0m2.345s sys 0m0.123s
- geocar 7y agoOh this is fun! Beating Decades of Optimised C (best of three) $ time wc w.txt 3156098 6312196 380648004 w.txt real 0m1.358s user 0m1.277s sys 0m0.066s ... with one line of q (best of three): q)\t g:{(sum[1<deltas where x]+sum[not x:max x],0),sum max x 0 1}0x0d0a2009=\:read1 `:w.txt 783 q)g 380648004i 6312196 3156098i 783msec: almost twice as fast!
- gmfawcett 7y ago
- saagarjha 7y agoHere is some more up-to-date source, though it still hasn't been updated since 2008: https://opensource.apple.com/source/text_cmds/text_cmds-99/wc/wc.c.auto.html https://opensource.apple.com/source/text_cmds/text_cmds-99/w...
- peteretep 7y ago> We're still orders of magnitude away from wc unfortunately Just a reminder that “orders of magnitude” means something specific, rather than “quite a bit”, and 3 is not “orders of magnitude” more than 0.3, and neither is 5.48 “orders of magnitude” more than 1.86
- sclangdon 7y agoActually, 3 is two orders of magnitude (or just 1 depending on whether you count 1 as an order of magnitude or not) more than 0.3 0.3 = 3 * 10^-1, which is -1 order of magnitude 3 = 0.3 * 10^1, which is 1 order of magnitude You are right that 5.48 is not an order of magnitude more than 1.86, however. They are the same order of magnitude.
- Noe2097 7y agoWhat a clickbait indeed. The end version is still eating 3 times more memory, but the worst is that it just doesn't work in the general case. The way I generally use "wc" is inside a somewhat complex command line, with commands preceding it. As in "feeding characters" to it. There is a reason why "wc" is not multithreaded: it just can't. It must work sequentially, because in the general case the input of "wc" cannot be skipped over. This is one of the two big assumptions that are made by the author ("wc works only for files, so we can lseek") -- the second, identified by the author, being that the underlying hardware and filesystem must support concurrent access to the same location efficiently.
- nightcracker 7y ago> There is a reason why "wc" is not multithreaded: it just can't. It must work sequentially, because in the general case the input of "wc" cannot be skipped over. Eh what? Word counting is embarrassingly parallel, at least for files. You start up k threads each working on its own chunk of the file, assuming that there is a word boundary at the start of its chunk. Then you sum up the total word count but inspect whether the chunk boundaries actually were word boundaries, and subtract 1 each time this was violated.
- taneq 7y agoThe sentence before your quote explains why that's not always an option. (Of course wc could switch to a multithreaded algorithm while working on files, but the point did make sense.)
- Noe2097 7y ago> work counting is embarrassingly parallel, at least for files. True; and "wc" works not just on files. "wc" also works on character devices, on streams of data that cannot be randomly accessed.
- heinrich5991 7y agoI think your parent meant that you can't do that if you get your data from a pipe. You can't `lseek` on a pipe.
- Smithalicious 7y ago> Basically we need to count the number of times a given invariant has changed from the start to the end of a sequence. I can say with confidence that the invariant will change exactly 0 times. No clue what the author is trying to say here.
- Someone 7y ago>>> foldMap countChar "one two\nthree" Counts {charCount = 13, wordCount = Flux NotSpace 3 NotSpace, lineCount = 1}”* That lineCount = 1 surprised me, but testing on a Mac showed it to be ‘correct’. At least there, you can have a non-empty file that has zero lines.
- boomlinde 7y agoIn POSIX, a text file is a file consisting of zero or more lines. A line is a sequence of non-null characters, shorter than a system defined maximum and terminated by a line feed character. So a file that completely matches the string "one two\nthree" is by POSIX standards not a text file. Of course, wc doesn't necessarily operate on text files so you could interpret the result as a "complete POSIX line count".
- z92 7y agoTitle should be "Beating Decades of Optimized Single Threaded* C with 80 Lines of Multi Threaded Haskell" That's not what I expected to read.
- jonny383 7y agoSerious question: Is it remotely possible for someone to write an article about Haskell without _completely_ jerking off over how "good" Haskell is? Edit: Case in point, the first photo on authors Twitter shows a Macbook with the Haskell logo as the background https://twitter.com/chrislpenner/status/1182787759582277632/photo/1 https://twitter.com/chrislpenner/status/1182787759582277632/...
- tinco 7y agoWhy wouldn't they? It's a very good programming language that's underrepresented in the market. I don't get why people get so upset over language evangelists. Is it that you already know the languages they advertise are good, or that you don't want to know?
- FpUser 7y ago"Is it that you already know the languages they advertise are good, or that you don't want to know?" How about do not care option. There are many decent languages to choose from, some general, some targeting particular areas. They're just tools.
- ncmncm 7y agoIt's that, by their own demonstration, the language is nowhere near as good as they say it is. What does "underrepresented" even mean, in this context? It is not used much because it is a PITA to get tolerable performance, where the C code -- and, moreso, the C++ code -- written in the most naive way is near optimal. I am not going to bother demonstrating the parallel C++ version, but you already know it will be only a little longer than the naive one, and quite a lot faster than the Haskell one.
- tinco 7y agoYou're right and Haskell doesn't really deserve more representation. I've built a couple of small web services, a network protocol and a compiler in Haskell, and for those cases it was super suitable, god forbid I'd have to do those things in C++. But definitely, there's a whole bunch of programming languages that would have been as suitable or better for those (except the compiler, Haskell really is the perfect compiler language). I meant underrepresentation more generally, I appreciated Ruby evangelism back in 2006, when adopting Ruby really improved the lives of web developers. And I appreciate Rust evangelism now, because it improves the lives of zero overhead developers. At some point those languages could be at their "optimal" representation though. And not all representation is fair, I still thing it's insane that people are advocating Rust for web development, but I also think it's insane to use Javascript for backend web development, and here we are with half the industry mired in shit.
- UweSchmidt 7y agoIn general terms, how is it possible to beat really optimized C code? In particular, what property of Haskell or any other functional language would make that possible (in theory or practice).
- hoseja 7y agoHere, it's apparently FEARLESS CONCURRENCY
- ummonk 7y agoThe C code is not particularly optimized, but more importantly, C being a low level language makes writing multi-threaded programs much more work. wc though cannot make use of multi-threading regardless because it must have the ability to work on streams, not just seekable files, as the haskell code here does.
- Annatar 7y agoC is a high level language with capability of low level access: we regularly made fun of C programmers in high school (like my math teacher) because they didn't know how to code in assembler and had to write abstract high level code in C, in order for the compiler to do it for them. The biggest brouhaha was always disassembly of "optimized" machine code generated by the C compiler, full of needless stack twiddling and housekeeping code, wasting hundreds or even thousands of CPU cycles on what amounts to useless abstractions. That's nonsense one finds only in a high level language. But it's always super for a good brouhaha!
- ummonk 7y agoWe've long since moved on from an era when anything above assembly could be considered high level. And the performance difference between idiomatic C code compiled with -O3 (to inline functions and minimize the stack twiddling and housekeeping code) and handwritten straightforward assembly is low enough as to be negligible. Not so with, say, Haskell vs C.
- cosarara 7y agoLast week he had "Learning Haskell is no harder than learning any other programming language"[1]. This week we have: > The program takes more than a few minutes and quickly spikes up to more than 3 GB of memory! What's gone wrong? Well, we used the strict version of foldl (indicated by the trailing tick '); BUT it's only strict up to "Weak Head Normal Form" (WHNF), which means it'll be strict in the structure of the tuple accumulator, but not the actual values! As easy as any other programming language! [1] https://news.ycombinator.com/item?id=21170547 https://news.ycombinator.com/item?id=21170547
- abhir00p 7y agoI believe in the cited article the author was simply pointing out to the fact that it is easy to learn the syntax and basic semantics of the language. It is extremely hard to write high performance Haskell, same as it is hard to write high performance C. And additionally I think it is foolish to claim that "Haskell is no harder to learn than any languages". Definitely there are certain misconceptions (like you need to know category theory to learn Haskell) which needs to be debunked, but it is quite difficult to grasp the evaluation semantics of Haskell and pretending that it is easy and natural will simply shove more users away from the language.
- philzook 7y agoHuge Haskell fanboy here. True high performance, fair enough that's hard everywhere. I think it is unlikely a novice C programmer would accidentally balloon their memory like this. The simplest Haskell program that a novice might write has abysmal performance. I think it is easier to write clear, succinct code in Haskell and easier to write decently fast code in C. Neither is impossible in either.
- skocznymroczny 7y agoA monad is just a monoid in the category of endofunctors, what's the problem?
- erichocean 7y ago
- zelly 7y agoEvery ”X new thing I made on a weekend is faster than Y old thing” is inevitably a half-implemented version of the old thing. Of course doing less instructions is going to be faster. You could also make a benchmark-winning web server that just write()s to a socket, skipping all sanitization and error handling.
- zmix 7y agoHasn't Pandoc[1] been written in Haskell? The only real slowdown I experience with it is startup time. > If you need to convert files from one markup format into another, pandoc is your swiss-army knife. So, Pandoc does a lot of text processing. [1] https://pandoc.org/ https://pandoc.org/
- atemerev 7y agoSo, if you can write research-level stuff, invent some new category-theoretical structures that warrant a scientific paper, know the exact language extension to enable from the multitude of exotic optimizations available in GHC, than yes, that’s perfectly simple and accessible to everyone!
- chii 7y agoIt's an unfair comparison - monads are relatively well known concept, and compiler options and libraries are just as baffling in C as it is in GHC. In all respects, the only "esotetic" thing is the WHNF (which, if you worked with haskell for any while, is quite understandable).
- atemerev 7y agoFlux monoids? You have to invent the new subclass of traversing monoids to achieve somewhat comparable performance to imperative code?
- chii 7y agoit is merely a monoid with some special property (which, is a logical property of concurrently counting words - "count the number of times a given invariant has changed from the start to the end of a sequence"). he wrote the monoid directly, rather than import the library - and it's a rather unimportant small detail. He didn't invent a new research topic that nobody has seen before. You would've implicitly done this same thing if you wrote a map/reduce algorithm to count words across different machines.
- dig1 7y agoI find funny this "beating C with X" attempts and articles, popular since the dawn of computing. Although all of them are trying hard to be a little bit faster (and shorter) than C code, this is usually the price they have to pay: 1. Abysmal compilation time. 2. Huge binaries. Sure, C static binaries aren't small, but much smaller than equivalent Go programs. 3. Complex language. C is still simple language (sans edgy cases). No need to dive into type theory, learn about functors and so on just to write something. 4. Complex implementations (compilers, garbage collectors...). Not something you can hack over the weekend. 5. Complex distribution. C natural environment is Unix/Linux and libc/glibc is always there. Everything else requires additional (usually tons of) libraries or static linking. 6. Language instability. Because of 3), these languages are always evolving. You can read and compile C code 20-30 years ago and I'm expecting the same for the next, at least, 10 years.
- Cieplak 7y agoWriting Haskell is almost trivial in practice. You just start with the magic fifty line {-# LANGUAGE ... #-} incantation to fast-forward to 2017, then add 150 libraries that you’ve blessed by trial and error to your cabal file, and then just write down a single type signature whose inhabitant is Refl to your program. In fact if your program is longer than your import list you’re clearly doing Haskell all wrong. Stephen Diehl — Reflecting on Haskell in 2017
- axilmar 7y agoProgram running with multiple threads beats program running without multiple threads. News at 11.
- maccard 7y agoAs a few have posted, this isn't decades of optimised C vs 80 lines of Haskell, this is basic C vs basic Haskell, and C is orders of magnitude faster. The entire source for wc is here [0], and is 900 lines of very readable C, it does more than count words, includes options, arguments, usage, licenses. WHen I strip everything back, it's only about 300 lines of very readable C. [0] https://github.com/coreutils/coreutils/blob/master/src/wc.c https://github.com/coreutils/coreutils/blob/master/src/wc.c
- tom_mellior 7y agoI grabbed the source linked from the article, made it run on Linux, compiled it with gcc -O3, and it beats my system's wc by a factor of almost 2x. C is faster than C! System wc, fastest of 5 runs: 59180000 213180000 1407437834 wc_input 11.53user 0.19system 0:11.74elapsed 99%CPU (0avgtext+0avgdata 2428maxresident)k 0inputs+0outputs (0major+102minor)pagefaults 0swaps Manually compiled wc, fastest of 5 runs: 59180000 213180000 1407437834 wc_input 6.08user 0.20system 0:06.29elapsed 99%CPU (0avgtext+0avgdata 2180maxresident)k 0inputs+0outputs (0major+92minor)pagefaults 0swaps This is on Ubuntu 18.04 on x86_64. If the author's wc also came precompiled (which it seems to be), they cannot make any valid comparison at all. If manually compiling on their machine with maximum optimization would also get them a 2x speedup, their fancy multicore Haskell would still be slower than C... and that's fine.
- sergeyz_prg 7y agoThe author compares a multi-core application performance to a single-core one . Is it fair?