Benchmark Factorial – Parámetros acumulados

Voy hacer un benckmark de 3 implementaciones de factorial:

Em primer lugar, la implementación más simple y eficiente, por siempre de los jamases, al menos para arquitecturas de Von Newman y monoprocesador:

long factorial_iterativo(long n)
{
	long i, ac = 1;
	for(i=n; i>0; i--)
		ac = ac * i;
	return ac;
}

Despues esta la recursiva lineal, típico ejemplo de recursividad. Fijaos en la linea de la llamada recursiva …

long factorial_recursivo(long n)
{
	if (n == 0)
		return 1;
	else
		return n * factorial_recursivo(n-1);
}

Y esta es la que realmente tenía curiosidad de comparar.  Es un tipo de recursividad que hace que la vuelta en lugar de ser de pila, sea de cola. Es necesario modificar la interfaz y crear una nueva función manejadora que respete la interfaz. Se trata de ir acumulando el resultado como parametro y principalmente que en la linea que se hace la llamada recursiva, solo haya una llamada recursiva.

Esta función, teoricamente implementado en Caml el compilador al pasarlo a código maquina la pasa a iterativa automaticamente. Si esto fuera tambien así en C, podríamos utilizar funciones recursivas, sin miedo a desbordar la pila y sin problemas de redimiento. Y por supuesto ganando la claridad de resolver algunos problemas de naturaleza recursiva.

long _factorial_recursivo_PA(long n, long r)
{
	if (n==0)
		return r;
	else
		return _factorial_recursivo_PA(n-1, n*r);
}

long factorial_recursivo_PA(long n)
{
	return _factorial_recursivo_PA(n, 1);
}

Los resultados son estos:

Señal SIGCHLD – Evitar Zombies

Hace un par de años hice una práctica de sockets, con el típico modelo cliente-servidor donde el servidor da servicio multicliente con fork(). La práctica cumplía los requisitos y los profesores no detectaron problemas.

Realmente la práctica tenía un bug y es que en ocaciones, se quedaban procesos zombies. Realmente el problema es que confie en el código base que nos daban los profesores, que estaba bugeado. Ahora he tenido que reutilizarla para otra asignatura, y ahora ya se cual era el problema.

En sistemas Unix, un proceso puede tener hijos ¬¬, creados mediante fork. Cuando el hijo termina, se envía la señal SIGCHLD al padre. Por defecto, la señal se ignora y se crea un proceso zombie. El padre debe instalar un manipulador de señales para actuar sobre la señal, ese era mi problema. En algunas plataformas Unix, se pueden evitar los zombies explícitamente ignorando la señal SIGCHLD. Sin embargo, instalar un manipulador de señales para SIGCHLD y llamar a wait es la mejor manera de evitar zombies conservando la portabilidad.
El manipulador de la señal:

void sigchld_handler(int s)
{
    while(wait(NULL) > 0);
}

Hay varias funciones o métodos para setear la señal, os pongo 2, el largo(más portable, POSIX) y el corto(desconozco su portabilidad):

    struct sigaction sa;
    sa.sa_handler = sigchld_handler; // manejador

    sigemptyset(&sa.sa_mask);
    sa.sa_flags = SA_RESTART;
    if (sigaction(SIGCHLD, &sa, NULL) == -1)
    {
        perror("Error en sigaction");
        exit(1);
    }

Os dejo la forma más corta y fácil:

signal(SIGCHLD , sigchld_handler);

No hace falta decir que necesitais el «signal.h»

Fuentes: http://es.wikipedia.org/wiki/SIGCHLD