News for hackers. Stuff that matters.
Re:An example of fast numerical computation using Haskell by tsahyt on Saturday November 30, 2013 @09:35AM (#6823240)
I've already posted this on /r/haskell on reddit but since the article turned up here as well, I might just as well post this again. Since we're talking optimization I had a short look at the C code and found it to be a very naive implementation and have managed to cut the execution time quite a bit by employing a sort of memoization. Once you get to a number of the sequence which you have already seen before, the length from there to 1 remains the same as before.

So here is the code: http://lpaste.net/96397

Here are my measurements:

    time ./original 1000000
    (329, 837799)

    real   0m0.183s
    user   0m0.180s
    sys    0m0.001s

    time ./new 1000000
    (329, 837799)
    
    real   0m0.017s
    user   0m0.015s
    sys    0m0.001s
Re:An example of fast numerical computation using Haskell by deletes on Saturday November 30, 2013 @10:20AM (#6823342)
The idea is to optimize while keeping the algorithm the same throughout the languages, at least if you want any meaningful comparison. You are comparing languages not different algorithms. +1 for effort though.
Re:An example of fast numerical computation using Haskell by anon1385 on Saturday November 30, 2013 @10:46AM (#6823405)
It doesn't seem that meaningful to compare a totally naive C implementation to an optimised Haskell one either. (Well, other than to show how fast C is even without any effort to optimise the code). Saying you have to keep the algorithm the same seems like a rather arbitrary limitation on the comparisons, especially since some algorithms are much less of a natural fit in some languages (see: quicksort in Haskell vs C [1]).

I would suggest it's best to show (at least) 4 versions of the code to compare two language: the naive implementation in both languages, and the really optimised version in both languages (plus intermediate levels of optimisation if you feel dedicated). That gives a picture of how fast the typical code one would write will be, as well as the potential for optimisation if you are experiencing bottlenecks, and how much effort it takes to optimise the code.

[1] http://augustss.blogspot.co.uk/2007/08/quicksort-in-haskell-...

Re:An example of fast numerical computation using Haskell by lelf on Saturday November 30, 2013 @11:50AM (#6823599)
> totally naive C implementation to an optimised Haskell one either.

Haskell version is totally naïve. That's the point.

Re:An example of fast numerical computation using Haskell by anon1385 on Saturday November 30, 2013 @12:06PM (#6823653)
The first version that takes 5.9 seconds is naive. The second one certainly isn't, and the third one is based on cleaning up the second version with the use of some library code. As somebody who isn't a Haskell programmer it isn't clear to me at all that anybody would write the final version of the code if they weren't trying to optimise it. Maybe they would but the article doesn't really argue that case and it appears that stream-fusion isn't a part of the language/standard libraries (you have to install it with cabal).

Once you start modifying code to make it run faster it's no longer a 'naive' implementation. No matter how nice or logical you think those transformations are.

I'm not saying you can't compare the stream-fusion version against other languages, just that it's highly disingenuous to optimise the Haskell code with some external libraries but then argue that optimisations of the C version are unfair.

Re:An example of fast numerical computation using Haskell by mietek on Saturday November 30, 2013 @12:51PM (#6823831)
If anyone is being disingenuous here, it's you.

The first version [1] is simple and slow. The second version [2] is complex and fast.

The third, fast version [3] is identical to the first, simple version, with list processing functions imported from the `stream-fusion` package. This is the entire point of this article.

The only transformation shown is purely mechanical (prepending symbol names with the qualified import prefix `S.`), and even this is not required (as `Prelude` could have been imported `hiding` the appropriate symbol names instead).

[1]: http://www.mit.edu/~mtikekar/posts/src/collatz.hs

[2]: http://www.mit.edu/~mtikekar/posts/src/collatz1.hs

[3]: http://www.mit.edu/~mtikekar/posts/src/collatz2.hs

Re:An example of fast numerical computation using Haskell by vinkelhake on Saturday November 30, 2013 @02:21PM (#6824202)
Are there downsides to using the stream-fusion package? If not, why hasn't it been made the default so that the first naive version is fast?
Re:An example of fast numerical computation using Haskell by mietek on Saturday November 30, 2013 @06:23PM (#6825144)
As I understand, stream fusion is still subject of active research. A paper showing generalised stream fusion in Haskell was submitted to this year's ICFP.

There is also no benevolent dictator in charge of Haskell.

http://research.microsoft.com/en-us/um/people/simonpj/papers...

http://www.reddit.com/r/haskell/comments/1br0ls/haskell_beat...

Re:An example of fast numerical computation using Haskell by carterschonwald on Saturday November 30, 2013 @06:47PM (#6825255)
indeed. The generalized stream fusion work is about lifting pointwise operations to their SIMD vectorized analogue.

Likewise, stream fusion isn't always a win! Stream fusion and its siblings are great for pointwise operations, but aren't always a good idea for computations with heavy reuse, like nested convolutions or performant matrix multipy

Re:An example of fast numerical computation using Haskell by dons on Saturday November 30, 2013 @09:58PM (#6825881)
Complexity of concatMap operations. Nested things don't always fuse.

If you want to use fusion, the best place is the `vector` package.

Re:An example of fast numerical computation using Haskell by tel on Saturday November 30, 2013 @12:39PM (#6823785)
I think the idea is that there are many more optimizations that could be performed, but this "naïve" version is still very idiomatic and high level.
Re:An example of fast numerical computation using Haskell by ejgottl on Saturday November 30, 2013 @03:24PM (#6824480)
Agreed. Optimizing the code without first fixing the asymptotic performance of the algorithm detracts significantly from the article. I've solved this problem before in Project Euler, in both Haskell and C++, and for my purposes as a beginning Haskell programmer, figuring out how to construct an asymptotically efficient algorithm for a Dynamic Programming problem in Haskell is what is interesting here.
Re:An example of fast numerical computation using Haskell by tsahyt on Sunday December 01, 2013 @04:09AM (#6826677)
I know what you mean but it's early in the morning here and I feel like being a bit pedantic: As far as we can tell neither of the algorithms actually terminates for arbitrary inputs. If we could show that, we'd have proven the Collatz conjecture. Therefore the notion of asymptotic performance doesn't make a lot of sense, since we want to give an upper bound on how long the algorithms takes to terminate. However, if we found such an upper bound, it would be equivalent to solving the problem itself, because the runtime depends on how long a given sequence is, and putting it into a closed form. At that point we'd trivially have an O(1) algorithm.

What we can do, is measure complexity empirically and extrapolate something from there. I haven't done a lot of tests with this code but to me it seemed like it would scale the same as the original one but had a much lower constant.