Recursive GO vs Scala

Question

The following Scala code complete in 1.5 minutes while the equivalent code in GO finish in 2.5 minutes.
Up to fib(40) both take 2 sec. The gap appear in fib(50)
I got the impression the GO, being native, should be faster then Scala.

Scala

def fib(n:Int):Long = {
    n match {
        case 0 => 0
        case 1 => 1
        case _ => fib(n-1) + fib(n-2)
    }
}

GO

func fib(n int) (ret int) {
    if n > 1 {
        return fib(n-1) + fib(n-2)
    }
    return n
}

Scala optimization?
Golang limitation?

As "My other car is a cadr" said the question is "how come Scala is faster than GO in this particular microbenchmark?"

Forget the Fibonacci lets say I do have a function that require recursion.
Is Scala superior in recursion situations?

Its probably an internal compiler implementation or even Scala specific optimization.
Please answer just if you know.

Go in loop run 15000000000 in 12 sec

func fib(n int) (two int) {
    one := 0
    two = 1
    for i := 1; i != n; i++ {
        one, two = two, (one + two)
    }
    return
}

I don't see any optimization, it is exponential, that same example of recursive fibonacci that's been used to show how **not** to write recursive functions. Seems, the effect is because of some implementation nuances, maybe garbage collection, maybe memory available to the process (say, for some reason in scala it is enough for the task and in go - not). I'd check memory consumpition at the peak. — dmitry, Jul 17 '14 at 05:19
Since Scala is JIT compiled, it could do some ad-hoc memoization after a few recursive calls. I've had the JVM do some incredibly good optimizations with regards to loop unrolling. — Linear, Jul 17 '14 at 06:03
Although go code is compiled to machine code, but the runtime still does all memory and stack management so it's basically the same with JVM. I'm not surprise JVM is better optimized than go. — chendesheng, Jul 17 '14 at 08:18

score 3 · Answer 1 · answered Jul 17 '14 at 09:01

For Go, use iteration not recursion. Recursion can be replaced by iteration with an explicit stack. It avoids the overhead of function calls and call stack management. For example, using iteration and increasing n from 50 to 1000 takes almost no time:

package main

import "fmt"

func fib(n int) (f int64) {
    if n < 0 {
        n = 0
    }
    a, b := int64(0), int64(1)
    for i := 0; i < n; i++ {
        f = a
        a, b = b, a+b
    }
    return
}

func main() {
    n := 1000
    fmt.Println(n, fib(n))
}

Output:

$ time .fib
1000 8261794739546030242
real    0m0.001s
user    0m0.000s
sys 0m0.000s

Use appropriate algorithms. Avoid exponential time complexity. Don't use recursion for Fibonacci numbers when performance is important.

Reference:

Recursive Algorithms in Computer Science Courses: Fibonacci Numbers and Binomial Coefficients

We observe that the computational inefficiency of branched recursive functions was not appropriately covered in almost all textbooks for computer science courses in the first three years of the curriculum. Fibonacci numbers and binomial coefficients were frequently used as examples of branched recursive functions. However, their exponential time complexity was rarely claimed and never completely proved in the textbooks. Alternative linear time iterative solutions were rarely mentioned. We give very simple proofs that these recursive functions have exponential time complexity.

Recursion is an efficient technique for definitions and algorithms that make only one recursive call, but can be extremely inefficient if it makes two or more recursive calls. Thus the recursive approach is frequently more useful as a conceptual tool rather than as an efficient computational tool. The proofs presented in this paper were successfully taught (over a five-year period) to first year students at the University of Ottawa. It is suggested that recursion as a problem solving and defining tool be covered in the second part of the first computer science course. However, recursive programming should be postponed for the end of the course (or perhaps better at the beginning of the second computer science course), after iterative programs are well mastered and stack operation well understood.

The question wasn't "how can I calculate fibonacci faster". The question was "how come Scala is faster than GO in this particular microbenchmark". — My other car is a cadr, Jul 17 '14 at 09:44
@Myothercarisacadr: Read the question carefully. The question asks about the jump in time from fib(40) to fib(50), from 2 seconds to 1.5 to 2.5 minutes. This answer addresses that issue for Go. It's likely a similar answer for Scala. — peterSO, Jul 17 '14 at 10:32
Well you should always use iteration if you can - recursion is the lazy programmers tool. — samthebest, Jul 17 '14 at 10:41
I don't fully agree. You can get the same complexity with recursion, since you can [cache the F(N-2) term](http://garrettwyrwas.com/scala-fibonacci-revisited-and-recursed/). — bluenote10, Jul 17 '14 at 11:12

score 0 · Answer 2 · edited May 23 '17 at 12:13

The Scala solution will consume stack, since it's not tail recursive (the addition happens after the recursive call), but it shouldn't be creating any garbage at all.

Most likely whichever Hotspot compiler you're using (probably server) is just a better compiler, for this code pattern, than the Go compiler.

If you're really curious, you can download a debug build of the JVM, and have it print out the assembly code.

Recursive GO vs Scala

2 Answers2