Cuando un recolector de basura compacta objetos en el montón, ¿cambia las referencias en la pila?

18

Esto parece una pregunta simple, pero después de leer mucho sobre el tema, todavía no he encontrado una respuesta definitiva (tal vez porque es muy simple).

Mi pregunta es esta: cuando un recolector de basura compacta objetos en el montón, ¿cómo se actualizan las referencias a esos objetos en la pila? Se me ocurren dos posibles soluciones:

  1. Revise la pila (y las referencias en el montón) y actualice la referencia para apuntar a la nueva ubicación del objeto. En una analogía con la mudanza, esto sería como enviar una carta a cualquier persona que tenga su dirección y pedirles que actualicen su libreta de direcciones con su nueva dirección.
  2. Proporcione algún tipo de tabla de consulta. Esto sería como dejar una dirección de reenvío con la oficina de correos local.

¿Los recolectores de basura utilizan predominantemente uno de estos dos métodos? ¿Algún otro método? ¿Ambos?

garbage-collection todorojo
fuente
Ver stackoverflow.com/questions/3799203/… y en.wikipedia.org/wiki/…
Gort the Robot
@StevenBurnap corrígeme si me equivoco, pero creo que el hilo al que vinculaste no tenía ninguna respuesta definitiva. Parecían estar especulando sobre esta pregunta exacta también. Puede que haya leído mal. Si respondieran a la pregunta, si no le importa, creo que sería útil resumir la respuesta aquí para futuros usuarios de SE (¡y para mí!)
todorojo
El término para lo que estás hablando es "recolector de basura en movimiento". Francamente, no sé qué tan comúnmente se usan.
Gort the Robot

Respuestas:

9

No tengo experiencia específica en esto, pero entiendo que generalmente se usa el primer método.

El recolector de basura tiene que analizar la pila de todos modos para encontrar a qué cosas del montón se hace referencia desde la pila. Una vez que decide mover algo, tiene que corregir las referencias a él de todos modos, y no hay ninguna razón para diferenciar entre el montón y la pila en ese punto.

El enfoque de la tabla de búsqueda en principio podría funcionar. Sin embargo, eso haría que todos los accesos de puntero necesiten tomar 2 pasos. Eso sería un gran impacto en el rendimiento en los tiempos de ejecución normales. Particularmente para el caso de uso de muchos objetos pequeños. (Que es un caso en el que los programas de GC de última generación generalmente superan el conteo de referencias).

btilly
fuente
3
Agregaría que creo que los GC probablemente no intenten mover las cosas en el montón a menos que tengan que hacerlo. En el mundo actual de multiprocesadores, debe ser una pesadilla de sincronización cuando necesitan actualizar todas las referencias a algo en el montón mientras se ejecuta un programa que usa esas referencias. La tabla de búsqueda simplificaría esto, pero creo que esa es la excepción en lugar de la norma, por lo que la mayoría de los GC probablemente tengan que bloquear algunas referencias, mover la memoria y luego actualizar las referencias. +1 Pregunta interesante, +1 buena respuesta.
GlenPeterson
3
@GlenPeterson Muchos GC no mueven cosas en el montón y no enfrentan este problema. Pero un GC compactador, por definición, mueve objetos vivos para desfragmentar la memoria.
btilly
@GlenPeterson es una buena observación que mover cosas en el montón es un gran dolor de sincronización, esto a menudo se pasa por alto, aunque la compactación GC tiene enormes efectos en un proceso en ejecución debido a esto. Es la razón más importante por la que se les dice a las personas que hagan todo lo posible para mantener los objetos lo más cortos posible, para evitar grandes actualizaciones de montón que causen que la compactación contenga un mutex largo. La ignorancia de la forma en que se comportan estas cosas puede conducir a lo que se conoce con cariño como modo GC Freakout.
Jimmy Hoffa
2
Tanto el Macintosh original como el sistema operativo Palm utilizaron un enfoque de tabla de búsqueda para la gestión de la memoria. Los punteros en la mesa se conocen como manijas. Un GC reubicado debe conocer el paradero de absolutamente absolutamente cada referencia a cualquier objeto que se esté moviendo; El uso de una sola tabla para tales fines simplifica mucho las cosas.
supercat