Limiting count of goroutines (work pool) when goroutines are created recursively

[Artjom Simon]

Dear Go community,

I'm diving into Go's concurrency patterns and trying to implement a recursive fibonacci tree algorithm in Go.

The problem I face is trying to limit the goroutines that are run concurrently. I want them to be limited to the number of CPUs available to minimize unneccessary context switches and other overhead, like RAM usage for the maintenance of a goroutine, when a recursive algorithm can't know how much work will have to be done. Imagine a recursively implemented solution where by walking a tree, you discover that a leaf could spawn N subtrees (=goroutines).

Coming from playing with C and OpenMP, I'd enclose a function in #pragma omp task shared(x) and #pragma omp taskwait and have GOMP take care of creating a thread pool with as many threads as CPUs available, and distribute the worker tasks among the threads. But how would I create a similar mechanism in Go?

I'm aware that I can control the number of threads using runtime.GOMAXPROCS(runtime.NumCPU()) - but I'd like to actually limit the number of goroutines running concurrently.

See for example, this implementation: http://play.golang.org/p/JUIAPm-CIf

In order to prevent this example from spawning 10945 goroutines, i've tried several implementations of a goroutine worker pool, jere is a simple example: http://play.golang.org/p/FjjbOr30cw

This example deadlocks, however, since the work pool crunches on incoming functions in order (range) using a buffered channel which blocks after receiving 2 tasks, but the tasks themselves are blocking since they wait for a result that will be made available much further down the recursion queue, which themselves will never reach the work pool.
Of course, lowering the input from 20 to 10 and enlarging the NewWorkerPool to buffer 100 functions prevents that deadlock.

I'm curious how you would approach this problem - I feel that by preventing the worker pool from seeing incoming work as a FIFO queue, I'd have to implement a scheduler which actively tries to get work that can be computed, and discards goroutines that are blocked by putting them to sleep - but I'm somehow feeling I'd be forcing Go into something that it's not designed for, and that could be solved much more elegantly.

What am I missing?

Thank you for your time,
Artjom

[Ian Lance Taylor]

On Fri, Oct 3, 2014 at 1:18 PM, Artjom Simon <artjom...@gmail.com> wrote:
>
> The problem I face is trying to limit the goroutines that are run
> concurrently.

You can control the number of goroutines that run concurrently via
runtime.GOMAXPROCS.

Don't worry about creating new goroutines. goroutines are cheap.

> I'm aware that I can control the number of threads using
> runtime.GOMAXPROCS(runtime.NumCPU()) - but I'd like to actually limit the
> number of goroutines running concurrently.

GOMAXPROCS does not control the number of threads. It controls the
number of goroutines that execute concurrently, just as you requested.

> This example deadlocks, however, since the work pool crunches on incoming
> functions in order (range) using a buffered channel which blocks after
> receiving 2 tasks, but the tasks themselves are blocking since they wait for
> a result that will be made available much further down the recursion queue,
> which themselves will never reach the work pool.
> Of course, lowering the input from 20 to 10 and enlarging the NewWorkerPool
> to buffer 100 functions prevents that deadlock.

I didn't really try to understand your code, but you seem to be
describing a complex dependency graph that requires an unknown queue
size. Just create all the goroutines you need. 10945 goroutines
takes something like 80K in 1.3, 40K on tip. I doubt it will be your
bottleneck.

Don't worry about minimizing goroutines until you know it is a
problem.

Ian

[Emily Maier]

On Fri, Oct 03, 2014 at 01:18:01PM -0700, Artjom Simon wrote:
> Dear Go community,
>
> I'm diving into Go's concurrency patterns and trying to implement a
> recursive fibonacci tree algorithm

> <https://mitpress.mit.edu/sicp/chapter1/node13.html> in Go.

> --
> You received this message because you are subscribed to the Google Groups "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

I don't see how the deadlock relates to GOMAXPROCS or the number of
running goroutines. The Go scheduler is putting the worker goroutines to
sleep when they block on the channel. But none of them receive anything
until the n - 1 and n - 2 workers return, so the worker pool has to be
able to create the entire Fibonacci recursive tree at once.

Emily