Equivalent Binary Trees Exercise, achieving the "concurrency"

Question

I'm solving the exercise from A Tour of Go, Equivalent Binary Tree. This exercise requires one to implement a Walk function which is supposed to walk a tree and send all values orderly from the tree to a channel.

The exercise statement states:

... We'll use Go's concurrency and channels to write a simple solution.

Reading that line, I think it is challenging to implement the Walk in a way that it launches a goroutine for each left/right subtree and enabling the Walk to run faster (regarding time complexity) than non-concurrent version. Let me explain in more detail with codes.

This is my early code for Walk:

func Walk(t *tree.Tree, ch chan int) {
    defer close(ch)
    if t == nil { return }
    
    lch, rch := make(chan int), make(chan int)
    go Walk(t.Left, lch)
    for v := range lch { ch <- v }

    ch <- t.Value

    go Walk(t.Right, rch)
    for v := range rch { ch <- v }

    return
}

It surely uses goroutines, but effectively isn't different from just traversing without goroutines because the ealry for v := range lch { ... } delays go Walk(t.Right, rch) until it ends.

It does not make any difference to move up go Walk(t.Right, rch):

func Walk(t *tree.Tree, ch chan int) {
    defer close(ch)
    if t == nil { return }
    
    lch, rch := make(chan int), make(chan int)
    go Walk(t.Left, lch)
    go Walk(t.Right, rch)

    for v := range lch { ch <- v }
    ch <- t.Value
    for v := range rch { ch <- v }
}

go Walk(t.Left, lch) walks along the entire left subtree (rooted on the blue) and values sent from lch are received immediately.

go Walk(t.Right, rch) tries to walk along as well but gets blocked as ch <- t.Value on the left-most node (the red) of the right subtree does so and propagates the blocking. This state persists until for v := range rch { ch <- v } is reached.

My question : How to implement Walk in a way that goroutines (corresponding to left or right) avoid being blocked by ch <- t.Value as much as possible?

user_3912693 · Answer

A buffer (e.g. a buffered channel) is required for the values from the right subtree as they must persist until the values preceding those (<-lch and t.Value) are consumed.

Preparing a buffer for a subtree, the size of which are unknown, has several implications

If a buffered channel, make(chan int, N), is used, choosing N is critical. If N happens to be too small for a subtree, the goroutine for the subtree blocks too soon. If it is too large, the memory is unnecessarily wasted.
Implementing the custom channel with auto-resizing buffer may be one solution, but it introduces additional complexity and overhead. I don’t know whether the penalties neutralize the performance gain or not. It depends on how the custom channel manages its internal buffer or how the pool of those are managed.

In my opinion, there is no simple and universal solution for this kind of problem, "traverse a random, unknown tree with concurrency squeezed out".

Equivalent Binary Trees Exercise, achieving the "concurrency"

1 Answers