Go Concurrency: Chudnovky Algorithmus, langsamer als Sync

Question

Ich habe gerade erst angefangen zu lernen gehen auf Empfehlung eines Freundes. Bis jetzt, ich liebe es, aber ich schrieb (was ich dachte) wäre das perfekte Beispiel für die Kraft der leichten Nebenläufigkeit, und hatte ein überraschendes Ergebnis ... also vermute ich, dass ich etwas falsch mache, oder ich bin Missverständnis, wie teuer Göroutinen sind. Ich hoffe, dass einige Gopher hier Einblick geben können.

Ich schrieb Chudnovsky-Algorithmus in Go mit beiden Göroutinen und einfache synchrone Ausführung. Ich nahm an, dass jede Berechnung unabhängig von den anderen zumindest zeitgleich schneller laufen würde.

Anmerkung: Ich bin diesen i7 auf einem fünften Generation laufen, also wenn goroutines auf Fäden gemultiplext werden, wie mir gesagt wurde, soll dies sowohl die gleichzeitige und parallel sein.

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 
} 

Und hier sind meine Ergebnisse:

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

Answer 1

Die Berechnungen Sie tun sind zu einfach jeder von ihnen in einem separaten goroutine zu tun. Sie verlieren mehr Zeit in der Laufzeit (Erstellen von Gououtlines, Multiplexing, Scheduling usw.) als bei tatsächlichen Berechnungen. Was Sie zu tun versuchen, ist beispielsweise besser für GPU geeignet, wo Sie eine große Anzahl paralleler Ausführungseinheiten haben, die diese einfachen Berechnungen alle gleichzeitig ausführen können. Dafür benötigen Sie jedoch andere Sprachen und APIs.

Was Sie tun können, ist Software-Thread der Ausführung für jeden Hardware-Thread der Ausführung zu erstellen. Sie möchten Ihre max Variable in große Teile aufteilen und parallel ausführen. Hier ist sehr einfach nehmen auf es nur um die Idee zu veranschaulichen:

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 
} 

Und hier die Ergebnisse

$ 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

Ich bin damit einverstanden, Ihre Berechnungen tun nicht genug, um die Verarbeitung der Overhead mit mehreren goroutines zu überwinden. Nur zum Spaß habe ich Ihren Code geändert, um die Berechnung mehrmals durchzuführen (1000, 10000, 100000, 1000000), bevor Sie das Ergebnis zurückgeben. Ich habe dies (mit 20 Iterationen) unter Mac OS X Yosemite ausgeführt, das auf einem Quad-Core-Xeon läuft, und, wie zu erwarten ist, nimmt die synchrone Version die Umgebung von vier Mal so lange in Anspruch wie die parallele Version.

Eine interessante Sache, die ich bemerkte, ist, dass mit einer großen Anzahl von Wiederholungen die synchrone Version tatsächlich mehr als vier mal so lange wie die parallele Version dauert. Ich vermute, das hat etwas mit Intels Hyperthreading-Architektur zu tun, die ein gewisses Maß an Parallelität in jedem Kern ermöglicht, aber ich bin mir nicht sicher.