tag:blogger.com,1999:blog-8688058551295946514.post4945505975267040962..comments2023-05-21T07:33:43.212-07:00Comments on Daily rant: Holy shmoly Haskell doesn't smoke Python away (that much)Filoxhttp://www.blogger.com/profile/07052058313681392060noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-8688058551295946514.post-39623986790287990502008-04-01T05:43:00.000-07:002008-04-01T05:43:00.000-07:00@stephanThe whole point was to compare the same pr...@stephan<BR/>The whole point was to compare the same program (approach) in different languages... That is why I used the naive Fibonacci instead of some iterative approach. I could have easily used the formula for the n-th Fibonacci number directly if I wanted fast codeFiloxhttps://www.blogger.com/profile/07052058313681392060noreply@blogger.comtag:blogger.com,1999:blog-8688058551295946514.post-15365015823891474902008-04-01T05:17:00.000-07:002008-04-01T05:17:00.000-07:00But with python you wouldn't go for a recursive ap...But with python you wouldn't go for a recursive approach like in haskell thats just crazy and creates a senseless big stack.<BR/><BR/>You either do:<BR/><BR/>def fib(n):<BR/> if n < 2:<BR/> return n<BR/> else:<BR/> a = 0<BR/> b = 1<BR/> x = 0<BR/> for i in xrange(2,n):<BR/> x = a + b<BR/> a = b<BR/> b = x<BR/> return x<BR/><BR/>for i in xrange(36):<BR/> print "n=%d => %d" % (i, fib(i))<BR/><BR/>Or you would cache:<BR/><BR/>fib_dict = {}<BR/><BR/>def fib(n):<BR/> if n > 1:<BR/> try:<BR/> x = fib_dict[n]<BR/> return x<BR/> except:<BR/> x = fib(n-1) + fib(n-2)<BR/> fib_dict[n] = x<BR/> return x<BR/> else:<BR/> return n<BR/><BR/>for i in range(36):<BR/> print "n=%d => %d" % (i, fib(i))<BR/><BR/>Both versions will easily compete or even outperform the parallel Haskell version.stephanhttps://www.blogger.com/profile/00413055202196348708noreply@blogger.comtag:blogger.com,1999:blog-8688058551295946514.post-89375944983605877762007-12-06T23:15:00.000-08:002007-12-06T23:15:00.000-08:00@filoxThanks for the clarification.The main proble...@filox<BR/><BR/>Thanks for the clarification.<BR/><BR/>The main problem to address though is that you're testing for speed, yet didn't compile the Haskell with the optimiser on.<BR/>Without optimisations, I get similar numbers to you:<BR/><BR/> $ ghc A.hs -o A<BR/> $ time ./A<BR/> ...<BR/> n=35 => 9227465<BR/>./A 3.76s user 0.09s system 99% cpu 3.861 total<BR/><BR/>However, compiling with -O2, as all production Haskell does:<BR/><BR/><BR/> $ ghc -O2 A.hs -o B -no-recomp<BR/> $ ./B<BR/> ...<BR/> n=35 => 9227465<BR/>./B 0.48s user 0.01s system 99% cpu 0.492 total<BR/><BR/>We get the same numbers in my original post: still a 50x speedup over serial Python, and 36x over the parallelised version.<BR/><BR/>If we then go ahead an parallelise the Haskell code at the top level -- here's one parallel top level:<BR/><BR/> main = mapM_ putStr $<BR/> parMap rnf (\i -> printf "n=%d => %d\n" i (fib i)) [0..35]<BR/><BR/>We get good multicore speedups again:<BR/><BR/> $ time ./A +RTS -N2<BR/> ...<BR/> n=35 => 9227465<BR/> ./A +RTS -N2 0.28s user 0.00s system 158% cpu 0.174 total<BR/><BR/>I'd argue that the result is much the same as I originally stated: 50x speedups over Python, much more so than the 6x you report, and remaining easier to parallelise.Don Stewarthttps://www.blogger.com/profile/08476737262404343154noreply@blogger.comtag:blogger.com,1999:blog-8688058551295946514.post-80739852412273763172007-12-04T07:48:00.000-08:002007-12-04T07:48:00.000-08:00Don:you are right, this is just top level parallel...Don:<BR/>you are right, this is just top level parallelization. It is different from the Haskell program, but my goal was just to show that some parallelization is also possible in Python... I will try to write a different program that will parallelize in the similar way to that in Haskell when I get some free time.<BR/>adept:<BR/>I used ghc 6.8.1, there is an error in the code that was later corrected. Again, when I get some time I'll run this corrected code.Filoxhttps://www.blogger.com/profile/07052058313681392060noreply@blogger.comtag:blogger.com,1999:blog-8688058551295946514.post-3009727510252610382007-12-03T12:51:00.000-08:002007-12-03T12:51:00.000-08:00And regarding "pseq: not in scope" - you have to h...And regarding "pseq: not in scope" - you have to have ghc 6.8.1 to use thatADEpthttps://www.blogger.com/profile/16464838579540251181noreply@blogger.comtag:blogger.com,1999:blog-8688058551295946514.post-69089040826908019932007-12-03T08:30:00.000-08:002007-12-03T08:30:00.000-08:00And you parallelise the code differently, I think?...And you parallelise the code differently, I think? (Spawning one thread for each top level fib call?).<BR/><BR/>Can you clarify if each recursive fib call is parallelised, or just the initial call for some value of N?<BR/><BR/>Doing just the top level parallelisation is much easier, but is a different program to the one presented. (Good to see its possible in python though!).Don Stewarthttps://www.blogger.com/profile/08476737262404343154noreply@blogger.comtag:blogger.com,1999:blog-8688058551295946514.post-73624285098721442462007-12-03T08:18:00.000-08:002007-12-03T08:18:00.000-08:00That code is compiled without optimisations:ghc -O...That code is compiled without optimisations:<BR/><BR/>ghc -O2<BR/><BR/>Or:<BR/><BR/>ghc -O2 -optc-O<BR/><BR/>The <A HREF="http://cgi.cse.unsw.edu.au/~dons/blog/2007/11/29#smoking-4core" REL="nofollow">followup post</A> explored the use of `par` and `pseq` some more, and corrected<BR/>a bug in the original parallelisation strategy.Don Stewarthttps://www.blogger.com/profile/08476737262404343154noreply@blogger.comtag:blogger.com,1999:blog-8688058551295946514.post-33536264504118217952007-12-03T08:11:00.000-08:002007-12-03T08:11:00.000-08:00This comment has been removed by the author.Don Stewarthttps://www.blogger.com/profile/08476737262404343154noreply@blogger.com