Working with channels in a recursive function

[Oleku Konko]

Hello, I would like to know the best way to close a channel in a recursive function ? 

Here is a typical example is a simple function to generate all possible 1-3 letter words :

package main

import "fmt"

func main() {
    result := make(chan string)
    go words(3, "", result)
    for v := range result {
        fmt.Printf("%s\n", v)
    }

    fmt.Println("got here")
}

func words(length int , prefix string, result chan string) {
    if length < 1 {
        return
    }
    letter := ""
    for i := 97 ; i < 123 ; i++ {
        letter = fmt.Sprintf("%s%c", prefix, i)
        result <- letter
        words(length - 1, letter , result)
    }
}

- How do you effectively close result or is there a better way to achieve the same result ? 

- What the best way to increase performance when working   with eg go words(10, "", result) because   go words(length - 1, letter , result) can lead to too many goroutines 

[egon]

On Saturday, December 21, 2013 2:30:02 PM UTC+2, Oleku Konko wrote:

Hello, I would like to know the best way to close a channel in a recursive function ? 

Here is a typical example is a simple function to generate all possible 1-3 letter words :

package main

import "fmt"

func main() {
    result := make(chan string)
    go words(3, "", result)

go func(){

  words(3, "", result)

  close(result)

}()

[egon]

The parallel version, that avoids too many goroutines is a bit more complicated... http://play.golang.org/p/b-9x0UpuwW

+ egon

On Saturday, December 21, 2013 2:30:02 PM UTC+2, Oleku Konko wrote:

[Oleku Konko]

- Thanks, did not thinking about wrapping it in a closure 

- The parallel version is more complicated as expected, i would take my time to study it and see if i can simplify it.

[egon]

On Saturday, December 21, 2013 7:08:44 PM UTC+2, Oleku Konko wrote:

- Thanks, did not thinking about wrapping it in a closure 

- The parallel version is more complicated as expected, i would take my time to study it and see if i can simplify it.

Mostly, I would say no... I once already spent several days on it actually to get it fully correct and safe. I.e. everything there is by necessity.

Although, I now was able to remove the alldone, by using close signaling... http://play.golang.org/p/iOJySmEUP0

* the todo chan, is a easy way of implementing a semaphore... it's there to notify that there are new jobs and block items.

* mu is there to protect the internal queue and other variables

* active counts the number of active routines... this is to prevent worker death from starvation and to see when we are actually done

* queue simply manages the work queue

Maybe there is a simpler design, I could not find one... (i.e. one that is thread-safe and finishes all go-routines properly when done)

[egon]

... and by modifying, immediately made a mistake... :/

Here should be a fixed one http://play.golang.org/p/ZZQ5HCYfrn

[egon]

But, there is an alternate design using a condition variable http://play.golang.org/p/06v_0JiGNy

+ egon

[Oleku Konko]

Still very much intense than i expected .. thanks looking at the code at the moment 

[Dmitry Vyukov]

In such cases, you usually do parallel recursive decomposition until
you reach the required grain size:
http://play.golang.org/p/epvbA0vjZX

> --
> 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/groups/opt_out.

[egon]

Indeed, that would be a simpler solution for this problem.

Now to think of it, my problem was somewhat different... i.e. I didn't know in advance how deep some recursion branch went and potentially had to deal with the state going to several hunderd GBs; so I had a potential need for persisting the state... although I never actually got to the persisting part. The recursive parallel decomposition for me was hard to control... since I also needed to have a particular order, how to recurse... otherwise the 100GB+ went easily into 1TB+...

But yes, if your problems have predictable recursion, then that solution is better.

+ egon