9 ms·

Haskell Beats C Using Generalized Stream Fusion [pdf]

108 points by profquail 14y ago

CJefferson 14y ago
While it is interesting to see generalised stream fusion, the conclusions are that Haskell is still half the speed of C++. Also, looking at the results most of the performance comes from which library you are using, and how well it is optimised. No compiler is good enough to do what the good libraries do.
- miga 14y ago
  Stream fusion is an optimization framework that is (to my knowledge) defined in the library, but common to most sequence types in Haskell.
- gngeal 14y ago
  "No compiler is good enough to do what the good libraries do." That's nonsense. And if you take a look, say, at NumPy, which uses heavily tuned BLAS/LAPACK code, and Numexpr, which uses the "compile the snippet and run it" approach, you'll see why. Libraries won't save your performance if you can't optimize across procedure and module boundaries.
  - ori_b 14y ago
    Which is why C and C++ under most state of the art compilers support link time optimization.
    - gngeal 14y ago
      That won't help you much, if you, say, need the fusion of matrix operations I mentioned.
taeric 14y ago
"The C++ programmer must worry about the performance implications of abstraction." This quote seems a touch odd when you consider just how much faster the C++ solution is. The Haskell programmer definitely does not get a complete pass on worrying about the implications of abstraction. Indeed, this seems to underscore that if performance is a major criteria, than language choice still matters.
- GhotiFish 14y ago
  I agree, auditing Haskell's performance characteristics is not easy. Then again, nothing in Haskell is easy.
  - miga 14y ago
    Writing short and clear code in Haskell is definitely easy. As for optimization - it quite often does it for you too!
    - GhotiFish 14y ago
      !!! I have never met a single person who has said this, let alone capable of following through. If you are capable, I am envious of your determination/natural talent. Or alternatively I and every programmer I know are idiots. Actually both seem like possibilities.
      - nilkn 14y ago
        > Or alternatively I and every programmer I know are idiots. Most programmers haven't taken the time to actually learn Haskell. Haskell only seems hard at first because it incorporates a lot of ideas that other languages do not. For a lot of developers, learning Haskell is a little bit like learning to program from scratch all over again. In that sense, yes, I guess it's hard, but so was whatever language you learned first.
        mbel 14y ago
kevingadd 14y ago
Before you say 'oh, Haskell is still only half the speed of C++', you should keep in mind just how insane the C++ code they had to write looks. The Eigen code they had to write is pretty nasty and getting it correct required some particular understanding. In comparison, the performance they're getting out of Haskell is coming from comparatively mundane, easy to understand code. That's pretty impressive. Or another way of putting it: It looks like naive Haskell outperforms naive C++, and naive Haskell is not that much slower than carefully-tuned C++. template < typename Derived > typename Derived::Scalar norm2( const MatrixBase <Derived >& v ) { return v.dot(v); } Why is it a template function? Why does it return Derived::Scalar instead of double? Dear god, Eigen is magic.
- dchichkov 14y ago
  The code (actual instructions) that beats C++ in their example is being generated by their experimental "stream fusion" framework. And NOT by a generic Haskell compiler. And now the question, do you really want to an unproven and unstable Haskell framework? While there are stable alternatives (lake Eigen, Theano, etc) available? So no. Haskell (production ready Haskell) doesn't even come close.
- ibotty 14y ago
  if i understand the paper correctly (and apply the knowledge to eigen), it't because of the same reason: you want to allow different stream fusion strategies to work.
- pbsd 14y ago
  While 'Derived::Scalar' could very well be replaced by 'double' in that case, you need the templated function to catch the temporary type (expression template) that represents the u-v computation. This lets Eigen compute u[i]-v[i] and the dot product inside the same inner loop. Without the templated function, the compiler would first generate the subtraction into a temporary vector, and then compute the dot product on that vector.
  - kevingadd 14y ago
    That makes sense, thanks! I figured the template was being used to magically substitute some sort of meta-type or container for temporaries.
jules 14y ago
Although the results are impressive, the title is a bit optimistic. Haskell beat GCC slightly in the first benchmark. Haskell beat C in the second benchmark because the C code is very poorly written. They did not compare with the obvious C implementation. Secondly, GCC isn't the best C compiler, even though the paper claims that it is the best compiler that "we could find". They should have used ICC. C++ is also 4x faster than Haskell in the second benchmark, giving further indication that the C is slow just because it is poorly written. So it's hard to justify such a title. The work itself is very good however.
- floody-berry 14y ago
  The first C example is pretty disingenuous as they explicitly added loop unrolling and prefetching tuned to x86-64 to the Vector library, then compared the basic C versions with with "-funroll-loops" (and no prefetching based on the icc/gcc/clang compiler output I looked at). For some reason they also use "-msse4.2" on a CPU supporting AVX while the Haskell version is generating AVX instructions. The paper would have been better off with more complex examples (e.g. functions that can't be trivially implemented in asm by hand with no register pressure) and fewer comparisons to implementations that could be doing what they are, but aren't.
  - mainland 14y ago
    First author here. The dot product example was compiled with GCC 4.7.2 -O3 -msse4.2 -ffast-math -ftree-vectorize -funroll-loops; see the caption to Figure 5. What compiler options would you have suggested? The Haskell version only used SSE instructions, not AVX; this should have been made clear in the paper. The more complex examples are in Section 5.2; see Figure 8. Granted, we would have liked to have done more, but deadlines are deadlines...
    - floody-berry 14y ago
      The Haskell assembly is using the 3-op AVX instructions, but not 256bit registers. The example is simple enough that it may not make a difference (2-op vs 3-op instructions), but in a more complex function with register spills it could have. ("-mavx" should be enough). all that said, it is still very impressive work!
Xcelerate 14y ago
I am curious why every time there is a "language" beats "other language" in some test posted on here, there is an inevitable slew of comments along the lines of "losing language was poorly written code". Is the probability really so high as to be 100% that all optimization tests were against a poorly written competitor? That's amazing if that's the case.
- taeric 14y ago
  I would wager a large contributor to this is that the idioms of some of these specialized fields do not generalize to other use cases. So, while some researchers have gotten it such that a relatively straight forward implementation in a new language with new tools is better than the old way, the folks working the old way have not exactly stagnated. This seems especially likely when you consider that for many of the really fast implementations, it is not that they are using no abstractions. The abstractions they are using are very close to the machine, because the machine is the abstraction they are using. (That make sense?)
- moomin 14y ago
  It seems to me that most X beats Y posts are written by people with a great deal of knowledge of X, but without a matching knowledge of Y. This, unfortunately, leaves every post wide open to this sort of attack.
- jules 14y ago
  I suspect this comment is at least partially directed at me. Did you read the paper? Excluding some O(1) operations, the goal of the second benchmark is this: double s = 0; for(int i=0; i<n; i++) s += pow(a[i]-b[i],2); return s; But they did not use this C code. The C code they used made 3 calls to the BLAS library. The end result is that the C code is doing something equivalent to this: double x=0, y=0, z=0; for(int i=0; i<n; i++) x += a[i]*a[i]; for(int i=0; i<n; i++) y += a[i]*b[i]; for(int i=0; i<n; i++) z += b[i]*b[i]; return x - 2*y + z; While this does return the same result (assuming infinite precision arithmetic) it is obviously not the way anybody would do it, since it's doing 3 times the work. Even worse, because their code is calling into the BLAS library for each loop, the compiler is explicitly prevented from optimizing the three loops and memory accesses by combining them into one. Note that the Haskell code is doing the efficient single loop. So yes, it is poorly written code.
andrewcooke 14y ago
i followed (and enjoyed) most of that, but i don't get (perhaps because i've not used haskell in a long time) how the consumer is automatically(?) chosen. from what i understand of section 3.2 the consumer is critical in selecting the correct stream type from the bundle. who decides that? does the user have to select the appropriate function? or does it some how fall out naturally from the use case? or does the compiler select it?
- mainland 14y ago
  The library writer is the "consumer" here. The programmer just uses the library, and the library chooses the proper stream representation. Of course the programmer can also use the lower-level stream interface directly if desired, but then the programmer must also know which stream representation to choose.
33a 14y ago
If Haskell beats C on that loop, then that is a compiler bug. Did they try repeating these experiments using say icc?
- kevingadd 14y ago
  Personally, I would say that leaping straight to 'compiler bug' is a little unwarranted. If you really think it's a compiler bug, you should compile the code (they provided it) using the settings they used (I think they provided that too; you can see them in a comment in this thread, actually) and then look at the output assembly and find the bug and file a bug against the compiler.
- lallysingh 14y ago
  Or Haskell semantics allows more aggressive optimization than C. icc's not actually that much better than gcc in optimization, it's primarily a much better runtime library that gives icc its speed boost.

108 points by profquail 14y ago

While it is interesting to see generalised stream fusion, the conclusions are that Haskell is still half the speed of C++. Also, looking at the results most of the performance comes from which library you are using, and how well it is optimised. No compiler is good enough to do what the good libraries do.

miga 14y ago
Stream fusion is an optimization framework that is (to my knowledge) defined in the library, but common to most sequence types in Haskell.
gngeal 14y ago
"No compiler is good enough to do what the good libraries do." That's nonsense. And if you take a look, say, at NumPy, which uses heavily tuned BLAS/LAPACK code, and Numexpr, which uses the "compile the snippet and run it" approach, you'll see why. Libraries won't save your performance if you can't optimize across procedure and module boundaries.
- ori_b 14y ago
  Which is why C and C++ under most state of the art compilers support link time optimization.
  - gngeal 14y ago
    That won't help you much, if you, say, need the fusion of matrix operations I mentioned.

taeric 14y ago

"The C++ programmer must worry about the performance implications of abstraction." This quote seems a touch odd when you consider just how much faster the C++ solution is. The Haskell programmer definitely does not get a complete pass on worrying about the implications of abstraction. Indeed, this seems to underscore that if performance is a major criteria, than language choice still matters.

GhotiFish 14y ago
I agree, auditing Haskell's performance characteristics is not easy. Then again, nothing in Haskell is easy.
- miga 14y ago
  Writing short and clear code in Haskell is definitely easy. As for optimization - it quite often does it for you too!
  - GhotiFish 14y ago
    !!! I have never met a single person who has said this, let alone capable of following through. If you are capable, I am envious of your determination/natural talent. Or alternatively I and every programmer I know are idiots. Actually both seem like possibilities.
    - nilkn 14y ago
      > Or alternatively I and every programmer I know are idiots. Most programmers haven't taken the time to actually learn Haskell. Haskell only seems hard at first because it incorporates a lot of ideas that other languages do not. For a lot of developers, learning Haskell is a little bit like learning to program from scratch all over again. In that sense, yes, I guess it's hard, but so was whatever language you learned first.
      - mbel 14y ago

kevingadd 14y ago

Before you say 'oh, Haskell is still only half the speed of C++', you should keep in mind just how insane the C++ code they had to write looks. The Eigen code they had to write is pretty nasty and getting it correct required some particular understanding. In comparison, the performance they're getting out of Haskell is coming from comparatively mundane, easy to understand code. That's pretty impressive. Or another way of putting it: It looks like naive Haskell outperforms naive C++, and naive Haskell is not that much slower than carefully-tuned C++. template < typename Derived > typename Derived::Scalar norm2( const MatrixBase <Derived >& v ) { return v.dot(v); } Why is it a template function? Why does it return Derived::Scalar instead of double? Dear god, Eigen is magic.

dchichkov 14y ago
The code (actual instructions) that beats C++ in their example is being generated by their experimental "stream fusion" framework. And NOT by a generic Haskell compiler. And now the question, do you really want to an unproven and unstable Haskell framework? While there are stable alternatives (lake Eigen, Theano, etc) available? So no. Haskell (production ready Haskell) doesn't even come close.
ibotty 14y ago
if i understand the paper correctly (and apply the knowledge to eigen), it't because of the same reason: you want to allow different stream fusion strategies to work.
pbsd 14y ago
While 'Derived::Scalar' could very well be replaced by 'double' in that case, you need the templated function to catch the temporary type (expression template) that represents the u-v computation. This lets Eigen compute u[i]-v[i] and the dot product inside the same inner loop. Without the templated function, the compiler would first generate the subtraction into a temporary vector, and then compute the dot product on that vector.
- kevingadd 14y ago
  That makes sense, thanks! I figured the template was being used to magically substitute some sort of meta-type or container for temporaries.

jules 14y ago

Although the results are impressive, the title is a bit optimistic. Haskell beat GCC slightly in the first benchmark. Haskell beat C in the second benchmark because the C code is very poorly written. They did not compare with the obvious C implementation. Secondly, GCC isn't the best C compiler, even though the paper claims that it is the best compiler that "we could find". They should have used ICC. C++ is also 4x faster than Haskell in the second benchmark, giving further indication that the C is slow just because it is poorly written. So it's hard to justify such a title. The work itself is very good however.

floody-berry 14y ago
The first C example is pretty disingenuous as they explicitly added loop unrolling and prefetching tuned to x86-64 to the Vector library, then compared the basic C versions with with "-funroll-loops" (and no prefetching based on the icc/gcc/clang compiler output I looked at). For some reason they also use "-msse4.2" on a CPU supporting AVX while the Haskell version is generating AVX instructions. The paper would have been better off with more complex examples (e.g. functions that can't be trivially implemented in asm by hand with no register pressure) and fewer comparisons to implementations that could be doing what they are, but aren't.
- mainland 14y ago
  First author here. The dot product example was compiled with GCC 4.7.2 -O3 -msse4.2 -ffast-math -ftree-vectorize -funroll-loops; see the caption to Figure 5. What compiler options would you have suggested? The Haskell version only used SSE instructions, not AVX; this should have been made clear in the paper. The more complex examples are in Section 5.2; see Figure 8. Granted, we would have liked to have done more, but deadlines are deadlines...
  - floody-berry 14y ago
    The Haskell assembly is using the 3-op AVX instructions, but not 256bit registers. The example is simple enough that it may not make a difference (2-op vs 3-op instructions), but in a more complex function with register spills it could have. ("-mavx" should be enough). all that said, it is still very impressive work!

Xcelerate 14y ago

I am curious why every time there is a "language" beats "other language" in some test posted on here, there is an inevitable slew of comments along the lines of "losing language was poorly written code". Is the probability really so high as to be 100% that all optimization tests were against a poorly written competitor? That's amazing if that's the case.

taeric 14y ago
I would wager a large contributor to this is that the idioms of some of these specialized fields do not generalize to other use cases. So, while some researchers have gotten it such that a relatively straight forward implementation in a new language with new tools is better than the old way, the folks working the old way have not exactly stagnated. This seems especially likely when you consider that for many of the really fast implementations, it is not that they are using no abstractions. The abstractions they are using are very close to the machine, because the machine is the abstraction they are using. (That make sense?)
moomin 14y ago
It seems to me that most X beats Y posts are written by people with a great deal of knowledge of X, but without a matching knowledge of Y. This, unfortunately, leaves every post wide open to this sort of attack.
jules 14y ago
I suspect this comment is at least partially directed at me. Did you read the paper? Excluding some O(1) operations, the goal of the second benchmark is this: double s = 0; for(int i=0; i<n; i++) s += pow(a[i]-b[i],2); return s; But they did not use this C code. The C code they used made 3 calls to the BLAS library. The end result is that the C code is doing something equivalent to this: double x=0, y=0, z=0; for(int i=0; i<n; i++) x += a[i]*a[i]; for(int i=0; i<n; i++) y += a[i]*b[i]; for(int i=0; i<n; i++) z += b[i]*b[i]; return x - 2*y + z; While this does return the same result (assuming infinite precision arithmetic) it is obviously not the way anybody would do it, since it's doing 3 times the work. Even worse, because their code is calling into the BLAS library for each loop, the compiler is explicitly prevented from optimizing the three loops and memory accesses by combining them into one. Note that the Haskell code is doing the efficient single loop. So yes, it is poorly written code.

andrewcooke 14y ago

i followed (and enjoyed) most of that, but i don't get (perhaps because i've not used haskell in a long time) how the consumer is automatically(?) chosen. from what i understand of section 3.2 the consumer is critical in selecting the correct stream type from the bundle. who decides that? does the user have to select the appropriate function? or does it some how fall out naturally from the use case? or does the compiler select it?

mainland 14y ago
The library writer is the "consumer" here. The programmer just uses the library, and the library chooses the proper stream representation. Of course the programmer can also use the lower-level stream interface directly if desired, but then the programmer must also know which stream representation to choose.

33a 14y ago

If Haskell beats C on that loop, then that is a compiler bug. Did they try repeating these experiments using say icc?

kevingadd 14y ago
Personally, I would say that leaping straight to 'compiler bug' is a little unwarranted. If you really think it's a compiler bug, you should compile the code (they provided it) using the settings they used (I think they provided that too; you can see them in a comment in this thread, actually) and then look at the output assembly and find the bug and file a bug against the compiler.
lallysingh 14y ago
Or Haskell semantics allows more aggressive optimization than C. icc's not actually that much better than gcc in optimization, it's primarily a much better runtime library that gives icc its speed boost.