Thanks for clarifying which tools and compiler flags you're using, however, there are some very serious flaws remaining.

Just to double check: you are still measuring different algorithms in each language, and also measuring different aspects of the total runtime.

To repeat: the programs you present aren't implementing the same functions. In particular, the Clojure version is using a loop, while the Haskell version is using memoization. 

Here, for example, is the iterative version you use in the Clojure example, translated to Haskell:

limit = 10^999

loop a b i
     | b < limit = loop b (a+b) (i+1)
     | otherwise = i

main = print (loop 0 1 1) 

This is a different algorithm, so comparing it against say, a memozing version *is meaningless*.

Secondly, what are you trying to measure? Total runtime? Runtime of just the inner loop excluding startup time?

The Clojure version doesn't seem to be doing IO, and you're not including its startup time, while, e.g. the Haskell version includes startup time *and* IO!

Unless they're doing *the same algorithm* and the *same total runtime*  -- the comparisons on this post will continue to be meaningless!

Could you please clarify what exactly you're trying to measure? I would suggest you state precisely:

 * iterative or memozing fibonacci (specify the required algorithm)
 * total runtime, as measured by one external tool

I haven't run the Scala code, but the page where that code snippet is posted seems to be saying the answer to Euler 25 is 3321, which is incorrect.

http://ideone.com/Tt4Yw0Ys

I presume you ignored the F# one-liner in your follow-up because you don't have Mono installed on your Linux box, so you couldn't compare performance on the same machine?

Just to follow up, using a statistically robust mechanism based on kernel density functions (see the Criterion package for robust benchmarking), the iterative Haskell solution measures out at at mean execution time of 0.819 ms, when we exclude all startup costs (as you do in the Clojure example), with a standard deviation over 20 runs of 39.29665 us.

This just illustrates how silly it is to time different algorithms, in different ways.

Hi Lau,

I am extremely sorry for the incorrect code (The Scala version). Here's a corrected version (translation of Aaron's Ruby version actually) : http://ideone.com/pvNdSwq3

Please update your blog post accordingly. Thanks.

Have you considered a solution like this in ruby?

limit = 10**999
i = 0
n, m = 0, 1
while n < limit do
    n, m = m, n + m
    i += 1
end
puts i

Dons: I get similar results to you for the looping version, but unlike what I would have thought the list one is much faster. Any idea why? I think I used Criterion correctly...

http://codepad.org/vO0sCnLF

(Sorry for the tangent - I don't think fibs is really worth benchmarking, but I'm interested in the work GHC does on the code.)

@domor: criterion is likely caching that fibs list, since it's a CAF. so you're not reevaluating it each time.

Here's a Scala version based on the first algorithm:

val limit = BigInt(10) pow 999
lazy val fib: Stream[BigInt] = 0 #:: 1 #:: fib.zip(fib.tail).map { case(x,y) => x + y }
fib takeWhile (_ < limit) length

Regarding the scala version I just posted. Stream doesn't have zipWith at the moment so I used zip and map. If zipWith was added fib would be like:

lazy val fib: Stream[BigInt] = 0 #:: 1 #:: fib.zipWith(fib.tail) { _ + _ }

I certainly agree with what Don has said above about comparing the same algorithm and the same runtime. As Scala and Clojure are both running in the JVM I just tried a comparison between both algorithms. I've written what should be basically the same method for recording time. Averaging over 10,000 iterations, and including a warm up of 10,000 as well, as suggested by Dhananjay in the previous post.

The code is here:
http://gist.github.com/314194
http://gist.github.com/314192

On this machine I get:

Clojure lazy-cat:  5.1545
Clojure loop: 1.7102

Scala memoized stream: 2.523
Scala while loop: 1.4752

And just in case... the above Scala is Scala 2.8. If anyone needs 2.7 then Stream.cons needs to be used rather than #:: in which case fib is:

lazy val fib: Stream[BigInt] = Stream.cons(0, Stream.cons(1, fib.zip(fib.tail).map { case(x,y) => x + y }))

Cheers

Hi all,

Time has been a little short lately, so I apologize for the slowness of replies both past and future :)

@Rahul: No need to apologize, in fact its me who is guilty for not double checking your code, something I usually do before posting on this blog. I'll pay closer attention next time.

@Don: You point out serious flaws and I agree. This benchmark, as well as every other microbenchmark I've seen to date, can give you a little indicator of the performance of a language and the algorithm chosen, but no more than that. For all JVM based languages HotSpot needs to be controlled in order to see whats actually going on with the code and to ensure that takes a lot more work than a fun little exercise like this justifies. The numbers were supposed to be shadows, nothing more nothing less. For this post, different algorithms are used in both posts, for the reason of showing off various styles and approaches to the problem. Those who have supplied code with a built in timer for the actual work, will see those timings. JVM based languages aren't penalized for the JVM startup/shutdown time. Its true that the Haskell timing also includes I/O, but when we're talking about unscientific timings which are below 10 milliseconds, it would be (for me at least) a waste of time to improve on the purity of the results. 

@Rest:: Real benchmarking is hard work and takes some thorough preparations - To do so in a several different languages is not trivial and therefor beyond the scope of this post. Take what you see as indicators of performance as well as a demonstration of how these 4 different languages can be used to approach a single problem from different angles.

-Ruby

This is more or less the same, although it seems to be a bit faster than the current implementation, might be worth checking out.

limit = 10**999
tmp = [0,1]
while tmp.last < limit 
 tmp << tmp.shift+tmp.first
end
p tmp.last

Here is an (almost 1:1) CL adaption of your Clojure code:

(defun euler25 ()
  (labels ((rec (a b i)
                (if (< b #.(expt 10 999))
                    (rec b (+ a b) (1+ i))
                  i)))
    (rec 0 1 1)))

DHL> (time (euler25))
(EULER25) took 16 milliseconds (0.016 seconds) to run 
                    with 2 available CPU cores.
During that period, 31 milliseconds (0.031 seconds) were spent in user mode
                    0 milliseconds (0.000 seconds) were spent in system mode
 1,048,848 bytes of memory allocated.

On my machine this took 29ms in average on CCL/win32, the clojure version 23.65ms.

Then, I gave SBCL a try, which blew both out of the water:

  seconds  |     consed    | calls |  sec/call  |  name  
-----------------------------------------------------------
     8.836 | 1,048,826,608 | 1,000 |   0.008836 | EULER25
-----------------------------------------------------------
     8.836 | 1,048,826,608 | 1,000 |            | Total

Sorry, but my last post got messed up by an angle bracket.

Danlei - Does it change your results of you move the calculation of limit, #.(expt 10 999) outside of the labels block?

It doesn't make much of a difference:


(defun euler25 ()
  (let ((limit (expt 10 999)))
    (labels ((rec (a b i)
                  (if (< b limit)
                      (rec b (+ a b) (1+ i))
                    i)))
      (rec 0 1 1))))


Is a wee bit slower:


  seconds  |     consed    | calls |  sec/call  |  name  
-----------------------------------------------------------
     9.228 | 1,048,835,080 | 1,000 |   0.009228 | EULER25
-----------------------------------------------------------
     9.228 | 1,048,835,080 | 1,000 |            | Total

estimated total profiling overhead: 0.01 seconds
overhead estimation parameters:
  2.18e-7s/call, 1.022e-5s total profiling, 5.8200003e-6s internal profiling


I would have used the aequivalent of #. in the Clojure versiont, too (namely #=), but it wouldn't work with .pow.

The interesting thing about the Clojure version is: It DOES get some really good timings (downto about 8ms), but in between, there often are calls around 50ms, sometimes even up to ~400ms.

Maybe that is due to HotSpot's dynamic optimization, but I really don't know anything about that.

Even tho "Microbenchmarking sucks", I'd like to see how Python performs at this task, using, e.g. one of the algorithms at:
    http://en.literateprograms.org/Fibonacci_numbers_%28Python%29

Anyone?

We are already at Euler 215. ;) http://clojure-euler.wikispaces.com/Problem+215

> This benchmark, as well as every other microbenchmark I’ve seen to date, can give you a little indicator of the performance of a language and the algorithm chosen, but no more than that. 

Not even that: If you vary algorithms and languages at the same time, you cannot deduce much meaningful information from the run times. As dons pointed out, the measurements are even less useful since you also vary the amount of processing you measure (input/output, startup time) at the same time as well, and in this case (microbenchmarks) input/output and startup time can be significant parts of the benchmark run time.

The microbenchmark might be a useful performance indicator if you used the same code with the same compiler and varied one flag at a time; perhaps even if you used the same code and different compilers, though care needs to be taken to keep compiler settings similar in some meaningful way.

The microbenchmark might be also a useful performance indicator if you compared two implementations using the same compiler and swapped only the underlying data structure.

But by varying just about everything from program to program, it becomes pointless to even tell us the run times; as presented here, they merely spread misinformation.
After a few posts like this one starts to feel that these numbers have only one purpose: To give the article's arbitrarily chosen ranking of languages by performance an air of authority.

For example: In both this post and the previous post the Clojure implementations just so happen to be the ones using an efficient approach to solving the problem, while the other languages typically implement Fibonacci in clearly slower ways (sometimes absurdly so).

I'm confident that you could have come up with a Clojure program that is slower than the three programs presented here -- but you chose not to. Instead, you end the article with the statement:

> 5 msecs. Hooray! It’s a new record!

Yes, it is a record: of all the unrelated runtimes you gave, this is the lowest.