同時実行：Chudnovkyのアルゴリズム、同期よりも遅い

Question

私は最近、友人の推薦で学習を始めました。これまでのところ、私はそれを愛していますが、私は軽い同時並行性のパワーの完璧な例を書いていました（私は思ったように）、驚くべき結果を得ました...私は間違ったことをしていると思われます。高価なgoroutinesがいかに誤解しているか。私はここにいるいくつかのgophersが洞察力を提供することを望んでいます。

私はgoroutinesと単純な同期実行の両方を使ってGoでChudnovskyのアルゴリズムを書いた。私は、それぞれの計算が他の計算と独立していると仮定すると、同時に実行するのが少し速くなると思っていました。

ノート：私は第五世代i7プロセッサーでこれを実行しているので、私が言われたようゴルーチンが、スレッド上に多重化されている場合、これは両方の同時と平行にする必要があります。

package main 

import (
    "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 
} 

func factorial(n uint64) (res uint64) { 
    if (n > 0) { 
    res = n * factorial(n-1) 
    return res 
    } 

    return 1 
} 

そして、ここに私の結果は次のとおりです。あなたがやっている

How many iterations? 20 
Duration of concurrent calculation: 573.944µs 
3.1415926535897936 
Duration of synchronous calculation: 63.056µs 
3.1415926535897936 

Answer 1

計算は別のゴルーチンでそれらのそれぞれを行うにはあまりにも簡単です。実際の計算よりもランタイム（ゴルーチン、多重化、スケジューリングなど）に多くの時間を費やしています。あなたがやろうとしていることは、例えば、この単純な計算をすべて一瞬で行うことができる膨大な数の並列実行ユニットがある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

だ、あなたの計算は、複数のゴルーチンを持つのオーバーヘッドを克服するのに十分な処理をしません。ちょうど楽しみのために、結果を返す前に計算を何度も（1000,10000,100000,1000000）行うようにコードを修正しました。私はクアッドコアXeon上で動作するMac OS X Yosemiteのもとでこれを（20回の繰り返しで）走らせました。予想通り、同期バージョンは並列バージョンの4倍の長さになります。

私が気づいた興味深いものは、繰り返し回数が多いと、同期バージョンは実際には並列バージョンの4倍以上の時間がかかります。私はこれがIntelのハイパースレッディングアーキテクチャと関係があり、各コア内である程度の並列性を可能にしていると思っていますが、それについてはわかりません。