I am fresh in haskell, and I defined a func in Haskell :
febs :: (Integral a)=> a -> a
febs n
| n<=0 =0
| n==1 =1
| n==2 =1
| otherwise =febs(n-1)+febs(n-2)
but, it runs so slow, and when I do "febs 30", it will take about 10s, and I do the same func in C++, it runs very fast.
int febs(int n)
{
if(n == 1 || n ==2)
{
return 1;
}
return febs(n-1)+febs(n-2);
}
Is there any way to promote my haskell func speed?
This is an odd comparison, for the following reasons:
You don't say whether you're compiling the Haskell code, or with what options. If you're just running it in ghci, then of course it will be slow - you're comparing interpreted code with compiled code.
Your Haskell code is polymorphic whereas your C++ code is monomorphic (that is, you've used a type class Integral a => a -> a instead of the concrete type Int -> Int). Your Haskell code is therefore more general than your C++ code, because it can handle arbitrarily large integers instead of being restricted to the range of an Int. It's possible that the compiler will optimize this away, but I'm not certain.
If I put the following code in a file fib.hs
fibs :: Int -> Int
fibs n = if n < 3 then 1 else fibs (n-1) + fibs (n-2)
main = print (fibs 30)
and compile it with ghc -O2 fib.hs then it runs fast enough that it appears instantaneous to me. You should try that, and see how it compares with the C++ code.
Int type at the call site. Which, thinking about it, isn't a fair assumption.
main that'd be at Integer, so somewhat slower than with Int. If you define it in a different file than it's used in, unless you make it {-# INLINABLE #-}, you get the very slow polymorphic code.Try compiling with optimization. With GHC 7.4.1 with -O2, your program runs quite quickly:
$ time ./test
832040
real 0m0.057s
user 0m0.056s
sys 0m0.000s
This is with main = print (febs 30).
Regarding the polymorphism considerations in Chris Taylor's answer, here's febs 40 with OP's polymorphic Fibonacci function:
$ time ./test
102334155
real 0m5.670s
user 0m5.652s
sys 0m0.004s
And here is a non-polymorphic one, i.e. with OP's signature replaced with Int -> Int:
$ time ./test
102334155
real 0m0.820s
user 0m0.816s
sys 0m0.000s
Per Tikhon Jelvis' comment, it'd be interesting to see if the speedup is due to replacing Integer with Int, or due to getting rid of polymorphism. Here's the same program again, except with febs moved to a new file per Daniel Fischer's comment, and with with febs :: Integer -> Integer:
$ time ./test
102334155
real 0m5.648s
user 0m5.624s
sys 0m0.008s
Again, with febs in a different file, and with the same polymorphic signature as originally:
$ time ./test
102334155
real 0m16.610s
user 0m16.469s
sys 0m0.104s
Integral type gets defaulted to Integer. I'm curious if the change in performance is just because of Integer vs Int or if the polymorphism also matters.main hadn't you? In separate files, with polymorphic code, I get a running time of 15.5s for febs 40, 5.4s for Integer -> Integer and 0.86s for Int -> Int. @TikhonJelvis this would answer your question. And 0.3s for gcc -O3.{-# SPECIALISE foo :: Int -> Int, Word -> Integer #-} [US spelling also accepted]), or - requires GHC >= 7 [perhaps 7.2, not sure] - with an {-# INLINABLE foo #-} pragma that it should expose the function for inlining/optimising/specialising in the interface file. Then (always with -O2) it will be done automatically, at least if the nesting isn't too deep [I can imagine that the optimiser gives up if your call-tree is 1000 polymorphic functions deep].INLINABLE, a specialised version is generated at the use site. If you use a polymorphic function at one specific type in a lot of modules, each gets its own specialised version, then it can be preferable to use a SPECIALISE pragma to reduce (compiled) code size.You could also write the function like this:
fibs = 0:1:zipWith (+) fibs (tail fibs)
It is very fast, even for big 'n' executes immediately:
Prelude> take 1000 fibs
fibs = 0 : scanl (+) 1 fibs
fix ((0:) . scanl (+) 1).