From d256570cee57e5f6a7e010dfd7aae3dd21ee2236 Mon Sep 17 00:00:00 2001 From: Leandro Lucarella Date: Sun, 24 May 2009 01:28:00 -0300 Subject: [PATCH] Utilizar nuevas extensiones para mejorar las figuras MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Además completa algunos comentarios sobre las figuras y otros detalles. --- source/conf.py | 3 +- source/gc.rst | 1553 ++++++++++++++++++++++++------------------------ 2 files changed, 784 insertions(+), 772 deletions(-) diff --git a/source/conf.py b/source/conf.py index bbf1ec0..db52cc9 100644 --- a/source/conf.py +++ b/source/conf.py @@ -22,7 +22,7 @@ sys.path.append(os.path.abspath('../ext')) # Add any Sphinx extension module names here, as strings. They can be extensions # coming with Sphinx (named 'sphinx.ext.*') or your custom ones. -extensions = ['graphviz', 'sphinx.ext.pngmath'] +extensions = ['fig', 'vref', 'graphviz', 'sphinx.ext.pngmath'] # Add any paths that contain templates here, relative to this directory. templates_path = ['.templates'] @@ -186,6 +186,7 @@ latex_logo = 'fiuba.png' # Additional stuff for the LaTeX preamble. latex_preamble = r''' +\usepackage{varioref} \usepackage{subfigure} \setcounter{tocdepth}{3} ''' diff --git a/source/gc.rst b/source/gc.rst index 100614f..94ab86c 100644 --- a/source/gc.rst +++ b/source/gc.rst @@ -4,7 +4,6 @@ un breve recorrido sobre el estado del arte. ESTADO: SIN EMPEZAR - .. _ref_gc: Recolección de basura @@ -244,71 +243,67 @@ Más formalmente, Definimos: Basura = V - Live \thickspace set -Esto es, efectivamente, una partición del *heap*. - -.. TODO: figure +Esto es, efectivamente, una partición del *heap* (ver figura +:vref:`fig:gc-heap-parts`). -.. raw:: latex - \begin{figure}[htp] \centering +.. fig:: fig:gc-heap-parts -.. digraph:: g1 + Distintas partes de la memoria, incluyendo relación entre *basura*, + *live set*, *heap* y *root set*. - margin = 0; - ratio = fill; - size = "4.6,3.6"; - node [ shape = record, width = 0, height = 0 ]; + .. digraph:: g1 - subgraph cluster_heap { - label = "Heap"; - style = dashed; - color = gray40; - fontcolor = gray40; + margin = 0; + ratio = fill; + size = "4.6,3.6"; + node [ shape = record, width = 0, height = 0 ]; - subgraph cluster_live { - label = "Live set"; + subgraph cluster_heap { + label = "Heap"; style = dashed; color = gray40; fontcolor = gray40; - node [ - style = filled, - fillcolor = gray25, - fontcolor = white, - ]; - h1; h2; h4; h5; h6; + + subgraph cluster_live { + label = "Live set"; + style = dashed; + color = gray40; + fontcolor = gray40; + node [ + style = filled, + fillcolor = gray25, + fontcolor = white, + ]; + h1; h2; h4; h5; h6; + } + + subgraph cluster_garbage { + label = "Basura"; + style = dashed; + color = gray40; + fontcolor = gray40; + node [ style = filled, fillcolor = white ]; + h7; h3; + } } - subgraph cluster_garbage { - label = "Basura"; + subgraph cluster_root { + label = "Root set"; style = dashed; color = gray40; fontcolor = gray40; - node [ style = filled, fillcolor = white ]; - h7; h3; + node [ style = filled, fillcolor = gray96 ]; + r0; r1; r2; } - } - - subgraph cluster_root { - label = "Root set"; - style = dashed; - color = gray40; - fontcolor = gray40; - node [ style = filled, fillcolor = gray96 ]; - r0; r1; r2; - } - - r0 -> h1 -> h2 -> h5; - r1 -> h5 -> h6 -> h1; - r2 -> h4; - h5 -> h4; - h7 -> h1; - h7 -> h3; - -.. raw:: latex - - \caption{Distintas partes de la memoria, incluyendo relación entre - basura, live set, heap y root set.} - \end{figure} + + r0 -> h1 -> h2 -> h5; + r1 -> h5 -> h6 -> h1; + r2 -> h4; + h5 -> h4; + h7 -> h1; + h7 -> h3; + Al proceso de visitar los vértices *conectados* desde el *root set* se lo denomina *marcado*, *fase de marcado* o *mark phase* en inglés, debido @@ -342,235 +337,234 @@ Esto es conocido también como **abstracción bicolor**, dado que en la literatura se habla muchas veces de *colorear* las celdas. En general, una celda sin marcar es de color blanco y una marcada de color negro. -.. TODO: figure +Puede observarse un ejemplo del algoritmo en la figura +:vref:`fig:gc-mark-1`, en la cual se marca el sub-grafo apuntando por +``r0``. Luego se marca el sub-grafo al que apunta ``r1`` (figura +:vref:`fig:gc-mark-2`), concluyendo con el marcado del grafo completo, +dejando sin marcar solamente las celdas *basura* (en blanco). + + +.. fig:: fig:gc-mark-1 + + Ejemplo de marcado del grafo de conectividad (parte 1). -.. raw:: latex + .. subfig:: - \begin{figure}[htp] - \centering - \subfigure[TODO texto más largo y más largo y larguísimo porque tiene - muchas cosas que decir]{ + Se comienza a marcar el grafo por la raíz r0. -.. digraph:: g2_1 + .. digraph:: g2_1 - margin = 0; - ratio = fill; - size = "2.0,2.6"; - node [ shape = record, width = 0, height = 0]; - edge [ color = gray40 ]; + margin = 0; + ratio = fill; + size = "1.9,2.6"; + node [ shape = record, width = 0, height = 0]; + edge [ color = gray40 ]; - subgraph cluster_all { + subgraph cluster_all { - root [ - label = "root\nset| r0\n*| r1", - style = filled, - fillcolor = gray96, - ]; + root [ + label = "root\nset| r0\n*| r1", + style = filled, + fillcolor = gray96, + ]; - subgraph marked { - node [ style = filled, fillcolor = gray25, fontcolor = white ]; - h1; - }; + subgraph marked { + node [ style = filled, fillcolor = gray25, fontcolor = white ]; + h1; + }; - root:r0 -> h1 [ style = bold, color = black ]; - h1 -> h2 -> h5 -> h1; - root:r1 -> h6 -> h2; - h4 -> h3; - h3 -> h5; + root:r0 -> h1 [ style = bold, color = black ]; + h1 -> h2 -> h5 -> h1; + root:r1 -> h6 -> h2; + h4 -> h3; + h3 -> h5; - } + } -.. raw:: latex + .. subfig:: - } - \subfigure[TODO]{ + Luego de marcar el nodo ``h1``, se procede al ``h2``. -.. digraph:: g2_2 + .. digraph:: g2_2 - margin = 0; - ratio = fill; - size = "2.0,2.6"; - node [ shape = record, width = 0, height = 0 ]; - edge [ color = gray40 ]; + margin = 0; + ratio = fill; + size = "1.9,2.6"; + node [ shape = record, width = 0, height = 0 ]; + edge [ color = gray40 ]; - subgraph cluster_all { + subgraph cluster_all { - root [ - label = "root\nset| r0\n*| r1", - style = filled, - fillcolor = gray96, - ]; + root [ + label = "root\nset| r0\n*| r1", + style = filled, + fillcolor = gray96, + ]; - subgraph marked { - node [ style = filled, fillcolor = gray25, fontcolor = white ]; - h1; h2; - }; + subgraph marked { + node [ style = filled, fillcolor = gray25, fontcolor = white ]; + h1; h2; + }; - root:r0 -> h1 [ color = gray10 ]; - h1 -> h2 [ style = bold, color = black ]; - h2 -> h5 -> h1; - root:r1 -> h6 -> h2; - h4 -> h3; - h3 -> h5; + root:r0 -> h1 [ color = gray10 ]; + h1 -> h2 [ style = bold, color = black ]; + h2 -> h5 -> h1; + root:r1 -> h6 -> h2; + h4 -> h3; + h3 -> h5; - } + } -.. raw:: latex + .. subfig:: - } - \subfigure[TODO]{ + Luego sigue el nodo h5. -.. digraph:: g2_3 + .. digraph:: g2_3 - margin = 0; - ratio = fill; - size = "2.0,2.6"; - node [ shape = record, width = 0, height = 0 ]; - edge [ color = gray40 ]; + margin = 0; + ratio = fill; + size = "1.9,2.6"; + node [ shape = record, width = 0, height = 0 ]; + edge [ color = gray40 ]; - subgraph cluster_all { + subgraph cluster_all { - root [ - label = "root\nset| r0\n*| r1", - style = filled, - fillcolor = gray96, - ]; + root [ + label = "root\nset| r0\n*| r1", + style = filled, + fillcolor = gray96, + ]; - subgraph marked { - node [ style = filled, fillcolor = gray25, fontcolor = white ]; - h1; h2; h5; - }; + subgraph marked { + node [ style = filled, fillcolor = gray25, fontcolor = white ]; + h1; h2; h5; + }; - root:r0 -> h1 [ color = gray10 ]; - h1 -> h2 [ color = gray10 ]; - h2 -> h5 [ style = bold, color = black ]; - h5 -> h1; - root:r1 -> h6 -> h2; - h4 -> h3; - h3 -> h5; + root:r0 -> h1 [ color = gray10 ]; + h1 -> h2 [ color = gray10 ]; + h2 -> h5 [ style = bold, color = black ]; + h5 -> h1; + root:r1 -> h6 -> h2; + h4 -> h3; + h3 -> h5; - } + } -.. raw:: latex - } - \caption{TODO, part 1} - \end{figure} +.. fig:: fig:gc-mark-2 - \begin{figure}[htp] - \centering - \subfigure[TODO]{ - -.. digraph:: g2_4 - - margin = 0; - ratio = fill; - size = "2.0,2.6"; - node [ shape = record, width = 0, height = 0 ]; - edge [ color = gray40 ]; + Ejemplo de marcado del grafo de conectividad (parte 2). - subgraph cluster_all { + .. subfig:: - root [ - label = "root\nset| r0\n*| r1", - style = filled, - fillcolor = gray96, - ]; + El nodo h5 tiene una arista al h1, pero el h1 ya fue visitado, por lo + tanto no se visita nuevamente. - subgraph marked { - node [ style = filled, fillcolor = gray25, fontcolor = white ]; - h1; h2; h5; - }; + .. digraph:: g2_4 - root:r0 -> h1 [ color = gray10 ]; - h1 -> h2 [ color = gray10 ]; - h2 -> h5 [ color = gray10 ]; - h5 -> h1 [ style = bold, color = black ]; - root:r1 -> h6 -> h2; - h4 -> h3; - h3 -> h5; + margin = 0; + ratio = fill; + size = "1.9,2.6"; + node [ shape = record, width = 0, height = 0 ]; + edge [ color = gray40 ]; - } + subgraph cluster_all { -.. raw:: latex + root [ + label = "root\nset| r0\n*| r1", + style = filled, + fillcolor = gray96, + ]; - } - \subfigure[TODO]{ + subgraph marked { + node [ style = filled, fillcolor = gray25, fontcolor = white ]; + h1; h2; h5; + }; -.. digraph:: g2_5 + root:r0 -> h1 [ color = gray10 ]; + h1 -> h2 [ color = gray10 ]; + h2 -> h5 [ color = gray10 ]; + h5 -> h1 [ style = bold, color = black ]; + root:r1 -> h6 -> h2; + h4 -> h3; + h3 -> h5; - margin = 0; - ratio = fill; - size = "2.0,2.6"; - node [ shape = record, width = 0, height = 0 ]; - edge [ color = gray40 ]; + } - subgraph cluster_all { + .. subfig:: - root [ - label = "root\nset| r0| r1\n*", - style = filled, - fillcolor = gray96, - ]; + Se concluye el marcado del sub-grafo al que conecta r0, se procede + a marcar el sub-grafo al que conecta r1, marcando al nodo h6. - subgraph marked { - node [ style = filled, fillcolor = gray25, fontcolor = white ]; - h1; h2; h5; h6; - }; + .. digraph:: g2_5 - root:r0 -> h1 [ color = gray10 ]; - h1 -> h2 [ color = gray10 ]; - h2 -> h5 [ color = gray10 ]; - h5 -> h1 [ color = gray10 ]; - root:r1 -> h6 [ style = bold, color = black ]; - h6 -> h2; - h4 -> h3; - h3 -> h5; + margin = 0; + ratio = fill; + size = "1.9,2.6"; + node [ shape = record, width = 0, height = 0 ]; + edge [ color = gray40 ]; - } + subgraph cluster_all { -.. raw:: latex + root [ + label = "root\nset| r0| r1\n*", + style = filled, + fillcolor = gray96, + ]; - } - \subfigure[TODO]{ + subgraph marked { + node [ style = filled, fillcolor = gray25, fontcolor = white ]; + h1; h2; h5; h6; + }; -.. digraph:: g2_6 + root:r0 -> h1 [ color = gray10 ]; + h1 -> h2 [ color = gray10 ]; + h2 -> h5 [ color = gray10 ]; + h5 -> h1 [ color = gray10 ]; + root:r1 -> h6 [ style = bold, color = black ]; + h6 -> h2; + h4 -> h3; + h3 -> h5; - margin = 0; - ratio = fill; - size = "2.0,2.6"; - node [ shape = record, width = 0, height = 0 ]; - edge [ color = gray40 ]; + } - subgraph cluster_all { + .. subfig:: - root [ - label = "root\nset| r0| r1\n*", - style = filled, - fillcolor = gray96, - ]; + El nodo h6 tiene una arista al h2, pero éste ya fue marcado por lo + que no se vuelve a visitar. No hay más raíces, se finaliza el marcado + del grafo. - subgraph marked { - node [ style = filled, fillcolor = gray25, fontcolor = white ]; - h1; h2; h5; h6; - }; + .. digraph:: g2_6 - root:r0 -> h1 [ color = gray10 ]; - h1 -> h2 [ color = gray10 ]; - h2 -> h5 [ color = gray10 ]; - h5 -> h1 [ color = gray10 ]; - root:r1 -> h6 [ color = gray10 ]; - h6 -> h2 [ style = bold, color = black ]; - h4 -> h3; - h3 -> h5; + margin = 0; + ratio = fill; + size = "1.9,2.6"; + node [ shape = record, width = 0, height = 0 ]; + edge [ color = gray40 ]; - } + subgraph cluster_all { -.. raw:: latex + root [ + label = "root\nset| r0| r1\n*", + style = filled, + fillcolor = gray96, + ]; - } - \caption{TODO, parte 2} - \end{figure} + subgraph marked { + node [ style = filled, fillcolor = gray25, fontcolor = white ]; + h1; h2; h5; h6; + }; + + root:r0 -> h1 [ color = gray10 ]; + h1 -> h2 [ color = gray10 ]; + h2 -> h5 [ color = gray10 ]; + h5 -> h1 [ color = gray10 ]; + root:r1 -> h6 [ color = gray10 ]; + h6 -> h2 [ style = bold, color = black ]; + h4 -> h3; + h3 -> h5; + + } .. [#gccycle] Un ciclo es un camino donde el *vértice inicial* es el mismo @@ -810,552 +804,569 @@ Ejemplo ^^^^^^^ A continuación se presenta un ejemplo gráfico para facilitar la comprensión -del algoritmo. - -Por simplicidad se asumen celdas de tamaño fijo con dos punteros, ``left`` -y ``right`` (estructura clásica para representar un árbol binario) y se -muestra el contador de referencias abajo del nombre de cada celda. Se parte -con una pequeña estructura ya construída y se muestra primero lo que ocurre -al eliminar la referencia :math:`r0 \to h1`: - -.. TODO: figure - -.. raw:: latex - - \begin{figure}[htp] - \centering - \subfigure[TODO]{ - -.. digraph:: g3_1 - - margin = 0; - ratio = fill; - size = "3.0,3.8"; - edge [ color = gray40 ]; - node [ - shape = record, - width = 0, - height = 0, - style = filled, - fillcolor = gray25, - fontcolor = white - ]; - - subgraph cluster_all { - - root [ - label = "root\nset| r0\n*| r1", - style = filled, - fillcolor = gray96, - fontcolor = black, - ]; - - h1 [ label = "h1\n1| left| right" ]; - h2 [ label = "h2\n2| left| right" ]; - h3 [ label = "h3\n2| left| right" ]; - h4 [ label = "h4\n1| left| right" ]; - h5 [ label = "h5\n1| left| right" ]; - h6 [ label = "h6\n1| left| right" ]; - - root:r0 -> h1 [ style = bold, color = black ]; - root:r1 -> h3; - h1:l -> h2; - h1:r -> h3; - h2:l -> h4; - h2:r -> h5; - h3:l -> h2; - h3:r -> h6; - - } - -.. raw:: latex - - } - \subfigure[TODO]{ - -.. digraph:: g3_2 - - margin = 0; - ratio = fill; - size = "3.0,3.8"; - edge [ color = gray40 ]; - node [ - shape = record, - width = 0, - height = 0, - style = filled, - fillcolor = gray25, - fontcolor = white - ]; - - subgraph cluster_all { - - root [ - label = "root\nset| r0\n*| r1", - style = filled, - fillcolor = gray96, - fontcolor = black, - ]; - - subgraph marked { - node [ fillcolor = white, fontcolor = black ]; - h1; - }; - - h1 [ label = "h1\n0| left| right" ]; - h2 [ label = "h2\n2| left| right" ]; - h3 [ label = "h3\n2| left| right" ]; - h4 [ label = "h4\n1| left| right" ]; - h5 [ label = "h5\n1| left| right" ]; - h6 [ label = "h6\n1| left| right" ]; - - root:r0 -> h1 [ style = invis ]; - root:r1 -> h3; - h1:l -> h2 [ style = bold, color = black ]; - h1:r -> h3; - h2:l -> h4; - h2:r -> h5; - h3:l -> h2; - h3:r -> h6; - - } - -.. raw:: latex - - } - \caption{TODO, part 1} - \end{figure} - - \begin{figure}[htp] - \centering - \subfigure[TODO]{ - -.. digraph:: g3_3 - - margin = 0; - ratio = fill; - size = "3.0,3.8"; - edge [ color = gray40 ]; - node [ - shape = record, - width = 0, - height = 0, - style = filled, - fillcolor = gray25, - fontcolor = white - ]; - - subgraph cluster_all { - - root [ - label = "root\nset| r0\n*| r1", - style = filled, - fillcolor = gray96, - fontcolor = black, - ]; - - subgraph marked { - node [ fillcolor = white, fontcolor = black ]; - h1; - }; - - h1 [ label = "h1\n0| left| right" ]; - h2 [ label = "h2\n1| left| right" ]; - h3 [ label = "h3\n2| left| right" ]; - h4 [ label = "h4\n1| left| right" ]; - h5 [ label = "h5\n1| left| right" ]; - h6 [ label = "h6\n1| left| right" ]; - - root:r0 -> h1 [ style = invis ]; - root:r1 -> h3; - h1:l -> h2 [ style = invis ]; - h1:r -> h3 [ style = bold, color = black ]; - h2:l -> h4; - h2:r -> h5; - h3:l -> h2; - h3:r -> h6; - - } - -.. raw:: latex - - } - \subfigure[TODO]{ - -.. digraph:: g3_4 - - margin = 0; - ratio = fill; - size = "3.0,3.8"; - edge [ color = gray40 ]; - node [ - shape = record, - width = 0, - height = 0, - style = filled, - fillcolor = gray25, - fontcolor = white - ]; - - subgraph cluster_all { - - root [ - label = "root\nset| r0| r1", - style = filled, - fillcolor = gray96, - fontcolor = black, - ]; - - subgraph marked { - node [ fillcolor = white, fontcolor = black ]; - h1; - }; - - h1 [ label = "h1\n0| left| right" ]; - h2 [ label = "h2\n1| left| right" ]; - h3 [ label = "h3\n1| left| right" ]; - h4 [ label = "h4\n1| left| right" ]; - h5 [ label = "h5\n1| left| right" ]; - h6 [ label = "h6\n1| left| right" ]; - - root:r0 -> h1 [ style = invis ]; - root:r1 -> h3; - h1:l -> h2 [ style = invis ]; - h1:r -> h3 [ style = invis ]; - h2:l -> h4; - h2:r -> h5; - h3:l -> h2; - h3:r -> h6; - - } - -.. raw:: latex - - } - \caption{TODO, parte 2} - \end{figure} - -Como se observa, la celda ``h1`` queda con el contador en 0, por lo tanto -pasa a ser *basura*. Los contadores de las celdas a las que apuntaban -``h1.left`` y ``h1.right`` son decrementados, pero no se detecta más basura -porque sigue existiendo un camino del *root set* a aquellas celdas, y por -transitividad a todas aquellas celdas apuntadas por éstas. Es por esto que -no es necesario seguir recorriendo el grafo de conectividad. - -A continuación se muestra como opera el algoritmo al cambiar a donde apunta -``h3.left``, haciéndola apuntar a ``h5``. Es decir, que pasa luego de la -operación ``update(h3.left, h5)`` (por simplicidad no se muestra más la -celda ``h1`` que ahora es *basura*): - -.. TODO: figure - -.. raw:: latex - - \begin{figure}[htp] - \centering - \subfigure[TODO]{ - -.. digraph:: g4_1 - - margin = 0; - ratio = fill; - size = "3.0,3.8"; - edge [ color = gray40 ]; - node [ - shape = record, - width = 0, - height = 0, - style = filled, - fillcolor = gray25, - fontcolor = white - ]; - - subgraph cluster_all { - - root [ - label = "root\nset| r0| r1", - style = filled, - fillcolor = gray96, - fontcolor = black, - ]; - - subgraph marked { - node [ fillcolor = white, fontcolor = black ]; - }; - - h2 [ label = "h2\n1| left| right" ]; - h3 [ label = "h3\n1| left\n*| right" ]; - h4 [ label = "h4\n1| left| right" ]; - h5 [ label = "h5\n1| left| right" ]; - h6 [ label = "h6\n1| left| right" ]; - - root:r1 -> h3; - h2:l -> h4; - h2:r -> h5; - h3:l -> h2 [ style = bold, color = black ]; - h3:r -> h6; - - } - -.. raw:: latex - - } - \subfigure[TODO]{ - -.. digraph:: g4_2 - - margin = 0; - ratio = fill; - size = "3.0,3.8"; - edge [ color = gray40 ]; - node [ - shape = record, - width = 0, - height = 0, - style = filled, - fillcolor = gray25, - fontcolor = white - ]; - - subgraph cluster_all { - - root [ - label = "root\nset| r0| r1", - style = filled, - fillcolor = gray96, - fontcolor = black, - ]; - - subgraph marked { - node [ fillcolor = white, fontcolor = black ]; - }; - - h2 [ label = "h2\n1| left| right" ]; - h3 [ label = "h3\n1| left\n*| right" ]; - h4 [ label = "h4\n1| left| right" ]; - h5 [ label = "h5\n2| left| right" ]; - h6 [ label = "h6\n1| left| right" ]; - - root:r1 -> h3; - h2:l -> h4; - h2:r -> h5; - h3:l -> h2 [ style = bold, color = black ]; - h3:l -> h5 [ style = dotted, color = black ]; - h3:r -> h6; - - } - -.. raw:: latex - - } - \caption{TODO, part 1} - \end{figure} - - \begin{figure}[htp] - \centering - \subfigure[TODO]{ - -.. digraph:: g4_3 - - margin = 0; - ratio = fill; - size = "3.0,3.8"; - edge [ color = gray40 ]; - node [ - shape = record, - width = 0, - height = 0, - style = filled, - fillcolor = gray25, - fontcolor = white - ]; - - subgraph cluster_all { - - root [ - label = "root\nset| r0| r1", - style = filled, - fillcolor = gray96, - fontcolor = black, - ]; - - subgraph marked { - node [ fillcolor = white, fontcolor = black ]; - h2; - }; - - h2 [ label = "h2\n0| left| right" ]; - h3 [ label = "h3\n1| left\n*| right" ]; - h4 [ label = "h4\n1| left| right" ]; - h5 [ label = "h5\n2| left| right" ]; - h6 [ label = "h6\n1| left| right" ]; - - root:r1 -> h3; - h2:l -> h4 [ style = bold, color = black ]; - h2:r -> h5; - h3:l -> h2 [ style = invis ]; - h3:l -> h5 [ style = dotted, color = black ]; - h3:r -> h6; - - } - -.. raw:: latex - - } - \subfigure[TODO]{ - -.. digraph:: g4_4 - - margin = 0; - ratio = fill; - size = "3.0,3.8"; - edge [ color = gray40 ]; - node [ - shape = record, - width = 0, - height = 0, - style = filled, - fillcolor = gray25, - fontcolor = white - ]; - - subgraph cluster_all { - - root [ - label = "root\nset| r0| r1", - style = filled, - fillcolor = gray96, - fontcolor = black, - ]; - - subgraph marked { - node [ fillcolor = white, fontcolor = black ]; - h2; h4; - }; - - h2 [ label = "h2\n0| left| right" ]; - h3 [ label = "h3\n1| left\n*| right" ]; - h4 [ label = "h4\n0| left| right" ]; - h5 [ label = "h5\n2| left| right" ]; - h6 [ label = "h6\n1| left| right" ]; - - root:r1 -> h3; - h2:l -> h4 [ style = invis ]; - h2:r -> h5 [ style = bold, color = black ]; - h3:l -> h2 [ style = invis ]; - h3:l -> h5 [ style = dotted, color = black ]; - h3:r -> h6; - - } - -.. raw:: latex - - } - \caption{TODO, part 2} - \end{figure} - - \begin{figure}[htp] - \centering - \subfigure[TODO]{ - -.. digraph:: g4_5 - - margin = 0; - ratio = fill; - size = "3.0,3.8"; - edge [ color = gray40 ]; - node [ - shape = record, - width = 0, - height = 0, - style = filled, - fillcolor = gray25, - fontcolor = white - ]; - - subgraph cluster_all { - - root [ - label = "root\nset| r0| r1", - style = filled, - fillcolor = gray96, - fontcolor = black, - ]; - - subgraph marked { - node [ fillcolor = white, fontcolor = black ]; - h2; h4; - }; - - h2 [ label = "h2\n0| left| right" ]; - h3 [ label = "h3\n1| left\n*| right" ]; - h4 [ label = "h4\n0| left| right" ]; - h5 [ label = "h5\n1| left| right" ]; - h6 [ label = "h6\n1| left| right" ]; - - root:r1 -> h3; - h2:l -> h4 [ style = invis ]; - h2:r -> h5 [ style = invis ]; - h3:l -> h5 [ style = bold, color = black ]; - h3:l -> h2 [ style = invis ]; - h3:r -> h6; - - } - -.. raw:: latex - - } - \subfigure[TODO]{ - -.. digraph:: g4_6 - - margin = 0; - ratio = fill; - size = "3.0,3.8"; - edge [ color = gray40 ]; - node [ - shape = record, - width = 0, - height = 0, - style = filled, - fillcolor = gray25, - fontcolor = white - ]; - - subgraph cluster_all { - - root [ - label = "root\nset| r0| r1", - style = filled, - fillcolor = gray96, - fontcolor = black, - ]; - - subgraph marked { - node [ fillcolor = white, fontcolor = black ]; - h2; h4; - }; - - h2 [ label = "h2\n0| left| right" ]; - h3 [ label = "h3\n1| left| right" ]; - h4 [ label = "h4\n0| left| right" ]; - h5 [ label = "h5\n1| left| right" ]; - h6 [ label = "h6\n1| left| right" ]; - - root:r1 -> h3; - h2:l -> h4 [ style = invis ]; - h2:r -> h5 [ style = invis ]; - h3:l -> h5; - h3:l -> h2 [ style = invis ]; - h3:r -> h6; - - } - -.. raw:: latex - - } - \caption{TODO, parte 3} - \end{figure} +del algoritmo. Por simplicidad se asumen celdas de tamaño fijo con dos +punteros, ``left`` y ``right`` y se muestra el contador de referencias +abajo del nombre de cada celda. Se parte con una pequeña estructura ya +construída y se muestra como opera el algoritmo al eliminar o cambiar una +referencia (cambios en la conectividad del grafo). + +Se comienza por eliminar la referencia de ``r0`` a ``h1``, que determina +que ``h1`` se convirtió en *basura* (figura :vref:`fig:gc-rc-rm-1`). Esto +conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el +*live set* ya que sus contadores siguen siendo mayores a 0 (figura +:vref:`fig:gc-rc-rm-2`). + + +.. fig:: fig:gc-rc-rm-1 + + Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 1). + + .. subfig:: + + Se ejecuta ``update(r0, null)``. + + .. digraph:: g3_1 + + margin = 0; + ratio = fill; + size = "3.0,3.8"; + edge [ color = gray40 ]; + node [ + shape = record, + width = 0, + height = 0, + style = filled, + fillcolor = gray25, + fontcolor = white + ]; + + subgraph cluster_all { + + root [ + label = "root\nset| r0\n*| r1", + style = filled, + fillcolor = gray96, + fontcolor = black, + ]; + + h1 [ label = "h1\n1| left| right" ]; + h2 [ label = "h2\n2| left| right" ]; + h3 [ label = "h3\n2| left| right" ]; + h4 [ label = "h4\n1| left| right" ]; + h5 [ label = "h5\n1| left| right" ]; + h6 [ label = "h6\n1| left| right" ]; + + root:r0 -> h1 [ style = bold, color = black ]; + root:r1 -> h3; + h1:l -> h2; + h1:r -> h3; + h2:l -> h4; + h2:r -> h5; + h3:l -> h2; + h3:r -> h6; + + } + + .. subfig:: + + Se decrementa el contador de ``h1`` y éste queda en 0 (indicando + que es basura). Esto desencadena la eliminación de las referencias + ``h1.left`` y ``h1.right``. + + .. digraph:: g3_2 + + margin = 0; + ratio = fill; + size = "3.0,3.8"; + edge [ color = gray40 ]; + node [ + shape = record, + width = 0, + height = 0, + style = filled, + fillcolor = gray25, + fontcolor = white + ]; + + subgraph cluster_all { + + root [ + label = "root\nset| r0\n*| r1", + style = filled, + fillcolor = gray96, + fontcolor = black, + ]; + + subgraph marked { + node [ fillcolor = white, fontcolor = black ]; + h1; + }; + + h1 [ label = "h1\n0| left| right" ]; + h2 [ label = "h2\n2| left| right" ]; + h3 [ label = "h3\n2| left| right" ]; + h4 [ label = "h4\n1| left| right" ]; + h5 [ label = "h5\n1| left| right" ]; + h6 [ label = "h6\n1| left| right" ]; + + root:r0 -> h1 [ style = invis ]; + root:r1 -> h3; + h1:l -> h2 [ style = bold, color = black ]; + h1:r -> h3; + h2:l -> h4; + h2:r -> h5; + h3:l -> h2; + h3:r -> h6; + + } + +.. fig:: fig:gc-rc-rm-2 + + Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 2). + + .. subfig:: + + Se decrementa el contador de ``h2`` pero no queda en 0, por lo + tanto no es necesario descender a sus hijas; se continúa con + ``h3``. + + .. digraph:: g3_3 + + margin = 0; + ratio = fill; + size = "3.0,3.8"; + edge [ color = gray40 ]; + node [ + shape = record, + width = 0, + height = 0, + style = filled, + fillcolor = gray25, + fontcolor = white + ]; + + subgraph cluster_all { + + root [ + label = "root\nset| r0\n*| r1", + style = filled, + fillcolor = gray96, + fontcolor = black, + ]; + + subgraph marked { + node [ fillcolor = white, fontcolor = black ]; + h1; + }; + + h1 [ label = "h1\n0| left| right" ]; + h2 [ label = "h2\n1| left| right" ]; + h3 [ label = "h3\n2| left| right" ]; + h4 [ label = "h4\n1| left| right" ]; + h5 [ label = "h5\n1| left| right" ]; + h6 [ label = "h6\n1| left| right" ]; + + root:r0 -> h1 [ style = invis ]; + root:r1 -> h3; + h1:l -> h2 [ style = invis ]; + h1:r -> h3 [ style = bold, color = black ]; + h2:l -> h4; + h2:r -> h5; + h3:l -> h2; + h3:r -> h6; + + } + + .. subfig:: + + El contador de ``h3`` tampoco queda en 0; no hay necesidad de + descender a sus hijas y finaliza el proceso. + + .. digraph:: g3_4 + + margin = 0; + ratio = fill; + size = "3.0,3.8"; + edge [ color = gray40 ]; + node [ + shape = record, + width = 0, + height = 0, + style = filled, + fillcolor = gray25, + fontcolor = white + ]; + + subgraph cluster_all { + + root [ + label = "root\nset| r0| r1", + style = filled, + fillcolor = gray96, + fontcolor = black, + ]; + + subgraph marked { + node [ fillcolor = white, fontcolor = black ]; + h1; + }; + + h1 [ label = "h1\n0| left| right" ]; + h2 [ label = "h2\n1| left| right" ]; + h3 [ label = "h3\n1| left| right" ]; + h4 [ label = "h4\n1| left| right" ]; + h5 [ label = "h5\n1| left| right" ]; + h6 [ label = "h6\n1| left| right" ]; + + root:r0 -> h1 [ style = invis ]; + root:r1 -> h3; + h1:l -> h2 [ style = invis ]; + h1:r -> h3 [ style = invis ]; + h2:l -> h4; + h2:r -> h5; + h3:l -> h2; + h3:r -> h6; + + } + + +Luego se cambia una referencia (en vez de eliminarse) realizándose la +operación ``update(h3.left, h5)``. Para esto primero se incrementa el +contador de referencias de ``h5`` para evitar confundirlo accidentalmente +con *basura* (figura :vref:`fig:gc-rc-up-1`). Luego se procede +a decrementar el contador de ``h2`` que queda en 0 (transformándose en +*basura*) y lo mismo pasa cuando se desciende a ``h4`` (figura +:vref:`fig:gc-rc-up-2`). Finalmente se decrementa el contador de ``h5`` +pero como esta celda va a ser apuntada por ``h3`` (por la operación que +está ejecutándose) sobrevive y permanece en el *live set*. Finalmente se +termina de actualizar la referencia ``h3.left`` para que apunte a ``h5`` +(figura :vref:`fig:gc-rc-up-3`). + + +.. fig:: fig:gc-rc-up-1 + + TODO Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 1). + + .. subfig:: + + TODO + + .. digraph:: g4_1 + + margin = 0; + ratio = fill; + size = "3.0,3.8"; + edge [ color = gray40 ]; + node [ + shape = record, + width = 0, + height = 0, + style = filled, + fillcolor = gray25, + fontcolor = white + ]; + + subgraph cluster_all { + + root [ + label = "root\nset| r0| r1", + style = filled, + fillcolor = gray96, + fontcolor = black, + ]; + + subgraph marked { + node [ fillcolor = white, fontcolor = black ]; + h1; + }; + + h1 [ label = "h1\n0| left| right" ]; + h2 [ label = "h2\n1| left| right" ]; + h3 [ label = "h3\n1| left\n*| right" ]; + h4 [ label = "h4\n1| left| right" ]; + h5 [ label = "h5\n1| left| right" ]; + h6 [ label = "h6\n1| left| right" ]; + + root:r0 -> h1 [ style = invis ]; + h1:l -> h2 [ style = invis ]; + h1:r -> h3 [ style = invis ]; + root:r1 -> h3; + h2:l -> h4; + h2:r -> h5; + h3:l -> h2 [ style = bold, color = black ]; + h3:r -> h6; + + } + + .. subfig:: + + TODO + + .. digraph:: g4_2 + + margin = 0; + ratio = fill; + size = "3.0,3.8"; + edge [ color = gray40 ]; + node [ + shape = record, + width = 0, + height = 0, + style = filled, + fillcolor = gray25, + fontcolor = white + ]; + + subgraph cluster_all { + + root [ + label = "root\nset| r0| r1", + style = filled, + fillcolor = gray96, + fontcolor = black, + ]; + + subgraph marked { + node [ fillcolor = white, fontcolor = black ]; + h1; + }; + + h1 [ label = "h1\n0| left| right" ]; + h2 [ label = "h2\n1| left| right" ]; + h3 [ label = "h3\n1| left\n*| right" ]; + h4 [ label = "h4\n1| left| right" ]; + h5 [ label = "h5\n2| left| right" ]; + h6 [ label = "h6\n1| left| right" ]; + + root:r0 -> h1 [ style = invis ]; + h1:l -> h2 [ style = invis ]; + h1:r -> h3 [ style = invis ]; + root:r1 -> h3; + h2:l -> h4; + h2:r -> h5; + h3:l -> h2 [ style = bold, color = black ]; + h3:l -> h5 [ style = dotted, color = black ]; + h3:r -> h6; + + } + +.. fig:: fig:gc-rc-up-2 + + TODO Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 2). + + .. subfig:: + + TODO + + .. digraph:: g4_3 + + margin = 0; + ratio = fill; + size = "3.0,3.8"; + edge [ color = gray40 ]; + node [ + shape = record, + width = 0, + height = 0, + style = filled, + fillcolor = gray25, + fontcolor = white + ]; + + subgraph cluster_all { + + root [ + label = "root\nset| r0| r1", + style = filled, + fillcolor = gray96, + fontcolor = black, + ]; + + subgraph marked { + node [ fillcolor = white, fontcolor = black ]; + h1; h2; + }; + + h1 [ label = "h1\n0| left| right" ]; + h2 [ label = "h2\n0| left| right" ]; + h3 [ label = "h3\n1| left\n*| right" ]; + h4 [ label = "h4\n1| left| right" ]; + h5 [ label = "h5\n2| left| right" ]; + h6 [ label = "h6\n1| left| right" ]; + + root:r0 -> h1 [ style = invis ]; + h1:l -> h2 [ style = invis ]; + h1:r -> h3 [ style = invis ]; + root:r1 -> h3; + h2:l -> h4 [ style = bold, color = black ]; + h2:r -> h5; + h3:l -> h2 [ style = invis ]; + h3:l -> h5 [ style = dotted, color = black ]; + h3:r -> h6; + + } + + .. subfig:: + + TODO + + .. digraph:: g4_4 + + margin = 0; + ratio = fill; + size = "3.0,3.8"; + edge [ color = gray40 ]; + node [ + shape = record, + width = 0, + height = 0, + style = filled, + fillcolor = gray25, + fontcolor = white + ]; + + subgraph cluster_all { + + root [ + label = "root\nset| r0| r1", + style = filled, + fillcolor = gray96, + fontcolor = black, + ]; + + subgraph marked { + node [ fillcolor = white, fontcolor = black ]; + h1; h2; h4; + }; + + h1 [ label = "h1\n0| left| right" ]; + h2 [ label = "h2\n0| left| right" ]; + h3 [ label = "h3\n1| left\n*| right" ]; + h4 [ label = "h4\n0| left| right" ]; + h5 [ label = "h5\n2| left| right" ]; + h6 [ label = "h6\n1| left| right" ]; + + root:r0 -> h1 [ style = invis ]; + h1:l -> h2 [ style = invis ]; + h1:r -> h3 [ style = invis ]; + root:r1 -> h3; + h2:l -> h4 [ style = invis ]; + h2:r -> h5 [ style = bold, color = black ]; + h3:l -> h2 [ style = invis ]; + h3:l -> h5 [ style = dotted, color = black ]; + h3:r -> h6; + + } + +.. fig:: fig:gc-rc-up-3 + + TODO Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 3). + + .. subfig:: + + TODO + + .. digraph:: g4_5 + + margin = 0; + ratio = fill; + size = "3.0,3.8"; + edge [ color = gray40 ]; + node [ + shape = record, + width = 0, + height = 0, + style = filled, + fillcolor = gray25, + fontcolor = white + ]; + + subgraph cluster_all { + + root [ + label = "root\nset| r0| r1", + style = filled, + fillcolor = gray96, + fontcolor = black, + ]; + + subgraph marked { + node [ fillcolor = white, fontcolor = black ]; + h1; h2; h4; + }; + + h1 [ label = "h1\n0| left| right" ]; + h2 [ label = "h2\n0| left| right" ]; + h3 [ label = "h3\n1| left\n*| right" ]; + h4 [ label = "h4\n0| left| right" ]; + h5 [ label = "h5\n1| left| right" ]; + h6 [ label = "h6\n1| left| right" ]; + + root:r0 -> h1 [ style = invis ]; + h1:l -> h2 [ style = invis ]; + h1:r -> h3 [ style = invis ]; + root:r1 -> h3; + h2:l -> h4 [ style = invis ]; + h2:r -> h5 [ style = invis ]; + h3:l -> h5 [ style = bold, color = black ]; + h3:l -> h2 [ style = invis ]; + h3:r -> h6; + + } + + .. subfig:: + + TODO + + .. digraph:: g4_6 + + margin = 0; + ratio = fill; + size = "3.0,3.8"; + edge [ color = gray40 ]; + node [ + shape = record, + width = 0, + height = 0, + style = filled, + fillcolor = gray25, + fontcolor = white + ]; + + subgraph cluster_all { + + root [ + label = "root\nset| r0| r1", + style = filled, + fillcolor = gray96, + fontcolor = black, + ]; + + subgraph marked { + node [ fillcolor = white, fontcolor = black ]; + h1; h2; h4; + }; + + h1 [ label = "h1\n0| left| right" ]; + h1 [ label = "h1\n0| left| right" ]; + h2 [ label = "h2\n0| left| right" ]; + h3 [ label = "h3\n1| left| right" ]; + h4 [ label = "h4\n0| left| right" ]; + h5 [ label = "h5\n1| left| right" ]; + h6 [ label = "h6\n1| left| right" ]; + + root:r0 -> h1 [ style = invis ]; + h1:l -> h2 [ style = invis ]; + h1:r -> h3 [ style = invis ]; + root:r1 -> h3; + h2:l -> h4 [ style = invis ]; + h2:r -> h5 [ style = invis ]; + h3:l -> h5; + h3:l -> h2 [ style = invis ]; + h3:r -> h6; + + } + .. _ref_gc_cycles: -- 2.43.0