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

Post by Erwin
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".

Post by Erwin
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

Post by Erwin
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.

Post by Erwin
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 }
}
return true

Post by Erwin
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)))
}

[Steven Blenkinsop]

Post by 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

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. :$

Post by Steven Blenkinsop

Post by 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

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
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 {
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
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
http://go-playground.appspot.com/p/XYh8G8KrY8

[Steven Blenkinsop]

Post by Steven Blenkinsop
Also, I made an implementation a while back using only func values and
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]

Post by 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"?

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.

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

Post by 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.

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.

[Kyle Lemons]

Post by 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

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