¿Resolvería el problema mundial de marcar y barrer con una tabla hash en la recolección de basura?

Actualizar referencias es no lo único que requiere una pausa. Todos los algoritmos estándar comúnmente agrupados en "barrido de marca" suponen que todo el gráfico de objetos permanece inalterado mientras se marca. El manejo correcto de las modificaciones (nuevos objetos creados, referencias cambiadas) requiere algoritmos alternativos bastante complicados, como el algoritmo tricolor. El término general es "recolección de basura concurrente".

Pero sí, la actualización de las referencias después de la compactación también necesita una pausa. Y sí, el uso de indirección (por ejemplo, a través de un ID de objeto persistente y una tabla hash para punteros reales) puede reducir considerablemente la pausa. Incluso podría ser posible hacer esta parte sin bloqueo si así lo desea. Sería tan difícil de resolver como cualquier concurrencia de memoria compartida de bajo nivel, pero no hay ninguna razón fundamental para que no funcione.

Sin embargo , tendría graves desventajas. Además de tomar espacio extra ( al menos dos palabras adicionales para todos los objetos), hace que cada desreferencia mucho sea más costosa. Incluso algo tan simple como obtener un atributo ahora implica una búsqueda completa de tabla hash. Estimo que el impacto en el rendimiento es mucho peor que para el seguimiento incremental.

  

Todos los problemas en informática pueden resolverse con otro nivel de direccionamiento indirecto ... excepto por el problema de demasiadas capas de direccionamiento indirecto

Su enfoque no resuelve de inmediato el problema de la recolección de basura, sino que solo lo eleva un nivel. ¡Y a qué precio! Ahora, cada acceso a la memoria pasa por otra desreferencia de puntero. No podemos almacenar en caché la ubicación del resultado, ya que podría haberse reubicado mientras tanto, siempre debemos pasar por la ID del objeto. En la mayoría de los sistemas, esta dirección indirecta no es aceptable, y se supone que detener el mundo tiene un costo total de tiempo de ejecución más bajo.

Dije que tu propuesta solo mueve el problema, no lo resuelve. El problema es alrededor de la reutilización de ID de objeto. Las ID de objeto ahora son nuestro equivalente de punteros, y solo hay una cantidad finita de direcciones. Es concebible (especialmente en un sistema de 32 bits) que durante la vida útil de su programa, se crearán más objetos INT_MAX, por ejemplo. en un bucle como

while (true) {
    Object garbage = new Object();
}

Si solo incrementamos la ID del objeto para cada objeto, nos quedaremos sin ID en algún momento. Por lo tanto, tenemos que averiguar qué ID todavía están en uso y cuáles son gratuitas para poder reclamarlas. ¿Suena familiar? Ahora estamos de vuelta en la plaza uno.

No hay ningún error en tu línea de pensamiento, acabas de describir algo muy parecido a cómo funcionaba el recolector de basura Java original

  

La máquina virtual Java original [6] y algunas máquinas virtuales Smalltalk usan punteros indirectos, llamados identificadores en [6], para referirse a objetos. Las asas permiten una fácil reubicación de los objetos durante la recolección de basura ya que, con las asas, solo hay un puntero directo a cada objeto: el que está en su asa. Todas las demás referencias al objeto son indirectas a través del controlador. En tales sistemas de memoria basados en el identificador, mientras que las direcciones de los objetos cambian a lo largo de la vida útil de los objetos y, por lo tanto, no se pueden utilizar para el hashing, las direcciones del identificador permanecen constantes.

     

Hashing de basura de espacio y tiempo eficiente Objetos recogidos

     

En la implementación actual de Sun de la Máquina Virtual Java, una referencia a   una instancia de clase es un puntero a un identificador que es en sí un par de punteros: uno a una tabla   que contiene los métodos del objeto y un puntero al objeto Clase que representa   el tipo de objeto y el otro a la memoria asignada desde Java   montón para los datos del objeto.

     

La especificación de la máquina virtual de Java (1997)

Así funciona, se ha probado y su ineficiencia llevó al desarrollo de sistemas generacionales de marca y barrido.