A Golang Enabled Pattern

Bruce Ediger

The Go programming language has a unique, built-in concurrency model that can make some processing much easier.

Have one goroutine do some (probably recursive) work. It puts results on a channel. The main goroutine reads results from the channel and possibly does some filtering on those results, like output unique values.

I used this pattern in a number of programs:

The art of using this technique comes in deciding what to have the “worker” goroutine do, and what to have the main goroutine do. In some of these I have the worker put all results on the channel, and the main routine outputs only unique results. In others, the main goroutine keeps track of a maximum or most special result, and outputs that when the worker has finished.

The following example is from an implementation of the old finding the max depth of a binary tree problem.

The main thread creates an appropriately typed Go channel. It passes the channel to a second thread (goroutine). The second thread traverses a binary tree (another input to the second thread), putting each leaf node along with its tree depth, on the channel. When it completes the traverse, the second thread closes the channel.

The main thread reads leaf nodes and accompanying depth from the channel. When the second thread closes the channel, the main thread can print the deepest node it got. The technique simplifies the recursive function that traverses a binary tree: it does not have to track the deepest node so far, or return anything, but only write leaf nodes and depths to a channel.

        ch := make(chan *deepNode, 5)
        go findDepth(root, ch)
        maxDepth := 0
        var deepest tree.Node
        for d := range ch {
            if d.depth > maxDepth {
                maxDepth = d.depth
                deepest = d.node
            }
        }
        fmt.Printf("Max depth %d, node value at depth %v\n", maxDepth, deepest)

Go channels can be read from until they’re closed using the range construct. Because this method needs the channel to stay open until the binary tree traverse finishes, there’s an initial function that starts a recursive traverse in the true recursive traversal function. The initial function closes the channel.

func findDepth(root tree.Node, ch chan *deepNode) {
    realFindDepth(root, 0, ch)
    close(ch)
    return
}

func realFindDepth(node tree.Node, depth int, ch chan *deepNode) {
    if node.IsNil() {
        return
    }

    if node.LeftChild().IsNil() && node.RightChild().IsNil() {
        ch <- &deepNode{node: node, depth: depth}
        return
    }

    realFindDepth(node.LeftChild(), depth+1, ch)
    realFindDepth(node.RightChild(), depth+1, ch)
}

This is extraordinarily similar to Linux programs that separate the work into processes that each have a clearly defined function. This method takes advantage of peculiarities of Go’s channels.

Inside any given program, this technique is similar to Python’s generators. Since you can use Go’s range builtin to loop over reading from an open channel, the equivalence is close.