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

31–40 of 119 posts

Re: When Haskell is Faster than C

#31

Post by ajg1977 »

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…

Well 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.

Re: When Haskell is Faster than C

#32

Post by raphaelj »

I 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.

Re: When Haskell is Faster than C

#33

Post by graue »

ajg1977 wrote: post #31
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…

Well 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 o…

But a JIT can perform such optimizations. Which doesn't help Haskell, but may help JavaScript or Lua beat C in some cases.

Re: When Haskell is Faster than C

#34

Post by jacquesm »

alayne wrote: post #29
jlarocco wrote: post #19

Earlier quoted context omitted.

Fair enough. My complaint is that the C code isn't given the same chance. He even calls out that reading data with getc is a known performance problem, but then does it anyway. Any book on learning C will point out that getc is slow for reading lots of data, and fscanf or fread should be used instead.

I would never encourage use of the f* I/O functions from the standard C library for high performance code. They're all buffered which means there's an extra copy happening. You should use read and other POSIX I/O functions instead.

This is not 100% true.

f* calls are buffered this is true. But depending on your workload this may be a blessing in disguise because if you're parsing a very long stream of unstructured data you'll have to re-implement most of that buffering logic in your own code to deal with the inevitable corner cases where your data overlaps the borders of the buffersize chosen. The obvious optimization here is to pre-allocate a buffer of the right size and read in the data in one go but for a stream of unknown and possibly infinite length (such as used in a filter like this) that is not possible.

So f* function have their place, even in optimized code, but should be used with care. If you're reading data with fixed size blocks (such as in this example) then yes, a simple 'read' call will likely be faster, because as you note the read call will place the data directly into a user accessible buffer without the need to go through more library calls to get at the data. (fread is a wrapper function around the read system call).

Re: When Haskell is Faster than C

#35

Post by chc »

PaulAJ wrote: post #13
nemo1618 wrote: post #11

As 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.

Its 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.

Does 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.

Re: When Haskell is Faster than C

#36

Post by papsosouid »

jlarocco wrote: post #3

I 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. N…

>He cherry picks optimizations for the Haskell, such as using Data.Vector.Unboxed instead of the regular lists and removing calls to isLetter

Neither of those complaints are reasonable at all. What is wrong with using Vectors? That is like complaining that a C++ version uses vectors, which it presumably would.

And how is changing a single function call that is unicode aware to one that isn't unfair? How is using getc in the C version unfair?

Re: When Haskell is Faster than C

#37

Post by cube13 »

Cowen wrote: post #15
ozataman wrote: post #12

Earlier quoted context omitted.

I'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.

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

Re: When Haskell is Faster than C

#38

Post by jrockway »

ozataman wrote: post #12
jlarocco wrote: post #3

I 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. N…

I'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.

It's also important to notice that Data.Vector.Unboxed has the same API as the other Data.Vector implementations and provides the same typechecking that the other implementations do. All it requires is that the underlying type have a Unbox instance. In most cases, you change:

   import Data.Vector as V
to

   import Data.Vector.Unboxed as V
and your code now gets the performance increase. (The reason it's not the default is because it's not most generic. What if you want to have a vector of IO computations? Good luck unboxing that. But if you just want integers, or something, that's much easier.)

Re: When Haskell is Faster than C

#39

Post by cube13 »

gnuvince wrote: post #30
jlarocco wrote: post #19

Earlier quoted context omitted.

Fair enough. My complaint is that the C code isn't given the same chance. He even calls out that reading data with getc is a known performance problem, but then does it anyway. Any book on learning C will point out that getc is slow for reading lots of data, and fscanf or fread should be used instead.

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 done there.

The biggest performance hit is actually the single character puts versus a block read or write.

Haskell is probably implemented to read a large block of the file(or perhaps the entire file) into memory, then parse after. That would be a minimal number of system fread calls over the entire run. Versus the C code, where 1 block's parse could be 1024 getc and putc calls.

Re: When Haskell is Faster than C

#40

Post by TheOsiris »

papsosouid wrote: post #36
jlarocco wrote: post #3

I 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. N…

>He cherry picks optimizations for the Haskell, such as using Data.Vector.Unboxed instead of the regular lists and removing calls to isLetter Neither of those complaints are reasonable at all. What is wrong with using Vectors? That is like complaining that a C++ version uses vectors, which it presumably would. And how is changing a single function call that is unicode aware to one that isn't unfair? How is using getc…

The unfairness is that he optimizes the Haskell code but then doesn't do the same for the C code and declared Haskell faster. Not what I'd call a reasonable test.
Post reply on HN