A Tour of Go, Exercise: Equivalent Binary Trees

[Erwin]

Hello peoples,

I'm working my way through the tour online, which I find an excellent idea, great way to learn, hands on!

I wondered if I could solve the binary tree exercise so that it would handle trees of unknown size, and this is what I came up with, is there a cleaner way?

Or more efficient?

package main

import (

    "fmt"

    "tour/tree"

)

// inorder depth-first tree traversal

func Walk(t *tree.Tree, ch chan int) {

    if t.Left != nil {

        Walk(t.Left, ch)

    }

    

    ch <- t.Value  // process node

    

    if t.Right != nil {

        Walk(t.Right, ch)

    }

}

// walk the full tree, close output channel when done

func FullWalk(t *tree.Tree, ch chan int) {

    Walk(t, ch)

    close(ch)

}

func Same(t1, t2 *tree.Tree) bool {

    ch1 := make(chan int)

    go FullWalk(t1, ch1)

    ch2 := make(chan int)

    go FullWalk(t2, ch2)

    

    for {

        v1, ok1 := <-ch1

v2, ok2 := <-ch2

if !ok1 && !ok2 {  // no more nodes in trees

   break

}

if ok1 != ok2 {    // trees with different number of nodes

   return false

}

        if v1 != v2 {

   return false

}

    }

    return true

}

func main() {

    fmt.Println("Trees equivalent?", Same(tree.New(1), tree.New(2)))   

}

[Kyle Lemons]

That's more or less the way I solved it, before I realized that the trees were going to be the same size to begin with.  Just a few things you could to make the code more concise (some of it improves readability, some of it doesn't):

// inorder depth-first tree traversal

func Walk(t *tree.Tree, ch chan int) {

I usually have my students check for null trees first, then recurse on both left and right unconditionally.  This is a direct transliteration of one recursive definition of a tree: "nothing or a piece of data with left and right trees".

 

    if t.Left != nil {

        Walk(t.Left, ch)

    }

    

    ch <- t.Value  // process node

    

    if t.Right != nil {

        Walk(t.Right, ch)

    }

}

 

I embedded what you have as Walk within what you have as FullWalk using a closure.  Something like:

func Walk(t *tree.Tree, ch chan int) {

  defer close(ch)

  var walk func(t *tree.Tree)

  walk = func(t *tree.Tree) {

    if t == nil { return }

    walk(t.Left)

    ch <- t.Value

    walk(t.Right)

  }

  walk(t)

}

It makes it somewhat more concise, and doesn't expose the "inner workings" of the walk to the outside world where it might be (ab)used out of context.

// walk the full tree, close output channel when done

func FullWalk(t *tree.Tree, ch chan int) {

    Walk(t, ch)

    close(ch)

}

func Same(t1, t2 *tree.Tree) bool {

    ch1 := make(chan int)

    go FullWalk(t1, ch1)

    ch2 := make(chan int)

you could do this on the same line as:

ch1, ch2 := make(chan int), make(chan int)

if you are so inclined.

 

    go FullWalk(t2, ch2)

    

    for {

If you really wanted to cut some lines out of this, you could do

v1, v2, ok1, ok2 := 0, 0, true, true

for ok1 && ok2 {

   v1, ok1 = <-ch1

   v2, ok2 = <-ch2

   if ok1 != ok2 || v1 != v2 { return false }

[Steven Blenkinsop]

On Mon, Oct 17, 2011 at 3:56 PM, Erwin <snes...@gmail.com> wrote:

Hello peoples,

I'm working my way through the tour online, which I find an excellent idea, great way to learn, hands on!

I wondered if I could solve the binary tree exercise so that it would handle trees of unknown size, and this is what I came up with, is there a cleaner way?

Or more efficient?

package main

import (

    "fmt"

    "tour/tree"

)

// inorder depth-first tree traversal

func Walk(t *tree.Tree, ch chan int) {

    if t.Left != nil {

        Walk(t.Left, ch)

    }

    

    ch <- t.Value  // process node

One thing to consider is that, if the trees can have different sizes or different contents, then Same will abort before having exhausted all the nodes in at least one of the trees. In this case, this statement will block forever trying to send values that are no longer being drained. While it is blocking forever, it will hold onto its stack and any head data it references, even though it will never have any impact on the rest of your program. In this toy program this is fine, since the program exits immediately after the comparison.

You can deal with this is multiple ways. One is to use a done channel to signal to any still-running goroutines that their services are no longer required:

func Walk(t *tree.Tree, ch chan int, done chan struct{}) {

  defer close(ch)

  var walk func(t *tree.Tree)

  walk = func(t *tree.Tree) {

    if t == nil { return }

    walk(t.Left)

    select {

    case ch <- t.Value:

    case <-done:

        os.Goexit() // stop the current goroutine cleanly

    }

    walk(t.Right)

  }

  walk(t)

}

to modify Kyle's example. Then, in Same, just create a done channel and pass it to both calls to Walk, then `defer close(done)` to ensure the done channel is closed before Same exits. This way, any Walks waiting on the select statement will receive a value on done and exit.

Gustavo Niemeyer recently posted an interesting way of handling this kind of situation with a new package: http://blog.labix.org/2011/10/09/death-of-goroutines-under-control

Also, I made an implementation a while back using only func values and thought it was neat. I have no idea how the performance compares:

http://go-playground.appspot.com/p/XYh8G8KrY8

[Steven Blenkinsop]

That should of course be "runtime.Goexit", of course. :$

[Steven Blenkinsop]

On Mon, Oct 17, 2011 at 8:02 PM, Steven Blenkinsop <stev...@gmail.com> wrote:

Also, I made an implementation a while back using only func values and thought it was neat. I have no idea how the performance compares:

http://go-playground.appspot.com/p/XYh8G8KrY8

As fortune would have it, there's a logic error in the function implementation I posted, introduced while quickly rewriting it for the code walk. It should be: http://go-playground.appspot.com/p/nAvxKT7H3M

I apologize for the noise. 

[Erwin]

Thanks Steven and Kyle for your suggestions. I like the idea of having the closure in Walk(), it minimizes the number of functions visible from the outside. And indeed, it seems better to first check if the node is not nil, before doing anything with it... Lastly, introducing a quit channel to stop any blocked goroutine will be a good way to avoid spilling recourses in a long running program. Are "lingering" goroutines like this the sources of what some refer to as go "memory leaks"? 

[Kyle Lemons]

Thanks Steven and Kyle for your suggestions. I like the idea of having the closure in Walk(), it minimizes the number of functions visible from the outside. And indeed, it seems better to first check if the node is not nil, before doing anything with it... Lastly, introducing a quit channel to stop any blocked goroutine will be a good way to avoid spilling recourses in a long running program. Are "lingering" goroutines like this the sources of what some refer to as go "memory leaks"?

It's definitely one way in which your base memory footprint can increase unbounded, but it's by no means the only source.  The map memory pinning bug actually had a noticeable effect on one of the three binaries in my current project, so that might have been the source in some cases too.  Often, it's just people keeping data around that they don't need that has some indirect reference to memory they don't expect to have remained.

~K

[Steven Blenkinsop]

This is essentially a memory leak, since the goroutine, as well as any memory it uniquely references, is no longer accessible to the program but isn't cleaned up.

Reply from off list:
On Oct 18, 2011, at 3:53 PM, Erwin <snes...@gmail.com> wrote:
> I understand. In this specific case, with the Walk(), what memory is exactly referenced? Just the single tree node that was given as the parameter? Or, because of the recursion, all the nodes that are used in the Walk() s that are being executed? I figure it's the latter case. Plus the channel?

The node, all it's descendants, the channel, and the goroutine's stack are all pinned by the goroutine.

[Kevin Ballard]

I seem to recall a while ago hearing a proposal whereby if a goroutine is blocked on a channel, and contains the only remaining reference to that channel (e.g. all other references are gc'd), then the whole goroutine can be cleaned up because it can never continue. Was that suggestion rejected, or is it just something that hasn't been done yet? Granted, it's not a panacea; two goroutines that are deadlocked on each other would live forever because the channel is now referenced from to separate goroutines, and I don't think we need Go's runtime to try and do sophisticated inter-goroutine deadlock analysis.

-Kevin

--
Kevin Ballard
http://kevin.sb.org
kbal...@gmail.com

[Kyle Lemons]

I seem to recall a while ago hearing a proposal whereby if a goroutine is blocked on a channel, and contains the only remaining reference to that channel (e.g. all other references are gc'd), then the whole goroutine can be cleaned up because it can never continue. Was that suggestion rejected, or is it just something that hasn't been done yet? Granted, it's not a panacea; two goroutines that are deadlocked on each other would live forever because the channel is now referenced from to separate goroutines, and I don't think we need Go's runtime to try and do sophisticated inter-goroutine deadlock analysis.

-Kevin

I personally hope it never happens.  I might be okay with that being considered a fatal program error, but that also seems very poor.  I would really like to be able to figure out where my hanging goroutines are (e.g. with ^\ or similar; I regularly do this and try to account for all active goroutines), but if you garbage collect them I can no longer tell where they were hanging.  It's a programmer error, and one that should not be hidden from the programmer.

~K