lunes, marzo 03, 2008

Tail Recursion

Pues bien. Tail Recursion es una técnica común de optimización para las llamadas recursivas. Básicamente lo que intenta hacer es eliminar los continuos llamados a la función (call) y mas bien los reemplaza con saltos. Para entender ésto comencemos con un ejemplo:

unsigned int
factorial(unsigned int n){
if (n != 0)
return (n * factorial(n-1));
else
return 1;
}


El factorial recursivo de toda la vida... cierto?

Miremos el ensamblador:


_factorial:
pushl %ebp
movl %esp, %ebp
subl $8, %esp
cmpl $0, 8(%ebp)
je L2
movl 8(%ebp), %eax
decl %eax
movl %eax, (%esp)
call _factorial
imull 8(%ebp), %eax
movl %eax, -4(%ebp)
jmp L1
L2:
movl $1, -4(%ebp)
L1:
movl -4(%ebp), %eax
leave
ret

Éste pedazo es lo que se encarga de mantener los registros de la pila. Cada llamada a una función debe hacer ésto. Crear un nuevo marco para preservar el "contexto".


_factorial:
pushl %ebp
movl %esp, %ebp
subl $8, %esp
...
L1:
movl -4(%ebp), %eax
leave
ret


Si la profundidad de la recursión es muy grande, corremos el riesgo de quedarnos sin pila dado que cada marco utiliza su propia fracción de la pila. Además... gastamos algunos ciclos en las operaciones para preservar el contexto.

Ahora bien... en el caso del factorial, pensar un código iterativo equivalente que no utilice pila resulta fácil. Mejor aún, es posible garantizar que para ciertos tipos de recursión se pueda hacer ésta traducción en forma automática. Las recursiones que se pueden traducir son llamadas Tail Recursions o Recursiones de cola y deben cumplir una sencilla condición. En el bloque que suceda la llamada, no debe haber trabajo extra... Es decir, el bloque donde suceda la llamada a la función solo debe estar ésta.

Siendo así él código en C, debe ser modificado: Una forma usual de hacer ésto es utilizar un acumulador para hacer la multiplicación:

unsigned int
factorial(unsigned int n, unsigned int accum){
if (n != 0)
return factorial(n-1, accum * n);
else
return accum;
}


Ésto nos genera:


_factorial:
pushl %ebp
movl %esp, %ebp
subl $12, %esp
cmpl $0, 8(%ebp)
je L2
movl 12(%ebp), %eax
imull 8(%ebp), %eax
movl %eax, 4(%esp)
movl 8(%ebp), %eax
decl %eax
movl %eax, (%esp)
call _factorial
movl %eax, -4(%ebp)
jmp L1
L2:
movl 12(%ebp), %eax
movl %eax, -4(%ebp)
L1:
movl -4(%ebp), %eax
leave
ret


Y con una simple modificación podemos evitarnos el overhead de cada llamada a la función y nos evitamos el gasto de memoria de pila:

Es cuestión de copiar los parámetros en donde estaban los antiguos, reemplazar el call por un salto al lugar justamente posterior que se encarga de mantener el marco de pila. Y se puede eliminar el código inalcanzable.


_factorial:
pushl %ebp
movl %esp, %ebp
subl $12, %esp
_tail:
cmpl $0, 8(%ebp)
je L2
movl 12(%ebp), %eax
imull 8(%ebp), %eax
movl %eax, 12(%ebp)
movl 8(%ebp), %eax
decl %eax
movl %eax, 8(%ebp)
jmp _tail
L2:
movl 12(%ebp), %eax
movl %eax, -4(%ebp)
movl -4(%ebp), %eax
leave
ret

No hay comentarios.: