0

I am testing a memoized recursive version for finding the Fibonacci number at a given point (I'm using 50). The execution time in Java is instantaneous, while on Scala it takes around 65-67 seconds. This is is the Scala code: 

def fibonacciDP(array : Array[Long] , counter : Int) : Long = {
        if (array(counter) != 0L) array(counter)
        if (counter == 1 || counter == 2) 1L
         else {
            val result = fibonacciDP(array, counter - 1) + fibonacciDP(array, counter - 2)
            array(counter) = result
            result
        }
    }

This is the Java code: 

private static long fibonacciDP(long[] array, int counter) {
        if (!(array[counter] == 0L)) {
            return array[counter];
        }
        if (counter == 1 || counter == 2) return 1L;
        final long result = fibonacciDP(array,counter - 1) + fibonacciDP(array, counter - 2);
        array[counter] = result;
        return result;
    }

I test them like this in:
Scala: 

def main(args: Array[String]): Unit = {
    val counter = 50
    val array = Array.fill(counter+1){0L}
    val startTime = System.currentTimeMillis()
    println(startTime)
    val result = fibonacciDP(array,counter)
    println(result)
    val endTime = System.currentTimeMillis()
    println(endTime - startTime)
}

Java: 

public static void main(String[] args) {
    final int counter = 50;
    long[] array = new long[50+1];
    final long startTime = System.nanoTime();
    final long fiboNum = fibonacciDP(array,counter);
    final long endTime = System.nanoTime();
    System.out.println((endTime - startTime)/1000000);
}

Then I added the return keyword to the values inside the first two conditions in the Scala function, the speed of execution dropped to 4ms average (3-5ms range).
Why is there a difference in execution speeds?

Shankha057
  • 1,296
  • 1
  • 20
  • 38
  • 1
    specifically, you forgot the `return` before `array(counter)` in your first `if`. – Andrey Tyukin Apr 03 '19 at 15:48
  • Yes, I have explicitly written the `return` keyword everywhere possible after I was getting such strange results. Then the time dropped down to 4ms avg. Why is that even when Java gives instantaneous results? In Java, I've used the `System.currentTimeMillis()` method as well. But same result: 0. – Shankha057 Apr 03 '19 at 15:51
  • And what does this zero say? It's essentially a random number... You have to warm up the JVM, make sure that the GC does not interfere, and then run the method few million times on a quiet machine to get somewhat robust results. This zero contains zero information. Obviously, the actual value must be strictly larger than zero. I've added a duplicate link about the joy of microbenchmarking. – Andrey Tyukin Apr 03 '19 at 16:01
  • 1
    Also, your benchmarks are obviously broken, because you are invoking `println` *two times* between the System.currentTimeMillis. Since the `println` takes several orders of magnitude more time than your `fibonacci` method, your first measurement has truly nothing whatsoever to do with the performance of the method you wanted to benchmark. – Andrey Tyukin Apr 03 '19 at 16:04
  • Yes, I removed both the `println()` and now the Scala code shows 0 as well (which is a random number as you have mentioned above) – Shankha057 Apr 03 '19 at 16:07
  • It's just way too small. You at least would have to repeat the function invocation few million times, then calculate the average time. – Andrey Tyukin Apr 03 '19 at 16:09
  • The problem is that you're using implicit returns wrong. Try changing your second `if` in Scala to `else if`. – Brian McCutchon Apr 03 '19 at 16:24
  • I'm now gonna use JProfiler. End of story. A few million times? As in inside an loop that will execute for like a million times and then call the function inside it? – Shankha057 Apr 03 '19 at 16:46

0 Answers0