Dude, your quad-cores have been smoking way too much Haskell !
Posted by ungraspiness Fri, 30 Nov 2007 05:26:00 GMT
Some Haskell fans seem impressed with better performance for a fibonacci function compared with similar implementations in Ruby and Python. They should be.
Read this and this before going on.
Impressive. Yea I thought so too until I implemented a fib function of my own in Lisp and ran it on SBCL.
Here it is…
(defun printfib-trec (start end)
(format t "n=~D => ~D~%" start (fib-trec start))
(if (< start end)
(printfib-trec (+ start 1) end)))
(defun fib-trec (n)
"Tail-recursive Fibonacci number function"
(labels ((calc-fib (n a b)
(if (= n 0)
a
(calc-fib (- n 1) b (+ a b)))))
(calc-fib n 0 1)))* (time (printfib-trec 0 45))
...
n=43 => 433494437
n=44 => 701408733
n=45 => 1134903170
Evaluation took:
0.001 seconds of real time
8.66e-4 seconds of user run time
4.4e-5 seconds of system run timeMy machine is a core2 duo macbook. i.e. it’s similar to a dual core machine.
Now it gets even better here are the results for N=4500
* (time (printfib-trec 0 4500))
...
n=4498 => 4752485956810555875004869018963973043700525724009578868769474882879459154152204647915407885135917631883990751157075912405221725368578720671564885897475897464613262304334914241607212435329497497641975738086751054186028251736658640131563596639794912789288873499340565150498450487979214802149192686689502839297300024458433225040572133069627134796358948692382679582705607173927112950805086075483639678885680596072818462793625622001172877975597935926640708898109961081915885811381688288593609679366923395036172748038315089504487795839374129751161426896402825970560364499274889268094208129756388749789034972452896098894495061580172690522720566378084685514727191994472473978536748311552532810887686013014142033821544140905176979343962968937988421450684068500158256897979615387686994353406906126123537769868642652059566362453067042981495901311000274164675176218086106464588110191710522184013092019809003619950257701727043382807151105254869074540999
n=4499 => 7689683809176044218107840158125230568446917722620919869236097185282672128990041547590451591499923310831823312141560648669244546575977267500013883217226532696996235625233074842634247978888031960169238969830083697466087304886911697471293091037341927771010057257419268694905456568117577378610866026860700484139627056952202998275203723635146181775748103435107099441981319375329968495793847287994466423823519958759013902933218530884486180862708252747927806488609582304095221977753080257381254319632253228943480013647285929110384030236906149951249019234788386174626368178393351733619384777746723301965464502113374050814595527544612527282323355098641401340340217066221028727128338402433420088106126843822136543545984881453537808419762831343814403375221726100769180787258588643276099557741697382968654545681825708651265429233690200167736105425793517509595122050585308615226674843578205297740460920468000168395676735878604229024852582106840990153001
n=4500 => 12442169765986600093112709177089203612147443446630498738005572068162131283142246195505859476635840942715814063298636561074466271944555988171578769114702430161609497929567989084241460414217529457811214707916834751652115556623570337602856687677136840560298930756759833845403907056096792180760058713550203323436927081410636223315775856704773316572107052127489779024686926549257081446598933363478106102709200554831832365726844152885659058838306188674568515386719543386011107789134768545974863998999176623979652761685601018614871826076280279702410446131191212145186732677668241001713592907503112051754499474566270149709090589124785217805043921476726086855067409060693502705665086713985952898993812856836278577367529022358714787763725800281802824825905794600927437685238204030963093911148603509092192315550468360710831791686757243149232006736793791674270298268671415079814785035288727481753552940277003788345934437605647611832003687361710064694000
Evaluation took:
8.698 seconds of real time
4.731282 seconds of user run time
0.361252 seconds of system run timeYes it only took under 9 seconds running in slime/emacs. Would probably be closer to 8 seconds on the command line.
As for the argument of Haskell being the easiest platform to benefit from multiple cores due to it’s parallel and concurrent libraries. The evidence contradicts that. No changes were required to the Lisp code above to have sbcl use all cores on my system. What would be easier ?
Also the readability of the Lisp code is far simpler.
Oops. Sorry Haskell…
BTW – Haskell is not faster than a C implementation either(at least one that imitates Lisp) but Haskell would be far more readable beyond a trivial C implementation like this—>
#include <stdio.h>
unsigned long fib_trec(unsigned long n, unsigned long a, unsigned long b) {
if (n==0) return 0;
if (n==1) return a;
if (n==2) return b;
return fib_trec(n-1, b , a+b);
}
int main() {
int i;
for (i=0; i <= 45; i++) {
printf("n=%d => %d\n", i, fib_trec(i, 1, 1));
}
return 0;
}
$ time bin/fib-c
...
n=43 => 433494437
n=44 => 701408733
n=45 => 1134903170
real 0m0.004s
user 0m0.001s
sys 0m0.003s
UPDATE : Thanks Don and the other guys for giving me a hard time for using an O(n) algorithm !
Maybe I’ve accepted the following quote for too long now ;-)
“The key to performance is elegance, not battalions of special cases.” - Jon Bentley and Doug McIlroy