How to create recursive concurrent tree search in go

Question

Is there a proper way to implement concurrency inside recursive tree search in go?

The following code shows basic recursive tree search for a tree of nodes having id and children properties. If I find a result I can close the channel but in case there is no result how to deal with that?

// Node is a struct containing int field ID and []*Node field Children.
type Node struct {
    ID       int
    Children []*Node
}

// Find search for a record by id inside an array of records
func Find(node *Node, id int) *Node {

    if node.ID == id {
        return node
    }

    for _, c := range node.Children {
        found := Find(c, id)
        if found != nil {
            return found
        }
    }

    return nil
}

Answer 1

here is a simple and stupid benchmark that i hope will be helpful to OP to better understand impacts of simplistic implementations of concurrent programming.

package main_test

import (
    "sync"
    "testing"
)

func SearchNonConcurrently(v int, mySlice []int) int {
    for idx, i := range mySlice {
        if i == v {
            return idx
        }
    }
    return -1
}

func SearchConcurrently(v int, mySlice []int) int {
    var wg sync.WaitGroup
    wg.Add(len(mySlice))
    res := make(chan int)
    for idx, i := range mySlice {
        go func(idx, i int) {
            defer wg.Done()
            if i == v {
                res <- idx
            }
        }(idx, i)
    }
    go func() {
        wg.Wait()
        close(res)
    }()
    idx, ok := <-res
    if !ok {
        return -1
    }
    return idx
}

func BenchmarkSearchNonConcurrently(b *testing.B) {
    mySlice := make([]int, 10000)
    mySlice[len(mySlice)-1] = 1
    for n := 0; n < b.N; n++ {
        SearchNonConcurrently(1, mySlice)
    }
}

func BenchmarkSearchConcurrently(b *testing.B) {
    mySlice := make([]int, 10000)
    mySlice[len(mySlice)-1] = 1
    for n := 0; n < b.N; n++ {
        SearchConcurrently(1, mySlice)
    }
}

The results:

$ go test -bench=. -benchmem -count=4
goos: linux
goarch: amd64
pkg: test/bencslice
BenchmarkSearchNonConcurrently-4       85780         13831 ns/op           0 B/op          0 allocs/op
BenchmarkSearchNonConcurrently-4       83619         13880 ns/op           0 B/op          0 allocs/op
BenchmarkSearchNonConcurrently-4       87128         14050 ns/op           0 B/op          0 allocs/op
BenchmarkSearchNonConcurrently-4       87366         13837 ns/op           0 B/op          0 allocs/op
BenchmarkSearchConcurrently-4            235       4867257 ns/op        2200 B/op          6 allocs/op
BenchmarkSearchConcurrently-4            244       4896937 ns/op        3360 B/op          8 allocs/op
BenchmarkSearchConcurrently-4            240       4871934 ns/op         453 B/op          2 allocs/op
BenchmarkSearchConcurrently-4            244       4884617 ns/op        3352 B/op          8 allocs/op
PASS
ok      test/bencslice  12.087s
$ go version
go version go1.15.2 linux/amd64

Answer 2

I created the follwing code. My only regret is that it keeps creating go routines even after finding the solution. I mean for a sorted tree with 1000 elements if I search for node with ID = 5 it keeps opening cases with above 900.

func FindConcurrent(node *Node, id int, c chan *Node) {
    select {
    case <-c:
        return
    default:
    }

    if node.ID == id {
        c <- node
        close(c)
        return
    }

    for _, child := range node.Children {
        go FindConcurrent(child, id, c)
    }

}