performance - 并行版本比golang中的串行版本慢得多

Question

我正在尝试编写一个简单算法的并行版本，该并行版本采用一个点和一个点列表，然后查找列表中最接近第一个点的点，以将执行时间与串行版本进行比较。
问题是运行并行版本需要超过1分钟，而串行版本需要大约1秒。

为确保并行性效果显着，我正在使用大约1200万点的列表来测试代码。

我的CPU详细信息:

型号名称:Intel(R)Core(TM)i5-4210U CPU @ 1.70GHz

CPU:4

这是两个版本:

共同部分:

type Point struct {
    X float64
    Y float64
}

func dist(p, q Point) float64 {
    return math.Sqrt(math.Pow(p.X-q.X,2)+math.Pow(p.Y-q.Y,2))
}

顺序功能:

func s_argmin(p Point, points_list []Point, i,j int)(int){
    best := 0
    d := dist(p, points_list[0])
    var new_d float64
    for k:=i;k<j+1;k++{
        new_d = dist(p, points_list[k])
        if new_d < d{
            d = new_d
            best = k
        }
    }
    return best
}

并行功能:

func p_argmin(p Point, points_list []Point, i,j int)(int){
    if i==j{
        return i
    }else{
        mid := int((i+j)/2)
        var argmin1, argmin2 int
        c1 := make(chan int)
        c2 := make(chan int)
        go func(){
            c1 <- p_argmin(p, points_list, i, mid)
        }()
        go func(){
            c2 <- p_argmin(p, points_list, mid+1, j)
        }()
        argmin1 = <- c1
        argmin2 = <- c2
        close(c1)
        close(c2)
        if dist(p,points_list[argmin1])<dist(p,points_list[argmin2]){
            return argmin1
        }else{
            return argmin2
        }
    }
}

我还尝试限制并行性，使用优化的函数仅在输入大小(j-i)大于一个值时才执行该函数的并行版本，但串行版本始终是更快的版本。

如何改善并行版本的结果？

Answer 1

毫无意义的微基准测试将产生毫无意义的结果。

我没有理由相信递归p_argmin可能比s_argmin更快。

$ go test micro_test.go -bench=. -benchmem
goos: linux
goarch: amd64
BenchmarkS-4      946197          1263 ns/op           0 B/op          0 allocs/op
--- BENCH: BenchmarkS-4
    micro_test.go:81: 1 946197 946197
BenchmarkP-4        3477        302076 ns/op       80958 B/op        843 allocs/op
--- BENCH: BenchmarkP-4
    micro_test.go:98: 839 2917203 3477
$ 

micro_test.go:

package main

import (
    "math"
    "sync"
    "testing"
)

type Point struct {
    X float64
    Y float64
}

func dist(p, q Point) float64 {
    //return math.Sqrt(math.Pow(p.X-q.X, 2) + math.Pow(p.Y-q.Y, 2))
    return math.Sqrt((p.X-q.X)*(p.X-q.X) + (p.Y-q.Y)*(p.Y-q.Y))
}

func s_argmin(p Point, points_list []Point, i, j int) int {
    mbm.Lock()
    nbm++
    mbm.Unlock()

    best := 0
    d := dist(p, points_list[0])
    var new_d float64
    for k := i; k < j+1; k++ {
        new_d = dist(p, points_list[k])
        if new_d < d {
            d = new_d
            best = k
        }
    }
    return best
}

func p_argmin(p Point, points_list []Point, i, j int) int {
    mbm.Lock()
    nbm++
    mbm.Unlock()

    if i == j {
        return i
    }
    mid := int((i + j) / 2)
    var argmin1, argmin2 int
    c1 := make(chan int)
    c2 := make(chan int)
    go func() {
        c1 <- p_argmin(p, points_list, i, mid)
    }()
    go func() {
        c2 <- p_argmin(p, points_list, mid+1, j)
    }()
    argmin1 = <-c1
    argmin2 = <-c2
    if dist(p, points_list[argmin1]) < dist(p, points_list[argmin2]) {
        return argmin1
    }
    return argmin2
}

var (
    nbm int
    mbm sync.Mutex
)

func BenchmarkS(b *testing.B) {
    mbm.Lock()
    nbm = 0
    mbm.Unlock()

    points := make([]Point, 420)
    b.ResetTimer()
    for N := 0; N < b.N; N++ {
        s_argmin(points[0], points, 0, len(points)-1)
    }
    b.StopTimer()

    mbm.Lock()
    b.Log(float64(nbm)/float64(b.N), nbm, b.N)
    mbm.Unlock()
}

func BenchmarkP(b *testing.B) {
    mbm.Lock()
    nbm = 0
    mbm.Unlock()

    points := make([]Point, 420)
    b.ResetTimer()
    for N := 0; N < b.N; N++ {
        p_argmin(points[0], points, 0, len(points)-1)
    }
    b.StopTimer()

    mbm.Lock()
    b.Log(float64(nbm)/float64(b.N), nbm, b.N)
    mbm.Unlock()
}