¿Cómo funciona la recolección de basura en los idiomas que se compilan de forma nativa?

79

Después de buscar varias respuestas en un desbordamiento de pila, está claro que algunos lenguajes compilados de forma nativa tienen recolección de basura . Pero no me queda claro cómo funcionaría exactamente esto.

Entiendo cómo la recolección de basura podría funcionar con un lenguaje interpretado. El recolector de basura simplemente se ejecutaría junto con el intérprete y eliminaría los objetos no utilizados e inalcanzables de la memoria del programa. Ambos corren juntos.

¿Cómo funcionaría esto con lenguajes compilados? Tengo entendido que una vez que el compilador ha compilado el código fuente en el código de destino, específicamente el código de máquina nativo, está listo. Su trabajo está terminado. Entonces, ¿cómo podría el programa compilado ser basura recolectada también?

¿El compilador funciona con la CPU de alguna manera mientras se ejecuta el programa para eliminar objetos "basura"? ¿O el compilador incluye algún recolector mínimo de basura en el ejecutable del programa compilado?

Creo que mi última declaración tendría más validez que la primera debido a este extracto de esta respuesta en Stack Overflow :

Uno de esos lenguajes de programación es Eiffel. La mayoría de los compiladores de Eiffel generan código C por razones de portabilidad. Este código C se usa para producir código de máquina por un compilador C estándar. Las implementaciones de Eiffel proporcionan GC (y a veces incluso GC preciso) para este código compilado, y no hay necesidad de VM. En particular, el compilador VisualEiffel generó código máquina nativo x86 directamente con soporte completo de GC .

La última declaración parece implicar que el compilador incluye algún programa en el ejecutable final que actúa como un recolector de basura mientras el programa se está ejecutando.

La página en el sitio web del lenguaje D sobre la recolección de basura , que se compila de forma nativa y tiene un recolector de basura opcional, también parece indicar que algún programa en segundo plano se ejecuta junto con el programa ejecutable original para implementar la recolección de basura.

D es un lenguaje de programación de sistemas con soporte para recolección de basura. Por lo general, no es necesario liberar memoria explícitamente. Simplemente asigne según sea necesario, y el recolector de basura devolverá periódicamente toda la memoria no utilizada al conjunto de memoria disponible.

Si se usa el método mencionado anteriormente , ¿cómo funcionaría exactamente? ¿El compilador almacena una copia de algún programa de recolección de basura y la pega en cada ejecutable que genera?

¿O tengo defectos en mi pensamiento? Si es así, ¿qué métodos se utilizan para implementar la recolección de basura para los lenguajes compilados y cómo funcionarían exactamente?

Christian Dean
fuente
1
Le agradecería si el votante cercano de esta pregunta pudiera decir exactamente qué está mal para poder solucionarlo.
Christian Dean
66
Si acepta el hecho de que el GC es básicamente parte de una biblioteca requerida por una implementación de lenguaje de programación particular, entonces la esencia de su pregunta no tiene nada que ver con el GC per se y todo que ver con la vinculación estática versus dinámica .
Theodoros Chatzigiannakis
77
Puede considerar que el recolector de basura es parte de la biblioteca de tiempo de ejecución que implementa el equivalente del lenguaje malloc().
Barmar
99
El funcionamiento de un recolector de basura depende de las características del asignador , no del modelo de compilación . El asignador conoce cada objeto que ha sido asignado; los asignó Ahora todo lo que necesita es una forma de saber qué objetos siguen vivos , y el recolector puede desasignar todos los objetos excepto ellos. Nada en esa descripción tiene nada que ver con el modelo de compilación.
Eric Lippert
1
GC es una característica de la memoria dinámica, no una característica del intérprete.
Dmitry Grigoryev

Respuestas:

52

La recolección de basura en un idioma compilado funciona de la misma manera que en un lenguaje interpretado. Los lenguajes como Go usan recolectores de basura de rastreo, aunque su código generalmente se compila en código de máquina antes de tiempo.

La recolección de basura (rastreo) generalmente comienza caminando las pilas de llamadas de todos los hilos que se están ejecutando actualmente. Los objetos en esas pilas siempre están vivos. Después de eso, el recolector de basura atraviesa todos los objetos que señalan los objetos vivos, hasta que se descubre todo el gráfico de objetos vivos.

Está claro que hacer esto requiere información adicional que los lenguajes como C no proporcionan. En particular, requiere un mapa del marco de la pila de cada función que contiene los desplazamientos de todos los punteros (y probablemente sus tipos de datos), así como mapas de todos los diseños de objetos que contienen la misma información.

Sin embargo, es fácil ver que los lenguajes que tienen fuertes garantías de tipo (por ejemplo, si no se permiten conversiones de puntero a diferentes tipos de datos) pueden calcular esos mapas en tiempo de compilación. Simplemente almacenan una asociación entre direcciones de instrucciones y mapas de cuadros de pila y una asociación entre tipos de datos y mapas de diseño de objetos dentro del binario. Esta información les permite hacer el recorrido del gráfico de objetos.

El recolector de basura en sí no es más que una biblioteca vinculada al programa, similar a la biblioteca estándar de C. Por ejemplo, esta biblioteca podría proporcionar una función similar a la malloc()que ejecuta el algoritmo de recopilación si la presión de la memoria es alta.

avdgrinten
fuente
99
Entre las bibliotecas de utilidades y la compilación JIT, las líneas entre "compilado a nativo" y "se ejecuta en un entorno de tiempo de ejecución" se vuelven cada vez más borrosas.
corsiKa
66
Solo para agregar un poco sobre los lenguajes que no son compatibles con GC: es cierto que C y otros lenguajes similares no brindan información sobre las pilas de llamadas, pero si está de acuerdo con algún código específico de la plataforma (generalmente incluye un poco del código de ensamblaje) todavía es posible implementar "recolección de basura conservadora". El GC Boehm es un ejemplo de esto utilizado en programas de la vida real.
Matti Virkkunen
2
@corsiKa O más bien, la línea es mucho más clara. Ahora vemos que esos son conceptos diferentes no relacionados, y no antónimos entre sí.
Kroltan
44
Una complejidad adicional que debe tener en cuenta en los tiempos de ejecución compilados e interpretados se relaciona con esta oración en su respuesta: "La recolección de basura (rastreo) generalmente comienza caminando las pilas de llamadas de todos los hilos que se están ejecutando actualmente". Mi experiencia de implementar GC en un entorno compilado es que el seguimiento de las pilas no es suficiente. El punto de partida generalmente es suspender los subprocesos durante el tiempo suficiente para rastrearlos desde sus registros , ya que pueden tener referencias en aquellos registros que aún no se han almacenado en la pila. Para un intérprete, esto no suele ser ...
Jules
... un problema, porque el entorno puede organizar que el GC tenga lugar en "puntos seguros" donde el intérprete sepa que todos los datos se almacenan de forma segura en las pilas interpretadas.
Jules
123

¿El compilador almacena una copia de algún programa de recolección de basura y lo pega en cada ejecutable que genera?

Suena poco elegante y extraño, pero sí. El compilador tiene una biblioteca de utilidades completa, que contiene mucho más que un simple código de recolección de basura, y las llamadas a esta biblioteca se insertarán en cada ejecutable que cree. Esto se llama la biblioteca de tiempo de ejecución , y usted se sorprendería de cuántas tareas diferentes que normalmente sirve.

Kilian Foth
fuente
51
@ ChristianDean Tenga en cuenta que incluso C tiene una biblioteca en tiempo de ejecución. Si bien no tiene GC, aún realiza la administración de memoria a través de esa biblioteca de tiempo de ejecución: malloc()y free()no están integrados en el lenguaje, no son parte del sistema operativo, pero son funciones en esta biblioteca. C ++ también a veces se compila con una biblioteca de recolección de basura, aunque el lenguaje no fue diseñado con GC en mente.
amon
18
C ++ también contiene una biblioteca en tiempo de ejecución que hace que cosas como hacer dynamic_casty excepciones funcionen, incluso si no agrega un GC.
Sebastian Redl
23
La biblioteca de tiempo de ejecución no se copia necesariamente en cada ejecutable (que se llama enlace estático), solo se puede hacer referencia a ella (una ruta al binario que contiene la biblioteca) y acceder en tiempo de ejecución: esto es un enlace dinámico.
mouviciel
16
Tampoco se requiere que el compilador salte directamente al punto de entrada de su programa sin que ocurra nada más. Estoy haciendo una suposición educada de que cada compilador en realidad inserta un montón de código de inicialización específico de la plataforma antes de llamar main(), y es perfectamente legal, por ejemplo, activar un hilo GC en este código. (Suponiendo que el GC no se realiza dentro de las llamadas de asignación de memoria). En tiempo de ejecución, el GC solo necesita saber qué partes de un objeto son punteros o referencias de objeto, y el compilador necesita emitir el código para traducir una referencia de objeto a un puntero si el GC reubica objetos.
millimoose
15
@millimoose: sí. Por ejemplo, en GCC, este pedazo de código es crt0.o(que significa " C R ONU T iempo, los conceptos básicos"), que consigue unida a todo el programa (o por lo menos cada programa que no es de independiente ).
Jörg W Mittag
58

¿O el compilador incluye algún recolector mínimo de basura en el código del programa compilado?

Esa es una forma extraña de decir "el compilador vincula el programa con una biblioteca que realiza la recolección de basura". Pero sí, eso es lo que está pasando.

Esto no es nada especial: los compiladores generalmente vinculan toneladas de bibliotecas a los programas que compilan; de lo contrario, los programas compilados no podrían hacer mucho sin volver a implementar muchas cosas desde cero: incluso escribir texto en la pantalla / un archivo / ... requiere una biblioteca.

¿Pero quizás GC es diferente de estas otras bibliotecas, que proporcionan API explícitas que el usuario llama?

No: en la mayoría de los idiomas, las bibliotecas de tiempo de ejecución hacen mucho trabajo detrás de escena sin API pública, más allá de GC. Considere estos tres ejemplos:

  1. Propagación de excepción y llamada de desenrollado / destructor de pila.
  2. Asignación de memoria dinámica (que generalmente no solo llama a una función, como en C, incluso cuando no hay recolección de basura).
  3. Seguimiento de información de tipo dinámico (para conversiones, etc.).

Por lo tanto, una biblioteca de recolección de basura no es nada especial, y a priori no tiene nada que ver con si un programa se compiló con anticipación.

Konrad Rudolph
fuente
Esto no parece ofrecer nada sustancial sobre los puntos hechos y explicados en la respuesta principal publicada 3 horas antes
mosquito
11
@gnat Sentí que era útil / necesario porque la respuesta principal no es lo suficientemente fuerte: menciona hechos similares, pero no señala que la recolección de basura es una distinción completamente artificial. Básicamente, la suposición de OP es defectuosa, y la respuesta principal no menciona esto. La mía sí (evitando el término bastante brusco "defectuoso").
Konrad Rudolph
No es tan especial, pero yo diría que es algo especial, ya que generalmente la gente piensa en las bibliotecas como algo que llaman explícitamente desde su código; en lugar de una implementación de la semántica del lenguaje fundamental. Creo que la suposición errónea del OP aquí es más bien que un compilador es solo para traducir código de una manera más o menos directa, en lugar de instrumentarlo con llamadas a la biblioteca que el autor no especificó.
millimoose
77
Las bibliotecas @millimoose Runtime operan detrás de escena de muchas maneras sin interacción explícita del usuario. Considere la propagación de excepciones y las llamadas de desenrollado / destructor de pila. Considere la asignación de memoria dinámica (que generalmente no es solo llamar a una función, como en C, incluso cuando no hay recolección de basura). Considere el manejo de información de tipo dinámico (para conversiones, etc.). Entonces el GC realmente no es único.
Konrad Rudolph
3
Sí, admito que lo había dicho de manera extraña. Eso fue simplemente porque era escéptico de que el compilador real hiciera algo así. Pero ahora que lo pienso, tiene mucho más sentido. El compilador podría simplemente vincular un recolector de basura como cualquier otra parte de la biblioteca estándar. Creo que parte de mi confusión surgió al pensar en un recolector de basura como solo una parte de la implementación de un intérprete y no como un programa separado por derecho propio.
Christian Dean
23

¿Cómo funcionaría esto con lenguajes compilados?

Tu redacción es incorrecta. Un lenguaje de programación es una especificación escrita en algún informe técnico (para un buen ejemplo, vea R5RS ). En realidad, te estás refiriendo a una implementación de lenguaje específica (que es un software).

(algunos lenguajes de programación tienen malas especificaciones, u otras aún faltan, o simplemente como conforme a alguna aplicación de la muestra, todavía, un lenguaje de programación define un comportamiento - por ejemplo, que tiene una sintaxis y la semántica -, es no un producto de software, pero podría haber implementado por algún producto de software; muchos lenguajes de programación tienen varias implementaciones; en particular, "compilado" es un adjetivo que se aplica a las implementaciones , incluso si algunos lenguajes de programación son implementados más fácilmente por los intérpretes que por los compiladores).

Tengo entendido que una vez que el compilador ha compilado el código fuente en el código de destino, específicamente el código de máquina nativo, está listo. Su trabajo está terminado.

Tenga en cuenta que los intérpretes y los compiladores tienen un significado suelto, y algunas implementaciones de lenguaje podrían considerarse como ambas. En otras palabras, hay un continuo en el medio. Lea el último Dragon Book y piense en bytecode , compilación JIT , emitiendo dinámicamente código C que se compila en algún "complemento" y luego dlopen (3) -editado por el mismo proceso (y en las máquinas actuales, esto es lo suficientemente rápido como para ser compatible con una REPL interactiva , mira esto )


Recomiendo leer el manual de GC . Se necesita un libro completo para responder . Antes de eso, lea el wikipage de Garbage Collection (que supongo que ha leído antes de leer a continuación).

El sistema de tiempo de ejecución de la implementación del lenguaje compilado contiene el recolector de basura, y el compilador está generando código que se ajusta a ese sistema de tiempo de ejecución particular. En particular, las primitivas de asignación (se compilan en código de máquina que) llamarán (o podrán) al sistema de tiempo de ejecución.

Entonces, ¿cómo podría el programa compilado ser basura recolectada también?

Simplemente emitiendo un código de máquina que usa (y es "amigable" y "compatible con") el sistema de tiempo de ejecución.

Tenga en cuenta que puede encontrar varias bibliotecas de recolección de basura, en particular Boehm GC , Ravenbrook's MPS o incluso mi Qish (sin mantenimiento) . Y codificar un GC simple no es muy difícil (sin embargo, depurarlo es más difícil y codificar un GC competitivo es difícil ).

En algunos casos, el compilador usaría un GC conservador (como Boehm GC ). Entonces, no hay mucho que codificar. El GC conservador (cuando el compilador llama a su rutina de asignación, o la rutina completa del GC) a veces escanea toda la pila de llamadas , y supone que cualquier zona de memoria (indirectamente) accesible desde la pila de llamadas está activa. Esto se llama un GC conservador porque la información de escritura se pierde: si un entero en la pila de llamadas se parece a alguna dirección, se seguiría, etc.

En otros casos (más difíciles), el tiempo de ejecución proporciona una recolección de basura de copia generacional (un ejemplo típico es el compilador Ocaml, que compila el código Ocaml al código de la máquina usando un GC de este tipo). Entonces, el problema es encontrar con precisión en las pilas de llamadas todos los punteros, y algunos de ellos son movidos por el GC. Luego, el compilador genera metadatos que describen los marcos de la pila de llamadas, que el tiempo de ejecución utiliza. Por lo tanto, las convenciones de llamadas y ABI se están volviendo específicas para esa implementación (es decir, el compilador) y el sistema de tiempo de ejecución.

En algunos casos, el código de máquina generado por el compilador (incluso los cierres que apuntan a él) es en sí mismo basura recolectada . Este es notablemente el caso de SBCL (una buena implementación de Common Lisp) que genera código de máquina para cada interacción REPL . Esto también requiere algunos metadatos que describen el código y los marcos de llamada utilizados dentro de él.

¿El compilador almacena una copia de algún programa de recolección de basura y la pega en cada ejecutable que genera?

Algo así como. Sin embargo, el sistema de tiempo de ejecución podría ser una biblioteca compartida, etc. A veces (en Linux y varios otros sistemas POSIX) incluso podría ser un intérprete de script, por ejemplo, pasado a execve (2) con un shebang . O un intérprete ELF , ver elf (5) y PT_INTERP, etc.

Por cierto, la mayoría de los compiladores para lenguaje con recolección de basura (y su sistema de tiempo de ejecución) son hoy software libre . Así que descargue el código fuente y estudíelo.

Basile Starynkevitch
fuente
55
Quiere decir que hay muchas implementaciones de lenguaje de programación sin una especificación explícita. Sí, estoy de acuerdo con eso. Pero mi punto es que un lenguaje de programación no es un software (como un compilador o un intérprete). Es algo que tiene una sintaxis y una semántica (quizás ambos están mal definidos).
Basile Starynkevitch
44
@KonradRudolph: Eso depende completamente de su definición de "formal" y "especificación" :-D Existe la Especificación del lenguaje de programación Ruby ISO / IEC 30170: 2012 , que especifica un pequeño subconjunto de la intersección de Ruby 1.8 y 1.9. Existe Ruby Spec Suite , un conjunto de ejemplos de casos límite que sirven como una especie de "especificación ejecutable". Luego, The Ruby Programming Language por David Flanagan y Yukihiro Matsumoto .
Jörg W Mittag
44
Además, la documentación de Ruby . Discusiones de problemas en el Ruby Issue Tracker . Debates sobre las listas de correo ruby-core (inglés) y ruby-dev (japonés). Expectativas de sentido común de la comunidad (por ejemplo, Array#[]O (1) en el peor de los casos, Hash#[]O (1) amortizado en el peor de los casos). Y por último pero no menos importante: el cerebro de matz.
Jörg W Mittag
66
@KonradRudolph: El punto es: incluso un lenguaje sin especificación formal y solo una sola implementación todavía se puede separar en "el lenguaje" (las reglas y restricciones abstractas) y "la implementación" (los programas de procesamiento de código de acuerdo con esas reglas y restricciones). Y la implementación aún da lugar a una especificación, aunque trivial, a saber: "lo que hace el código es la especificación". Así es como se escribieron la especificación ISO, RubySpec y los RDoc, después de todo: jugando con MRI de ingeniería inversa y / o inversa.
Jörg W Mittag
1
Me alegra que hayas traído el recolector de basura de Bohem. Recomendaría que el OP lo estudie porque es un excelente ejemplo de cuán simple puede ser la recolección de basura, incluso cuando está "atornillado" a un compilador existente.
Cort Ammon
6

Ya hay algunas buenas respuestas, pero me gustaría aclarar algunos malentendidos detrás de esta pregunta.

No existe el "lenguaje compilado de forma nativa" per se. Por ejemplo, se interpretó el mismo código Java (y luego se compiló en tiempo justo en tiempo de ejecución) en mi teléfono anterior (Java Dalvik) y se compila (antes de tiempo) en mi nuevo teléfono (ART).

La diferencia entre ejecutar código de forma nativa e interpretarla es mucho menos estricta de lo que parece ser. Ambos necesitan algunas bibliotecas de tiempo de ejecución y algún sistema operativo para funcionar (*). El código interpretado necesita un intérprete, pero el intérprete es solo una parte del tiempo de ejecución. Pero incluso esto no es estricto, ya que podría reemplazar el intérprete por un compilador (justo a tiempo). Para obtener el máximo rendimiento, es posible que desee ambos (el tiempo de ejecución Java de escritorio contiene un intérprete y dos compiladores).

No importa cómo ejecute el código, debe comportarse igual. Asignar y liberar memoria es una tarea para el tiempo de ejecución (al igual que abrir archivos, iniciar subprocesos, etc.). En tu idioma solo escribes new X()o igual. La especificación del lenguaje dice lo que debería suceder y el tiempo de ejecución lo hace.

Se asigna algo de memoria libre, se invoca al constructor, etc. Cuando no hay suficiente memoria, se llama al recolector de basura. Como ya está en el tiempo de ejecución, que es un código nativo, la existencia de un intérprete no importa en absoluto.

Realmente no hay una conexión directa entre la interpretación del código y la recolección de basura. Es solo que los lenguajes de bajo nivel como C están diseñados para la velocidad y el control detallado de todo, lo que no encaja bien con la idea de un código no nativo o un recolector de basura. Entonces solo hay una correlación.

Esto era muy cierto en los viejos tiempos, donde, por ejemplo, el intérprete de Java era muy lento y el recolector de basura bastante ineficiente. Hoy en día, las cosas son muy diferentes y hablar sobre un lenguaje interpretado ha perdido todo sentido.


(*) Al menos cuando se habla de código de propósito general, dejando de lado los cargadores de arranque y similares.

maaartinus
fuente
Tanto Ocaml como SBCL son compiladores nativos. Por lo que no son puestas en práctica del "idioma nativo compilado".
Basile Starynkevitch
@BasileStarynkevitch WAT? ¿Cómo se relacionan los nombres de algunos compiladores menos conocidos con mi respuesta? ¿No es SBCL como compilador de un lenguaje originalmente interpretado un argumento a favor de mi afirmación de que la distinción no tiene sentido?
maaartinus
Common Lisp (o cualquier otro idioma) no se interpreta ni se compila. Es un lenguaje de programación (una especificación). Su implementación puede ser un compilador, o un intérprete, o algo intermedio (por ejemplo, un intérprete de código de bytes). SBCL es una implementación compilada interactiva de Common Lisp. Ocaml también es un lenguaje de programación (con un intérprete de bytecode y un compilador nativo como implementaciones).
Basile Starynkevitch
@BasileStarynkevitch Eso es lo que estoy reclamando. 1. No existe un lenguaje interpretado o compilado (aunque C rara vez se interpreta y LISP solía compilarse raramente, pero esto realmente no importa). 2. Existen implementaciones interpretadas, compiladas y mixtas para la mayoría de los lenguajes conocidos y no hay lenguaje que impida la compilación o interpretación.
maaartinus
66
Creo que tu argumento tiene mucho sentido. El punto clave de grok es que siempre ejecuta un "programa nativo" o "nunca", como quiera verlo. Ningún exe en Windows es per se ejecutable; necesita un cargador y otras características del sistema operativo solo para comenzar y en realidad también se "interpreta" en parte. Esto se vuelve más obvio con los ejecutables .net. java myproges tan o tan poco nativo como grep myname /etc/passwdo ld.so myprog: es un ejecutable (lo que sea que eso signifique) que toma un argumento y realiza operaciones con los datos.
Peter - Restablece a Monica el
3

Los detalles varían entre implementaciones, pero generalmente es una combinación de lo siguiente:

  • Una biblioteca de tiempo de ejecución que incluye un GC. Esto manejará la asignación de memoria y tendrá algunos otros puntos de entrada, incluida una función "GC_now".
  • El compilador creará tablas para el GC para que sepa qué campos en qué tipos de datos son referencias. Esto también se hará para los marcos de la pila para cada función, de modo que el GC pueda rastrear desde la pila.
  • Si el GC es incremental (la actividad del GC se intercala con el programa) o concurrente (se ejecuta en un hilo separado), el compilador también incluirá un código de objeto especial para actualizar las estructuras de datos del GC cuando se actualicen las referencias. Los dos tienen problemas similares para la consistencia de los datos.

En el GC incremental y concurrente, el código compilado y el GC deben cooperar para mantener algunos invariantes. Por ejemplo, en un recopilador de copias, el GC funciona copiando datos en vivo del espacio A al espacio B, dejando atrás la basura. Para el siguiente ciclo, gira A y B y se repite. Por lo tanto, una regla puede ser garantizar que cada vez que el programa del usuario intente referirse a un objeto en el espacio A se detecte y el objeto se copie inmediatamente en el espacio B, donde el programa puede continuar accediendo a él. Se deja una dirección de reenvío en el espacio A para indicarle al GC que esto ha sucedido para que cualquier otra referencia al objeto se actualice a medida que se rastrea. Esto se conoce como una "barrera de lectura".

Los algoritmos de GC se han estudiado desde los años 60, y existe una extensa literatura sobre el tema. Google si quieres más información.

Paul Johnson
fuente