Ejercicio Golang: Cálculo números primos con goroutines

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

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.

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:

Crearía 3 variables i,j,z que se usarían dentro del bucle pero no tendríamos que definir.

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

Tampoco hay mucho secreto aquí, aunque si que tendremos que explicar algunos detalles interesantes.

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.

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

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.

PrimeResult es una estructura que hemos definido nosotros así:

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».

¡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.

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.

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

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.

 

Publicado por

Jordi Giménez

¡Hola! Me llamo Jordi Giménez, soy programador y vivo en Barcelona.

4 comentarios en “Ejercicio Golang: Cálculo números primos con goroutines”

  1. Buenas tardes, estoy realizando un programa en lenguaje go , el cual consiste en genera código de máquina en lugar de respuestas de inmediata cuando le introduces 4+5 (por ejemplo). Una vez que se alcanza el final de una instrucción, se ejecuta el código generado ( «interpretarse») para calcular el resultado deseado. No se si podrías ayudarme a entender más del lenguaje Go ya que soy inexperta en el lenguaje. Y tener contacto por medio del correo.
    Saludos y muy buen artículo.

Responder a Luis Pazos Cancelar respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *