I am a beginner in Golang
I was reading about concurrency in Go from here.
Things were going fine until I was presented with the question on the 8th slide.
The question is: Find out whether two given Binary trees are equivalent or not.
My Approach: Do an Inorder traversal, save the values from both the trees in a slice and compare them.
Here is my solution: [incomplete]
package main
import (
"fmt"
"golang.org/x/tour/tree"
)
// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
if t != nil {
Walk(t.Left, ch)
ch <- t.Value
Walk(t.Right, ch)
}
}
// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
ch1 := make(chan int)
ch2 := make(chan int)
go func() {
fmt.Println("executing first go routing")
Walk(t1, ch1)
fmt.Println("closing channel [ch1]")
close(ch1)
}()
go func() {
fmt.Println("executing second go routing")
Walk( t2, ch2 )
fmt.Println("closing channel [ch2]")
close(ch2)
}()
shouldContinue := true
var continue1, continue2 bool
for shouldContinue {
select {
case r1, ok1 := <-ch1:
fmt.Println("[ch1] [rcvd]", r1)
continue1 = ok1
case r2, ok2 := <-ch2:
fmt.Println("[ch2] [rcvd]", r2)
continue2 = ok2
}
shouldContinue = continue1 || continue2
}
return true
}
func main() {
Same(tree.New(1), tree.New(1))
}
I know that goroutines are cooperatively scheduled and one and completely block another one if it is looping or doing computation continuously. So I expected that for the output, It would first receive the values from either of channels, close it and then it would receive values from another channel and then close. Once both are closed, the for loop will break.
To my surprise, the first go routine never gets scheduled. Here is the output I am receiving:
executing second go routing
[ch2] [rcvd] 1
[ch2] [rcvd] 2
[ch2] [rcvd] 3
[ch2] [rcvd] 4
[ch2] [rcvd] 5
[ch2] [rcvd] 6
[ch2] [rcvd] 7
[ch2] [rcvd] 8
[ch2] [rcvd] 9
[ch2] [rcvd] 10
closing channel [ch2]
[ch2] [rcvd] 0
Can anyone explain what is going on here? Once channel2 is closed and second go routine finishes, why doesn't the first one gets executed?
Any help would be appreciated. Thank you.
UPDATE:
I googled about breaking out of the channels and I found a SO question here.
According to which, I updated my solution as follows:
package main
import (
"fmt"
"golang.org/x/tour/tree"
// "time"
)
// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
// time.Sleep(time.Millisecond)
if t != nil {
Walk(t.Left, ch)
ch <- t.Value
Walk(t.Right, ch)
}
}
// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
ch1 := make(chan int)
ch2 := make(chan int)
go func() {
fmt.Println("executing first go routing")
Walk(t1, ch1)
fmt.Println("closing channel [ch1]")
close(ch1)
}()
go func() {
fmt.Println("executing second go routing")
Walk( t2, ch2 )
fmt.Println("closing channel [ch2]")
close(ch2)
}()
for {
select {
case r1, ok1 := <-ch1:
fmt.Println("[ch1] [rcvd]", r1)
if !ok1 {
ch1 = nil
}
case r2, ok2 := <-ch2:
fmt.Println("[ch2] [rcvd]", r2)
if !ok2 {
ch2 = nil
}
}
if ch1 == nil && ch2 == nil {
break
}
}
return true
}
func main() {
Same(tree.New(1), tree.New(1))
}
Which gives the exact output which I thought the first snippet would:
executing second go routing
[ch2] [rcvd] 1
[ch2] [rcvd] 2
[ch2] [rcvd] 3
[ch2] [rcvd] 4
[ch2] [rcvd] 5
[ch2] [rcvd] 6
[ch2] [rcvd] 7
[ch2] [rcvd] 8
[ch2] [rcvd] 9
[ch2] [rcvd] 10
closing channel [ch2]
[ch2] [rcvd] 0
executing first go routing
[ch1] [rcvd] 1
[ch1] [rcvd] 2
[ch1] [rcvd] 3
[ch1] [rcvd] 4
[ch1] [rcvd] 5
[ch1] [rcvd] 6
[ch1] [rcvd] 7
[ch1] [rcvd] 8
[ch1] [rcvd] 9
[ch1] [rcvd] 10
closing channel [ch1]
[ch1] [rcvd] 0
I am now even more confused about what is going on.
Once channel2 is closed, why doesn't the first one gets executed?
Channels are not executed. What gets executed over and over is your select. Note that both cases can execute always, no matter if the channel is closed or not. So it is okay for select to select the second case which id did and you aborted. (Your abort condition looks fishy: You are done once both channels are closed i.e. if both ok1 and ok2 are false).
Do not think of select as a "goroutine scheduling facility" per se. It is not. It will randomly select one of the runnable cases. If all your cases are of the form val, ok := <- ch than all are runnable and select may always select the second. Or the first, or ...
[Second Solution] I am now even more confused about what is going on.
You abort condition is different. You break once both channels are nil which happens once both channels have been closed. This is different from your first solution because the first breaks once any one channel gets closed.
The problem with concurrency here is not the goroutine scheduling but solely the abort condition of your for loop doing the select. They differ from the first and the second and the first is fundamentally wrong as it stops once any channel is exhausted.