Duda respecto al calculo del stack

Duda respecto al calculo del stack

de Agustín Occhiuzzi Rodríguez -
Número de respuestas: 12

Hola buenas, quería sacarme esta duda porque cuando resuelvo recursivos en donde luego piden calcular el stack difiero un poco de la solución, mi duda es la siguiente y es : que debería sumar en el consumo del stack en un llamado recursivo? En cuanto a calcular el consumo en el paso base creo que lo tengo claro pero cuando voy a calcular el paso recursivo me entran dudas. Pongo un ejemplo simple: 

funcionEjemplo proc

"Se preserva contexto y otras operaciones de asignacion"

CMP condicion (condicion para ir al paso base)

JE casoBase

"aqui pase al paso recursivo(no cumplí la condicion del paso base)"

PUSH AX  ; pusheo un valor que tenía en ax que NO es parametro para guardar y popearlo después que es algo que hago y las soluciones no

PUSH Parametros*pusheo parametros*

CALL funcion

POP Resultado

POP AX ; recupero el que pushié anteriormente para preservarlo luego de salir de la recursion

*más codigo*


Luego del ejemplo mi pregunta es la siguiente, cuando calculo el consumo de stack de este paso recursivo, este valor (o mas valores que pusheo antes de pushear los parametros) que preservo forma parte del consumo de stack del paso recursivo? O por popearlo luego no genera un consumo extra? Desde ya muchas gracias.

En respuesta a Agustín Occhiuzzi Rodríguez

Re: Duda respecto al calculo del stack

de Gustavo Brown -

Agustín,

  Lo tenes que tomar en cuenta porque esa palabra que pusheas queda en el stack hasta que retornes de las llamadas recursivas que se hagan en tu programa. Es decir que se van apilando mientras tu rutina siga haciendo llamadas recursivas. Recién recuperas su consumo en el stack al retornar de la llamada recursiva.

Si en tu ejemplo tuvieses otra llamada recursiva luego de la primera (y luego de hacer el POP AX) entonces para el cálculo de la segunda llamada recursiva no lo tendrías en cuenta (porque recuperaste el espacio previo a llamarla).

Es decir, tenes que tener en cuenta cuantas palabras adicionales agregaste al stack desde que se activó la función hasta el punto en que comenzas a colocar los parámetros de la llamada recursiva.

Podés hacerte un esquema, ejecutando con el dedo la rutina y viendo cómo va quedando el stack a medida que ejecutás hasta la llamada recursiva. Ahi podés chequear que estés haciendo bien los cálculos.

Saludos,
  Gustavo

En respuesta a Gustavo Brown

Re: Duda respecto al calculo del stack

de Agustín Occhiuzzi Rodríguez -
Gracias Gustavo, entendí bien pero me surgió otra duda, entonces cuando calculo este consumo del paso recursivo tengo en cuenta lo que está en el stack antes de hacerle push a los parametros, o sea que se sumarían al consumo los parametros de antes de llamar al paso recursivo , o estos no se sumarían? La misma duda tengo con el IP de cuando hago el call en el paso recursivo. Si creo que entendí bien , cuando haga un esquema a mano de todo lo que tengo en el stack cuando hago el paso recursivo sería :

CONTEXTO + DIR_RET + PARAMETROS + VALORES_QUE_PUSHEO (como el ax de mi ejemplo) + PARAMETROS_REC + DIR_RET_REC

Y mi paso base tendría consumo por ejemplo :

CONTEXTO + DIR_RET + PARAMETROS

estoy en lo correcto o estoy sumando de más?
En respuesta a Agustín Occhiuzzi Rodríguez

Re: Duda respecto al calculo del stack

de Belen Brandino -
hola,
si, todas esas cosas se suman. si quisiera hacer un esquema como dijo gustavo haria algo asi (es de otro ejercicio):

en este caso vemos la primer llamada a la función y la primer llamada recursiva. tenemos dos parametros (aquiArbolito, arquiChirimbolo), el IP y el contexto salvado al inicio del programa. Luego, en la segunda llamada se apilan en el stack los parametros correspondientes, el IP (apilado al ejecutar el CALL) y el contexto, que solo se ve el BP pero irían todos los registros, y luego todas las llamadas sucesivamente. 
Aca siempre tenes que tener cuidado de no contar algo en lo que llamas paso recursivo y luego contarlo en el paso base nuevamente. Por ejemplo, en tu caso interpreto que contas en el paso base los parámetros e IP que ya están contados en la última llamada recursiva antes del paso base haciendo PARAMETROS_REC + DIR_RET_REC
si quedan dudas pregunta de nuevo
saludos!
En respuesta a Belen Brandino

Re: Duda respecto al calculo del stack

de Franco Pelua Camacho -
Hola! me sumo a la consulta porque no se si estoy entendiendo bien. Pongamos de ejemplo el ejercicio 2 del práctico 8, de la secuencia de Fibonacci.

Por como hice mi función, tengo dos paso base que, según entiendo, no consumen stack, porque en ellos no hay llamadas recursivas ni pusheo de valores al stack.

Luego, en mi paso recursivo hay: 2 instrucciones PUSH de registros de 16 bits, y dos instrucciones CALL.

Primera pregunta, cuando hago CALL, entiendo que detrás de escena lo que pasa es un PUSH IP, ¿IP es de 16 bits?
Voy a suponer que IP es efectivamente de 16 bits para seguir el ejemplo.

Entonces en definitiva, en el paso recursivo, hago dos push de 2 bytes cada uno, y dos CALL de 2 bytes cada uno tambien.

Finalmente, si quiero calcular consumo(N) donde N es el indice del número de fibo que quiero conseguir, esto sería:

consumo(N) = consumo(0) + consumo(1) + consumo(N-1) + consumo(N-2)
= consumo(N-1) + consumo(N-2) (Por que los pasos base consumen cero bytes)
= (8 bytes/call recursiva) x N-1 + (8 bytes/call recursiva) * N-2 (Porque en los pasos recursivos termino consumiendo 8 bytes)

¿Está bien ese análisis?
Gracias y saludos de antemano!
En respuesta a Franco Pelua Camacho

Re: Duda respecto al calculo del stack

de Gustavo Brown -
Franco,
Pasá el código para ver el consumo, porque justamente depende de tu implementación.
El stack siempre se maneja de a palabra de 16 bits, solamente se puede PUSHear una palabra o POPear una palabra. IP es un registro de 16 bits
El paso base seguro consume stack, al menos 1 palabra para la dirección de retorno.
Luego el paso recursivo también consume al menos 1 palabra para la dirección de retorno más el contexto que guardes.
Y a todo eso seguramente le tengas que sumar los parámetros de la invocación. El balance en si, repito, depende de tu programa en particular.

Saludos,
Gustavo
En respuesta a Gustavo Brown

Re: Duda respecto al calculo del stack

de Franco Pelua Camacho -
Hola. buenos días.

Adjunto el código:


Entonces, según entiendo tu respuesta, ¿la instrucción RET también consume stack? Si no me equivoco, RET lo que hace es un POP de lo que a priori tendría que ser una dirección de retorno, entonces, cuando POPeas cosas del stack, ¿se entiende que también estas consumiendo stack?
En respuesta a Franco Pelua Camacho

Re: Duda respecto al calculo del stack

de Franco Pelua Camacho -

Ah ok, ya entendí lo de la dirección de retorno. No es que cuando hagas POP consumas stack, sino más bien cuando haces el CALL, que pusheas la dir de retorno. 

La confusión venía de que no había entendido que cuando haces la “invocación” del procedimiento por primera vez, eso ya cuenta cómo consumo del procedimiento. 

En respuesta a Franco Pelua Camacho

Re: Duda respecto al calculo del stack

de Gustavo Brown -

Franco,

  Ya vi en otro mensaje que entendiste que RET no consume stack (de hecho libera 1 palabra del stack) pero igualmente voy a escribir aquí el cálculo de consumo para este ejemplo por si más adelante alguien tiene la misma duda.


La rutina se llama F y de acuerdo a tu programa recibe un parámetro por registro AX y retorna el resultado en el registro BX.

Paso base:

El programa tiene 2 paso base, cuando AX=0 y cuando AX=1. 

En este caso no se salva contexto por lo que la rutina consume 2 bytes de stack (el CALL que llama a la rutina coloca la dirección de retorno).

Paso recursivo:

El programa tiene 2 llamadas recursivas, una llamado a F(AX-1) y la otra llamado a F(AX-2). Entonces hay que calcular el consumo de cada llamada por separado y tomar el peor caso.

Cuando se llama a F(AX-1) se guarda 1 palabra de contexto en el stack (2 bytes)

Por su parte cuando se llama a F(AX-2) primero se recupera el contexto guardado y se guarda 1 palabra de contexto en el stack. El balance de stack queda incambiado respecto al punto previo a hacer el segundo CALL. Luego de retornar de esta segunda llamada se recupera CX dejando el balance de stack correcto.

Es decir que en ambos casos la llamda recursiva consume 4 bytes (2 por la dirección de retorno y 2 por el contexto guardado), pero el peor caso se da en la primer llamada porque es la que llama a rutina con el AX más grande.

El consumo total de stack es entonces:

  2 bytes si AX=0 o AX=1

  4*(AX-1) + 2 si AX > 1  (pues se hacen AX-1 pasos recursivos cada uno consumiendo 4 bytes más el paso base)

Saludos,
  Gustavo

En respuesta a Gustavo Brown

Re: Duda respecto al calculo del stack

de Agustín Marcio Ribeiro García -
¡Buenas! Yo pensé de esta otra forma el procedimiento y también estaba con dudas con el consumo de stack. Siguiendo el razonamiento que planteaste:

Paso base:
4 bytes // 2 de Ax y 2 de la Ip
Paso recursivo 1: 4 bytes // 2 de Ax y 2 de la Ip de fibonacci en ax-1
Paso recursivo 2: 6 bytes // 2 de Ax, 2 de Bx y 2 de la Ip de fibonacci en ax-2

Tomo el 2 como peor caso: y queda que el consumo total es 6(AX-2) + 4. En el caso de Ax=5 quedaría 22 bytes. ¿Esto sería correcto?

Además, quería preguntar: siempre que tengamos más de una llamada recursiva, ¿para calcular el consumo nos quedamos con la peor? ¿Eso es porque no importa que haya 2 recursiones en el paso, la primera se va a "ejecutar toda", digamos, y cuando vuelva al punto donde fue llamada por primera vez, el stack va a quedar como antes (ídem para la segunda), por lo que solo importa ver cuál de las dos llega a crecer más? Desde ya muchas gracias!
Adjunto imagen_2024-11-05_151114466.png
En respuesta a Agustín Marcio Ribeiro García

Re: Duda respecto al calculo del stack

de Gonzalo Tejera -

Hola Agustìn. cómo estás? 

No estás encontrando correctamente el camino en la ejecución que consume más entiendo que es por asumir que hay AX-2 llamadas anidadas que consumen 6 bytes, lo cual no es correcto pues en cada paso si vas por el paso recursivo 2 vas decrementando de a dos el AX.

Si dibujas el árbol de ejecución para tu solución el peor caso son las llamadas anidadas a f(5), f(4), f(3), f(2) y f(0) que generan un consumo de 24 bytes

Saludos, Gonzalo

En respuesta a Gonzalo Tejera

Re: Duda respecto al calculo del stack

de Agustín Marcio Ribeiro García -
¡Buenas Gonzalo! Gracias por tu respuesta. Solo para confirmar si entendí, si tomara el paso recursivo dos todas las veces, el árbol sería: f(5), f(3), f(1), con un consumo de 6 + 6 + 4 = 16 bytes. Finalmente, quisiera consultar si el peor caso se puede dar "mezclando" a lo largo de la ejecución dos llamadas recursivas distintas, o si, por el contrario, hay que analizar cada una por separado. Pregunto esto por esta parte del mensaje de Gustavo: "El programa tiene 2 llamadas recursivas, una llamada a f(AX-1) y la otra llamada a f(AX-2). Entonces, hay que calcular el consumo de cada llamada por separado y tomar el peor caso."
Desde ya muchas gracias!
En respuesta a Agustín Marcio Ribeiro García

Re: Duda respecto al calculo del stack

de Gonzalo Tejera -

Hola. Eso, en tu peor caso de anidamiento el consumo es 16B. Dependiendo de la implementación pueden ocurrir cosas como las que comentás. El cálculo es especifico de la implementación y de la estructura de la entrada proporcionada.

Saludos, Gonzalo