13 ms·
When Haskell is Faster than C
- metajack 14y agoA similar anecdote from my own experience: Chesspark had a web and a win32 native client. It kept track of your friends with a roster (the underlying stack was based on XMPP). As a way to make new users feel welcome, I and a few coworkers were added to all new user's roster (like MySpace Tom). It wasn't long before this overwhelmed our clients. Each client was written by a different developer. One was in JavaScript, and one in C. Due to some poor design choices on the C side, the JavaScript client was substantially faster. I don't remember the exact benchmarks, but I think it was close to 50x faster. The JavaScript code took less time to develop and less time to fix. The C code did eventually get fixed and outpace the JavaScript on raw speed, but if I were doing it again, I never would have made a native client to begin with.
- tedunangst 14y agoGood design choices are better than bad design choices?
- PaulAJ 14y agoMore like: good design choices are vastly more important than micro-optimisation, and Haskell is a good design choice.
- pekk 14y agoNice story. If I flatly said that JavaScript was 50x faster than C, I'd have butchered your story and some real points of interest here. Supposing your team is productive in JavaScript, but not too exceptional with C, then a similar time investment can produce significantly faster JavaScript programs. In this way, in real practice, language productivity can totally drown technical performance differences. Even when you need to optimize, optimization is also subject to productivity differences. It is probably inherently somewhat harder to reach the required level of ability in C to get the required performance, and thus to find people with this ability. Ergonomics and ease of entry don't just make people happy, they also have an impact on the performance of the average program to be written. But even if it turns out that C is at no disadvantage here - it matters more what you will be able to use well. If C makes insane things possible that you will never do, they aren't a good reason for you to use C. Moreover: following a general policy of writing JavaScript (or other favored language, within reason) is going to give you good-enough performance in a HUGE variety of problems. Even if this performance is less than C's for an important program, there are two mitigating factors: 1. The slower performance may still be easily 'good enough'. There are diminishing returns on speed improvements. More speed does not always make the software better. 2. You can get the required speed by optimizing and replacing the bits which are bottlenecking the speed-critical bits, without committing to writing the entire project at 'max speed' out of the gate, which will often be a gigantic waste of resources on speed improvements that no one will ever see. Most projects have limited applicability and limited lifespans. What matters isn't whether you are at maximum performance. What matters is whether performance is good enough for purpose.
- deleted 14y ago[deleted]
- PommeDeTerre 14y agoWhat exactly were these "poor design choices" that affected the C implementation's performance so badly?
- dakimov 14y agoIn general, JavaScript wouldn't take less time to develop and especially less time to fix than a modern C++ 11 / boost code. That's a stupid myth ("very slow C++ development times") from the guys who suck at programming.
- jlarocco 14y agoI don't think his example is helping his argument at all. He cherry picks optimizations for the Haskell, such as using Data.Vector.Unboxed instead of the regular lists and removing calls to isLetter, but then he rolls his own linked list and uses getc in the C version. He doesn't even have the correct return type for main. Haskell written by decent Haskell programmers is faster than C written by poor C programmers. Not very surprising.
- ozataman 14y agoI'm no C expert - too bad to hear that about his C code. However I can tell people here that Vector.Unboxed is a very common optimization as soon as you start thinking about performance in Haskell. Nothing "expertly" about it, really. I, for one, use it in all of my computational Haskell code.
- zura 14y agoMy impression is that, while it is possible to come up with a performance oriented Haskell code, it becomes quite ugly and diverges from those beautiful and idiomatic examples found in books. E.g. explicit strictness specifications, real quicksort (with Array.ST), etc..
- Cowen 14y agoThat's actually the problem he's hinting at near the end as he's trying to make his point about optimizing C. The optimizations he needs to make to the C code didn't seem clear to him when he was writing it, but they're very common optimizations for someone with more experience writing in C. That he made the seemingly-natural optimization in Haskell while not affording C the same luxury is what's hurting his argument.
- pekk 14y agoThe contradiction of "C is always faster than everything" (apparently shown untrue by comparison on the reverse-complement problem) is not "Haskell is faster than C".
- deleted 14y ago[deleted]
- threedaymonk 14y agoIndeed not. The useful point this article makes, I think, is that if you're a good Haskell programmer and a competent C programmer, you can produce working code in both, but you can still produce better-performing code in Haskell. Essentially, the lesson is that there's little point writing code in C for performance unless you're good at it. If you can write good-enough code in a higher-level language that you're happy with, you might already have reached an optimum.
- jacquesm 14y agoI'm in no position to judge the quality of the Haskell code (I couldn't program my way out of a wet paper bag in Haskell) but after half a lifetime of writing C for a living I can say with confidence that the C code is horribly written and horribly inefficient. It is tempting to pull the code and fix it. If you want to compare two languages make sure that you are proficient in both.
- CountSessine 14y agoI agree - if you're comparing runtime implementations. I think this is actually a useful comparison, though. I would argue it's a lot easier to become a proficient, performance-conscious programmer in python, java, or even Haskell, than C. And you're more likely to shoot yourself in the foot with C. From the point of view of someone who hasn't learned either language (maybe a scientist or engineer looking to do some simulation work), the message here is, "with the same time and effort, not only is Haskell as fast as C in many cases, but in some cases it will actually be faster than the C code that you, a beginner, can write."
- nemo1618 14y agoAs many advocates of functional programming point out, in many cases the speed of development is more valuable than the running time of the code. The great strength of Haskell and other FPs is their readability and modularity. Trying to win people over with benchmarks is the wrong approach IMO.
- PaulAJ 14y agoIts more a matter of trying to nix the "Haskell would be nice, but its too slow to be practical" line that many see as a killer.
- chc 14y agoDoes Haskell really have a reputation for being slow? In a world where Ruby is the de facto standard for startups, I wouldn't think Haskell would have anything to worry about.
- chongli 14y agoIt does. A lot of people have written ignorant blog posts whereby they show their first "real" Haskell program is extremely slow compared to their heavily optimized C version (with years of experience behind it). A cursory glance at the code, however, reveals that their Haskell program is using linked lists of linked lists of boxed arbitrary precision integers while the C version uses a 2D array of ints. Okay, perhaps that's a bit of an exaggeration but you get the idea.
- lucian1900 14y agoThe point is that it's comparable to C in speed, which is almost always good enough.
- Xcelerate 14y agoHmm... it seems to me that whenever any article is posted that claims "X is faster than C", there are immediately 40 replies saying "Well, the author's C is horrible. If I wrote that, it would be much different." Okay, as someone who has NOT been programming in C 8 hours a day for years on end, I would actually like to see somebody do this -- to show me what GOOD C looks like. So if someone wouldn't mind, could you take his C code and show me the improved version? This would really help me understand. (And I don't just mean an example where one line could be improved; I'm talking abou the whole thing.)
- jacquesm 14y agoOk, I pledge to re-write this properly and to benchmark the current implementation vs a nice one. I'll post the results. I need something to get my mind off things and this is as good as any. It will take at least until Monday (it is my sons birthday tomorrow).
- decad 14y agoLooking forward to seeing your results from this.
- zxcdw 14y agoSubscribing to this.
- michaelkscott 14y agoSeconded. How are you going to be posting it?
- zxcdw 14y agoAs always talking about performance differences and optimization without thoroughly profiling and pointing out bottlenecks should be frowned upon big time. I would really love to see the generated assembly code and see what makes the difference in performance. Anyone up to analyzing?
- taylodl 14y agoThe paragraph beginning with "To put it another way, C is no longer close to the real machine" really drove the point home. The further C gets away from the real machine then the less useful C will become. Higher-level languages have the advantage that a compiler can more easily determine what the program is attempting to accomplish and optimize the result for a specified architecture. This will be very difficult to do for C. As a result I would expect the performance of higher-level languages to start exceeding the performance of C. I guess we're just going to have to change our conventional wisdom when that time comes.
- ajg1977 14y agoWell that point is complete nonsense so you should undrive it. Just because a piece of code incurs hardware related performance issues does not mean it's "no longer close to the real machine". Cache misses? Reorder your data, or start inserting prefetch statements. Mispredicted branches? Issue a hint, or structure your code better. Both of these are profile-guided optimizations. It's very difficult for compilers to optimize for access patterns that will only become clear in the context of execution, and often depend on your target spec machine.
- graue 14y agoBut a JIT can perform such optimizations. Which doesn't help Haskell, but may help JavaScript or Lua beat C in some cases.
- DannoHung 14y agoThe program in question copies data from stdin, does the barest minimum of preprocessing, statically remaps all characters, and writes to stdout... Why on earth is this a demonstration of what Haskell can do effectively? There's no room to exploit anything interesting about type level reasoning.
- raphaelj 14y agoI want to point something nobody ever talk about : Efficient data containers. For instance, Haskell and C++ come in standard with a lot of these (maps, sets, various linked lists, ...) whereas the C standard doesn't come with anything like this. Moreover, type parameters and templates from these languages make usage of such structures easier and safer. I've seen some C codes where programmers has used sub-effective containers to answer the problem (like arrays or simple linked lists) as they were lazy to use a non-standardized or to implement a faster but also more complex container. In C++ or Haskell, these efficient structures come for free. Also, we can say the same for algorithms and concurrency. Haskell awesome safety and expressiveness made it really easy for me to implement such complex yet efficient systems. These two features of high level languages tend to build ofter faster programs in those languages.
- Snoptic 14y agoHaskell maps, being persistent, aren't anywhere close to efficient for mutable maps.
- haberman 14y agoThese "faster than C" claims are almost always embarrassing (usually involving C code that would easily win if it were as aggressively optimized as the high-level language) but that's almost not the point. The real point is the larger narrative. The subtext of these posts is what we are really arguing about. So let's just duke that out directly. High-level language fans have a point, which is that high-level languages are sometimes an better overall "bang for the buck" in developer time, and that sometimes they can be pretty fast (possibly even out-performing an un-optimized C program). Reasonable C guys aren't arguing against this. We're certainly not arguing that people should use C for everything. But here's what high-level language fans have to understand. First of all, you depend on us. Your language runtime is (very likely) implemented in our language (possibly with a little assembly thrown in). So as much as you may like your language, it certainly does not obsolete C. C guys like me get cranky when high-level language fans imply that it does. Second of all, a C+ASM approach will always win eventually, given enough time invested. That is because a C+ASM programmer has at his/her disposal literally every possible optimization technique that is implementable on that CPU, with no language-imposed overhead. What this means is that a higher-level language being "faster than C" is just a local maximum; the global maximum is that C is faster. Yes, it's absolutely true that in limited development timeframes a higher-level language might still be the right choice, and in rare cases might even have better performance. But for long-term projects that want the absolute best performance, C (or C++) are still the only choice. (But maybe Rust someday).
- raverbashing 14y ago"Second of all, a C+ASM approach will always win eventually, given enough time invested. That is because a C+ASM programmer has at his/her disposal literally every possible optimization technique that is implementable on that CPU, with no language-imposed overhead. What this means is that a higher-level language being "faster than C" is just a local maximum; the global maximum is that C is faster." Exactly The C program presented is very naive. getc? ungetc? malloc inside a loop? For example, I can create a table to convert 4 characters at once instead of only one. Just as a start. Doable in haskell sure, but it would most likely not use the resources of modern processors (SSE2, AVX, etc)
- 14y ago
- confluence 14y agoI want an article that says "Why it doesn't matter what's faster than what - just ship product people use". I code everything I create using the language that gives me the least amount of friction between me and the working product. On Android that's Java/C/C++, for my servers it's Python/Ruby/Java/C++/C (everything is service oriented consumable APIs), for the browser it's Javascript. Any time I want something faster - I recode and bind it in C/C++ if at all possible. I feel like a lot of these language comparison posts are just a massive pissing contest. All that matters is that people use the thing that you made. Billions of lines of code have been written in the past. Make sure your code isn't part of the billion that nobody cares about.
- chj 14y agoAnother monthly claim of XXX is faster than C. Please improve your C experience first.
- TheNewAndy 14y agoBefore you go and rewrite everything in Haskell for speed, it might be worth trying to reproduce the results from here. I tried to and C was much faster than Haskell: http://paulspontifications.blogspot.com.au/2013/01/when-haskell-is-faster-than-c.html?showComment=1358558313945#c3252681956440975671 http://paulspontifications.blogspot.com.au/2013/01/when-hask...
- vilhelm_s 14y agoWhen I try it, the Haskell version is faster (1.3s versus 2.6s on a 98MB input file). GHC 7.0.4 with -O3, GCC 4.6.2 with -O3. Not sure why these results are different...
- martinced 14y agoI've got an honest question: it's not sarcasm... How do you write fast multithreaded C-code? The article mentions that the C code is too disconnected from the real hardware which, in this case, has multiple cores. Do you need to call (non portable?) code setting mutexes manually? (not that it would be a problem) How do you use the CPU's underlying CAS operation? (by inline assembly?) As an example: the guys who wrote the very fast LMAX disruptor pattern in Java relied on the fact that Java does provide methods inside the AtomicXXX classes calling CAS operations under the hood. But sadly they couldn't "pick" the one operation they'd like, which would have been faster than the one Java decided to use (it's a RFE if I recall correctly: they'd like Oracle to modify Java so that it uses the faster version when it makes sense). I take it that in C you can inline assembly and do as you want!?
- Yttrill 14y agoI'm afraid the argument that C+ASM is always faster is flawed in reality. Pure ASM, with a bit of C thrown in, maybe, but this is just as impractical for complex codes as C itself is. It is well known that for numerical codes Fortran beats the pants off C. Why is this? Because the structure of C programs proves difficult to optimise automatically. Indeed the C committee attempted to address one of the main problems by introducing the restrict keyword (the problem of course is aliasing). For complex codes, ASM isn't an option. For large functions, high levels of optimisation aren't an option for C because C compilers are incapable of optimisation in a reasonable time frame: I have short code that cannot be compiled in less than 2 minutes on either gcc or clang. Full alias analysis requires data flow which is cubic order on function size and C compilers are incapable of partitioning functions to keep the cost down. Furthermore, C has an weak set of control operations and an object model which is generally inappropriate for modern software. K&R C compilers were hopeless because of the ABI required the caller push and pop arguments to support varargs, preventing tail rec optimisation of C function calls. Subroutine calling is useful, but it is not the only control structure. Continuation passing, control exchange, and other fundamentals are missing from C. These things can always be emulated by turning your program into one large function, but then, it isn't C and it cannot be compiled because the best C compilers available cannot optimise large functions. Similarly, complex data structures which involve general graph shapes require garbage collection for memory management. With C that's not built in so you have no choice but to roll your own (there is no other way to manage a graph). It's clear that modern copying collectors will beat the pants of C in this case. C++ pushes the boundaries. It can trash C easily because it has more powerful constructions. It had real inlining before C, and whole program compilation via templates. It is high enough level for lazy evaluators to perform high level optimisations (expression templates) C programmers could never dream of. And C++ virtual dispatch is bound to be more effective than roll your own OO in C, once the program gets complex because the C programmer will never get it right: the type system is too weak. Many other languages generate C and have an FFI, some, like Felix, go much further and allow embedding. Indeed, any C++ program you care to write is a Felix program by embedding, so Felix is necessarily faster than C by the OP's argument: C++ is Felix's assembler. As the compiler writer I have to tell you that the restriction to the weak C/C++ object model is a serious constraint. I really wish I could generate machine code to get around the C language. Its slow. Its hard to express useful control structures in. It tends to generate bad code. With separate compilation bad performance is assured. I am sorry but the OP is just plain wrong. C is not assured to be faster, on the contrary, its probably the worst language you could dream up in terms of performance. The evidence is in the C compilers themselves. They're usually written in C, and they're incapable of generating reasonable code in many cases and impossible to improve because C is such a poor language that all the brain power of hundreds of contributors cannot do it. Compare with the Ocaml compiler, written in Ocaml, which is lightning fast and generates reasonable code, all the time: not as fast as C for micro-benchmarks but don't even think about solving complex graph problems in C, the Ocaml GC (written in C), will easily trash a home brew collection algorithm. Compare with ATS(2) compiler, written in Ocaml(ATS), which by using dependent typing eliminates the need for run time checks that plague C programs given the great difficulty reasoning about the correctness of C codes. AST generates C, but you would never be able to hand write that same C and also be confident your code was correct. Compare with Felix, compiler written in Ocaml, which generates C++, can do very high level optimisations, which can embed C++ in a more flexible way than a mere FFI, and which provides some novel control structures (fibres, generators) which you'd never get right hand coding in C. The bottom line is that OP's claim is valid only in a limited context. C is good for small functions where correctness is relatively easy to verify manually and optimisation is easy to do automatically, and any decent C code generating compiler for a high level language will probably generate C code with comparable performance. So the converse of the argument is true: good high level languages will trash C in all contexts other than micro tests where they will do roughly the same.
- pretoriusB 14y ago>Conventional wisdom says that no programming language is faster than C, and all higher level languages (such as Haskell) are doomed to be much slower because of their distance from the real machine. No: conventional wisdom just says that no higher level programming language is consistently faster than C AND/OR better to reason about with regards to memory consumption and runtime behaviour. (Conventional wisdom also adds fortran, forth, Ada and C++ in the same "speedy" category). Conventional wisdom adds that micro-benchmarks of some BS outlier examples (Java where the JIT can take advantage of some known condition to do something clever, etc) do not matter in real life programs, which are far more complex. Conventional wisdom also adds that C to be speedier it doesn't even have to be highly optimized or carefully crafted by some C programming wizard or anything. Merely avoiding gross mistakes (like using an algorithm of the wrong complexity for the job) will do. Conventional wisdom concludes that writing in your high level language in an unconventional (non idiomatic) way to get to "as fast a C" speeds is bullshit too, because it doesn't represent idiomatic (and far more common) high level language use.
- dakimov 14y ago1) There is the C++ language. Will you ever remember it? Stop comparing everything to C — it is an oversimplified outdated language with specific uses for low-level system programming where you don't need complex data structures or high-level application logic. 2) If you summarize all the benchmarks comparing C to other languages, it turns out that the C language is one of the slowest. Of course, that's hardly the case. It's just the dudes who did the benchmarks suck in C/C++ and suck in programming in general. 3) Haskell makes you 10 times more productive without microoptimizing? ORLY? Try doing some big enough data manipulation with C++ 11 & boost vs Haskell. In C++ you're done with the task as long as you get decent performance with the simplest naive very high-level code, whereas in Haskell you're in the beginning of your optimization journey as the simplest code is not good enough, and after optimization you end up with much more complex, cluttered and hard to understand code than in C++ and its performance is still comparable to the naive C++ version if you're lucky.
- sampo 14y ago> The winningest programs are always written in highly optimised C Actually, for example looking at the winningest programs for x64 single core (http://benchmarksgame.alioth.debian.org/ http://benchmarksgame.alioth.debian.org/): Ada: 1, C: 5, C++: 2, Fortran: 1, Haskell: 1, Java: 2, Javascript: 1 So plain C is only winningest in 5/12 = 38%, and C/C++ in 7/13 = 54%.
- deleted 14y ago[deleted]