X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/blobdiff_plain/b0956c037ae52da777b06705157486067755ec2c..8554af7b6c3350a7bd644661868b38aa4fdb924e:/source/dgc.rst?ds=inline diff --git a/source/dgc.rst b/source/dgc.rst index bb0f3ba..dc32223 100644 --- a/source/dgc.rst +++ b/source/dgc.rst @@ -7,7 +7,7 @@ ESTADO: SIN EMPEZAR, REVISAR LO HECHO -.. _ref_dgc: +.. _dgc: Recolección de basura en D ============================================================================ @@ -23,24 +23,484 @@ TODO +.. _dgc_actual: + Recolector de basura actual de D ---------------------------------------------------------------------------- -TODO +Como paso básico fundamental para poder mejorar el recolector de basura de D_, +primero hay que entender la implementación actual, de forma de conocer sus +puntos fuertes, problemas y limitaciones, de manera tal de poder analizar +formas de mejorarlo. + +Como se mencionó en la sección :ref:`d_lang`, en D_ hay dos bibliotecas base +para soportar el lenguaje (*runtimes*): Phobos_ y Tango_. La primera es la +biblioteca estándar de D_, la segunda un proyecto más abierto y dinámico que +surgió como alternativa a Phobos_ debido a que Phobos_ es muy desprolija y que +era muy difícil impulsar cambios en ella. Ahora Phobos_ tiene el agravante de +estar *congelada* en su versión 1 (solo se realizan correcciones de errores). + +Dado que Tango_ está mejor organizada, su desarrollo es más abierto (aceptan +cambios y mejoras) y que hay una mayor disponibilidad de programas +y bibliotecas escritos para Tango_, en este trabajo se decide tomar esta +biblioteca *runtime* como base para el análisis y mejoras propuestas, a pesar +de ser Phobos_ la estándar. De todas formas el recolector de basura de Tango_ +es prácticamente el mismo que el de Phobos_, por lo tanto éste análisis en +particular es válido para cualquiera de las dos. + +El recolector actual es un recolector :ref:`indirecto `, :ref:`no +incremental ` que realiza un :ref:`marcado y barrido ` +relativamente básico. A diferencia del algoritmo clásico presentado éste +realiza un marcado no recursivo. La fase de marcado es :ref:`stop-the-world +`; si +bien posee alguna información de tipos (distingue entre celdas que pueden +tener punteros y celdas que definitivamente no los tienen, pero no dispone de +información sobre qué campos de las celdas son punteros y cuales no). Además +no tiene soporte alguno de :ref:`recolección particionada `. + +Si bien el recolector es bastante básico, posee una :ref:`organización de +memoria ` relativamente moderna (utiliza una :ref:`lista de libres +` con un *two level allocator*) y algunas optimizaciones +particulares para amortiguar casos patológicos. + + +.. _dgc_org: + +Organización del *heap* +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +La memoria del *heap* está organizada en *pools*. Un *pool* es una región de +*páginas* contíguas. Una página es, en general, la unidad mínima de memoria que +maneja un sistema operativo con soporte de memoria virtual. Cada página dentro +de un *pool* sirve a su vez como contenedora de bloques (llamados *bin* en la +:ref:`implementación `) de tamaño fijo. Todos los bloques +pertenecientes a la misma página tienen el mismo tamaño de bloque (ver figura +:vref:`fig:dgc-org`). Los tamaños de bloque posibles son potencias de 2 desde +16 bytes hasta 4096 (el tamaño típico de una página), es decir: 16, 32, 64, +128, 256, 512, 1024, 2048 y 4096 [#dgcpageplus]_. Todos los objetos, arreglos +o celdas en general se ubican en estos bloques (en uno del tamaño más pequeño +que haya que sea suficientemente grande como para almacenar dicho objeto). En +caso de que un objeto sea mayor a una página, se utilizan la menor cantidad de +páginas contíguas de un pool que tengan espacio suficiente para almacenar +dicho objeto. + +.. [#dgcpageplus] Además existe otro tamaño de bloque especial que se utiliza + para indicar la continuación de un objeto grande (que ocupan más de una + página). + +.. fig:: fig:dgc-org + + Organización del *heap* del recolector de basura actual de D. + + Organización del *heap*. En este ejemplo todos los *pools* tienen 2 páginas + excepto el *pool* 2 que tiene una sola. El tamaño de bloque que almacena + cada página varía entre 64 bytes (página 0 del *pool* 2) hasta 4096 (ambas + páginas del *pool* N) que es una página completa. + + .. aafig:: + :scale: 1.4 + + +----------------------------------------------------------------------+ + | Heap | + +======================================================================+ + | "Pool 0" "Pool 1" "Pool 2" "Pool 3" ... "Pool N" | + | +----------+ +----------+ +----------+ +----------+ +----------+ | + | | Página 0 | | Página 0 | | Página 0 | | Página 0 | ... | Página 0 | | + | | (8x512) | | (4x1024) | | (64x64) | | (2x2048) | ... | (1x4096) | | + | |+--------+| |+--------+| |+--------+| |+--------+| |+--------+| | + | || Bloque || || || ||qqqqqqqq|| || || || || | + | |+--------+| || Bloque || ||qqqqqqqq|| || || || || | + | || Bloque || || || ||qqqqqqqq|| || || || || | + | |+--------+| |+--------+| ||qqqqqqqq|| || Bloque || || || | + | || Bloque || || || ||qqqqqqqq|| || || || || | + | |+--------+| || Bloque || ||qqqqqqqq|| || || || || | + | || Bloque || || || ||qqqqqqqq|| || || || || | + | |+--------+| |+--------+| ||qqqqqqqq|| |+--------+| || Bloque || | + | || Bloque || || || ||qqqqqqqq|| || || || || | + | |+--------+| || Bloque || ||qqqqqqqq|| || || || || | + | || Bloque || || || ||qqqqqqqq|| || || || || | + | |+--------+| |+--------+| ||qqqqqqqq|| || Bloque || || || | + | || Bloque || || || ||qqqqqqqq|| || || || || | + | |+--------+| || Bloque || ||qqqqqqqq|| || || || || | + | || Bloque || || || ||qqqqqqqq|| || || || || | + | |+--------+| |+--------+| |+--------+| |+--------+| |+--------+| | + | | Página 1 | | Página 1 | +----------+ | Página 1 | ... | Página 1 | | + | | (16x256) | | (8x512) | | (32x128) | ... | (1x4096) | | + | |+--------+| |+--------+| |+--------+| |+--------+| | + | |+--------+| || Bloque || ||nnnnnnnn|| || || | + | |+--------+| |+--------+| ||nnnnnnnn|| || || | + | |+--------+| || Bloque || ||nnnnnnnn|| || || | + | |+--------+| |+--------+| ||nnnnnnnn|| || || | + | |+--------+| || Bloque || ||nnnnnnnn|| || || | + | |+--------+| |+--------+| ||nnnnnnnn|| || || | + | |+--------+| || Bloque || ||nnnnnnnn|| || || | + | |+--------+| |+--------+| ||nnnnnnnn|| || Bloque || | + | |+--------+| || Bloque || ||nnnnnnnn|| || || | + | |+--------+| |+--------+| ||nnnnnnnn|| || || | + | |+--------+| || Bloque || ||nnnnnnnn|| || || | + | |+--------+| |+--------+| ||nnnnnnnn|| || || | + | |+--------+| || Bloque || ||nnnnnnnn|| || || | + | |+--------+| |+--------+| ||nnnnnnnn|| || || | + | |+--------+| || Bloque || ||nnnnnnnn|| || || | + | |+--------+| |+--------+| |+--------+| ... |+--------+| | + | +----------+ +----------+ +----------+ +----------+ | + +----------------------------------------------------------------------+ + +Cada página de un *pool* puede estar asignada a contener bloques de un tamaño +específico o puede estar libre. A su vez, cada bloque puede estar ocupado por +una celda o estar libre. Los bloques libres de un tamaño específico (a +excepción de aquellos bloques que ocupen una página entera) además forman +parte de una :ref:`lista de libres ` (ver figura +:vref:`fig:dgc-free-list`). Esto permite asignar objetos relativamente +pequeños de forma bastante eficiente. + +.. fig:: fig:dgc-free-list + + Ejemplo de listas de libres. + + .. digraph:: dgc_free_list + + margin = 0; + rankdir = LR; + ratio = fill; + size = "4.6,3.6"; + node [ shape = record, width = 0, height = 0 ]; + + subgraph cluster_heap { + style = solid; + color = black; + + free [ label = "Libres| 16| 32| 64| 128| 256| 512| 1024| 2048" ]; + + free:p16 -> b1 -> b2 -> b3; + free:p32 -> b4 -> b5 -> b6 -> b7 -> b8; + // free:p64 is empty + free:p128 -> b9; + free:p256 -> b10 -> b11; + free:p512 -> b12; + free:p1024 -> b13 -> b14; + free:p2048 -> b15 -> b16 -> b17; + } + + +Atributos de *pool* +^^^^^^^^^^^^^^^^^^^ +Cada *pool* tiene la siguiente información asociada: + +*number_of_pages*: + cantidad de páginas que tiene. Esta cantidad es fija en toda la vida de un + *pool*. + +*pages*: + bloque de memoria contíguo de tamaño ``PAGE_SIZE * number_of_pages`` + (siendo ``PAGE_SIZE`` el tamaño de página, que normalmente son 4096 bytes). + + +Atributos de página +^^^^^^^^^^^^^^^^^^^ +Cada página dentro de un *pool* tiene un único atributo asociado: *block_size*. +Se trata del tamaño de los bloques que almacena esta página. + +Una página siempre almacena bloques del mismo tamaño, que pueden ser 16, 32, +64, 128, 256, 512, 1024, 2048 o 4096 (llamado con el nombre especial +``PAGE``). Además hay dos tamaños de bloque símbólicos que tienen un +significado especial: + +``FREE``: + indica que la página está completamente libre y que la página está + disponible para albergar cualquier tamaño de bloque que sea necesario (pero + una vez que se le asignó un nuevo tamaño de bloque ya no puede ser cambiado + hasta que la página vuelva a liberarse por completo). + +``CONTINUATION``: + indica que esta página es la continuación de un objeto grande (es decir, + que ocupa una o más páginas). Luego se presentan más detalles sobre objetos + grandes. + +Las páginas con esto tamaños de bloque especiales (conceptualmente) no +contienen bloques. + + +Atributos de bloque +^^^^^^^^^^^^^^^^^^^ +Cada bloque tiene asociados varios atributos: + +*mark*: + utilizado en la fase de :ref:`marcado `, indica que un nodo + ya fue visitado (serían las celdas *negras* en la :ref:`abstracción + tricolor `). + +*scan*: + utilizado también en la fase de :ref:`marcado `, indica que + una celda visitada todavía tiene *hijas* sin marcar (serían las celdas + *grises* en la :ref:`abstracción tricolor `). + +*free*: + indica que el bloque está libre (no está siendo utilizado por ningún objeto + *vivo*). Esto es necesario solo por la forma en la que realiza el + :ref:`marcado ` y :ref:`barrido ` en el + :ref:`algoritmo actual ` (las celdas con el atributo este + atributo son tomadas como *basura* aunque estén marcadas con *mark*). +*final*: + indica que el bloque contiene un objeto que tiene un destructor (que debe + ser llamado cuando la celda pasa de *viva* a *basura*). -Diseño -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +*noscan*: + indica que el bloque contiene un objeto que no tiene punteros y por lo + tanto no debe ser marcado de forma conservativa (no tiene *hijas*). -.. Acá iría básicamente lo que escribí en el blog sobre la implmentación - actual -TODO +Objetos grandes +^^^^^^^^^^^^^^^ +El recolector de basura actual de D_ trata de forma diferente a los objetos +grandes. Todo objeto grande empieza en un bloque con tamaño ``PAGE`` +y (opcionalmente) continúa en los bloques contíguos subsiguientes que tengan +el tamaño de bloque ``CONTINUATION`` (si el objeto ocupa más que una página). +El fin de un objeto grande queda marcado por el fin del *pool* o una página +con tamaño de bloque distinto a ``CONTINUATION`` (lo que suceda primero). +Cuando un objeto grande se convierte en *basura*, todas sus páginas se liberan +por completo, siendo marcadas con tamaño ``FREE`` para que puedan ser +almacenado en ellas otros objetos grandes o incluso nuevos bloques de un +tamaño determinado. -Implementación + +.. _dgc_algo: + +Algoritmos del recolector +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +A continuación se explica como provee el recolector actual de D_ los servicios +básicos que debe proveer cualquier recolector, como se presentó en la sección +:ref:`gc_intro_services`. + +Cabe aclarar que se presenta una versión simplificada del algoritmo, o más +precisamente, de la implementación del algoritmo, ya que no se exponen en esta +sección muchas optimizaciones que harían muy compleja la tarea de explicar +como funciona conceptualmente. En la siguiente sección, :ref:`dgc_impl`, se +darán más detalles sobre las optimizaciones importantes y diferencias con el +algoritmo aquí presentado, junto con detalles sobre como se implementa la +organización del *heap* que se explicó en la sección anterior. + + +.. _dgc_algo_collect: + +Recolección +^^^^^^^^^^^ +A grandes razgos el algoritmo de recolección puede resumirse de las dos fases +básicas de cualquier algoritmo de :ref:`marcado y barrido `:: + + function collect() is + mark_phase() + sweep_phase() + + +.. _dgc_algo_mark: + +Fase de marcado +^^^^^^^^^^^^^^^ +Esta fase consiste de varios pasos, que pueden resumirse en el siguiente +algoritmo:: + + function mark_phase() is + more_to_scan = false + stop_the_world() + clear_mark_scan_bits() + mark_free_lists() + mark_static_data() + push_registers_into_stack() + mark_stacks() + mark_user_roots() + mark_heap() + start_the_world() + +La variable **global** ``more_to_scan`` indica al algoritmo iterativo cuando +debe finalizar: la función ``mark()`` (que veremos más adelante) lo pone en +``true`` cuando una nueva celda debe ser visitada, por lo tanto la iteración +se interrumpe cuando no hay más celdas por visitar. + +Las funciones ``stop_the_world()`` y ``start_the_world()`` sencillamente +pausan y reanudan todos los hilos respectivamente:: + + function stop_the_world() is + foreach thread in threads + thread.pause() + + function start_the_world() is + foreach thread in threads + thread.resume() + +La función ``clear_mark_scan_bits()`` se encarga de resetear todos los +atributos *mark* y *scan* de cada bloque del *heap*:: + + function clear_mark_scan_bits() is + foreach pool in heap + foreach page in pool + foreach block in page + block.mark = false + block.scan = false + +La función ``mark_free_lists()`` por su parte se encarga de activar el bit +*mark* de todos los bloques de las listas de libres de manera de que la fase +de marcado (que es iterativa y realiza varias pasadas sobre **todo** el +*heap*, incluyendo las celdas libres) no visite las celdas libres perdiendo +tiempo sin sentido y potencialmente manteniendo *vivas* celdas que en +realdidad son *basura* (falsos positivos):: + + function mark_free_lists() is + foreach free_list in heap + foreach block in free_list + block.mark = true + block.free = true + +Notar que los bloques libres quedan entonces marcados aunque sean *basura* por +definición. Para evitar que en la etapa de barrido se tomen estos bloques como +celdas vivas, a todos los bloques en la lista de libres también se los marca +con el bit *free*, así el barrido puede tomar como *basura* estos bloques +aunque estén marcados. + +El *root set* está compuesto por el área de memoria estática (variables +globales), los *stacks* de todos los hilos y los registros del procesador. +Primero se marca el área de memoria estática de manera :ref:`conservativa +` (es decir, tomando cada *word* como si fuera un puntero):: + + function mark_static_data() is + foreach word in static_data + pointer = cast(void*) word + mark(pointer) + +Para poder tomar los registros como parte del *root set* primero se apilan +en el *stack* a través de la función:: + + function push_registers_into_stack() is + foreach register in registers + push(register) + +Una vez hecho esto, basta marcar (de forma conservativa) los *stacks* de todos +los threads para terminar de marcar el *root set*:: + + function mark_stacks() is + foreach thread in threads + foreach word in thread.stack + pointer = cast(void*) word + mark(pointer) + +Dado que D_ soporta manejo de memoria manual al mismo tiempo que memoria +automática, es posible que existan celdas de memoria que no estén en el *root +set* convencional ni en el *heap* del recolector. Para evitar que se libere +alguna celda que estaba siendo referenciada desde memoria administrada por el +usuario, éste debe informarle al recolector sobre la existencia de estoas +nuevas raíces. Es por esto que para concluir el marcado del *root set* +completo se procede a marcar las raíces definidas por el usuario:: + + function mark_user_roots() is + foreach pointer in user_roots + mark(pointer) + +El algoritmo de marcado no es recursivo sino iterativo por lo tanto al marcar +una celda (o bloque) no se siguen sus *hijas*, solo se activa el bit de *scan* +(a menos que la celda no contenga punteros, es decir, tenga el bit *noscan*):: + + function mark(pointer) is + [pool, page, block] = find_block(pointer) + if block is not null and block.mark is false + block.mark = true + if block.noscan is false + block.scan = true + more_to_scan = true + +Por lo tanto en este punto, tenemos todas las celdas inmediatamente +alcanzables desde el *root set* marcadas y con el bit *scan* activado si la +celda puede contener punteros. Por lo tanto solo resta marcar (nuevamente de +forma conservativa) iterativamente todo el *heap* hasta que no hayan más +celdas para visitar (con el bit *scan* activo):: + + function mark_heap() is + while more_to_scan + more_to_scan = false + foreach pool in heap + foreach page in pool + if page.block_size <= PAGE // saltea FREE y CONTINUATION + foreach block in page + if block.scan is true + block.scan = false + if page.block_size is PAGE // objeto grande + start = cast(byte*) page + end = find_big_object_end(pool, page) + foreach word in start..end + pointer = cast(void*) word + mark(pointer) + else // objeto pequeño + foreach word in block + pointer = cast(void*) word + mark(pointer) + +Aquí puede verse, con un poco de esfuerzo, la utilización de la +:ref:`abtracción tricolor `: todas las celdas alcanzables +desde el *root set* son pintadas de *gris* (tienen los bits *mark* y *scan* +activados), excepto aquellas celdas atómicas (es decir, que se sabe que no +tienen punteros) que son marcadas directamente de *negro*. Luego se van +obteniendo celdas del conjunto de las *grises*, se las pinta de *negro* (es +decir, se desactiva el big *scan*) y se pintan todas sus *hijas* de *gris* (o +*negro* directamente si no tienen punteros). Este procedimiento se repite +mientras el conjunto de celdas *grises* no sea vacío (es decir, que +``more_to_scan`` sea ``true``). + +A continuación se presenta la implementación de las funciones suplementarias +utilizadas en la fase de marcado:: + + function find_big_object_end(pool, page) is + pool_end = cast(byte*) pool.pages + (PAGE_SIZE * pool.number_of_pages) + do + page = cast(byte*) page + PAGE_SIZE + while page.block_size is CONTINUATION and page < pool_end + return page + + function find_block(pointer) is + foreach pool in heap + foreach page in pool + if page.block_size is PAGE + big_object_start = cast(byte*) page + big_object_end = find_big_object_end(pool, page) + if big_object_start <= pointer < big_object_end + return [pool, page, big_object_start] + else if page.bloc_size < PAGE + foreach block in page + block_start = cast(byte*) block + block_end = block_start + page.block_size + if block_start <= pointer < block_end + return [pool, page, block_start] + return [null, null, null] + +Cabe destacar que la función ``find_block()`` devuelve el pool, la página y el +comienzo del bloque al que apunta el puntero, es decir, soporta punteros +*interiores*. + + +.. _dgc_algo_sweep: + +Fase de barrido +^^^^^^^^^^^^^^^ +Esta fase es considerablemente más sencilla que el marcado; el algoritmo puede +dividirse en dos pasos básicos:: + + function sweep_phase() is + sweep() + rebuild_free_lists() + +El barrido se realiza con una pasada por sobre todo el heap + + + +.. _dgc_impl: + +Detalles de implementación ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. Acá diría por qué hay que reescribirlo para usar lo que está @@ -57,87 +517,82 @@ TODO -Como se ha visto, D_ es un lenguaje de programación muy completo, -pero aún tiene algunos aspectos inconclusos. Su recolector de basura -está en un estado de evolución muy temprana. Se trata de un marcado y -barrido (*mark and sweep*) conservativo que, en ciertas circunstancias, -no se comporta como es debido, ya que revisa toda la memoria del programa -en busca de referencias a objetos en el *heap* (en vez de revisar sólo -las partes que almacenan punteros). Esto produce que, en ciertos casos, -por ejemplo al almacenar arreglos de número o *strings* en la pila, el -recolector de basura se encuentre con *falsos positivos*, pensando que -un área del *heap* está siendo utilizada cuando en realidad el puntero -que hacía referencia a ésta no era tal. Este efecto puede llevar a la -pérdida de memoria masiva, llegando al límite de que eventualmente +Como se ha visto, D_ es un lenguaje de programación muy completo, pero aún +tiene algunos aspectos inconclusos. Su recolector de basura está en un estado +de evolución muy temprana. Se trata de un marcado y barrido (*mark and sweep*) +conservativo que, en ciertas circunstancias, no se comporta como es debido, ya +que revisa toda la memoria del programa en busca de referencias a objetos en +el *heap* (en vez de revisar sólo las partes que almacenan punteros). Esto +produce que, en ciertos casos, por ejemplo al almacenar arreglos de número +o *strings* en la pila, el recolector de basura se encuentre con *falsos +positivos*, pensando que un área del *heap* está siendo utilizada cuando en +realidad el puntero que hacía referencia a ésta no era tal. Este efecto puede +llevar a la pérdida de memoria masiva, llegando al límite de que eventualmente el sistema operativo tenga que matar al programa por falta de memoria -[DNG46407]_. Aún cuando el programa no tenga estos problemas de por sí, -por usar datos que no pueden ser confundidos con direcciones de memoria, -este problema podría ser explotado por ataques de seguridad, inyectando -valores que sí sean punteros válidos y provocando el efecto antes -mencionado que deriva en la terminación abrupta del programa [DNG35364]_. -Finalmente, a estos problemas se suman los problemas de *performance* -[DNG43991]_. - -Es difícil que D_ pueda ser un lenguaje de programación exitoso si -no provee un recolector de basura eficiente y que realmente evite la -pérdida masiva de memoria. Por otro lado, D_ podría atraer a una base de -usuarios mucho más amplia, si la gama de estrategias de recolección es -más amplia, pudiendo lograr adaptarse a más casos de uso sin llegar al -límite de tener que caer en el manejo explícito de memoria y perder por -completo las ventajas de la recolección de basura (con la consecuencia -ya mencionada de que el manejo de memoria tenga que pasar a ser parte -de las interfaces y la complejidad que esto agrega al diseño -y uso- -de una biblioteca). +[DNG46407]_. Aún cuando el programa no tenga estos problemas de por sí, por +usar datos que no pueden ser confundidos con direcciones de memoria, este +problema podría ser explotado por ataques de seguridad, inyectando valores que +sí sean punteros válidos y provocando el efecto antes mencionado que deriva en +la terminación abrupta del programa [DNG35364]_. Finalmente, a estos problemas +se suman los problemas de *performance* [DNG43991]_. + +Es difícil que D_ pueda ser un lenguaje de programación exitoso si no provee un +recolector de basura eficiente y que realmente evite la pérdida masiva de +memoria. Por otro lado, D_ podría atraer a una base de usuarios mucho más +amplia, si la gama de estrategias de recolección es más amplia, pudiendo lograr +adaptarse a más casos de uso sin llegar al límite de tener que caer en el +manejo explícito de memoria y perder por completo las ventajas de la +recolección de basura (con la consecuencia ya mencionada de que el manejo de +memoria tenga que pasar a ser parte de las interfaces y la complejidad que esto +agrega al diseño -y uso- de una biblioteca). Soluciones Propuestas -Para poder implementar un recolector de basura no conservativo es -necesario disponer de un soporte de reflexión (en tiempo de compilación -[DNG44607]_ y de ejecución [DNG29291]_) bastante completo . De otra forma -es imposible distinguir si un área de memoria de la pila es utilizada -como un puntero o como un simple conjunto de datos. D_ provee algún -grado de reflexión, pero muy limitado como para poder obtener este -tipo de información. Ya hay un plan para agregar mayores capacidades -de reflexibilidad [DNG6842]_, y un pequeño avance en este sentido en la -`versión 1.001`_, pero con algunos problemas [DNG6890]_ [DNG6893]_. +Para poder implementar un recolector de basura no conservativo es necesario +disponer de un soporte de reflexión (en tiempo de compilación [DNG44607]_ y de +ejecución [DNG29291]_) bastante completo . De otra forma es imposible +distinguir si un área de memoria de la pila es utilizada como un puntero o como +un simple conjunto de datos. D_ provee algún grado de reflexión, pero muy +limitado como para poder obtener este tipo de información. Ya hay un plan para +agregar mayores capacidades de reflexibilidad [DNG6842]_, y un pequeño avance +en este sentido en la `versión 1.001`_, pero con algunos problemas [DNG6890]_ +[DNG6893]_. .. _`versión 1.001`: http://www.digitalmars.com/d/changelog.html#new1_001 -Se han propuesto otros métodos e implementaciones de recolector de basura, -por ejemplo colectores con movimiento (*moving collectors*) [DNG42557]_ -y conteo de referencias [DNG38689]_. Pero D_ es un lenguaje muy particular -en cuanto a la recolección de basura (al permitir :ref:d_low_level hay -muchas consideraciones a las que otros lenguajes no deben enfrentarse) y no -es sencillo pensar en otras implementaciones sin hacer modificaciones de -base al lenguaje. +Se han propuesto otros métodos e implementaciones de recolector de basura, por +ejemplo colectores con movimiento (*moving collectors*) [DNG42557]_ y conteo de +referencias [DNG38689]_. Pero D_ es un lenguaje muy particular en cuanto a la +recolección de basura (al permitir :ref:d_low_level hay muchas consideraciones +a las que otros lenguajes no deben enfrentarse) y no es sencillo pensar en +otras implementaciones sin hacer modificaciones de base al lenguaje. Problemas para Implementar Colectores con Movimiento -El principal problema es la capacidad de D_ de manipular punteros y -otras estructuras de bajo nivel, como uniones. O incluso la capacidad -de interactuar con C. Al mover un objeto de un área de memoria a otro, -es necesario actualizar todos los punteros que apuntan a éste. En D_ -esta tarea no es trivial [DNG42564]_ +El principal problema es la capacidad de D_ de manipular punteros y otras +estructuras de bajo nivel, como uniones. O incluso la capacidad de interactuar +con C. Al mover un objeto de un área de memoria a otro, es necesario actualizar +todos los punteros que apuntan a éste. En D_ esta tarea no es trivial +[DNG42564]_ Problemas para Implementar Conteo de Referencias -Este tipo de recolectores reparten la carga de la recolección de forma -uniforme a lo largo (y a la par) de la ejecución del programa. El -problema principal para implementar este tipo de recolección es -la necesidad de soporte en el compilador (cada asignación debe ser -acompañada por el incremento/decremento de contadores de referencia), a -menos que se implemente en una biblioteca. Por otro lado, características -como el rebanado de arreglos (ver :ref:d_high_level) son -difíciles de proveer con el conteo de referencias, entre otros problemas +Este tipo de recolectores reparten la carga de la recolección de forma uniforme +a lo largo (y a la par) de la ejecución del programa. El problema principal +para implementar este tipo de recolección es la necesidad de soporte en el +compilador (cada asignación debe ser acompañada por el incremento/decremento de +contadores de referencia), a menos que se implemente en una biblioteca. Por +otro lado, características como el rebanado de arreglos (ver :ref:d_high_level) +son difíciles de proveer con el conteo de referencias, entre otros problemas [DNG38704]_. .. include:: links.rst -.. vim: set ts=2 sts=2 sw=2 et tw=75 : +.. vim: set ts=3 sts=3 sw=3 et tw=78 :