CODEWITHSUNDEEP
gogarbage-collectionpprof
Francis
Francis

Reputation: 53

Go GC responsible for 90% of CPU time

I'm writing a virtual machine for a simple, made-up programming language in Go. I'm using the profiler pprof to improve performance. I'm running the Fibonacci function in my made up language to test recursive functions.

func fib(n) {
    if n < 2 {
        return n
    } else {
        return fib(n-1) + fib(n-2)
    }
}
print fib(34)

When I run this it takes 14 seconds, in Python it takes 2 seconds. Here's an image from PProf. I've highlighted my actual program's function calls in green. They take 2 seconds, the other 12 seconds appears to be all Go's garbage collector. enter image description here Is there any way to figure out why the garbage collector is taking so much of the time?

Upvotes: 1

Views: 1148

Answers (2)

peterSO
peterSO

Reputation: 166529

It's your recursive algorithm which generates a combinatorial explosion. Use an iterative algorithm.

Try this iterative algorithm:

package main

import "fmt"

// fibonacci returns the Fibonacci number for 0 <= n <= 92.
// OEIS: A000045: Fibonacci numbers:
// F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1.
func fibonacci(n int) int64 {
    if n < 0 {
        panic("fibonacci: n < 0")
    }
    f := int64(0)
    a, b := int64(0), int64(1)
    for i := 0; i <= n; i++ {
        if a < 0 {
            panic("fibonacci: overflow")
        }
        f, a, b = a, b, a+b
    }
    return f
}

func main() {
    for _, n := range []int{0, 1, 2, 3, 90, 91, 92} {
        fmt.Printf("%-2d  %d\n", n, fibonacci(n))
    }
}

Playground: https://play.golang.org/p/_5CMHZm3Hlo

Output:

0   0
1   1
2   1
3   2
90  2880067194370816120
91  4660046610375530309
92  7540113804746346429

real    0m0.003s
user    0m0.002s
sys     0m0.000s

Reference :

The Fibonacci Sequence and Combinatorial Explosion

Upvotes: 2

torek
torek

Reputation: 487725

As icza noted in a comment, actually compiling and running this as Go code, it runs quite fast:

package main

import (
    "fmt"
    "time"
)

func fib(n int) int {
    if n < 2 {
        return n
    } else {
        return fib(n-1) + fib(n-2)
    }
}

func main() {
    s := time.Now()
    fmt.Println(fib(34))
    d := time.Now().Sub(s)
    fmt.Println("took", d)
}

$ go run fib.go
5702887
took 49.244697ms

(note: the above is sloppy: we should use int64, I was just lazy).

The Python3 variant:

import time
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

s = time.time()
print(fib(34))
print(f"took {time.time() - s}s")

takes a bit longer:

$ python3 fib.py
5702887
took 2.1027958393096924s

As peterSO notes, the recursive algorithm makes a lot of calls:

package main

import (
    "fmt"
    "time"
)

var calls int

func fib(n int) int {
    calls += 1
    if n < 2 {
        return n
    } else {
        return fib(n-1) + fib(n-2)
    }
}

func main() {
    s := time.Now()
    fmt.Println(fib(34))
    d := time.Now().Sub(s)
    fmt.Println("took", d, "to make", calls, "calls")
}

$ go run fib.go
5702887
took 53.328049ms to make 18454929 calls

(the extra few milliseconds are due to counting the calls). So Go ran 18.45 million calls in about 50 ms, and Python ran the same 18.45 million calls in about 2.1 s. Go took about 2.7 ns per call, and Python took about 114 ms per call.

Upvotes: 2

Related Questions