Benchmark Fibonacci in Java and Scala

[proyb2]

On my test, Java version took just 3 microsecond to compute but Scala version (Scala 2.10.1) took:

Scala commandline : 60564 microsecond
Scala IDE worksheet : 5500 microsecond
Scala REPL : 34 microsecond ( run on fib(40) more than once )

Is there an efficient code to improve my Scala code?

Scala Code:

object FibonacciGitHub {

def time[A](a: => A) = {
    val now = System.nanoTime
    val result = a
    val micros = (System.nanoTime - now) / 1000
    println("%d micro".format(micros))
    result
}

lazy val fib: Stream[BigInt] = {
    def loop(h: BigInt, n: BigInt): Stream[BigInt] = h #:: loop(n, h + n)
    loop(1, 1)
}

time{
fib(40)
}

}

Java Code:

public class Test {

    public static int fib(int n) {
        int prev1=0, prev2=1;
            for(int i=0; i<n; i++) {
                int savePrev1 = prev1;
                prev1 = prev2;
                prev2 = savePrev1 + prev2;
            }
        return prev1;
    }

    public static void main(String[] args) {
        long start = System.nanoTime();
        int result = fib(41); // 40+1 to get the correct result
        long time = System.nanoTime() - start;
        System.out.println(result+" result");
        System.out.println(time/1000);
        // System.out.println(count);
    }
}

[Sonnenschein]

Did you see https://groups.google.com/forum/?fromgroups=#!topic/scala-user/9FoSIzZGAgk?
Peter

[proyb2]

Tried other Iterative code from the link you mentioned, it fare at 200 ms slower than Java.

[HamsterofDeath]

the java code uses long, the scala code uses bigint - so it would be a miracle if they were equally fast

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Rex Kerr]

BigInt is not the same as int.

Int is the same as int.

Loading the entire environment (command line) is not the same as computing ~40 multiplications and additions.

You should actually get a few tens of nanoseconds for the 40th Fibonacci number if you do a proper benchmark (exclude all the extraneous work except for the computation and give the JVM a chance to compile it).

  --Rex

P.S.

scala> def fib(n: Int)(m: Long = 0, k: Long = 1): Long = if (n==0) m else fib(n-1)(k, m+k)
fib: (n: Int)(m: Long, k: Long)Long

scala> thyme.pbench(fib(40)())
Benchmark (327660 calls in 36.38 ms)
  Time:    23.05 ns   95% CI 23.01 ns - 23.08 ns   (n=20)
res8: Long = 102334155

P.P.S. Use ScalaMeter or Google Caliper for similar benchmarking.

--

[Erik Osheim]

On Sat, Mar 16, 2013 at 11:05:59AM -0400, Rex Kerr wrote:
> P.P.S. Use ScalaMeter or Google Caliper for similar benchmarking.

+100

Rex is right, these kinds of ad-hoc benchmarks don't prove very much.
If you want to know how fast the code will run in production, you need
to allow warmup and such.

It's always possible to write Scala code like Java, so if you are
worried that some Java code is faster than Scala you can always try
writing "Java in Scala" and test it out:

def fib(n: Int): Int = {
var prev1 = 0
var prev2 = 0
var i = 0
while (i < n) {
val savePrev1 = prev1

prev1 = prev2
prev2 = savePrev1 + prev2

i += 1
}
prev1
}

That runs in exactly the same time as Java. Of course, once you get
benchmarking working you'll observe that this ugly code is no faster
than the much nicer:

def fib(n: Int): Int = {
@tailrec def loop(n: Int, a: Int, b: Int): Int =
if (n == 0) a else loop(n - 1, b, a + b)
loop(n, 0, 1)
}

Finally, since Int will overflow on the 47th Fibonacci number, it's
probably wiser to benchmark with BigInteger, or at least Long (which
overflows on the 93rd Fibonacci number).

-- Erik

[proyb2]

Not bad, manage to reduce to 13 microsecond on Scala Worksheet with tail recusion.

Ok, will run on ScalaMeter or Caplier.