Use a Better Algorithm and Beat Haskell Today!
Note: This refers to the article “Use those extra cores and beat C today! (Parallel Haskell redux)”, and should be viewed as a good-natured ribbing!
I’ll see your sensational headline and raise you a better algorithm!
The Code:
#include "gmpxx.h" #include #include using namespace std; mpz_class fib(unsigned int num) { mpz_class a(1), b(1); mpz_class temp; while(num-- > 1) { temp = a; a = a + b; b = temp; } return a; } #define NUM 200000 int main() { cout<<"Fibonacci test for Fib("<<<")"<<<"Time: "<<<" seconds"<
Build With:
g++ fib.cpp -O2 -lgmp -lgmpxx
The Result: (On a Toshiba Laptop w/ Core 2 Duo @ 1.6GHz)
Fibonacci test for Fib(200000) Time: 2.44233 seconds
That’s a lot better than what we can get in Haskell using the detailed multicore approach. 32 seconds to calculate fib(45)? Please!
The Lesson:
- There’s more than one way to get a speedup in your code, and you should carefully weigh your options when writing. This algorithm can be bettered if you have phi calculated to many digits, or if you use a better recurrence, so I’m not claiming “optimal” results here!
- Throwing more cores at a problem does not always solve it best
- I found out that writing sensational headlines is actually pretty fun.
Popularity: 11% [?]
Reader Comments
I’ll see your linear C++, and raise you some linear Haskell:
main = print (fib 200000)
fib :: Int -> Integer
fib n = go n 1 1
where
go 1 a _ = a
go n a b = go (n-1) (a + b) a
On my machine, your code:
$ g++ fib.cpp -O2 -lgmp -lgmpxx -o fib
$ time ./fib
Fibonacci test for Fib(200000)
Time: 1.34055 seconds
./fib 1.32s user 0.02s system 98% cpu 1.360 total
And the Haskell translation:
$ ghc-6.8.1 -O2 -optc-O2 A.hs -o A
$ time ./A
2440914874035154859992549871532124086962886075690…
…622248628614359062
./A 0.48s user 0.01s system 98% cpu 0.504 total
Maybe you need more cores! (Or did I do something wrong?)
The Parallel haskell post you referenced specifically stated that they were using the *naive* algorithm in order to test ease of parallelization rather than that specific algorithm. Binet’s Formula, the Matrix Multiplication method will yield faster results than iteration for larger n. If you want an apples to apples comparison to your iterative method consider:
xor ax, ax
push ax
mov ax, 1
push ax
mov cx, 0x24 ; number of loops, in hex
crunch:
pop ax
pop bx
add sp, 4
add ax, bx
push ax
loop crunch
ret
from http://patrickyeon.blogspot.com/2007/11/holy-cannoli-here-comes-assembly.html
If I define the equivalent program:
> fibs = 1:1:(zipWith (+) fibs (tail fibs))
>
> main = do let x = fibs !! 200000 in print “done”
and compile it,
% ghc tmp.hs
% time ./a.out
“done”
./a.out 0.00s user 0.00s system 84% cpu 0.003 total
0 seconds!!
anyway if I shove a seq in there to force evaluation I get,
8.73s user 0.04s system 99% cpu 8.773 total
@dons:
You didn’t do anything wrong, but I had used the C++ interface instead of the C interface for legibility reasons. (there is some overhead involved)
Lisp !
http://jng.imagine27.com/articles/2007/11/29/dude-your-quad-cores-have-been-smoking-way-too-much-haskell