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

When Haskell is Faster than C

paulspontifications.blogspot.com

Post reply on HN
Print view View original

41–50 of 119 posts

Re: When Haskell is Faster than C

#41

Post by haberman »

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

Re: When Haskell is Faster than C

#42

Post by cube13 »

taylodl wrote: post #24

The 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…

None of the problems he cites are issues with his code, though, nor are they as much of an issue with modern processors. Unless I'm missing something, the presentation he cites are running on the Cell processor, not a modern x86 system.

RAM cache misses are pretty bad, but with the blocks that he's dealing with, he's looking at maybe 1 miss per block, and that's assuming that the processor is letting the blocks get entirely out of the 3 levels of cache to RAM.

The compliment array should stay in memory 100% of the time because it's tiny and referenced constantly, and the individual arrays shouldn't be that bad. He's not branching all that much, so unless the while and for loops are triggering after 1 or 2 characters, it's unlikely that's the issue.

The actual problem he's more likely running into is the OS rescheduling the thread to a different core, which is a gigantic hit.

Re: When Haskell is Faster than C

#43

Post by raverbashing »

haberman wrote: post #41

These "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 language…

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

Re: When Haskell is Faster than C

#44

Post by shrughes »

cube13 wrote: post #37
Cowen wrote: post #15

Earlier quoted context omitted.

That'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…

"Haskell is easier to optimize than C" != "Haskell is faster than C".

Are you writing that in Haskell or in C? Because in Haskell, you'd want to use the /= operator. In C, you'd want to use strcmp.

Re: When Haskell is Faster than C

#45

Post by iheartc »

haberman wrote: post #41

These "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 language…

Thank you.

Re: When Haskell is Faster than C

#46

Post by dllthomas »

cube13 wrote: post #37
Cowen wrote: post #15

Earlier quoted context omitted.

That'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…

"Haskell is easier to optimize than C" != "Haskell is faster than C".

If Haskell is easier to optimize than C, then it could easily be that there's some amount of programmer effort, for which expending that much effort in Haskell yields a faster program than expending that much effort in C. If that amount of effort is in the range of effort most people are able to expend on a class of projects, then Haskell is faster than C for those projects. It may even be that those are most projects.

It is, of course, not the case that Haskell is faster than C with arbitrary effort expended tuning to the specific hardware - no one is claiming that.

Re: When Haskell is Faster than C

#47

Post by dllthomas »

cube13 wrote: post #39
gnuvince wrote: post #30

Earlier quoted context omitted.

From what I understood from his post, using a buffered input function would a) make the code differ from the specification, b) require more refactoring than the Haskell code needed. b) seems particularly important when the program is not <100LOC, but tens or hundreds of lines of code.

The problem is that his implementation is essentially a test of how he's using libc versus how Haskell is using it. The pointer arithmetic he's using shouldn't need to be optimized, since the page sizes he's malloc'ing and pulling from memory are small enough that they should stay in the L1/L2 cache for the entire run(he's using 1k blocks of data, most processors use 4k pages). There's almost no optimization to be do…

It's not about system calls, it's about locks. The getc function is buffered (by default) - that's what's going on behind the scenes in that FILE structure. What is slow about calling getc over and over is synchronization around that FILE object (hence the existence of functions getc_unlocked, &c).

Re: When Haskell is Faster than C

#48

Post by michaelkscott »

jacquesm wrote: post #20
Xcelerate wrote: post #17

Hmm... 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 t…

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

Seconded. How are you going to be posting it?

Re: When Haskell is Faster than C

#49

Post by ChuckMcM »

haberman wrote: post #41

These "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 language…

I wish I could up vote this 10x. When folks were saying "Oh with HotSpotUltimateOptoMix III Java is going to be faster than C code!" or whatever the optimizer de-jour was I would sigh. We have very much reached a stage where there are computers which can dedicate way more cycles to your effort than you need to get it done in time, we can spend this "surplus" on making writing code easier, and that is a huge win. Enjoy it. Don't worry that someone could craft it in C+Asm and give the idle loop more cycles to play with, it doesn't need them.

Re: When Haskell is Faster than C

#50

Post by jacquesm »

michaelkscott wrote: post #48
jacquesm wrote: post #20

Earlier quoted context omitted.

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

Seconded. How are you going to be posting it?

Blog entry, already working on it. It's fun.
Post reply on HN