3 ms·

Holy Shmoly, GHC Haskell 6.8 smokes Python and Ruby away! And you can parallelise it for free

10 points by nickb 19y ago

amichail 19y ago
In the example, parallelization annotations were used and the speedup is not impressive.
- dfranke 19y ago
  It's a dual-core machine. The par annotations get you a factor of two at best. Dons is still arguably pulling a fast one, though. Even though the Haskell program looks like it should behave in more-or-less the same way as the other two, the semantics are actually quite different. Haskell defaults to lazy evaluation with memoization -- hence the "naive" recursion isn't really naive. That's where the orders of magnitude come from. That said, Haskell is still a pretty fast language, on par with Java.
  - SamReidHughes 19y ago
    It isn't memoizing anything here. If it were memoizing, do you think it would take 0.48 seconds? Laziness is not the same thing as memoization of function arguments.
    - dfranke 19y ago
      Okay, apparently I didn't quite think this one through. I wasn't claiming that GHC memoizes values, but it does memoize thunks. I thought this algorithm would be getting some benefit from that, but having inserted some trace statements, I was apparently wrong. Here's a version that really is memoized: import Control.Parallel import Control.Monad import Text.Printf cutoff = 35 fibs = [ fib n | n <- [0..] ] fib' :: Int -> Integer fib' 0 = 0 fib' 1 = 1 fib' n = fibs !! (n-1) + fibs !! (n-2) fib :: Int -> Integer fib n | n < cutoff = fib' n | otherwise = r `par` (l `seq` l + r) where l = fibs !! (n-1) r = fibs !! (n-2) main = forM_ [0..45] $ \i -> printf "n=%d => %d\n" i (fib i)
dreish 19y ago
This is about the most bogus test the author could have constructed. You have to explicitly memoize functions in languages that aren't purely functional like Haskell. Fibonacci is around O(1.6^n) if you conveniently "forget" to memoize it, or else O(n). So the upside of a pure functional language is you don't have to explicitly memoize. To see the downside, try explaining monads to an undergrad. Haskell is a cool enough language that it doesn't need misleading hype like this post.
- SamReidHughes 19y ago
  What gives you the idea that Haskell implicitly memoizes functions? And it obviously isn't memoizing. If the function were memoized, the timing would be much, much less than 0.48 seconds.
  - dreish 19y ago
    I have to admit I understand Haskell a lot less than I thought I did (which wasn't much to begin with -- I've done maybe four or five Euler Project puzzles with it and nothing else). I tried this same Fibonacci function on my machine using GHC 6.8.1, and it's clearly O(1.62^N). I withdraw my earlier dumb statement.
rontr 19y ago
Some people get too excited by micro benchmarks.

10 points by nickb 19y ago

amichail 19y ago

In the example, parallelization annotations were used and the speedup is not impressive.

dfranke 19y ago
It's a dual-core machine. The par annotations get you a factor of two at best. Dons is still arguably pulling a fast one, though. Even though the Haskell program looks like it should behave in more-or-less the same way as the other two, the semantics are actually quite different. Haskell defaults to lazy evaluation with memoization -- hence the "naive" recursion isn't really naive. That's where the orders of magnitude come from. That said, Haskell is still a pretty fast language, on par with Java.
- SamReidHughes 19y ago
  It isn't memoizing anything here. If it were memoizing, do you think it would take 0.48 seconds? Laziness is not the same thing as memoization of function arguments.
  - dfranke 19y ago
    Okay, apparently I didn't quite think this one through. I wasn't claiming that GHC memoizes values, but it does memoize thunks. I thought this algorithm would be getting some benefit from that, but having inserted some trace statements, I was apparently wrong. Here's a version that really is memoized: import Control.Parallel import Control.Monad import Text.Printf cutoff = 35 fibs = [ fib n | n <- [0..] ] fib' :: Int -> Integer fib' 0 = 0 fib' 1 = 1 fib' n = fibs !! (n-1) + fibs !! (n-2) fib :: Int -> Integer fib n | n < cutoff = fib' n | otherwise = r `par` (l `seq` l + r) where l = fibs !! (n-1) r = fibs !! (n-2) main = forM_ [0..45] $ \i -> printf "n=%d => %d\n" i (fib i)

dreish 19y ago

This is about the most bogus test the author could have constructed. You have to explicitly memoize functions in languages that aren't purely functional like Haskell. Fibonacci is around O(1.6^n) if you conveniently "forget" to memoize it, or else O(n). So the upside of a pure functional language is you don't have to explicitly memoize. To see the downside, try explaining monads to an undergrad. Haskell is a cool enough language that it doesn't need misleading hype like this post.

SamReidHughes 19y ago
What gives you the idea that Haskell implicitly memoizes functions? And it obviously isn't memoizing. If the function were memoized, the timing would be much, much less than 0.48 seconds.
- dreish 19y ago
  I have to admit I understand Haskell a lot less than I thought I did (which wasn't much to begin with -- I've done maybe four or five Euler Project puzzles with it and nothing else). I tried this same Fibonacci function on my machine using GHC 6.8.1, and it's clearly O(1.62^N). I withdraw my earlier dumb statement.

rontr 19y ago

Some people get too excited by micro benchmarks.