Fibonacci function performance compare between clojure and scala

[gerr...@gmail.com]

Clojure's

(defn fib [n]
(if (or (zero? n) (= n 1))
1
(+ (fib (dec n) ) (fib (- n 2)))))

(time (fib 36))

"Elapsed Time: 10475.325226 msecs"
24157817

Scala's

def fib(n:Int):Int=if (n==0||n==1)1 else fib(n-1)+fib(n-2)
def time(cal: =>Int)={
val beginTime=System.currentTimeMillis
cal
val endTime=System.currentTimeMillis
println(endTime-beginTime)
}
fib(36)
res70:Int=24157817
time(fib(36))
263

Both not tail recursive,both running on Repl (scala's interpreter),but
the difference between two is huge
10475~263
My box : Intel core2 cpu 1.86G，2G mem
Clojure and scala both latest build from svn

any ideas?

[Rastislav Kassak]

Just use type hint in Clojure version and you'll see quite a
difference in performance.

Your scala version is completely optimized / crippled to integers
(maybe even unboxed), so there is no dynamic runtime overhead.

IMHO, this kind of microbenchmarks are just good for finding general
weak points of particular language / implementation and have nothing
in common with real world performance.
As you said in this case - it's not tail recursive at least.

[Parth Malwankar]

On Oct 19, 7:49 pm, "gerryx...@gmail.com" <gerryx...@gmail.com> wrote:
> Clojure's
>
> (defn fib [n]
> (if (or (zero? n) (= n 1))
> 1
> (+ (fib (dec n) ) (fib (- n 2)))))
>
> (time (fib 36))
>
> "Elapsed Time: 10475.325226 msecs"
> 24157817
>
> Scala's
>
> def fib(n:Int):Int=if (n==0||n==1)1 else fib(n-1)+fib(n-2)
> def time(cal: =>Int)={
> val beginTime=System.currentTimeMillis
> cal
> val endTime=System.currentTimeMillis
> println(endTime-beginTime)}
>
> fib(36)
> res70:Int=24157817
> time(fib(36))
> 263
>

I am not a scala expert but I suspect scala Int maps directly to
java ints.

In clojure, the number are boxed and checked by default IIRC.
This would roughly correspond to BigInt in scala.

For clojure, you could coerce ints to native java types using
(int ..).
Also, unchecked-dec could be used.
Doing this should make the code as fast as java or scala.
There was some discussion along these lines here:
http://groups.google.com/group/clojure/browse_thread/thread/4274ce8bd44664ef#

That said, for most practical uses the default behavior
should be fast enough. Its not considered idiomatic to
use coersion and unchecked operation unless absolutely
necessary.

Parth

[gerr...@gmail.com]

Here is coersion version for Clojure

(defn fib [n]
(let [n (int n)]

(if (or (zero? n) (= n 1))
1

(+ (fib (dec n) ) (fib (- n 2))))))

(time (fib 36))
"Elapsed time 8848.865149"

not much better and how to type hint for a int type?

[gerr...@gmail.com]

Scala is sure to use java primitive int type underline, i.e value
type and boxed to java Integer when necessarily

But why not Clojure auto make this ?




gerry


On Oct 19, 11:31 pm, "gerryx...@gmail.com" <gerryx...@gmail.com>
wrote:

[Lauri Oherd]

There is also a faster way to calculate fibonacci numbers in Clojure
(code taken from from
http://en.wikibooks.org/wiki/Clojure_Programming#Lazy_Fibonacci):

(defn fib-seq []
((fn rfib [a b]
(lazy-cons a (rfib b (+ a b))))
0 1))

user=> (time (take 38 (fib-seq)))
"Elapsed time: 0.032965 msecs"
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
10946 17711 28657 46368 75025 121393 196418 317811 514229 832040
1346269 2178309 3524578 5702887 9227465 14930352 24157817)

Lauri

2008/10/19 gerr...@gmail.com <gerr...@gmail.com>:

[gerr...@gmail.com]

This lazy cached calculate is wonderful ,but i think the benefit from
it mostly due to cache .....

On Oct 19, 11:56 pm, "Lauri Oherd" <lauri.oh...@gmail.com> wrote:
> There is also a faster way to calculate fibonacci numbers in Clojure

> (code taken from fromhttp://en.wikibooks.org/wiki/Clojure_Programming#Lazy_Fibonacci):

>
> (defn fib-seq []
> ((fn rfib [a b]
> (lazy-cons a (rfib b (+ a b))))
> 0 1))
>
> user=> (time (take 38 (fib-seq)))
> "Elapsed time: 0.032965 msecs"
> (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
> 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040
> 1346269 2178309 3524578 5702887 9227465 14930352 24157817)
>
> Lauri
>

> 2008/10/19 gerryx...@gmail.com <gerryx...@gmail.com>:

[Meikel Brandmeyer]

Hello,

Am 19.10.2008 um 17:56 schrieb Lauri Oherd:

> There is also a faster way to calculate fibonacci numbers in Clojure
> (code taken from from
> http://en.wikibooks.org/wiki/Clojure_Programming#Lazy_Fibonacci):
>
> (defn fib-seq []
> ((fn rfib [a b]
> (lazy-cons a (rfib b (+ a b))))
> 0 1))
>
> user=> (time (take 38 (fib-seq)))
> "Elapsed time: 0.032965 msecs"
> (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
> 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040
> 1346269 2178309 3524578 5702887 9227465 14930352 24157817)

This timing is wrong. Since take returns a lazy sequence
you only get the timing for the call to take. The sequence
is forced later on when the Repl prints it.

The correct way is to force the evaluation with doall.

user=> (time (take 38 (fib-seq)))

"Elapsed time: 0.055 msecs"
...
user=> (time (doall (take 38 (fib-seq))))
"Elapsed time: 0.3 msecs"
...

Sincerely
Meikel