Haskell: performance

It turned out that it's not Haskell who was slow in my previous Fibonacci test. It was my lack of Haskell knowledge. Haskell has two integral types - Int, which has bounds -2147483648..2147483647 and Integer, which is unbounded. Both types implement Integral type class, so out fib function can be defined in terms of this type class:

	fib :: Integral a => a -> a
	fib 0 = 0
	fib 1 = 1
	fib x = fib (x - 2) + fib (x - 1)

view raw fast_fib.hs hosted with ❤ by GitHub

OK, now we can test performance of the function parametrizing it with the two concrete types. Integer first:

	main :: IO()
	main = do
	args <- getArgs
	case args of
	[nStr] ->
	mapM_
	putStrLn
	$ map (\x -> "fib " ++ (show x) ++ " = " ++ (show $ fib x))
	$ [0..(read nStr :: Integer)] -- note the Integer type hint
	_ -> print "Wrong arguments"
	putStrLn "done."
	> Main.exe 39 +RTS -s
	fib 0 = 0
	...
	fib 39 = 63245986
	...
	INIT time 0.00s ( 0.00s elapsed)
	MUT time 14.76s ( 14.89s elapsed)
	GC time 0.05s ( 0.07s elapsed)
	EXIT time 0.00s ( 0.00s elapsed)
	Total time 14.80s ( 14.95s elapsed)
	Productivity 99.7% of total user, 98.7% of total elapsed

view raw call_fib_Integer.hs hosted with ❤ by GitHub

We get our previous result ~15 seconds which is rather slow. Now test it with Int type:

	main :: IO()
	main = do
	args <- getArgs
	case args of
	[nStr] ->
	mapM_
	putStrLn
	$ map (\x -> "fib " ++ (show x) ++ " = " ++ (show $ fib x))
	$ [0..(read nStr :: Int)] -- we simply change the type to Int
	_ -> print "Wrong arguments"
	putStrLn "done."
	> Main.exe 39 +RTS -s
	fib 0 = 0
	...
	fib 39 = 63245986
	...
	INIT time 0.00s ( 0.00s elapsed)
	MUT time 2.39s ( 2.40s elapsed)
	GC time 0.00s ( 0.00s elapsed)
	EXIT time 0.00s ( 0.00s elapsed)
	Total time 2.39s ( 2.41s elapsed)
	Productivity 100.0% of total user, 99.2% of total elapsed

view raw call_fib_Int.hs hosted with ❤ by GitHub

Whoa! The Int type is ~6 times faster than Integer! And with result of 2.8 seconds Haskell's took the third position in our small rating :) Current list (in seconds):

• C# - 1.26
• F# - 1.38
• Nemerle - 1.45
• Haskell - 2.8
• Clojure - 9
• Erlang - 17
• Ruby - 60
• Python - 120