A partir de este punto consideramos el intérprete de LISP como completo en el sentido de que con él es posible evaluar interactivamente. Esto no significa que no podamos seguir añadiendo mejoras. A estas mejoras le dedicaremos los últimos cinco posts, aunque no añadiré ya código para implementarlas.
Cache de celdas y cadenas
Hasta ahora siempre que usábamos una celda de tipo CT_EMPTY, por ejemplo, siempre reservábamos memoria (via CreateEmpty() ). Es una tontería reservar varias veces la celda CT_EMPTY ya que no tiene estado y dos celdas de este tipo son idénticas.
La solución es bien sencilla. CreateEmpty() va a devolver siempre la misma celda. De esta forma ahorramos muchas celdas ya que todas las listas tienen un CT_EMPTY al final. La misma idea se puede usar para CT_BOOL cuando es true y cuando es false. Incluso, se podría usar para los números enteros más usados: el cero, el uno, el dos, etc.
Existe un impedimento para este tipo de técnica. Si queremos añadir a cada celda un localizador que nos diga en qué fichero fuente, en qué línea y en qué columna aparece esa celda; no tendremos más remedio que usar una celda distinta para cada aparición en el código.
En el caso de las cadenas es muy conveniente tener una única tabla de cadenas. De esta forma todas las celdas CT_STRING y CT_NAME no contienen la cadena en sí, sino una referencia a la tabla de cadenas. De esta manera aunque haya cien celdas CT_STRING con la misma cadena, sólo habrá una única copia de la cadena en nuestra tabla de cadenas.
Estas tablas asociativas se denominan comunmente cache.
Recolección de basura
Aún así tenemos el grandísimo problema de que celda que creemos es celda que perdemos. No podemos liberarla una vez no se use. Este problema ya surgió en los años 1960 cuando se creó el LISP. La solución consiste en usar una técnica llamada recolección de basura (garbage collection).
En su forma más simple es tal como se describe en el siguiente diagrama.
En primer lugar seleccionamos unas celdas las cuales sabemos que están siendo usadas. A estas celdas las llamamos el conjunto raíz. Un ejemplo de celda siempre usada es el entorno global. Estas celdas son las marcadas en (a).
En segundo lugar seguimos las referencias a otras celdas. Si una celda que sabemos usada referencia a otra celda, es posible llegar a usar esa celda referenciada y, por tanto, la consideramos usada también. Es lo que hacemos en (b). A este paso se le llama el marcado.
La idea es que las celdas no marcadas no van a poder ser usadas en el futuro porque no existe una referencia a ellas. Estas son las celdas blancas en (c). En este momento es cuando se liberan esas celdas no marcadas. A este paso se le denomina el barrido.
No es difícil averiguar por qué se denomina a este método de recolección de basura "marcado y barrido" (mark and sweep).
Existen muchísimos otros algoritmos de recolección de basura (conteo de referencias, marcado y barrido incremental, por generaciones, paralelo, etc.) No los veremos aquí.
0 comentarios:
Publicar un comentario