4 ms·

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 bec

by 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!
  - pbsd 14y ago
    Figure 7 shows Haskell-generated AVX instructions, albeit only using the lower 128 bits. That code would not run on an SSE4.2-capable Nehalem, for instance. There are some other CPU-related slight inaccuracies in the paper. Prefetching is repeatedly mentioned, even though its effect is negligible when one has a perfectly linear memory access pattern; unaligned loads are mentioned as a performance hit, but they are essentially free on the test processor (2600k, Sandy Bridge). Matrix multiplication would perhaps be a better example to show the power of clever prefetching.
- jules 14y ago
  I would be surprised if prefetching helped at all, given that the memory access pattern is completely linear. But yes, it's always a problem that the work in a paper is tuned to the particular machine the benchmark is run on, while the things that are compared against are not. Also agreed that it's suspicious that Haskell is using AVX while the C isn't. However compared to the second benchmark, the first one is very fair ;-) Perhaps somebody with an AVX capable processor can redo the two benchmarks with correct compiler options (i.e. -mavx) and/or with ICC, and replacing the C code of the second benchmark with code that is equivalent to the Haskell code: double s=0; for(int i=0; i<n; i++) s += pow(a[i]-b[i],2);
  - floody-berry 14y ago
    I made a quick test for the C versions to try out flags and such: https://gist.github.com/floodyberry/5335542 https://gist.github.com/floodyberry/5335542 I found out gcc supports -fprefetch-loop-arrays, although it is not guaranteed to have a positive effect. In this case, it does appear to run faster than without prefetching. AVX versions also run faster than the standard SSE counterparts even with 128 bit registers. ymm regs are faster than xmm. gcc is faster than icc actually, and icc runs faster with the plain c version than the vectorized versions. I can't figure out how to make icc prefetch either, the switch that controls it doesn't seem to have an effect.
    - jules 14y ago
      Nice! What were the results?
mpyne 14y ago
> 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. That would imply that the C version of the C++ code would be just as fast, if only it were not "poorly written". However there are some types of code (including this kind) where having C++ available to generate the code for you makes it almost inherently faster than C. You could certainly reimplement specific matrix operations for very specific types in C, but the C++ Eigen library does this all for you at compile time, and does it the best way for each combination of types and operations. If you do this in C, even with macros everywhere, it's going to be much more difficult, especially since you can't (AFAIK) declare and discard temporary types within macros, though C11 at least allows you to refer generically to types within macros. The canonical example for this kind of disparity is C's qsort() vs. C++ templated sorts. This is kind of the point to the paper. Performance of this sort is only possible in C++ if you're careful to follow the instructions provided with Eigen about using templated functions, and some very smart devs had to write Eigen in the first place. The Haskell code comes fairly close starting from the source code you'd write naïvely, and without tons of optimization on the stream fusion code generator.
- jules 14y ago
  In general, you're absolutely right. For this particular benchmark, this is not the case. See here: https://news.ycombinator.com/item?id=5508948 https://news.ycombinator.com/item?id=5508948
kostya-kow 14y ago
GHC and GCC are 2 of the most widely used compilers for the respective languages. The research uses most popular compilers, which are used by many different projects, not the most micro-optimized once.
- jules 14y ago
  The paper claims otherwise.
army 14y ago
That sums it up pretty well: great work, but take the evaluation with a grain of salt.

by jules 14y ago

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!
- pbsd 14y ago
  Figure 7 shows Haskell-generated AVX instructions, albeit only using the lower 128 bits. That code would not run on an SSE4.2-capable Nehalem, for instance. There are some other CPU-related slight inaccuracies in the paper. Prefetching is repeatedly mentioned, even though its effect is negligible when one has a perfectly linear memory access pattern; unaligned loads are mentioned as a performance hit, but they are essentially free on the test processor (2600k, Sandy Bridge). Matrix multiplication would perhaps be a better example to show the power of clever prefetching.
jules 14y ago
I would be surprised if prefetching helped at all, given that the memory access pattern is completely linear. But yes, it's always a problem that the work in a paper is tuned to the particular machine the benchmark is run on, while the things that are compared against are not. Also agreed that it's suspicious that Haskell is using AVX while the C isn't. However compared to the second benchmark, the first one is very fair ;-) Perhaps somebody with an AVX capable processor can redo the two benchmarks with correct compiler options (i.e. -mavx) and/or with ICC, and replacing the C code of the second benchmark with code that is equivalent to the Haskell code: double s=0; for(int i=0; i<n; i++) s += pow(a[i]-b[i],2);
- floody-berry 14y ago
  I made a quick test for the C versions to try out flags and such: https://gist.github.com/floodyberry/5335542 https://gist.github.com/floodyberry/5335542 I found out gcc supports -fprefetch-loop-arrays, although it is not guaranteed to have a positive effect. In this case, it does appear to run faster than without prefetching. AVX versions also run faster than the standard SSE counterparts even with 128 bit registers. ymm regs are faster than xmm. gcc is faster than icc actually, and icc runs faster with the plain c version than the vectorized versions. I can't figure out how to make icc prefetch either, the switch that controls it doesn't seem to have an effect.
  - jules 14y ago
    Nice! What were the results?

mpyne 14y ago

> 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. That would imply that the C version of the C++ code would be just as fast, if only it were not "poorly written". However there are some types of code (including this kind) where having C++ available to generate the code for you makes it almost inherently faster than C. You could certainly reimplement specific matrix operations for very specific types in C, but the C++ Eigen library does this all for you at compile time, and does it the best way for each combination of types and operations. If you do this in C, even with macros everywhere, it's going to be much more difficult, especially since you can't (AFAIK) declare and discard temporary types within macros, though C11 at least allows you to refer generically to types within macros. The canonical example for this kind of disparity is C's qsort() vs. C++ templated sorts. This is kind of the point to the paper. Performance of this sort is only possible in C++ if you're careful to follow the instructions provided with Eigen about using templated functions, and some very smart devs had to write Eigen in the first place. The Haskell code comes fairly close starting from the source code you'd write naïvely, and without tons of optimization on the stream fusion code generator.

jules 14y ago
In general, you're absolutely right. For this particular benchmark, this is not the case. See here: https://news.ycombinator.com/item?id=5508948 https://news.ycombinator.com/item?id=5508948

kostya-kow 14y ago

GHC and GCC are 2 of the most widely used compilers for the respective languages. The research uses most popular compilers, which are used by many different projects, not the most micro-optimized once.

jules 14y ago
The paper claims otherwise.

army 14y ago

That sums it up pretty well: great work, but take the evaluation with a grain of salt.