21 responses

  1. Valentino Volonghi
    November 30, 2007

    Remember to optimize lisp code for speed :)

    (defun fib (n)
    (declare (optimize speed (safety 0) (debug 0))
    (fixnum n))
    (if (<= (1- n) 0)
    n
    (the fixnum (+ (fib (- n 1)) (fib (- n 2))))))

    With this simple change the function should become 3 to 4 times faster, making lisp not that slow compared to haskell.

  2. Brian Adkins
    November 30, 2007

    Strange. With n=35, I got 3.9 seconds for Lisp and 6.9 seconds for Haskell.

    Linux airstream 2.6.20-16-386 #2 Thu Jun 7 20:16:13 UTC 2007 i686 GNU/Linux

    I’m running:
    Dual Core AMD Opteron(tm) Processor 270

    I just fired up the sbcl repl, pasted your Lisp code and changed 45 to 35 (I didn’t feel like waiting).
    n=34 => 5702887
    n=35 => 9227465
    Evaluation took:
    3.881 seconds of real time
    3.792237 seconds of user run time
    0.008 seconds of system run time
    0 calls to %EVAL
    0 page faults and
    134,584 bytes consed.
    NIL

    With Haskell, I pasted your code into a file and ran:
    ghc -o fib2 fib2.hs
    time ./fib2

    n=34 => 5702887
    n=35 => 9227465

    real 0m6.925s
    user 0m6.788s
    sys 0m0.024s

  3. Brian Adkins
    November 30, 2007

    Wow, I just read Valentino’s post and Lisp is about 4 times faster now :)

    n=34 => 5702887
    n=35 => 9227465
    Evaluation took:
    1.645 seconds of real time
    1.580099 seconds of user run time
    0.0 seconds of system run time
    0 calls to %EVAL
    0 page faults and
    142,728 bytes consed.
    NIL

    By the way, I really like how your comments show the country flag, operating system icon and browser icon. Is that a public theme?

  4. Antonio Cangiano
    November 30, 2007

    @Valentino: that’s cheating. 😛

    @Brian: It’s a WordPress plugin called Firestats.

  5. Jeremy Shaw
    November 30, 2007

    Brian: try, ghc -O2 -o fib2 fib2.hs

    No optimization is done by default. -O2 will enable all optimizations.

    j.

  6. Alec
    November 30, 2007

    You must declare the numbers in the Common Lisp version to be fixnums if you want it to be equivalent to the Haskell solution; Haskell is using unsigned integers, but without the fixnum declaration, Common Lisp is using bignums, the equivalent of Haskell’s Integer.

    If you don’t ask to optimize for speed, it’s very likely your Common Lisp compiler isn’t doing tail recursion.

    Your Common Lisp solution also definitely isn’t using both cores.

  7. Valentino Volonghi
    November 30, 2007

    No it’s not :). Haskell has mandatory static typing, lisp makes that optional and once you use it, common lisp generates asm code and executes that, that’s why it’s waaay faster :). Common Lisp is a wonderful wonderful language IMHO.

  8. Antonio Cangiano
    November 30, 2007

    @Brian: Try Jeremy’s suggestion. For the parallel program you can use:

    $ ghc Fib.hs -O2 -o fib –make -threaded
    $ time ./fib +RTS -N2

  9. Larbo McFly
    November 30, 2007

    “well sbcl, which supposedly uses both cores, though there is no documented proof of this”

    SBCL will use both cores if you write explicitly multithreaded code, which that isn’t (no idea if threads are supported on mac os x, either – I have mac hardware, but run linux on it exclusively). Automatic parallelisation is not an SBCL feature as far as I know.

    (Just a pity haskell’s syntax is so godawful compared to lisp’s.)

  10. Bill Mill
    November 30, 2007

    Also check out eigenclass’ analysis of the ASM generated by three compilers on this problem:

    http://eigenclass.org/hiki/legitimate-microbenchmarks

    and psykotic and others take that analysis further in the reddit comments:

    http://programming.reddit.com/info/61tc0/comments/c02kcpp

  11. Antonio Cangiano
    November 30, 2007

    Valentino wrote:
    > Common Lisp is a wonderful wonderful language IMHO.

    On this we entirely agree, and it’s fast too. Mine was a tongue in cheek reply to the Lisper who wrongly compared apples and oranges. :)

  12. w-g
    November 30, 2007

    – Include type declarations
    – Set optimizations on
    – Compile the functions using a fast Lisp compiler (SBCL or CMUCL)

    – If you use CMUCL, then use block compilation

    I tried both on my machine, and Lisp was several times faster.

  13. w-g
    December 1, 2007

    For both non-tail-recursive versions:

    Haskell (ghc with -O2):
    real 3m7.850s (187.85s)
    user 2m23.953s (143.95s)
    sys 0m1.188s

    Lisp (GCL with optimization turned on):
    real time : 137.860 secs
    run-gbc time : 117.470 secs
    child run time : 0.000 secs
    gbc time : 0.000 secs

    “Sorry Haskell…”

  14. Antonio Cangiano
    December 1, 2007

    Ahah, that’s cool w-g. With all the optimizations on, and using Valentino’s optimized version, I can see that Lisp is very fast. That’s very good. We knew already that the main compilers for Lisp and Haskell were very fast, just like OCaml and F# are too. But establishing which one is faster and for what applications, is beyond the reach of our silly test. :)

  15. Brian Adkins
    December 1, 2007

    Compiling the Haskell code with optimizations made a *huge* difference. The fastest of several runs w/o optimization was 6.552s and with optimization was 0.860s. With that, the Lisp code took 1.8 times as long to execute.

    Either one of those blows away Ruby which is what I typically code in. It took 95s :)

  16. Geir Aalberg
    December 14, 2007

    Guys,

    for precise benchmarking you should turn always off I/O during iterations. Running under clisp on my MacBook Pro (same config as yours), the recursive Fibonacci test takes 0.005539 sec for n=45, while turning off the call to the actual computation reduces it to 0.003004 sec, i.e. only a 45 % reduction in cpu time.

    Granted, some of this is startup overhead, but commenting out the format statement gives only a run time of 0.000125 sec, so unless it’s smart enough to optimize out those function calls this can be neglected.

  17. Mike Hansen
    December 26, 2007

    This nice thing about Python is that it has Cython ( http://www.cython.org ). The original Python code took 131s on my machine. The following is the conversion of that code to Cython:

    cdef fib(int n):
    if n == 0 or n == 1:
    return n
    else:
    return fib(n-1) + fib(n-2)

    def test(n):
    for i in range(n):
    print “n=%d => %d” % (i, fib(i))

    This code runs in 2.08 CPU seconds on my machine.

  18. Geir Aalberg
    January 2, 2008

    You might also find this comparative test between SBCL Lisp and GHC Haskell useful. The “recursive” test does a series of recursive computations including Fibonacci, and here SBCL is only 20 % slower:

    http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=sbcl&lang2=ghc

    Also, note the wise words on the front page:

    “How can we benchmark a programming language?
    We can’t – we benchmark programming language implementations.
    How can we benchmark language implementations?
    We can’t – we measure particular programs.”

  19. Isaac Gouy
    January 7, 2008

    Geir Aalberg wrote
    > this comparative test between SBCL Lisp and GHC Haskell

    And note all those SBCL “due to type uncertainty” warnings.

  20. Muha
    April 24, 2008

    Fastest:

    import Control.Monad
    import Text.Printf
    
    fibs :: [Integer]
    fibs = 0:1:zipWith (+) fibs (tail fibs)
    
    fib n = fibs !! n
    
    main = forM_ [0..45] $ \i -> printf "n=%d => %d\n" i (fib i)
    
  21. Austin
    August 13, 2014

    Simplest:
    f 0 a b = a
    f n a b = f (n-1) b (a+b)
    fibs n = f n 0 1

    calculate fibs 80000 in 2 Sec.

Leave a Reply

 

 

 

Back to top
mobile desktop