Go Concurrency：Chudnovky 的算法，比同步慢

Question

我最近在朋友的推荐下开始学习围棋。到目前为止，我很喜欢它，但我写了（我认为会是）轻量级并发力量的完美例子，并得到了令人惊讶的结果......所以我怀疑我做错了什么，或者我是误解 goroutine 的成本有多高。我希望这里的一些地鼠可以提供洞察力。我使用 goroutines 和简单的同步执行在 Go 中编写了 Chudnovsky 的算法。我假设，由于每个计算都独立于其他计算，因此并发运行至少会快一点。注意：我在第 5 代 i7 上运行它，所以如果 goroutine 像我被告知的那样多路复用到线程上，这应该是并发和并行的。 package mainimport (  "fmt"  "math"  "strconv"  "time")func main() {  var input string  var sum float64  var pi float64  c := make(chan float64)  fmt.Print("How many iterations? ")  fmt.Scanln(&input)  max,err := strconv.Atoi(input)  if err != nil {    panic("You did not enter a valid integer")  }  start := time.Now() //start timing execution of concurrent routine  for i := 0; i < max; i++ {    go chudnovskyConcurrent(i,c)  }  for i := 0; i < max; i++ {    sum += <-c  }  end := time.Now() //end of concurrent routine  fmt.Println("Duration of concurrent calculation: ",end.Sub(start))  pi = 1/(12*sum)  fmt.Println(pi)  start = time.Now() //start timing execution of syncronous routine  sum = 0  for i := 0; i < max; i++ {    sum += chudnovskySync(i)  }  end = time.Now() //end of syncronous routine  fmt.Println("Duration of synchronous calculation: ",end.Sub(start))  pi = 1/(12*sum)  fmt.Println(pi)}func chudnovskyConcurrent(i int, c chan<- float64) {  var numerator float64  var denominator float64  ifloat := float64(i)  iun := uint64(i)  numerator = math.Pow(-1, ifloat) * float64(factorial(6*iun)) * (545140134*ifloat+13591409)  denominator = float64(factorial(3*iun)) * math.Pow(float64(factorial(iun)),3) * math.Pow(math.Pow(640320,3),ifloat+0.5)  c <- numerator/denominator}func chudnovskySync(i int) (r float64) {  var numerator float64  var denominator float64  ifloat := float64(i)  iun := uint64(i)  numerator = math.Pow(-1, ifloat) * float64(factorial(6*iun)) * (545140134*ifloat+13591409)  denominator = float64(factorial(3*iun)) * math.Pow(float64(factorial(iun)),3) * math.Pow(math.Pow(640320,3),ifloat+0.5)  r = numerator/denominator  return}

Answer 1

您正在执行的计算太简单了，无法在单独的 goroutine 中进行每一项计算。与实际计算相比，您在运行时（创建 goroutine、多路复用、调度等）浪费的时间更多。您正在尝试做的更适合 GPU，例如，在那里您拥有大量并行执行单元，可以在瞬间完成这些简单的计算。但是你需要其他语言和 API 来做到这一点。

您可以做的是为每个硬件执行线程创建软件执行线程。您想将max变量分成大块并并行执行。这是一个非常简单的例子，只是为了说明这个想法：

package main

import (

  "fmt"

  "math"

  "strconv"

  "time"

  "runtime"

)

func main() {

  var input string

  var sum float64

  var pi float64

  c := make(chan float64, runtime.GOMAXPROCS(-1))

  fmt.Print("How many iterations? ")

  fmt.Scanln(&input)

  max,err := strconv.Atoi(input)

  if err != nil {

    panic("You did not enter a valid integer")

  }

  start := time.Now() //start timing execution of concurrent routine

  for i := 0; i < runtime.GOMAXPROCS(-1); i++ {

    go func(i int){

      var sum float64

      for j := 0; j < max/runtime.GOMAXPROCS(-1); j++  {

        sum += chudnovskySync(j + i*max/runtime.GOMAXPROCS(-1))

      }

      c <- sum

    }(i)

  }

  for i := 0; i < runtime.GOMAXPROCS(-1); i++ {

    sum += <-c

  }

  end := time.Now() //end of concurrent routine

  fmt.Println("Duration of concurrent calculation: ",end.Sub(start))

  pi = 1/(12*sum)

  fmt.Println(pi)

  start = time.Now() //start timing execution of syncronous routine

  sum = 0

  for i := 0; i < max; i++ {

    sum += chudnovskySync(i)

  }

  end = time.Now() //end of syncronous routine

  fmt.Println("Duration of synchronous calculation: ",end.Sub(start))

  pi = 1/(12*sum)

  fmt.Println(pi)

}

func chudnovskySync(i int) (r float64) {

  var numerator float64

  var denominator float64

  ifloat := float64(i)

  iun := uint64(i)

  numerator = math.Pow(-1, ifloat) * float64(factorial(6*iun)) * (545140134*ifloat+13591409)

  denominator = float64(factorial(3*iun)) * math.Pow(float64(factorial(iun)),3) * math.Pow(math.Pow(640320,3),ifloat+0.5)

  r = numerator/denominator

  return

}

func factorial(n uint64) (res uint64) {

  if ( n > 0 ) {

    res = n * factorial(n-1)

    return res

  }

  return 1

}

这是结果

$ go version

go version go1.5.2 windows/amd64

$ go run main.go

GOMAXPROCS = 4

How many iterations? 10000

Duration of concurrent calculation:  932.8916ms

NaN

Duration of synchronous calculation:  2.0639744s

NaN 

Answer 2

我同意，您的计算没有做足够的处理来克服拥有多个 goroutine 的开销。只是为了好玩，在返回结果之前，我修改了您的代码以进行多次计算（1000、10000、100000、1000000）。我在四核 Xeon 上运行的 Mac OS X Yosemite 下运行了这个（20 次迭代），并且如您所料，同步版本的时间大约是并行版本的四倍。

我注意到的一件有趣的事情是，在大量重复的情况下，同步版本的时间实际上是并行版本的四倍多。我猜这与 Intel 的超线程架构有关，该架构允许在每个内核中实现某种程度的并行性，但我不确定这一点。