1
package main

import (
    "fmt"
    "runtime"
)

func main() {
    runtime.GOMAXPROCS(1)
    go spinner()
    const n = 45
    fibN := fib(n)
    fmt.Printf("\rFibonacci(%d) = %d\n", n, fibN)
}

func spinner() {
    for {
        for _ = range `-\|/` {
        }
    }
}

func fib(x int) int {
    fmt.Println(x)
    if x < 2 {
        return x
    }
    return fib(x-1) + fib(x-2)
}

After a few seconds, it stopped printing x in fib anymore. I deliberately use 1 processor to understand why it stops. Is the scheduler stuck and not rescheduling the goroutine running the fib anymore?

Bagas Wahyu Hidayah
  • 119
  • 2
  • 8
  • 2
    @icza I think its not the "When the main goroutine ends, your app ends as well" problem, I ran code with run time tracer, it seems the problem is golang scheduler with `fmt.Println` it never rechedule `spinner` after few calls to `fib` it maybe be due (I may well be wrong) but go's scheduler is partially preemptive not fully. Also `fib` algorithm has exponential complexity so call `fib` won't be returned that early. – Gaurav Dhiman Jan 04 '20 at 11:43
  • 1
    @GauravDhiman Yes, right. Goroutine scheduling is "out of your hands" without explicit synchronization, `spinner()` has a busy loop and the goroutine scheduler never switches back to the `main` goroutine. – icza Jan 04 '20 at 12:37
  • 1
    @gaurav-dhiman, in Go ≤ 1.13 it's not preemptive at all. 1.14 should be the first release when it will be "almost" preemptive, and the problem of tight loops should be solved. – kostix Jan 04 '20 at 12:41
  • 1
    Note that while there may be improvements for preempting loops coming up, a busy loop is almost always a programming error and should be avoided. Spinning a CPU at 100% rather than using a blocking mechanism is rarely what you want to do. – JimB Jan 04 '20 at 14:26
  • @JimB: except sometimes you _do_ need to do that (and 100% cpu usage is not a concern). I hope they leave us this option. – Sergio Tulentsev Jan 05 '20 at 08:43

1 Answers1

1

Is the scheduler stuck and not rescheduling the goroutine running the fib anymore?

Short answer: yes.

Longer answer: you aren't guaranteed that this will happen, even with just one CPU. The system could do an occasional reschedule on its own. It's just that the implementation on which you are testing this, doesn't.

As JimB notes in a comment, the kind of hard-spin-loop you have in spinner is ... unfriendly, at best. It should contain some method of releasing computing resources, such as spinning with time.After or time.NewTicker, or at the very least, call runtime.Gosched(). I imagine your original spinner was something like this, only without the time.NewTicker:

func spinner() {
    t := time.NewTicker(50 * time.Millisecond)
    for {
        for _, c := range `-\|/` {
            fmt.Print(string(c), "\b")
            <-t.C
        }
    }
}

With the ticker in place, the spinner spins pretty fast, but the program completes (despite the non-caching fib). Of course a smarter fib helps rather more:

var fibcache = map[int]int64{}

func fib(x int) int64 {
    if x < 2 {
        return int64(x)
    }
    r, ok := fibcache[x]
    if !ok {
        r = fib(x-1) + fib(x-2)
        fibcache[x] = r
    }
    return r
}

(I changed the return type to int64 for what I hope are obvious reasons.) Now we can find Fibonacci(90) = 2880067194370816120 in 0.00 seconds (rounded).

torek
  • 448,244
  • 59
  • 642
  • 775
  • All the infinite loop and the use of naive recursive `fib` was deliberate, as I was trying to understand why it stuck, for which using the faster solution (or using ticker), the problem didn't occur. Now I understand that when the scheduler runs the `spinner` goroutine, it never reschedules the `fib` anymore since it stuck in a loop. Thanks for the snippet anyway. – Bagas Wahyu Hidayah Jan 05 '20 at 08:50