Hace tiempo que voy dándole vueltas a la manera en que se desarrollan la mayoría de aplicaciones web, especialmente en php y cada vez más siento la necesidad de cambiar la manera de trabajar, en realidad, casi de cambiar mi lenguaje de programación habitual, php, por otra cosa.
Uno de los lenguajes que me interesa mucho es golang. Me gusta su sintaxis parecida al C, que es un lenguaje compilado, que está muy pensado para ayudar al programador y, sobretodo, me interesa lo fácil que es crear rutinas que corren en paralelo y que se pueden comunicar limpiamente mediante canales seguros.
Las CPUs de hoy en día tienen múltiples cores, cualquier ordenador doméstico o teléfono puede tener fácilmente entre 2 y 8 cpus corriendo y golang es posiblemente el lenguaje que permite usar esa potencia con más facilidad.
Hoy me he decidido a hacer un pequeño ejercicio, un cálculo de los números primos en un rango dado de enteros. Quería ver si es fácil implementar un problema simple, y también quería probar si es fácil el uso del cálculo paralelo con Go. La verdad es que me he divertido mucho. Go es fácil de usar, el compilador te ayuda mucho a la hora de programar y la sintaxis es limpia y se entiende muy rápido.
El problema a resolver
El problema es sencillo. Dado un rango de números enteros, por ejemplo 1 a 1.000.000, queremos saber cuales de ellos son números primos.
En un lenguaje tradicional como php, o en java o C++ si no queremos complicarnos la vida, el algoritmo sería algo así como:
Para todos los enteros entre <inicio> y <fin>, si es primo, mételo a la lista y mira el siguiente.
Un número primo es aquel que sólo es divisible por 1 y por si mismo, o sea que es un problema que podría resolverse por fuerza bruta, intentando dividir ese número por todos los inferiores superiores a 1. Si el resto (módulo) de la división es cero en algún momento, el número no es primo. Hay otros métodos más óptimos de calcular un número primo, pero no es ese nuestro objetivo y ya nos va bien para el ejercicio usar un mecanismo de fuerza bruta.
¿Que ocurriría si en lugar de iterar sobre un bucle para cada posible candidato, lanzásemos todos los cálculos en paralelo? A fin de cuentas, ¿a quien no se le ha pasado por la cabeza lanzar un millón de procesos en paralelo y ver como la CPU salta por los aires 😉 ? La respuesta: No ha pasado nada. En mi máquina de pruebas, Go ha sido capaz de ejecutar 1 millón de procesos simultáneos sin pestañear, devolviendo la respuesta en menos de 10 segundos.
Te reto a hacer la prueba con php, java o incluso C++. Y en menos de 100 líneas de código.
El código fuente y cómo instalarlo
No es necesario que te bajes el código para seguir el tutorial, pero si quieres toquetear un poco y no te apetece copiar y pegar, lo tienes en https://github.com/x1m3/primeNumberTest.
Primero tendrás que instalar go, en mi caso un simple apt-get golang. Luego tendrás que crear un directorio de trabajo y apuntar la variable GOPATH a este. En mi caso, mkdir golang; cd golang; export GOPATH=pwd.
Finalmente, go get github.com/x1m3/primeNumberTest bajará el código y te lo dejará dentro de la carpeta ./src. En ./bin encontrarás el ejecutable, que siempre podrás generar de nuevo ejecutando go install github.com/x1m3/primeNumberTest
¿Fácil, verdad? y es que golang está pensado para que los desarrolladores sean felices.
La ineficiente rutina que nos dice si un número es primo
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
package main import "math" /** * A non very optimal function that checks if a number is prime * * A prime number is one that only is divisible by 1 or itself * * The algorithm is pure brute force, iterating by numbers smaller * than the candidate and calculating the modulus * * We only use 3 optimizations. * 1) If the number is different than 2, but divisible by 2, it is not a prime. * 2) Then, we only test for odd divisors (3,5,7,9, etc..) * 3) We only check for numbers smaller or equal the root square * of the candidate. It is imposible to have divisors greater * than this value */ func isPrime(candidate int64) (bool) { var i,limit int64 if candidate==2 { return true } if math.Mod(float64(candidate), 2)==0 { return false; } limit = int64( math.Ceil( math.Sqrt(float64(candidate) ))) for i=3; i<=limit; i+=2 { //Only odd numbers if math.Mod(float64(candidate), float64(i))==0 { return false } } return true } |
Vamos a comentar un poco el código, algo que nos vendrá muy bien si eres nuevo en go.
Lo primero que vemos es que hay pocos paréntesis y prácticamente ningún punto y coma. Los condicionales o bucles no necesitan los paréntesis, a fin de cuentas son obvios. Tampoco es necesario usar ; para indicar final de línea. Menos cosas a escribir (Veo que se me coló un ; en la línea 28… si es que salen automáticos ya).
La definición de la función es limpia y no tiene secretos.
|
|
func isPrime(candidate int64) (bool) { |
La función se llama isPrime, acepta un parámetro de tipo int64 y devuelve un booleano. Primera sorpresa: Golang tiene tipos, algo que puede resultar un poco engorroso para los programadores de javascript o php pero que también puede ayudarnos mucho a la hora de evitar efectos indeseados.
Hay que definir las variables e indicar su tipo. 2 comentarios aquí. Golang no compilará si una variable se ha definido pero no se ha usado. Una buena ayuda para mantener nuestro código limpio. También es posible definir variables en marcha sin especificar el tipo, siempre que este pueda ser inferido por el programador. Para ello, en lugar de usar la asignación con =, escribiremos :=.
Por ejemplo:
Creará una variable llamada i de tipo integer, ya que 5 es un entero. Esto es muy útil para definir variables «tontas», de aquellas que sólo tienen sentido en una pequeña parte del código. Por ejemplo una variable que sólo vaya a usarse en un bucle:
|
|
for i:=0; i<10; i++ { for j:=0; j<i; j++ { for z:=0; z<j; z++ { |
Crearía 3 variables i,j,z que se usarían dentro del bucle pero no tendríamos que definir.
|
|
package main import "math" . . . if math.Mod(float64(candidate), float64(i))==0 { . . . |
WTF.. ¿Esto es necesario para calcular el módulo? No. Lo hemos hecho así para realizar los cálculos en coma flotante y darle más caña a la CPU. En realidad, podríamos haber usado el operador % sobre integers. Pero ya que estamos, expliquemos de que va.
math.Mod calcula el resto de una división entera entre sus dos parámetros, que son número flotantes de 64 bits. Para usar la función hemos tenido que hacer un import de la librería math. Como no tenemos conversión implícita de tipos, hemos tenido que forzar una conversión (cast) y convertir los enteros en flotantes. La sintaxis es limpia, float64() tiene forma de función, lo cual me parece más agradable que la sintaxis en C o php.
La versión secuencial de la función que calcula todos los primos en un rango
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
package main import "fmt" /** * Accepts a range of integers [min, max] and * returns an array with all the prime numbers in this range. * * Execution is done sequentially */ func primesInRange( min int64, max int64) []int64 { var primeNumbers []int64 var prev int64 prev=0 for i:=min; i<=max; i++ { if isPrime(i) { primeNumbers= append(primeNumbers, i) // -- Stupid code that shows the progress to the user. done := 100 * (i-min)/(max-min) if prev!=done { fmt.Printf("%d %% done.\n",done) prev=done } } } return primeNumbers } |
Tampoco hay mucho secreto aquí, aunque si que tendremos que explicar algunos detalles interesantes.
|
|
func primesInRange( min int64, max int64) []int64 { |
Atentos a los corchetes en el parámetro de retorno. Esta función acepta 2 enteros de 64 bits y devuelve una slice (una «lista») de enteros de 64 bits. Los arrays son de longitud fija en Go, igual que en C. Los slices son un concepto que permite referirnos a un rango dentro de un array. Yo los interpreto con un puntero al array, en el que también sería posible definir la longitud. En el ejemplo que nos interesa a nosotros, podemos considerarlo como una lista de longitud variable.
Por lo demás, ningún secreto en esta función. Se itera desde el primero hasta el último con un bucle for y se va comprobando si es primo llamando a la función isPrime() que ya comentamos antes.
|
|
for i:=min; i<=max; i++ { if isPrime(i) { primeNumbers= append(primeNumbers, i) |
A comentar aquí, para añadir un elemento a la lista primeNumbers hemos de usar la función append, pasándole la lista original y el nuevo elemento. Esto no es muy óptimo, ya que append hace una copia del array y devuelve la nueva copia. Luego ya vendrá el garbage collector a salvarnos el culo, pero este mecanismo podría causarnos problemas de memoria.
La versión paralela. Empieza la fiesta
Hasta ahora, nada interesante. Un código que podríamos haber picado en cualquier lenguaje. Pero nos hemos dado cuenta de una cosa. Averiguar si cada número es primo o no es independiente de sus vecinos. ¿Por qué calcularlos de uno en uno si podríamos hacerlos todos a la vez? O, por lo menos, podríamos hacerlo de cuatro en cuatro u ocho en ocho en función del número de procesadores que tengamos.
La idea sería crear un thread para cada cálculo y recoger la respuesta de alguna manera. Hacer eso con php sería complicado y poco eficiente. Su librería de threads no es lo mejor que se ha inventado. Programadores de C++ o Java se atreverían a picar unas cuantas líneas de código y algún mutex para hacerlo. Un trabajo pesado. Los de javascript y node podrían tenerlo más fácil, usando las funciones de callback. Por desgracia node.js no es precisamente óptimo en operaciones que usan mucha cpu.
¿Y que tal con Golang?
El código completo de este apartado está en rangeParallel.go
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
func primesInRangeParallel( min int64, max int64) []int64 { var primeNumbers []int64 var res PrimeResult var prev int64 channel := make(chan PrimeResult) defer close(channel) go firePrimeCalculations(min, max, channel) prev=0 for i:=min; i<=max; i++ { res = <- channel if res.prime { primeNumbers= append( primeNumbers, res.number) done := 100 * (i-min)/(max-min) if prev!=done { fmt.Printf("%d %% done.\n",done) prev=done } } } return primeNumbers } |
Vamos a ir poco a poco. Primero decir que la función se parece mucho a la anterior, salvo unos ligeros cambios. Lo primero que hacemos es definir un canal (chan) que acepta tipos PrimeResult.
|
|
channel := make(chan PrimeResult) |
PrimeResult es una estructura que hemos definido nosotros así:
|
|
// We will use this struct to communicate results via a channel type PrimeResult struct { number int64 // A number prime bool // Is prime or not } |
es decir, un número y un booleano que nos dice si el número es primo o no.
Ya podemos intuir que eso llamado canal no es otra cosa que un canal de comunicación que usaremos para comunicar procesos. Piensa en ello como algo parecido a un pipe de unix.
Una línea interesante. El mecanismo defer es propio de Golang y sirve para especificar que ese comando debe ejecutarse cuando la función finalice. Así no nos olvidaremos nunca de cerrar el canal, algo que es obligatorio hacer. Por decirlo de manera coloquial, defer close(channel) significa «y cuando acabes, cierra el canal llamado channel».
|
|
go firePrimeCalculations(min, max, channel) |
¡Guau! Nuestra primera llamada a go. A partir de este punto tendremos 2 hilos de ejecución, el actual, y uno nuevo que ejecutará la rutina firePrimeCalculations.
|
|
func firePrimeCalculations( min int64, max int64, channel chan PrimeResult) { var i int64 for i=min; i<=max; i++ { go isPrimeAsync(i, channel) } } |
firePrimeCalculations() es muy sencillita, pero importante. Tiene un bucle en el que va lanzando ejecuciones paralelas de isPrimeAsync(). Fijaos en la palabra go antes de la llamada. Por cada vuelta del bucle creará un nuevo hilo de ejecución. ¿Y si el bucle tiene 1.000.000 de valores? Pues.. crearemos 1.000.000 de hilos..
Notar también que cada llamada a isPrimeAsync() recibe un número diferente y el canal por el que debe devolver el resultado.
|
|
func isPrimeAsync(number int64, channel chan PrimeResult) { result:= new (PrimeResult) result.number= number result.prime= isPrime(number) channel <- *result } |
Aquí tenemos el secreto de la comunicación entre los procesos. Primero creamos un objeto de tipo PrimeResult. Notad el uso del comando new. Luego asignamos sus dos valores number y prime. Para calcular si es primo llamamos a la función isPrime() que habíamos definido al principio.
Y la parte interesante. Devolvemos el resultado por el canal, para quien pueda estar interesado. Notad aquí ese asterisco, que huele a C de mala manera. result es en realidad un puntero, nosotros queremos devolver el valor al que apunta, por eso el *.
Vale, ¿Y quien diablos lee el canal?
Pues tienes la lectura del canal en la función primesInRangeParallel(), cuyo código mostramos bastante arriba. En concreto, en este bucle
|
|
for i:=min; i<=max; i++ { res = <- channel if res.prime { primeNumbers= append( primeNumbers, res.number) |
La línea res= <- channel es la que nos interesa. Espera a que alguien escriba en el canal y recoge el resultado que llegue. Es importante señalar en que la lectura es bloqueante. Esperará a que cualquier hilo finalice y tomará el resultado.
Todo se ejecuta dentro de un bucle por que si habíamos lanzado n hilos de cálculo, tenemos que esperar n respuestas.
¿Y los benchmarks donde están?
La gracia de esta prueba era probar un poco las posibilidades de golang, y el paralelismo es posiblemente la más importante de ellas. La verdad es que el ejemplo que hemos usado no es óptimo para probar paralelismo, porque un cálculo de módulo es tan rápido que el overhead introducido a la hora de crear y destruir hilos puede ser mayor que la ventaja obtenida con el paralelismo. Por eso hemos complicado un poco el cálculo del módulo forzando una operación en punto flotante.
No lo he explicado hasta ahora, pero si bajas el código fuente y lo instalas encontrarás un ejecutable llamado primeNumberTest que acepta 3 parámetros: valor inicial, valor final y parallel o sequential.
Con eso podrás hacer pruebas ajustadas a tu ordenador y probar que versión es la más rápida.
Por lo general, la versión secuencial será más rápida en máquinas con pocos nucleos y/o cálculos de números pequeños. Las máquinas con muchos cores se beneficiarán mucho más de la versión paralela.
Atención a la variable de entorno GOMAXPROCS. Le indica a go el número de procesadores que debe usar. Según la documentación se ajusta al número de cores disponibles automáticamente, pero yo me he encontrado con que no era así en un server virtual de linode. Para ello he debido asignarle el valor 4, para que use 4 cores de los 6 que tenía la máquina disponible
Para que te hagas una idea de los tiempos que he obtenido, estos son los resultados, ejecutados con 4 procesadores, en un servidor que actualmente tiene 6 y que estaba trabajando con un apache y un varnish, sirviendo webs en producción (con un par…).
export GOMAXPROCS=4
time ./bin/primeNumberTest 2000000 3000000 parallel
real 0m8.355s
user 0m26.730s
sys 0m2.550s
time ./bin/primeNumberTest 2000000 3000000 sequential
real 0m20.681s
user 0m20.273s
sys 0m0.177s
Ignora el valor de user en el caso paralelo, porque suma el tiempo de cálculo en cada core. Como usamos 4 cores casi al 100% se ha ido a un valor de 26 segundos. Pero el tiempo que el usuario esperó no es ese.
Dicho a lo bruto, la versión paralela ha sido casi 2 veces y media más rápida que la secuencial. A cambio, hemos usado 4 cores en lugar de uno, por lo que hemos perdido casi un core y medio en la gestión del paralelismo. Si el problema hubiese sido diferente, por ejemplo, con conexiones de entrada/salida o esperas de usuario, la eficiencia habría sido superior.
Conclusiones
No me quiero enrollar más, que ya me he alargado mucho, pero quisiera hacer dos o tres comentarios.
Golang me ha parecido agradable de usar y creo que es un lenguaje robusto con mucho recorrido. La sintaxis es clara y los canales y las gorutinas son una maravilla que permite jugar con el paralelismo muy fácilmente.
Golang no es demasiado orientado a objetos. Pero tampoco es un lenguaje procedural. Para mi, es un lenguaje orientado al paralelismo. Quizás se echan a faltar algunas características de la orientación a objetos pero su simpleza sintáctica y las llamadas go permiten resolver problemas de manera sencilla que podrían ser un infierno en otros lenguajes.
Está muy orientado a los flujos de trabajo actuales, por ejemplo la instalación de vendors desde repositorios git. No lo he tratado aquí pero tiene soporte para tests unitarios de serie.
Verdaderamente, creo que golang ha llegado para quedarse. Personalmente, pienso meterme más a fondo con el. Seguro que seguiré dándoos la vara con el.