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
}
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.
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.