]> git.llucax.com Git - z.facultad/75.00/informe.git/blob - informe.rst
47627103a5fe9b3051ed0ae3b3516690e3ae8e98
[z.facultad/75.00/informe.git] / informe.rst
1
2 ==========================
3 Recolección de basura en D
4 ==========================
5
6
7 -----
8 Tesis
9 -----
10
11 :Autor: Leandro Lucarella (77891)
12 :Contacto: llucare@fi.uba.ar
13 :Autor: Tutora: Lic. Rosa Wachenchauzer
14 :Organización: Departamento de Computación, Facultad de Ingeniería
15 :Organización: Universidad de Buenos Aires
16 :Fecha: |date|
17 :Revisión: 1
18 :Estado: Borrador
19
20
21 .. contents::
22
23
24 .. ===========================================================================
25
26
27 Introducción
28 ============
29 .. Presenta el problema y temas a ser tratados en el trabajo.
30    ESTADO: TERMINADO
31
32 Los lenguajes de programación modernos tienen una tendencia cada vez
33 más marcada a adoptar técnicas sofisticadas, haciéndolos más ricos y
34 convirtiéndolos realmente en lenguajes, no en meros preprocesadores que
35 convierten de una forma muy directa el código en *assembly*, permitiendo
36 construcciones semánticamente más ricas y permitiendo al programar una
37 mayor expresividad para plasmar algoritmos sin detenerse en los detalles
38 del *hardware*.
39
40 Estos conceptos supuestamente avanzados provienen, en general, de
41 lenguajes académicos (muchos de ellos funcionales) que implementan estas
42 funcionalidades hace mucho tiempo, pero que para su época, o bien no
43 tuvieron suficiente difusión en el ambiente comercial, o bien eran muy
44 lentos por la baja capacidad de procesamiento de la época o incluso
45 demasiado *revolucionarios* para ser adoptados por programadores que no
46 podían ver las ventajas que esos nuevos conceptos proveen.
47
48 El caso de la recolección de basura (*garbage collection* en inglés)
49 es uno de los más representativos. Lisp_ introdujo a principio de los
50 '60 este concepto, como un mecanismo para alocar
51 y liberar recursos de forma automática. Pero no fue hasta avanzados los
52 '90 que esta técnica se empezó a utilizar en lenguajes de programación
53 de uso comercial, cuando fue popularizado por Java_. Incluso luego de
54 más de 30 años para Java_ era costosa la recolección de basura, lo que
55 sumado a la presencia de una máquina virtual para ejecutar los programas
56 producidos, condujo a que estos lenguajes sean notablemente lentos. Aún
57 así Java_ creció y entre las mejoras introducidas hubieron mejoras en
58 la recolección de basura. Otros lenguaje de programación populares que
59 utilizan alguna forma de recolección de basura son Python_, Ruby_, PHP_
60 y `C#`_, entre otros.
61
62 .. _Lisp: http://www.lisp.org/
63 .. _Java: http://www.java.com/
64 .. _Python: http://www.python.org/
65 .. _Ruby: http://www.ruby-lang.org/
66 .. _PHP: http://www.php.net/
67 .. _`C#`: http://www.ecma-international.org/publications/standards/Ecma-334.htm
68
69 .. INTRODUCCION ..............................................................
70
71 Importancia de la Recolección de Basura
72 ---------------------------------------
73 .. Breve descripción de la utilidad de la recolección de basura
74    ESTADO: TERMINADO
75
76 La recolección de basura es muchas veces vista por sus críticos de
77 una forma bastante *naive*. Muchas veces se argumenta que sólo es
78 útil para programadores descuidados o que su necesidad es sólo una
79 manifestación de un mal diseño. Si bien estas dos afirmaciones pueden
80 ser, en algunos casos, ciertas, es falaz pensar que ese es la única
81 ventaja de un recolector de basura. Uno de los aspectos más importantes
82 de un recolector de basura es lograr un mayor nivel de abstracción
83 [JOLI96]_. En particular, al diseñar o programar bibliotecas, de no
84 haber un recolector de basura, **la administración de memoria pasa a ser
85 parte de la interfaz de la biblioteca**. Y lo peor de este aspecto es
86 que muy pocas veces esto es tenido en cuenta, derivando en bibliotecas
87 muy difíciles de usar correctamente sin perder memoria, por no quedar
88 bien clara la responsabilidad del manejo de memoria.
89
90 Esto se debe a que, como se mencionó anteriormente, el manejo de memoria
91 es un *artefacto* proveniente del *hardware*, no un concepto propio
92 de los algoritmos a representar y como tal, nos impide desarrollar una
93 mayor abstracción.
94
95 Muchas veces se aduce también que la recolección de basura impide
96 el desarrollo de programas eficientes. Si bien es innegable que la
97 recolección de basura impone una carga extra, ésta es, en la mayoría
98 de los casos, imperceptible. Incluso algunos algoritmos de recolección
99 de basura pueden aumentar la eficiencia en casos determinados, como los
100 recolectores que compactan, que pueden minimizar considerablemente la
101 cantidad de páginas de memoria referenciadas por el programa, mejorando
102 el *hit-ratio* tanto de la memoria virtual como del *cache*.  Aún si
103 este no fuera el caso, o en casos de sistemas de tiempo real o zonas muy
104 críticas en cuanto a la eficiencia, muchas veces es posible suspender
105 el recolector de basura en dicho fragmento de código. Es cierto que esto
106 rompe un poco con la idea de ganar abstracción, pero es necesario sólo
107 en casos donde hay que realizar optimizaciones y las optimizaciones son,
108 en general, dependientes de la plataforma (*hardware*) y por lo tanto
109 de difícil abstracción.
110
111 El recolector de basura debe tener un comportamiento correcto y predecible
112 para que sea útil, si el programador no puede confiar en el recolector
113 de basura, éste se vuelve más un problema que una solución, porque
114 introduce nuevos puntos de falla en los programas, y lo que es peor,
115 puntos de falla no controlados por el programador, volviendo mucho más
116 difícil la búsqueda de errores.
117
118 .. INTRODUCCION ..............................................................
119
120 El Lenguaje de Programación D
121 -----------------------------
122 .. Breve descripción del lenguaje de programación D
123    ESTADO: TERMINADO
124
125 D_ es un lenguaje de programación joven. Nació en 1999 y el 2 de enero
126 de 2007 salió su `versión 1.0`_. Poco tiempo después se continúo el
127 desarrollo del lenguaje en la `versión 2.0`_, aún inestable y en la
128 cual se está experimentando principalmente sobre *const-correctness*
129 (ya sea como una forma de programación por contratos como para mejorar
130 las oportunidades de optimización del compilador, en especial con
131 código multi-hilo), reflexión y características para soportar mejor
132 programación funcional (como *clausuras* completas) y programación
133 genérica.
134
135 Su creador, `Walter Bright`_, desarrollador principal de Zortech C++,
136 uno de los primeros compilador de C++ que compilaba a código nativo,
137 dice bien claro como nace el lenguaje, citando en su sitio web:
138
139   It seems to me that most of the "new" programming languages fall
140   into one of two categories: Those from academia with radical new
141   paradigms and those from large corporations with a focus on RAD and
142   the web. Maybe it's time for a new language born out of practical
143   experience implementing compilers.
144
145 .. _D: http://www.digitalmars.com/d/
146 .. _`versión 1.0`: http://www.digitalmars.com/d/1.0/changelog.html
147 .. _`versión 2.0`: http://www.digitalmars.com/d/changelog.html
148 .. _`Walter Bright`: http://www.walterbright.com/
149
150 Lo que podría traducirse como:
151
152   Parece que la mayoría de los lenguajes de programación "nuevos" caen
153   en 2 categorías: aquellos académicos con nuevos paradigmas radicales y
154   aquellos de grandes corporaciones con el foco en el desarrollo rápido
155   y web. Tal vez es hora de que nazca un nuevo lenguaje de la experiencia
156   práctica implementando compiladores.
157
158 D_ es un lenguaje de programación con sintaxis tipo C, multiparadigma,
159 compilado, con tipado fuerte y estático, con buenas capacidades tanto de
160 programación de bajo nivel (*system programming*) como de alto nivel,
161 siendo incluso compatible binariamente con C (se puede enlazar código
162 objeto C con código objeto D). Y este es tal vez el punto más fuerte
163 de D_, brindar lo mejor de los 2 mundos. Si bien tiene herramientas
164 de muy bajo nivel, que por lo tanto son muy propensas a errores, da
165 una infinidad de mecanismos para evitar el uso de estas herramientas
166 a menos que sea realmente necesario.  Además pone mucho énfasis en
167 la programación confiable, para lo cual provee muchos mecanismos para
168 detectar errores en los programas de forma temprana.
169
170 Si puede pensarse en C++ como un "C mejor", podría decirse que D_ es
171 un "C++ mejor", ya que el objetivo del lenguaje es muy similar a C++,
172 pero implementa muchas características que jamás pudieron entrar en
173 el estándar de C++ y lo hace de una forma mucho más limpia, ya que
174 no debe lidiar con problemas de compatibilidad hacia atrás, y cuenta
175 con la experiencia del camino recorrido por C++, pudiendo extraer de
176 él los mejores conceptos pero evitando sus mayores problemas también.
177
178 Una de las características que nunca pudo entrar en el estándar de C++
179 es la recolección de basura. D_ no comete el mismo error.
180
181 .. INTRODUCCION ..............................................................
182
183 Objetivo
184 --------
185 .. Objetivo de la tesis
186    ESTADO: TERMINADO, EN REVISION
187
188 La recolección de basura en D_ es un problema prácticamente nuevo. Si bien
189 pueden considerarse válidos todos los modelos propuestos para recolección
190 de basura en C, estos son muy restrictivos y poco eficientes, por lo
191 promiscuo que este lenguaje. Por otro lado D_ provee muchas construcciones
192 de alto nivel, lo que hace que la necesidad de utilizar construcciones de
193 bajo nivel sea muy escasa, por lo tanto brinda un campo importante a
194 explorar en cuanto a mejoras para el recolector de basura.
195
196 Por lo tanto el objetivo del presente trabajo puede resumirse en los
197 siguientes puntos:
198
199 - Investigar y analizar la viabilidad de mejoras al recolector de
200   basura de D_, tanto mejoras menores dentro de las limitaciones actuales
201   del lenguaje (incluyendo pero no limitado a mejoras en el algoritmo
202   actual de recolección y soluciones en *espacio de usuario* -como
203   biblioteca-), como proponiendo mejoras al lenguaje que permitan la
204   implementación recolectores más precisos y eficientes.
205 - Elegir un conjunto de las mejores soluciones halladas e implementarlas.
206   Las soluciones que necesiten modificaciones en el lenguaje serán
207   implementadas modificando el compilador libre de D_ GDC_, que
208   también será utilizado como plataforma principal de desarrollo y
209   prueba (debido a la disponibilidad completa del código fuente y
210   la libertad de usarlo y modificarlo libremente). De todas formas,
211   siempre se priorizarán las modificaciones al *frontend* [#frontend]_
212   sobre las modificaciones al *backend*, permitiendo así que las mejoras
213   puedan ser probadas eventualmente en otros compiladores que utilicen
214   el *frontend* publicado por DigitalMars_, como DMD_.
215 - Realizar pruebas sobre aplicaciones lo más variadas y reales posible
216   sobre todas las soluciones implementadas, de manera de determinar de
217   forma fehaciente las ventajas de unas y otras en cuanto a latencia,
218   consumo de memoria, consumo de procesador, tiempos de pausa, etc.
219 - Presentar las conclusiones obtenidas del análisis y las pruebas
220   realizadas, tanto en el ámbito académico de la facultad como a la
221   comunidad de D_ (con el objetivo de sumar lo construido en este trabajo
222   al lenguaje).
223
224 .. [#frontend] El *frontend* es el módulo del compilador que realiza el
225    análisis sintáctico y semántico del lenguaje. GDC_ utiliza como
226    *frontend* el que provee libremente DigitalMars_.
227 .. [#backend] El *backend* es el módulo del compilador que emite
228    el código binario (o *assembly*, o el lenguaje que produzca el
229    compilador como resultado final). GDC utiliza el *backend* del GCC_
230    (*GNU Compiler Collection*), uno de los compiladores más populares.
231
232
233 .. INTRODUCCION ..............................................................
234
235 Limitaciones
236 ------------
237 .. Cosas que no se pretenden hacer en esta tesis
238    ESTADO: TERMINADO, EN REVISION
239
240 Dado que el lenguaje de programación D_ puede ser enlazado con código
241 objeto C, y por lo tanto interactuar directamente con éste, habrán
242 limitaciones en el recolector resultante con respecto a esto. En este
243 trabajo se busca lograr un recolector que sea eficiente para casos en donde
244 el código que interactúa con C esté bien aislado, por lo que estas
245 porciones de código pueden quedar por fuera del recolector de basura.
246
247 De otra forma probablemente se llegaría a un recolector conservativo y
248 simple como el que está disponible en la actualidad.
249
250 .. ===========================================================================
251
252
253 Recolección de Basura
254 =====================
255 .. Introducción a la importancia de la recolección de basura y sus
256    principales técnicas, con sus ventajas y desventajas. También se da
257    un breve recorrido sobre el estado del arte.
258    ESTADO: SIN EMPEZAR
259
260
261 .. ===========================================================================
262
263
264 El Lenguaje de Programación D
265 =============================
266 .. Introducción y breve reseña del lenguaje de programación D. También
267    se presentan las necesidades particulares de D con respecto al
268    recolector de basura y su estado actual.
269    ESTADO: SIN EMPEZAR, REVISAR LO HECHO
270
271 A continuación se enumeran las principales características de D_,
272 agrupadas por unidades funcional o paradigmas que soporta:
273
274 .. EL LENGUAJE DE PROGRAMACION D .............................................
275
276 Programación Genérica
277 ---------------------
278 - Clases y funciones pueden ser parametrizadas.
279 - Instanciación implícita de funciones parametrizadas.
280 - Especialización parcial y explícita.
281 - Acepta tipos, valores y plantillas como parámetros.
282 - Acepta cantidad de parámetros variables.
283 - Soporta *mixins* [#dmixin]_.
284 - ``if`` estático (``static if``) [#dstaticif]_.
285 - Inferencia de tipos básica implícita [#dtypeinf]_ y explícita
286   (mediante ``typeof``) [#dtypeof]_.
287 - Expresiones ``is`` [#difexpr]_.
288 - Iteración sobre colecciones (``foreach``).
289
290 .. [#dmixin] *Mixin* tiene significados distintos en varios lenguajes de
291    programación. En D_ *mixin* significa tomar una secuencia arbitraria de
292    declaraciones e insertarla en el contexto (*scope*) actual. Esto puede
293    realizarse a nivel global, en clases, estructuras o funciones. Más
294    información en http://www.digitalmars.com/d/mixin.html
295 .. [#dstaticif] Esta construcción puede verse como similar a la
296    directiva del preprocesador de C/C++ ``#if``, pero a diferencia de
297    esto, en D_ el ``static if`` tiene acceso a todos los símbolos del
298    compilador (constantes, tipos, variables, etc). Más información
299    en http://www.digitalmars.com/d/version.html#staticif
300 .. [#dtypeinf] Si no se especifica un tipo al declarar una variable,
301    se infiere del tipo de su inicializador. Más información en
302    http://www.digitalmars.com/d/declaration.html#AutoDeclaration
303 .. [#dtypeof] ``typeof`` permite especificar un tipo
304    inferido de una expresión. Más información en
305    http://www.digitalmars.com/d/declaration.html#typeof
306 .. [#difexpr] Las *expresiones ``if``* permiten la compilación condicional
307    basada en las características de un tipo. Esto se realiza en favor
308    a una técnica utilizada en C++ de realizar *pattern matching*
309    sobre los parámetros de las plantillas. Más información en
310    http://www.digitalmars.com/d/expression.html#IsExpression
311
312 .. EL LENGUAJE DE PROGRAMACION D .............................................
313
314 Programación de Bajo Nivel (*system programming*)
315 -------------------------------------------------
316 - Compila a código de máquina nativo (no necesita una máquina virtual).
317 - Provee acceso a *assembly* (y por lo tanto, acceso directo al
318   *hardware*).
319 - ``goto``.
320 - Soporta todos los tipos de C.
321 - ABI [#abi]_ compatible con C (genera archivos objeto estándar por lo que
322   se puede enlazar con código C).
323 - Permite manejo de memoria explícito (permitiendo alocar estructuras en
324   el *stack* o en el *heap*).
325 - Objetos *livianos* (no polimórficos) y arreglos *livianos* (estáticos,
326   sin *overhead* como C).
327 - La `programación genérica`_ permite realizar muchas optimizaciones
328   ya que se resuelve en tiempo de compilación y por lo tanto aumentando
329   la *performance* en la ejecución.
330 - Número de punto flotante de 80 bits.
331 - Control de alineación de miembros de una estructura.
332
333 .. [#abi] Interfaz de Aplicación Binaria (del inglés *Application Binary
334    Interface*).
335
336 .. EL LENGUAJE DE PROGRAMACION D .............................................
337
338 Programación de Alto Nivel
339 --------------------------
340 - Manejo de memoria automática (recolección de basura).
341 - Sistema de módulos (similar a Python_).
342 - Funciones y delegados:
343
344   - Son ciudadanos de primera clase [#1stclasscity]_.
345   - Pueden ser sobrecargados.
346   - Pueden estar anidados.
347   - Argumentos de entrada/salida.
348   - Argumentos por omisión.
349   - Evaluación perezosa (*lazy*) de argumentos.
350   - Cantidad de argumentos variables (con tipado seguro).
351
352 - Arreglos *dinámicos* (de longitud variable) y arreglos asociativos
353   (también conocidos como *hashes* o diccionarios) y son ciudadanos
354   de primera clase [#1stclasscity]_, soporta rebanado (*array slicing*
355   [#dslicing]_) y chequeo de límites (*bound checking*).
356 - Soporta *strings* como tipo nativo (con codificación utf-8), incluyendo
357   la capacidad de hacer un ``switch`` sobre estos.
358 - ``alias`` [#dalias]_.
359 - Documentación embebida.
360 - Números complejos.
361
362 .. [#1stclasscity] Por ciudadano de primera clase se entiende que se
363    trata de un tipo soportado por completo por el lenguaje, disponiendo de
364    expresiones literales anónimas, pudiendo ser almacenados en variables,
365    estructuras de datos, teniendo una identidad intrínseca, más allá
366    de un nombre dado, etc. En realidad los arreglos asociativos no pueden
367    ser expresados como literales anónimos pero sí tienen una sintaxis
368    especial soportada directamente por el lenguaje.
369 .. [#dslicing] Se refiere a la capacidad de referirse a una porción de
370    un arreglo. Profundizaremos sobre esta característica más adelante
371    porque es importante a la hora de elegir un método de recolección
372    de basura.
373 .. [#dalias] Análogo al ``typedef`` de C/C++.
374
375 .. EL LENGUAJE DE PROGRAMACION D .............................................
376
377 Programación Orientada a Objetos
378 --------------------------------
379 - Objetos *pesadas* (polimórficos).
380 - Interfaces.
381 - Sobrecarga de operadores (con tipos de retorno covariantes [#dcovariant]_).
382 - Clases anidadas.
383 - Propiedades [#dprop]_.
384
385 .. [#dcovariant] Tipo de retorno covariante se refiere a la
386    capacidad de que una función sobreescrita por una clase derivada
387    puede retornar un tipo que sea derivado del tipo retornado
388    por la función original sobreescrita. Más información en
389    http://www.digitalmars.com/d/function.html
390 .. [#dprop] En D_ se refiere a funciones miembro que pueden ser tratadas
391    sintácticamente como campos de esa clase/estructura. Más información
392    en http://www.digitalmars.com/d/property.html#classproperties
393
394 .. EL LENGUAJE DE PROGRAMACION D .............................................
395
396 Programación Confiable
397 ----------------------
398 - Diseño por contrato [#ddbc]_:
399
400   - Precondiciones.
401   - Postcondiciones.
402   - Invariantes de representación.
403   - Afirmaciones (*asserts*).
404
405 - Pruebas unitarias.
406 - Orden de construcción estática (inicialización de módulos) determinado.
407 - Inicialización garantizada.
408 - RAII [#draii]_ (*Resource adquisition is initialization*).
409 - Guardias de contexto (*scope guards*).
410 - Excepciones (con ``try``, ``catch`` y ``finally``).
411 - Primitivas de sincronización de hilos (``synchronized``).
412
413 .. [#ddbc] El diseño por contrato es un concepto creado por Eiffel_ a
414    mediados/finales de los '80. Más información sobre el soporte de D_ en
415    http://www.digitalmars.com/d/dbc.html
416 .. [#draii] Es una técnica muy utilizada en C++ que consiste en reservar
417    recursos por medio de la construcción de un objeto y liberarlos cuando
418    se libera éste. Al llamarse al destructor de manera automática cuando
419    se sale del *scope*, se asegura que el recurso será liberado también.
420    Esta técnica es la base para desarrollar código seguro en cuanto a
421    excepciones (*exception-safe*) [SUTT99]_.
422
423 .. _Eiffel: http://www.eiffel.com/
424
425
426 .. ===========================================================================
427
428
429 Definición del Problema
430 =======================
431 .. Describe más detalladamente los problemas actuales del recolector de
432    basura de D, sentando las bases para el análisis de los requerimientos
433    de recolección de basura en dicho lenguaje (se explica por qué las
434    particularidades descriptas en la sección anterior complican la
435    recolección de basura).
436    ESTADO: SIN EMPEZAR, REVISAR LO HECHO
437
438 Como se ha visto, D_ es un lenguaje de programación muy completo,
439 pero aún tiene algunos aspectos inconclusos. Su recolector de basura
440 está en un estado de evolución muy temprana. Se trata de un marcado y
441 barrido (*mark and sweep*) conservativo que, en ciertas circunstancias,
442 no se comporta como es debido, ya que revisa toda la memoria del programa
443 en busca de referencias a objetos en el *heap* (en vez de revisar sólo
444 las partes que almacenan punteros). Esto produce que, en ciertos casos,
445 por ejemplo al almacenar arreglos de número o *strings* en la pila, el
446 recolector de basura se encuentre con *falsos positivos*, pensando que
447 un área del *heap* está siendo utilizada cuando en realidad el puntero
448 que hacía referencia a ésta no era tal. Este efecto puede llevar a la
449 pérdida de memoria masiva, llegando al límite de que eventualmente
450 el sistema operativo tenga que matar al programa por falta de memoria
451 [DNG46407]_. Aún cuando el programa no tenga estos problemas de por sí,
452 por usar datos que no pueden ser confundidos con direcciones de memoria,
453 este problema podría ser explotado por ataques de seguridad, inyectando
454 valores que sí sean punteros válidos y provocando el efecto antes
455 mencionado que deriva en la terminación abrupta del programa [DNG35364]_.
456 Finalmente, a estos problemas se suman los problemas de *performance*
457 [DNG43991]_.
458
459 Es difícil que D_ pueda ser un lenguaje de programación exitoso si
460 no provee un recolector de basura eficiente y que realmente evite la
461 pérdida masiva de memoria. Por otro lado, D_ podría atraer a una base de
462 usuarios mucho más amplia, si la gama de estrategias de recolección es
463 más amplia, pudiendo lograr adaptarse a más casos de uso sin llegar al
464 límite de tener que caer en el manejo explícito de memoria y perder por
465 completo las ventajas de la recolección de basura (con la consecuencia
466 ya mencionada de que el manejo de memoria tenga que pasar a ser parte
467 de las interfaces y la complejidad que esto agrega al diseño -y uso-
468 de una biblioteca).
469
470
471 .. ===========================================================================
472
473
474 Análisis de la Solución
475 =======================
476 .. Describe los resultados del análisis y explica los fundamentos para
477    elegir los algoritmos seleccionados para implementar, en base a los
478    requerimientos hallados anteriormente.
479    ESTADO: SIN EMPEZAR, REVISAR LO HECHO
480
481 .. ANALISIS DE LA SOLUCION ...................................................
482
483 Soluciones Propuestas
484 ---------------------
485 Para poder implementar un recolector de basura no conservativo es
486 necesario disponer de un soporte de reflexión (en tiempo de compilación
487 [DNG44607]_ y de ejecución [DNG29291]_) bastante completo . De otra forma
488 es imposible distinguir si un área de memoria de la pila es utilizada
489 como un puntero o como un simple conjunto de datos. D_ provee algún
490 grado de reflexión, pero muy limitado como para poder obtener este
491 tipo de información. Ya hay un plan para agregar mayores capacidades
492 de reflexibilidad [DNG6842]_, y un pequeño avance en este sentido en la
493 `versión 1.001`_, pero con algunos problemas [DNG6890]_ [DNG6893]_.
494
495 .. _`versión 1.001`: http://www.digitalmars.com/d/changelog.html#new1_001
496
497 Se han propuesto otros métodos e implementaciones de recolector de
498 basura, por ejemplo colectores con movimiento (*moving collectors*)
499 [DNG42557]_ y conteo de referencias [DNG38689]_. Pero D_ es un
500 lenguaje muy particular en cuanto a la recolección de basura (al
501 permitir `programación de bajo nivel (system programming)`_ hay muchas
502 consideraciones a las que otros lenguajes no deben enfrentarse) y no es
503 sencillo pensar en otras implementaciones sin hacer modificaciones de
504 base al lenguaje.
505
506 .. ANALISIS DE LA SOLUCION ...................................................
507
508 Problemas para Implementar Colectores con Movimiento
509 ----------------------------------------------------
510 El principal problema es la capacidad de D_ de manipular punteros y
511 otras estructuras de bajo nivel, como uniones. O incluso la capacidad
512 de interactuar con C. Al mover un objeto de un área de memoria a otro,
513 es necesario actualizar todos los punteros que apuntan a éste. En D_
514 esta tarea no es trivial [DNG42564]_
515
516 .. ANALISIS DE LA SOLUCION ...................................................
517
518 Problemas para Implementar Conteo de Referencias
519 ------------------------------------------------
520 Este tipo de recolectores reparten la carga de la recolección de forma
521 uniforme a lo largo (y a la par) de la ejecución del programa. El
522 problema principal para implementar este tipo de recolección es
523 la necesidad de soporte en el compilador (cada asignación debe ser
524 acompañada por el incremento/decremento de contadores de referencia), a
525 menos que se implemente en una biblioteca. Por otro lado, características
526 como el rebanado de arreglos (ver `Programación de Alto Nivel`_) son
527 difíciles de proveer con el conteo de referencias, entre otros problemas
528 [DNG38704]_.
529
530
531 .. ===========================================================================
532
533
534 Implementación de la solución:
535 ==============================
536 .. Describe el diseño e implementación de los algoritmos
537    seleccionados. Se detalla si la solución se implementa como
538    biblioteca o si fue necesario modificar el compilador y de ser así
539    si se modificó el *frontend* o el GDC y se comentan problemas y
540    limitaciones encontradas.
541    ESTADO: SIN EMPEZAR
542
543
544 .. ===========================================================================
545
546
547 Conclusiones
548 ============
549 .. Se presentan las conclusiones del trabajo, comparando los resultados
550    obtenidos con el punto de partida. Se mencionan puntos pendientes o
551    nuevas líneas de investigación.
552    ESTADO: SIN EMPEZAR
553
554
555
556
557 .. ===========================================================================
558 .. ============================ FIN DEL DOCUMENTO ============================
559 .. ===========================================================================
560
561 .. Pone links "offline" (para generar PDF para imprimir).
562 .. .. target-notes::
563
564 .. Macros:
565 .. |date| date:: %e de %B de %Y
566
567 .. Citas:
568 .. [JOLI96] Richard Jones, Rafael D Lins. Garbage Collection: Algorithms
569    for Automatic Dynamic Memory Management. John Wiley & Sons, 1996.
570    ISBN 0-471-94148-4.
571 .. [SUTT99] Herb Sutter. Exceptional C++: 47 Engineering Puzzles,
572    Programming Problems, and Solutions, 1ra edición. Addison-Wesley
573    Professional, 1999. ISBN 0-201-61562-2.
574 .. [DNG46407] Oskar Linde. The problem with the D GC. Grupo de noticias
575    digitalmars.D, 8 de enero de 2007. `Mensaje número 46407`_.
576 .. _`Mensaje número 46407`: http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=46407
577 .. [DNG43991] Andrey Khropov. [Performance] shootout.binarytrees when
578    implemented with gc is 10x slower than C# on .NET 2.0. Grupo de noticias
579    digitalmars.D, 11 de noviembre de 2006. `Mensaje número 43991`_.
580 .. _`Mensaje número 43991`: http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=43991
581 .. [DNG35364] Frank Benoit. GC implementation. Grupo de noticias
582    digitalmars.D, 18 de marzo de 2006. `Mensaje número 35364`_.
583 .. _`Mensaje número 35364`: http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=35364
584 .. [DNG44607] Russ Lewis. A TODO for somebody: Full Reflection Gets You
585    Smarter GC. Grupo de noticias digitalmars.D, 20 de noviembre de
586    2006. `Mensaje número 44607`_.
587 .. _`Mensaje número 44607`: http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=44607
588 .. [DNG29291] Larry Evans. How does RTTI help gc?. Grupo de noticias
589    digitalmars.D, 21 de octubre de 2005. `Mensaje número 29291`_.
590 .. _`Mensaje número 29291`: http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=29291
591 .. [DNG6842] Walter Bright. Transitioning to a type aware Garbage
592    Collector. Grupo de noticias digitalmars.D.announce, 22 de enero de
593    2007. `Mensaje número 6842`_.
594 .. _`Mensaje número 6842`: http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D.announce&article_id=6842
595 .. [DNG42557] Lionello Lunesu. Is a moving GC really needed?. Grupo de
596    noticias digitalmars.D, 2 de octubre de 2006. `Mensaje número 42557`_.
597 .. _`Mensaje número 42557`: http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=42557
598 .. [DNG38689] Frank Benoit. GC, the simple solution. Grupo de noticias
599    digitalmars.D, 4 de junio de 2006. `Mensaje número 38689`_.
600 .. _`Mensaje número 38689`: http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=38689
601 .. [DNG42564] xs0. Re: Is a moving GC really needed?. Grupo de noticias
602    digitalmars.D, 2 de octubre de 2006. `Mensaje número 42564`_.
603 .. _`Mensaje número 42564`: http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=42564
604 .. [DNG38704] Walter Bright. Re: GC, the simple solution. Grupo de
605    noticias digitalmars.D, 4 de junio de 2006. `Mensaje número 38704`_.
606 .. _`Mensaje número 38704`: http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=38704
607 .. [DNG6890] Lionello Lunesu. std.string.split is broken :( (Re: DMD 1.001
608    release). Grupo de noticias digitalmars.D.announce, 24 de enero de
609    2007. `Mensaje número 6890`_.
610 .. _`Mensaje número 6890`: http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D.announce&article_id=6890
611 .. [DNG6893] Oskar Linde. Re: DMD 1.001 release. Grupo de noticias
612    digitalmars.D.announce, 24 de enero de 2007. `Mensaje número 6893`_.
613 .. _`Mensaje número 6893`: http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D.announce&article_id=6893
614 .. [HDH03] Martin Hirzel, Amer Diwan, and Matthew Hertz, Proceedings
615    of the 18th Conference on Object-Oriented Programming, Systems,
616    Languages, and Applications (OOPSLA 2003), Anaheim, CA, Oct. 26-30,
617    2003.
618 .. [LINS05] Rafael D Lins. A New Multi-Processor Architecture for
619    Parallel Lazy Cyclic Reference Counting. Proceedings of the 17th
620    International Symposium on Computer Architecture on High Performance
621    Computing - Volume 00 (páginas 35-43), 2005.
622
623 .. vim: set ts=2 sts=2 sw=2 et tw=75 :