Recursive tree building in Goroutines

Question

I want to build and display a tree of linked issues using the github.com/xlab/treeprint package. I have a working version, but it doesn't use go-routines, and seems like a good candidate.

The tree part may be irrelevant, though maybe if I return different values from my function, I could build it in a different way.

func main {
    tree := treeprint.New()
    recurseTreeFetching(fetcher, tree, *issueID)
    fmt.Println(tree.String())
}

func recurseTreeFetching(fetcher Fetcher, tree treeprint.Tree, issueID string) {
    issues := fetcher.fetchIssues(issueID)
    if len(issues) == 0 {
        return
    }
    for i := 0; i < len(issues); i++ {
        currIssueID := issues[i].Key
        currBranch := tree.AddBranch(currIssueID)
        recurseTreeFetching(fetcher, currBranch, currIssueID)
    }
}

This works, but it's pretty slow. I've looked at answers like this: /recursive-goroutines-what-is-the-neatest-way-to-tell-go-to-stop-reading-from-ch, but I'm struggling to get it to work.

I'm not limiting depth, nor checking for already added nodes.

I've tried "sprinkling on some concurrency." But the function deadlocks. Any guidance or fixes?

func main {
    tree := treeprint.New()
    var ch chan int
    go recurseTreeFetching(fetcher, tree, *issueID, ch)
    tocollect := 1
    for n := 0; n < tocollect; n++ {
        tocollect += <-ch
    }
    fmt.Println(tree.String())

}

func recurseTreeFetching(fetcher Fetcher, tree treeprint.Tree, issueID string, ch chan int) {
    issues := fetcher.fetchIssues(issueID)
    if len(issues) == 0 {
        return
    }
    ch <- len(issues)
    for i := 0; i < len(issues); i++ {
        currIssueID := issues[i].Key
        currBranch := tree.AddBranch(currIssueID)
        go recurseTreeFetching(fetcher, currBranch, currIssueID, ch)
    }
}

looks to me like you're not instantiating channels. Does your error say goroutine 1 [chan send (nil chan)]: ? Include your error here. — erik258
– erik258, Commented Mar 21, 2021 at 1:28
not reproducable. insufficient code to demonstrate issue met by OP. — user4466350
– user4466350, Commented Mar 21, 2021 at 11:31

erik258 · Accepted Answer · 2021-03-21 01:32:33Z

1

I think I've been able to reproduce your error, though it's just a guess based on your code (because you didn't provide your actual error message).

The tl;dr here is that you have to make(chan int) your channel. The error message mentions "deadlock" but the real issue is that the channel is still nil.

package main
import(
  "log"
)


func summer(src <-chan int, result chan<- int64) {
  var sum int64
  var count int
  for i := range src {
    sum += int64(i)
    count++
  }
  log.Printf("summer: summed %d ints: %d", count, sum)
  result<-sum
}

func main() {
  var src chan int
  var dest chan int64
  go summer(src,dest)
  for i:=0; i<1000;i++{
    src<-i
  }
  close(src)
  <-dest
}

$ go run main.go
fatal error: all goroutines are asleep - deadlock!

goroutine 1 [chan send (nil chan)]:
main.main()
    /Users/danfarrell/git/stackoverflow/66727888/main.go:22 +0x66

goroutine 6 [chan receive (nil chan)]:
main.summer(0x0, 0x0)
    /Users/danfarrell/git/stackoverflow/66727888/main.go:10 +0x59
created by main.main
    /Users/danfarrell/git/stackoverflow/66727888/main.go:20 +0x41
exit status 2

But if I add make(...) to the channels:

package main
import(
  "log"
)


func summer(src <-chan int, result chan<- int64) {
  var sum int64
  var count int
  for i := range src {
    sum += int64(i)
    count++
  }
  log.Printf("summer: summed %d ints: %d", count, sum)
  result<-sum
}

func main() {
  var src = make(chan int)
  var dest = make(chan int64)
  go summer(src,dest)
  for i:=0; i<1000;i++{
    src<-i
  }
  close(src)
  <-dest
}

then the same code works:

$ go run main.go
2021/03/20 20:31:01 summer: summed 1000 ints: 499500

answered Mar 21, 2021 at 1:32

erik258

16.5k2 gold badges32 silver badges47 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

icicleking Over a year ago

Instantiating the channel is a good start, thanks. But the program still pauses and never completes. Though it does go through more loops. I think the issue is I end up never leaving the for loop.

icicleking · Accepted Answer · 2021-03-21 02:42:52Z

0

Thanks to help here I got on the right track. I also took a hint form another thread and added a depth variable, and send true to done to keep the program moving.

func recurseTreeFetching(fetcher Fetcher, tree treeprint.Tree, issueID string, done chan bool, depth int) {
    issues := fetcher.fetchIssues(issueID)
    if len(issues) == 0 {
        return
    }
    depth--
    if depth == 0 {
        done <- true
        return
    }

    for i := 0; i < len(issues); i++ {
        currIssueID := issues[i].Key
        currBranch := tree.AddBranch(currIssueID)
        go recurseTreeFetching(fetcher, currBranch, currIssueID, done, depth)
    }
}

answered Mar 21, 2021 at 2:42

icicleking

1,0851 gold badge16 silver badges41 bronze badges

1 Comment

icicleking Over a year ago

This isn't exactly right, if my depth is greater than the tree the program hangs...

icicleking · Accepted Answer · 2021-03-21 15:30:21Z

Adding another answer because it uses a different method.

The problem with my first solution is if we never reach the depth variable, we never get a done <- true, so the function never "wraps up". If this is not called deadlock, what is it called?

The idea of the following code is as follows:

maintain a number of function calls being executed, these are equivalent to the number of children (including the initial "tree-top").
once a function execution finishes, subtract that from the number.
once we get to zero, we've exhausted our function calls and can print the tree

Potential problems: If one branch takes significantly longer than another, I believe the code could subtract the children value to 0 before the slow branch is complete.

func recurseTreeFetching(fetcher Fetcher, tree treeprint.Tree, issueID string, ch chan int, depth int) {
    issues := fetcher.fetchIssues(issueID)
    if len(issues) == 0 {
        // delete this child
        ch <- -1
        return
    }
    depth--
    if depth == 0 {
        // delete this child
        ch <- -1
        return
    }
    // add the number of child issues, minus the current one
    ch <- len(issues) - 1

    for i := 0; i < len(issues); i++ {
        currIssueID := issues[i].Key
        currBranch := tree.AddBranch(currIssueID)
        go recurseTreeFetching(fetcher, currBranch, currIssueID, ch, depth)
    }
}

And the client code:

    go recurseTreeFetching(fetcher, tree, *issueID, ch, *depth)
    childs := 1
    for childs > 0 {
        childs += <-ch
    }

    fmt.Println(tree.String())

Here's a test that I thought would demonstrate the bug, however it displays correctly, so maybe this works.

type fakeUnEvenFetcher struct {
}

func (f fakeUnEvenFetcher) fetchIssues(issueID string) []Issue {
    var array []Issue
    // initial return
    if issueID == "a" {
        b := Issue{Key: "b"}
        array = append(array, b)
        c := Issue{Key: "c"}
        array = append(array, c)
    }
    // branch b quickly returns three results
    if issueID == "b" {
        d := Issue{Key: "d"}
        array = append(array, d)
        e := Issue{Key: "e"}
        array = append(array, e)

    }
    // branch c returns two returns after 3 seconds
    if issueID == "c" {
        time.Sleep(3 * time.Second)
        f := Issue{Key: "f"}
        array = append(array, f)
        g := Issue{Key: "g"}
        array = append(array, g)
        h := Issue{Key: "h"}
        array = append(array, h)
    }

    return array
}

func TestUnEvenFetch(t *testing.T) {
    fetcher := fakeUnEvenFetcher{}
    tree := treeprint.New()
    var ch = make(chan int)

    go RecurseTreeFetching(fetcher, tree, "a", ch, 3)
    childs := 1
    for childs > 0 {
        childs += <-ch
    }

    fmt.Println(tree.String())
}

This prints:

.
├── b
│   ├── d
│   └── e
└── c
    ├── f
    ├── g
    └── h

Which is my expected result, but not the failure I was expecting.

Collectives™ on Stack Overflow

Recursive tree building in Goroutines

3 Answers 3

1 Comment

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related