concurrency - run - ¿Por qué la adición de concurrencia ralentiza este código de golang?

go channels

Question

Tengo un poco de código Go con el que he estado retocando para responder a una pequeña curiosidad mía relacionada con un videojuego que juega mi cuñado.

Esencialmente, el siguiente código simula las interacciones con los monstruos en el juego y la frecuencia con la que puede esperar que suelten objetos tras su derrota. El problema que tengo es que esperaría que un código como este sea perfecto para la paralelización, pero cuando agrego concurrencia, el tiempo que se tarda en hacer todas las simulaciones tiende a disminuir en 4 a 6 veces el original. sin concurrencia.

Para darte una mejor comprensión de cómo funciona el código, tengo tres funciones principales: La función de interacción que es una interacción simple entre el jugador y un monstruo. Devuelve 1 si el monstruo arroja un objeto, y 0 de lo contrario. La función de simulación ejecuta varias interacciones y devuelve una porción de resultados de interacción (es decir, 1 y 0 que representan interacciones exitosas / no exitosas). Finalmente, existe la función de prueba que ejecuta un conjunto de simulaciones y devuelve una porción de resultados de simulación que son el número total de interacciones que dieron como resultado un elemento descartado. Es la última función que intento ejecutar en paralelo.

Ahora, podría entender por qué el código se ralentizaría si creara una rutina para cada prueba que quiero ejecutar. Asumiendo que estoy ejecutando 100 pruebas, el cambio de contexto entre cada una de las goroutinas a través de las 4 CPUs que mi MacBook Air tiene matará el rendimiento, pero solo estoy creando tantos goroutines como tengo procesadores y dividiendo el número de pruebas entre los procesadores. goroutines. Esperaría que esto realmente acelere el rendimiento del código ya que estoy ejecutando cada una de mis pruebas en paralelo, pero, por supuesto, en su lugar, estoy recibiendo una mayor ralentización.

Me encantaría descubrir por qué sucede esto, por lo que cualquier ayuda sería muy apreciada.

A continuación se muestra el código regular sin las rutinas go:

package main

import (
    "fmt"
    "math/rand"
    "time"
)

const (
    NUMBER_OF_SIMULATIONS = 1000
    NUMBER_OF_INTERACTIONS = 1000000
    DROP_RATE = 0.0003
)

/**
 * Simulates a single interaction with a monster
 *
 * Returns 1 if the monster dropped an item and 0 otherwise
 */
func interaction() int {
    if rand.Float64() <= DROP_RATE {
        return 1
    }
    return 0
}

/**
 * Runs several interactions and retuns a slice representing the results
 */
func simulation(n int) []int {
    interactions := make([]int, n)
    for i := range interactions {
        interactions[i] = interaction()
    }
    return interactions
}

/**
 * Runs several simulations and returns the results
 */
func test(n int) []int {
    simulations := make([]int, n)
    for i := range simulations {
        successes := 0
        for _, v := range simulation(NUMBER_OF_INTERACTIONS) {
            successes += v
        }
        simulations[i] = successes
    }
    return simulations
}

func main() {
    rand.Seed(time.Now().UnixNano())
    fmt.Println("Successful interactions: ", test(NUMBER_OF_SIMULATIONS))
}

Y, aquí está el código concurrente con los goroutines:

package main

import (
    "fmt"
    "math/rand"
    "time"
    "runtime"
)

const (
    NUMBER_OF_SIMULATIONS = 1000
    NUMBER_OF_INTERACTIONS = 1000000
    DROP_RATE = 0.0003
)

/**
 * Simulates a single interaction with a monster
 *
 * Returns 1 if the monster dropped an item and 0 otherwise
 */
func interaction() int {
    if rand.Float64() <= DROP_RATE {
        return 1
    }
    return 0
}

/**
 * Runs several interactions and retuns a slice representing the results
 */
func simulation(n int) []int {
    interactions := make([]int, n)
    for i := range interactions {
        interactions[i] = interaction()
    }
    return interactions
}

/**
 * Runs several simulations and returns the results
 */
func test(n int, c chan []int) {
    simulations := make([]int, n)
    for i := range simulations {
        for _, v := range simulation(NUMBER_OF_INTERACTIONS) {
            simulations[i] += v
        }
    }
    c <- simulations
}

func main() {
    rand.Seed(time.Now().UnixNano())

    nCPU := runtime.NumCPU()
    runtime.GOMAXPROCS(nCPU)
    fmt.Println("Number of CPUs: ", nCPU)

    tests := make([]chan []int, nCPU)
    for i := range tests {
        c := make(chan []int)
        go test(NUMBER_OF_SIMULATIONS/nCPU, c)
        tests[i] = c
    }

    // Concatentate the test results
    results := make([]int, NUMBER_OF_SIMULATIONS)
    for i, c := range tests {
        start := (NUMBER_OF_SIMULATIONS/nCPU) * i
        stop := (NUMBER_OF_SIMULATIONS/nCPU) * (i+1)
        copy(results[start:stop], <-c)
    }

    fmt.Println("Successful interactions: ", results)
}

ACTUALIZACIÓN (12/01/13 18:05)

Agregué una nueva versión del código simultáneo a continuación que crea una nueva instancia de Rand para cada goroutine según la sugerencia del "sistema" a continuación. Ahora veo una ligera aceleración en comparación con la versión en serie del código (alrededor de un 15-20% de reducción en el tiempo total empleado). Me encantaría saber por qué no veo algo más cercano a una reducción del 75% en el tiempo, ya que estoy distribuyendo la carga de trabajo sobre los 4 núcleos de mi MBA. ¿Alguien tiene alguna sugerencia adicional que pueda ayudar?

package main

import (
    "fmt"
    "math/rand"
    "time"
    "runtime"
)

const (
    NUMBER_OF_SIMULATIONS = 1000
    NUMBER_OF_INTERACTIONS = 1000000
    DROP_RATE = 0.0003
)

/**
 * Simulates a single interaction with a monster
 *
 * Returns 1 if the monster dropped an item and 0 otherwise
 */
func interaction(generator *rand.Rand) int {
    if generator.Float64() <= DROP_RATE {
        return 1
    }
    return 0
}

/**
 * Runs several interactions and retuns a slice representing the results
 */
func simulation(n int, generator *rand.Rand) []int {
    interactions := make([]int, n)
    for i := range interactions {
        interactions[i] = interaction(generator)
    }
    return interactions
}

/**
 * Runs several simulations and returns the results
 */
func test(n int, c chan []int) {
    source := rand.NewSource(time.Now().UnixNano())
    generator := rand.New(source)
    simulations := make([]int, n)
    for i := range simulations {
        for _, v := range simulation(NUMBER_OF_INTERACTIONS, generator) {
            simulations[i] += v
        }
    }
    c <- simulations
}

func main() {
    rand.Seed(time.Now().UnixNano())

    nCPU := runtime.NumCPU()
    runtime.GOMAXPROCS(nCPU)
    fmt.Println("Number of CPUs: ", nCPU)

    tests := make([]chan []int, nCPU)
    for i := range tests {
        c := make(chan []int)
        go test(NUMBER_OF_SIMULATIONS/nCPU, c)
        tests[i] = c
    }

    // Concatentate the test results
    results := make([]int, NUMBER_OF_SIMULATIONS)
    for i, c := range tests {
        start := (NUMBER_OF_SIMULATIONS/nCPU) * i
        stop := (NUMBER_OF_SIMULATIONS/nCPU) * (i+1)
        copy(results[start:stop], <-c)
    }

    fmt.Println("Successful interactions: ", results)
}

ACTUALIZACIÓN (13/01/13 17:58)

Gracias a todos por la ayuda para resolver mi problema. Finalmente obtuve la respuesta que estaba buscando y pensé que simplemente resumiría aquí para cualquier persona que tenga el mismo problema.

Básicamente, tenía dos problemas principales: primero, aunque mi código era vergonzosamente paralelo , iba más lento cuando lo dividía entre los procesadores disponibles, y segundo, la solución abría otro problema, que era que mi código de serie se ejecutaba dos veces. lento como el código simultáneo que se ejecuta en un solo procesador, lo que esperaría que fuera más o menos el mismo. En ambos casos, el problema fue la función de generador de números aleatorios rand.Float64 . Básicamente, esta es una función de conveniencia proporcionada por el paquete rand . En ese paquete, cada una de las funciones de conveniencia crea y utiliza una instancia global de la estructura Rand . Esta instancia global de Rand tiene un bloqueo de exclusión mutua asociado. Dado que estaba usando esta función de conveniencia, no pude en verdad paralelizar mi código ya que cada uno de los goroutines tendría que alinearse para acceder a la instancia global de Rand . La solución (como "el sistema" sugiere a continuación) es crear una instancia separada de la estructura Rand para cada goroutine. Esto resolvió el primer problema pero creó el segundo.

El segundo problema fue que mi código concurrente no paralelo (es decir, mi código simultáneo que se ejecuta con un solo procesador) se ejecutaba dos veces más rápido que el código secuencial. La razón de esto fue que, aunque solo estaba ejecutando con un único procesador y una sola rutina de administración, esa rutina tenía su propia instancia de la estructura Rand que había creado, y la había creado sin el bloqueo de exclusión mutua. El código secuencial todavía estaba usando la función de conveniencia rand.Float64 que hizo uso de la instancia global Rand protegida mutex. El costo de adquirir ese bloqueo estaba haciendo que el código secuencial se ejecutara dos veces más despacio.

Entonces, la moraleja de la historia es que, siempre que el rendimiento sea importante, asegúrese de crear una instancia de la estructura Rand y llamar a la función que necesita fuera de ella en lugar de usar las funciones de conveniencia proporcionadas por el paquete.

Answer 1

El problema parece provenir del uso de rand.Float64() , que utiliza un objeto global compartido con un bloqueo Mutex en él.

En cambio, si para cada CPU se crea un rand.New() separado. rand.New() , se pasa a las interactions() y se usa para crear Float64() , hay una mejora masiva.

Actualice para mostrar los cambios al nuevo código de ejemplo en la pregunta que ahora usa rand.New()

La función de test() se modificó para usar un canal determinado o devolver el resultado.

func test(n int, c chan []int) []int {
    source := rand.NewSource(time.Now().UnixNano())
    generator := rand.New(source)
    simulations := make([]int, n)
    for i := range simulations {
        for _, v := range simulation(NUMBER_OF_INTERACTIONS, generator) {
            simulations[i] += v
        }   
    }   
    if c == nil {
        return simulations
    }   
    c <- simulations
    return nil 
}

La función main() se actualizó para ejecutar ambas pruebas y generar el resultado programado.

func main() {
    rand.Seed(time.Now().UnixNano())

    nCPU := runtime.NumCPU()
    runtime.GOMAXPROCS(nCPU)
    fmt.Println("Number of CPUs: ", nCPU)

    start := time.Now()
    fmt.Println("Successful interactions: ", len(test(NUMBER_OF_SIMULATIONS, nil)))
    fmt.Println(time.Since(start))

    start = time.Now()
    tests := make([]chan []int, nCPU)
    for i := range tests {
        c := make(chan []int)
        go test(NUMBER_OF_SIMULATIONS/nCPU, c)
        tests[i] = c
    }

    // Concatentate the test results
    results := make([]int, NUMBER_OF_SIMULATIONS)
    for i, c := range tests {
        start := (NUMBER_OF_SIMULATIONS/nCPU) * i
        stop := (NUMBER_OF_SIMULATIONS/nCPU) * (i+1)
        copy(results[start:stop], <-c)
    }
    fmt.Println("Successful interactions: ", len(results))
    fmt.Println(time.Since(start))
}

La salida es que recibí:

> Number of CPUs: 2 > > Successful interactions: 1000 > 1m20.39959s > > Successful interactions: 1000 > 41.392299s

Answer 2

Mis resultados, que muestran concurrencia sustancial para 4 CPUs versus 1 CPU:

CPU Intel Core 2 Quad Q8300 a 2.50 GHz x 4

Código fuente: ACTUALIZACIÓN (12/01/13 18:05)

$ go version
go version devel +adf4e96e9aa4 Thu Jan 10 09:57:01 2013 +1100 linux/amd64

$ time  go run temp.go
Number of CPUs:  1
real    0m30.305s
user    0m30.210s
sys     0m0.044s

$ time  go run temp.go
Number of CPUs:  4
real    0m9.980s
user    0m35.146s
sys     0m0.204s

Answer 3

Probando tu código en mi computadora portátil Linux quad core i7 entiendo esto

Aquí hay una hoja de cálculo de Google

Esto muestra que en Linux, al menos, la escala es muy lineal por núcleo.

Creo que puede haber dos razones por las que no estás viendo esto.

El primero es que su macbook air solo tiene 2 núcleos reales. Tiene 4 hyperthreads aunque es por eso que informa 4 como max cpus. Un hyperthread por lo general solo ofrece un 15% de rendimiento extra sobre un solo núcleo en lugar del 100% que cabría esperar. ¡Así que limítese a la evaluación comparativa de 1 o 2 CPUs solo en el macbook air!

La otra razón podría ser el rendimiento del subproceso OS X en comparación con Linux. Usan diferentes modelos de subprocesamiento que pueden estar afectando el rendimiento.

Answer 4

Su código está muestreando una variable aleatoria binomial, B (N, p) donde N es el número de ensayos (aquí 1M), y p es la probabilidad de una prueba individual exitosa (aquí 0.0003).

Una forma de hacerlo es construir una tabla T de probabilidades acumuladas, donde T [i] contiene la probabilidad de que el número total de ensayos sea menor o igual que i. Para luego producir una muestra, puedes elegir una variable aleatoria uniforme (a través de rand.Float64) y encontrar el primer índice en la tabla que contenga una probabilidad mayor o igual a él.

Aquí es un poco más complicado porque tienes una N realmente grande y una p bastante pequeña, así que si tratas de construir la tabla obtienes problemas con números realmente pequeños y precisión aritmética. Pero puede construir una tabla más pequeña (digamos 1000 de gran tamaño) y muestrearla 1000 veces para obtener su 1 millón de intentos.

Aquí hay un código que hace todo esto. No es demasiado elegante (1000 está codificado), pero genera 1000 simulaciones en menos de un segundo en mi computadora portátil anterior. Es fácil optimizar aún más, por ejemplo, levantando la construcción del BinomialSampler fuera del circuito, o usando la búsqueda binaria en lugar de un escaneo lineal para encontrar el índice de la tabla.

package main

import (
    "fmt"
    "math"
    "math/rand"
)

type BinomialSampler []float64

func (bs BinomialSampler) Sample() int {
    r := rand.Float64()
    for i := 0; i < len(bs); i++ {
        if bs[i] >= r {
            return i
        }
    }
    return len(bs)
}

func NewBinomialSampler(N int, p float64) BinomialSampler {
    r := BinomialSampler(make([]float64, N+1))
    T := 0.0
    choice := 1.0
    for i := 0; i <= N; i++ {
        T += choice * math.Pow(p, float64(i)) * math.Pow(1-p, float64(N-i))
        r[i] = T
        choice *= float64(N-i) / float64(i+1)
    }
    return r
}

func WowSample(N int, p float64) int {
    if N%1000 != 0 {
        panic("N must be a multiple of 1000")
    }
    bs := NewBinomialSampler(1000, p)
    r := 0
    for i := 0; i < N; i += 1000 {
        r += bs.Sample()
    }
    return r
}

func main() {
    for i := 0; i < 1000; i++ {
        fmt.Println(WowSample(1000000, 0.0003))
    }
}