使用 golang 的四叉树递归并发

Question

我正在尝试通过使用 go-routines 来共享递归查找来并行化我的四叉树查找。

我的四叉树结构如下所示：

type Quadtree struct {
    Rectangle //Boundary of the quadtree
    Points   []Point
    Ne       *Quadtree
    Se       *Quadtree
    Sw       *Quadtree
    Nw       *Quadtree
    Divided  bool
    Capacity int
    Parent   *Quadtree
}

我有一个名为 QueryForNearestPoints 的方法，它接受一个 Point 和一个 searchRadius 以及 returns 四叉树中 searcharea 内的所有点。如果在给定的 searchRadius 内未找到任何点，则增加 searchRadius 并再次尝试。

points 是搜索半径中的点发送到的通道。我还使用 sync.WaitGroup wg 来等待所有 go-routines 完成。

func (q *Quadtree) QueryForNearestPoints(p Point, searchRadius float64) []QueryResult {
    searcharea = Circle{p, searchRadius}
    var testResults []QueryResult

    for {

        go func() {
        loop:
            for {
                select {
                case item, _ := <-points:
                    testResults = append(testResults, item)
                case <-done:
                    break loop
                }
            }
        }()
        wg.Add(1)
        go q.query(searcharea)
        wg.Wait()
        done <- true
        if len(testResults) > 0 {
            break
        } else {
            // Proportionally increase the search radius if no points are found.
            searcharea = Circle{p, searcharea.Radius + searcharea.Radius*50/100}
        }
    }
    return testResults
}

并行四叉树的查询方式：

func (q *Quadtree) query(area Circle) {
    defer wg.Done()
    if !q.overlapsCircle(area) {
        return
    }
    if len(q.Points) > 0 {
        for i, point := range q.Points {
            if area.contains(point) {
                points <- QueryResult{point, i, q}
            }
        }
    }
    if q.Divided {
        wg.Add(4)
        go q.Ne.parallelquery(area)
        go q.Se.parallelquery(area)
        go q.Sw.parallelquery(area)
        go q.Nw.parallelquery(area)
    }
}

(q *Quadtree) parallelquery方法：

func (q *Quadtree) parallelquery(area Circle) {
    semaphore <- struct{}{}
    defer func() {
        <-semaphore
    }()
    q.query(area)
}

如果我没记错的话，这是一个 cpu 绑定的工作负载，因此拥有 1000 个 go-routines 没有帮助，所以我使用缓冲通道 semaphore 作为一个计数信号量，以确保在任何时候只有 n 个 go-routines 处于活动状态。（这里我将 n 设置为 4，因为我的计算机有 4 cpus。）

唯一的问题是这种方法比正常的非并发顺序方法慢得多。我在这里错过了什么？我怎样才能让它更快？

Answer 1

这要慢得多，因为您在每个 goroutine 中所做的工作非常便宜，而且 goroutine 非常多。

对于那些批评此答案中的术语的人，我将交替使用并行性和并发性。尽管严格来说，并行性是运行时/计算机的属性，而并发性是代码的属性。如果在单处理器硬件上运行某些代码仍然可以并发，但不会运行并行。

这里并发版本较慢的原因是因为在使用通道等时仍然需要一些同步。在幕后，通道使用互斥锁来同步通道上的发送/接收。这意味着您在 goroutine 之间引入了争用。

每次调用 parallelquery(area) 时，您都会启动另外 4 个必须调度的 goroutine，但是（使用信号量通道）您已将并发 goroutine 的数量限制为 4。

在 n 次递归之后，您有 4^n 个 goroutine 都试图从信号量通道接收值，这会引起很多争用。

对此使用阻塞 CPU 分析器，您可能会发现大部分执行时间都花在了试图从信号量获取令牌的争用上。

使用 golang 的四叉树递归并发

recursive concurrency for quadtree with golang

concurrency

recursion

quadtree

go

goroutine