Así que has aprendido todo sobre las goroutinas y canales de Go, y estás emocionado de sumergirte en una programación concurrente. ¡Pero espera! Antes de comenzar a generar miles de goroutinas, tomemos un paso atrás y comprendamos cómo hacerlo de manera eficiente. En este artículo, exploraremos el concepto de un grupo de trabajadores Y cómo puede ayudarlo a administrar la concurrencia en Go sin abrumar su sistema.
Digamos que te mudas a un nuevo lugar. Tus cosas están en cajas en movimiento y la camioneta está esperando afuera. Podrías intentar llevar las cajas, una a la vez, pero eso llevaría una eternidad. ¿Qué puedes hacer? Si está en buena forma, puede llevar dos cajas a la vez, pero seamos sinceros, somos sofá. En cambio, invitas a tus amigos y les pides que ayuden. Ahora tienes un equipo de personas que llevan cajas, y el trabajo se hace mucho más rápido. Genial, pero ¿cuántos amigos? Solo hay una puerta, y si demasiadas personas intentan llevar cajas a la vez, se toparán entre sí y reducirán el proceso.
En Go, las goroutinas son como esos amigos que te ayudan a moverte. Son hilos livianos que pueden ejecutarse simultáneamente, lo que le permite realizar múltiples tareas a la vez sin la sobrecarga de los hilos tradicionales. Sin embargo, al igual que invitar a demasiados amigos puede conducir al caos, generar demasiadas goroutinas puede conducir a problemas de rendimiento. Aquí es donde un grupo de trabajadores es útil.
1. Goroutinas y canales: un resumen rápido
Pero antes de sumergirnos en las piscinas de trabajadores, recapitulemos rápidamente nuestros bloques de construcción: goroutinas y canales. Las goroutinas son hilos livianos administrados por el tiempo de ejecución de GO. Le permiten ejecutar funciones simultáneamente sin la complejidad de administrar los hilos usted mismo. Los canales se utilizan para comunicarse entre las goroutinas, lo que les permite sincronizar y compartir datos de manera segura. Hay otras formas para que las goroutinas se comuniquen, pero esta es la forma más segura e idiomática de acuerdo con “No comuníquese compartiendo memoria; comparta la memoria al comunicarse”.
Aquí hay un ejemplo básico de usar una goroutine con un canal:
ch := make(chan int)
go func() {
ch <- someWork() // Ship consequence to channel when prepared
}()
// Essential goroutine continues different work...
otherWork()
// Once we want the consequence, we obtain from the channel
consequence := <-ch // This blocks till the goroutine sends a worth
fmt.Printf("Acquired consequence: %dn", consequence)
En este ejemplo, la goroutina principal puede continuar ejecutando otras tareas mientras someWork() corre simultáneamente. Cuando se necesita el resultado, <-ch Bloquea la goroutina principal hasta que la Goroutine del trabajador envíe el valor a través del canal.
Un canal puede ser bloqueo o no bloqueado: Un canal de bloqueo esperará hasta que se envíe o reciba un valor, mientras que un canal no bloqueado volverá inmediatamente si no hay valor disponible. El ejemplo anterior usa un canal de bloqueo.
2. Concurrencia ≠ Paralelismo
Es importante entender que la concurrencia no significa paralelismo. GO le permite ejecutar muchas goroutinas, pero no puede ejecutar hilos más paralelos que la cantidad de núcleos de CPU disponibles. El tiempo de ejecución de GO aparecerá y ejecutará tu concurrente Goroutinas, pero no todos correrán en paralelo al mismo tiempo. Sí, todos se programarán, pero no necesariamente a la vez.
Además, las goroutinas introducen algunos gastos generales, como el espacio de pila y el trabajo de programador. Si genera miles de goroutinas, puede terminar perjudicando el rendimiento en lugar de mejorarlo. Go es excelente para administrar las goroutinas de manera eficiente, pero aún es importante tener en cuenta cuántos creas.
3. Paralelización de un algoritmo de división y conquista
Una familia de algoritmos que puede beneficiarse más de la concurrencia son los algoritmos recursivos de división y conclusión. Estos algoritmos descomponen un problema en subproblemas más pequeños, los resuelven de forma independiente y luego combinan los resultados.
El ejemplo más clásico de un algoritmo de división y conquista es Acelerar. Divide el conjunto de datos en dos particiones, ordene cada partición y luego combina los resultados.
3.1 Quicksort secuencial
Veamos una versión no paralela de QuickSort:
func quickSort(arr []int) []int {
// Halt situation: if the array has lower than 0 or 1 ingredient, it is sorted
if len(arr) == 1 || len(arr) == 0 {
return arr
}
// Divide the array into two partitions
// All the pieces lower than the pivot goes to the left, the whole lot higher (or equal) goes to the proper
pivot := arr[len(arr)/2]
left := []int{}
proper := []int{}
for _, v := vary arr {
if v < pivot {
left = append(left, v)
} else if v > pivot {
proper = append(proper, v)
}
}
// Recursively type the partitions
left = quickSort(left)
proper = quickSort(proper)
// Mix the left array, the pivot ingredient, and the proper array
// Right here each left and proper are already sorted due to the recursive calls
return append(append(left, pivot), proper...)
}
Si miramos este código, podemos ver que la clasificación de particiones izquierda y derecha se puede hacer en paralelo. Podemos generar dos goroutinas para ordenar las particiones izquierda y derecha simultáneamente, lo que puede acelerar significativamente el proceso de clasificación para conjuntos de datos grandes. No podemos hacer mucho sobre el paso de fusión, pero sigue siendo una mejora.
3.2 Quicksort paralelo: el enfoque ingenuo
Aquí hay una versión paralela easy que usa goroutinas RAW:
func quickSort(arr []int) []int {
if len(arr) == 1 || len(arr) == 0 {
return arr
}
pivot := arr[len(arr)/2]
left := []int{}
proper := []int{}
for _, v := vary arr {
if v < pivot {
left = append(left, v)
} else if v > pivot {
proper = append(proper, v)
}
}
// Create channels to obtain the sorted partitions
leftCh := make(chan []int)
rightCh := make(chan []int)
// Kind the left and proper partitions in goroutines
go func() {
leftCh <- quickSort(left)
}()
go func() {
rightCh <- quickSort(proper)
}()
// Look ahead to each goroutines to complete and acquire the outcomes
left = <-leftCh
proper = <-rightCh
return append(append(left, pivot), proper...)
}
En esta versión, generamos dos goroutinas para ordenar las particiones izquierda y derecha simultáneamente. Esto puede girar fuera de management rápidamente. Aunque con cuidadosa (o afortunada) selección de elementos dinámicos, la profundidad de la recursión será O(log n)en el peor de los casos, puede subir a O(n). Y en cada nivel de recursión, generamos dos goroutinas, lo que significa que el número de goroutinas crece exponencialmente, por lo que es fácil repasar la cantidad de núcleos de CPU disponibles. Y recuerde, cada goroutine tiene su propio espacio de pila y programación de sobrecarga.
3.3 Quicksort paralelo optimizado con un grupo de trabajadores
Para evitar los problemas con el desove de demasiadas goroutinas, podemos usar un grupo de trabajadores. Un grupo de trabajadores es un patrón de diseño en el que un número limitado de trabajadores extrae tareas de una cola. Esta concurrencia de estrangulamiento a lo que la CPU puede manejar y evita que se apague de demasiadas goroutinas. También podemos recurrir a una implementación secuencial si no hay trabajadores disponibles, en lugar de esperar una ranura para trabajadores free of charge. Esta devolución de retención también es útil para pequeños conjuntos de datos donde la sobrecarga de las goroutinas de desove supera los beneficios del paralelismo.
Así es como podemos implementar un grupo de trabajadores para QuickSort:
bundle fundamental
import (
"fmt"
"runtime"
)
// World employee pool - semaphore to restrict concurrent goroutines
var workerPool chan struct{}
func init() {
// Initialize with variety of CPU cores
workerPool = make(chan struct{}, runtime.NumCPU())
}
func quickSortWithPool(arr []int) []int {
if len(arr) <= 1 {
return arr
}
// Use sequential for small arrays to keep away from overhead
if len(arr) < 1000 {
return quickSortSequential(arr)
}
// Partition the array
pivot := arr[len(arr)/2]
left := []int{}
proper := []int{}
for _, v := vary arr {
if v < pivot {
left = append(left, v)
} else if v > pivot {
proper = append(proper, v)
}
}
// Channels to obtain outcomes
leftCh := make(chan []int, 1)
rightCh := make(chan []int, 1)
// Attempt to get a employee for left partition
choose {
case workerPool <- struct{}{}: // Acquired employee slot
go func() {
defer func() { <-workerPool }() // Launch slot when finished
leftCh <- quickSortWithPool(left)
}()
default: // No staff out there - use sequential
leftCh <- quickSortSequential(left)
}
// Attempt to get a employee for proper partition
choose {
case workerPool <- struct{}{}: // Acquired employee slot
go func() {
defer func() { <-workerPool }() // Launch slot when finished
rightCh <- quickSortWithPool(proper)
}()
default: // No staff out there - use sequential
rightCh <- quickSortSequential(proper)
}
// Look ahead to each outcomes
sortedLeft := <-leftCh
sortedRight := <-rightCh
// Mix outcomes
return append(append(sortedLeft, pivot), sortedRight...)
}
Nos aseguramos de que nunca generemos más goroutinas que la cantidad de núcleos de CPU disponibles. Hay varias optimizaciones más que podemos hacer, como volver a ser secuencial después de una cierta profundidad de recursión, procesamiento por lotes o partición en el lugar (para una mejor localidad de caché). También hay un gran potencial en una mejor selección de pivote. Pero la thought básica es usar un grupo de trabajadores para limitar el número de goroutinas concurrentes y evitar abrumar el sistema.
4. Benchmarking
En el repositorio de códigos adjuntos, puede encontrar las implementaciones del QuickSort secuencial, el rápido QuickSort paralelo y la versión del grupo de trabajadores, con un contenedor delgado para ejecutarlas en un conjunto de datos aleatorizado de 100,000 elementos. Si los ejecuta, los resultados serán algo como esto:
$ go run sequential/fundamental.go
Sorted Information: [0 2 7 9 10 20 22 26 29 38] ... [999931 999939 999945 999964 999967 999972 999979 999984 999988 999997]
Elapsed time: 32.9421ms
$ go run parallel/fundamental.go
Sorted Information: [0 2 7 9 10 20 22 26 29 38] ... [999931 999939 999945 999964 999967 999972 999979 999984 999988 999997]
Elapsed time: 66.6936ms
$ go run workerpool/fundamental.go
Sorted Information: [0 2 7 9 10 20 22 26 29 38] ... [999931 999939 999945 999964 999967 999972 999979 999984 999988 999997]
Elapsed time: 31.0905ms
Los resultados muestran que la rápida rápida paralela ingenua es significativamente más lenta que la versión secuencial, mientras que el grupo de trabajadores mejora significativamente el rendimiento del algoritmo paralelo, solo superando la ejecución de un solo hilo.
El bajo rendimiento de la versión paralela ingenua puede ser una sorpresa, pero demuestra muy bien nuestro punto: desovar descuidadamente las goroutinas puede conducir a una degradación seria del rendimiento. Además, el acelerado easy y secuencial está muy bien, no es trivial encontrar algo más rápido.
Resumen
En este artículo, examinamos lo que sucede cuando dejamos que las goroutinas se descontrolen y lo que podemos hacer al respecto.
Nuestro grupo de trabajadores es muy easy: una implementación sólida utilizaría una cola de tareas más sofisticada con cancelación de trabajo, tiempos de espera a través de context.Context and so forth. no cubrimos los patrones de gestión de la memoria, como usar sync.Pool Para reutilizar las asignaciones de memoria para las particiones izquierda y derecha. Y la lista continúa.
La concurrencia es un tema vasto, y hay muchos patrones y técnicas para explorar, solo comenzamos a rascar la superficie aquí.
El patrón de grupo de trabajadores es una herramienta poderosa para administrar goroutinas, pero no la única. La conclusión clave es: el paralelismo controlado supera la concurrencia caótica cada vez.
