Monthly Archives: September 2008

You are browsing the site archives by month.

La Formula 1 enciende las luces

Este fin de semana se celebra el Gran Premio de Formula 1 Singapur 2008. Éste se caracteriza por ser la primera vez en la historia donde se realizará una carrera de formula 1 de noche, con luz artificial.

El resultado no puede ser más espectacular:

Quien no haya pensando en un Need for Speed al ver el vídeo, es que no lo conoce.

Esperemos que no llueva en el gran premio, pues se vería mucho menos la carrera (e incluso podría llegar a suspenderse por la peligrosa combinación de lluvia más luz artificial).

Actualización [28 sept. 17h]: La carrera ha sido increíble en ambos sentidos, tanto el desarrollo de la carrera con adelantamientos (casi imposibles), coches de seguridad, estrategias e incidentes; como por el espectáculo de la noche como telón del espectáculo.

El derroche en energía consumida debe de ser descomunal, pero siendo egoísta, espero que más carreras sigan esta nueva moda de carreras nocturnas.

Paralelizando quicksort en Erlang

Haciendo pruebas con erlang, se me ocurrió que sería divertido probar a paralelizar algún algoritmo típico (sobretodo debido a que mi cpu es ahora un quadcore). Como mi imaginación no está muy avanzada, probé con el quicksort.

Su implementación en un lenguaje funcional suele ser bastante simple. Y en Erlang podría ser algo simplemente como:

qsort([]) ->
   [];
qsort([Pivot|T]) ->
   qsort([X || X <- T, X < Pivot])   ++
   [Pivot]                           ++
   qsort([X || X <- T, X >= Pivot]).

En un primer (y estúpido) intento por paralelizarlo, probé simplemente a que cada llamada recursiva fuese un nuevo proceso. El asunto terminó con el ordenador medio bloqueado al intentar crear millones de procesos (pues inicié erlang poniéndole explícitamente que no hubiese límite :P, por defecto tiene 216 como límite).

El asunto tiene simple solución. Si tenemos un problema por permitir un exceso de procesos, pues se pone un límite y arreglado, ¿no?. El esquema usado simplemente es que para cada llamada recursiva, se indicará el número máximo de procesos que puede crear el proceso en cuestión y todos sus hijos. Si las llamadas recursivas de un quicksort van a ser un árbol donde cada nodo tendrá dos hijos, simplemente vamos a podarlo para que finalmente las hojas de dicho árbol ejecuten el algoritmo quicksort normal y el resto, los nodos, realizarán el quicksort paralelo (p_qsort lo he llamado).

%%
%% Params: 
%%   - List to be sorted
%%
p_qsort(L) ->
   S   = self(),
   Ref = erlang:make_ref(),
 
   spawn(fun() -> 
            p_qsort(L, ?THREAD_LIMIT, S, Ref) 
         end),
 
   gather(Ref).
%%
%% Params: 
%%   - List to be sorted
%%   - Maximum number of processes can be created
%%   - Father process (the results will be sent to him)
%%   - Unique reference for knowing what position the results are in
p_qsort([], _, Father, Ref) ->
   Father ! {Ref, []};
p_qsort([Pivot|T], Limit, Father, Ref) when Limit > 2 ->
   S       = self(),
   R_right = erlang:make_ref(),
   R_left  = erlang:make_ref(),
 
   spawn(fun() -> 
            p_qsort( [X || X <- T, X <   Pivot], Limit div 2, S, R_left)
         end),
   spawn(fun() -> 
            p_qsort( [X || X <- T, X >=  Pivot], Limit div 2, S, R_right) 
         end),
 
   Father ! {Ref, gather(R_left) ++ [Pivot] ++ gather(R_right)};
p_qsort(L, _, Father, Ref) ->
   Father ! {Ref, qsort(L)}.

La función con un único parámetro es la función pública de entrada. Ésta, crea un proceso con la función de quicksort paralelo indicando un número, como segundo parámetro, que significa el número máximo de procesos que puede crear. En las funciones siguientes tenemos primero el caso de lista vacía, seguido de la función que ejecutarán los nodos (los que todavía pueden crear procesos hijos) y finalmente cuando no podemos crear más procesos se resolverá simplemente llamando a qsort(L) (los procesos hoja del árbol de llamadas).

Algunas aclaraciones adicionales por si no estas muy puesto en Erlang:

  • Con spawn estamos creando un nuevo proceso. En este caso le pasamos una referencia al actual proceso, tercer parámetro, para que nos “mande” sus resultados
  • Con Variable ! Algo se está mandando el mensaje ‘Algo’ al proceso ‘Variable’
  • Erlang llama a las funciones con un matching de los parámetros (similar a prolog), en este ejemplo es bastante importante la condición when Limit > 2 que condicionará si crearemos más procesos o no
  • La función gather es solo una función para “recolectar” un resultado que me he montado copié de Joe Amstrong:
    %%
    %% Purpose: Receive a response of a process which have sent {Ref, Something}
    %% Params :
    %%   - A erlang reference for matching the message
    %% Return : The second item inside the received message
    gather(Ref) ->
       receive
          {Ref, Ret} -> Ret
       end.

    Para hacer pruebas, me he creado un par de módulos erlang para facilitar la ejecución:

    • benchmark.erl: define do/1 y do_silent/1 a las cuales les pasamos una función y nos devolverá el tiempo en µs (e imprimiendo un mensaje por pantalla).
    • test_sorting.erl: define funciones para ejecutar algoritmos de ordenación generando listas de tamaño variable de forma aleatoria. Usa el modulo de benchmark anteriormente citado, para crear csv‘s con los resultados de las ejecuciones.

    Mientras se ejecutaban los algoritmos, me pareció que sería curioso capturar el consumo de cpu de ambos, te dejo que intentes adivinar cual se corresponde con el algoritmo “tradicional” y cual con el “paralelo” (no vale mirar el nombre :P).

    Los resultados detallados, los he copiado en esta hoja de cálculo para OpenOffice, y un resumen de ellos los podemos ver en esta gráfica creada con gruff en ruby leyendo los csv generados desde erlang.

    ejecución de un quicksort paralelo en erlang

    El algoritmo paralelo es el doble de rápido que el tradicional, con valores medianos o grandes. Con valores menores a 1000 elementos es más costoso (al crear procesos, aunque erlang es mucho erlang, estamos incorporando un coste adicional, principalmente por el envío de mensajes, no por la creación per-se), pero en tales casos no sé para qué narices estamos mirando formas de mejorar el rendimiento, pues mil elementos los ordena hasta MySQL mi vecino.

    Lo que hay que destacar es la mejora sustancial conseguida, prácticamente sin cambiar nada (el código paralelo es trivial una vez se tiene la versión “normal”).

    Algunas cosas interesantes de probar serían:

    • Intentar ésto mismo con un número de cpus mayor a 4, y encontrar la relación entre cpus y ganancia.
    • Crear algún “behaviour” para erlang para poder generalizar la paralelización de algoritmos de divide y vencerás (que son bastante comunes) y siguen este esquema con bastante homogeneidad.

    Si quieres obtener todos los ficheros para ojear o jugar por ti mismo, aquí lo tenemos.

    Have fun.

La elite de los programadores, los que leen

Comentario con miga de Joel Spolsky, que se podría traducir algo así como:

La audiencia que lee Coding Horror y la audiencia que lee Joel On Software están ya entre la elite de los programadores, porque son los tipo de personas que leen cosas con el propósito de mejorar sus cualidades. Y son, así a ojo de buen cubero, 5-10% del total de programadores activos.

No es la gran masa de carne java quienes fueron anteriormente machacateclas en visual basic quienes fueron previamente tiralíneas de cobol quienes están haciendo ahora grandes cantidades de historias extremadamente aburridas internamente en algún lugar. Ah, ¿No te he ofendido?.

Más que elite yo los llamaría decentes. Más sobre el tema aquí.

Garfield sin garfield, como la vida misma

Una de mis tiras cómicas preferidas.

También en español (aunque tampoco es que tenga mucho texto que digamos…).