¿Cómo implementar cierres sin gc?

Question

Estoy diseñando un lenguaje. Primero, quiero decidir qué código generar. El idioma tendrá cierres léxicos y una herencia basada en prototipos similar a javascript. Pero no soy fan de gc y trato de evitar tanto como sea posible. Entonces, la pregunta: ¿existe una manera elegante de implementar cierres sin recurrir a asignar el marco de pila en el montón y dejarlo como recolector de basura?

Mis primeros pensamientos:

1. Uso recuento de referencias y la basura recogen los ciclos (en realidad no me gusta este)
2. pila Uso de espagueti (ve muy ineficiente) formando
3. límite de los cierres de algunos contextos de tal manera que, me puedo salir con una pila de direcciones de devolución y una pila de locales.

No utilizaré un lenguaje de alto nivel ni seguiré ninguna convención de llamadas, por lo que puedo destrozar la pila todo lo que quiera.

(Edit: Yo sé recuento de referencias es una forma de recolección de basura pero estoy usando GC en su significado más común)

Answer 1

Esta sería una mejor pregunta si se puede explicar lo que está tratando de evitar por no usando GC. Como estoy seguro de que sabe, la mayoría de los lenguajes que proporcionan cierres léxicos los asignan en el montón y les permiten retener referencias a enlaces de variables en el registro de activación que los creó.

La única alternativa a este enfoque que conozco es la que usa gcc para las funciones anidadas: crear un trampolín para la función y asignarlo a la pila. Pero como dice el manual de gcc:

Si intenta llamar a la función anidada a través de su dirección después de que la función contenedora haya salido, se desatará el infierno. Si intentas llamar después de que ha salido un nivel de ámbito que lo contiene, y si se refiere a algunas de las variables que ya no están dentro del alcance, puede que tengas suerte, pero no es prudente correr el riesgo. Sin embargo, si la función anidada no se refiere a nada que haya salido del alcance, debe estar seguro.

versión corta es, usted tiene tres opciones principales:

• asignar los cierres en la pila, y no permiten su uso después de que sus salidas de función que contienen.
• asignar cierres en el montón, y utilizar la recolección de basura de algún tipo.
• hacer investigación original, tal vez a partir de la región cosas que ML, Cyclone, etc. tienen.

Answer 2

Si tiene la maquinaria para una copia exacta de GC, puede asignar inicialmente en la pila y copiar al montón y actualizar punteros si descubre en la salida que se ha escapado un puntero a este marco de pila. De esa forma, solo pagará si realmente captura un cierre que incluya este marco de pila. Si esto ayuda o duele depende de la frecuencia con la que use cierres y cuánto capturen.

También puede considerar el enfoque de C++ 0x (N1968), aunque como cabría esperar de C++, consiste en contar con el programador para especificar qué se copia y a qué se hace referencia, y si se equivoca, simplemente obtener accesos no válidos

Answer 3

O simplemente no haga GC en absoluto. Puede haber situaciones en las que es mejor simplemente olvidar la fuga de memoria y dejar que el proceso se solucione después de que finalice.

Dependiendo de sus dudas sobre GC, puede tener miedo de los barridos periódicos de GC. En este caso, podría hacer un GC selectivo cuando un elemento se sale del alcance o cambia el puntero. Sin embargo, no estoy seguro de lo caro que sería.

@Allen

¿De qué sirve un cierre si no puede usarlos cuando los contienen sale de la función? Por lo que entiendo, ese es el objetivo de los cierres.

Answer 4

La especificación C++ 0x define lambdas sin recolección de elementos no utilizados. En resumen, la especificación permite un comportamiento no determinista en los casos en que el cierre lambda contiene referencias que ya no son válidas. Por ejemplo (pseudo-sintaxis):

(int)=>int create_lambda(int a) 
{ 
    return { (int x) => x + a } 
} 

create_lambda(5)(4) // undefined result 

La lambda en este ejemplo se refiere a una variable (a) que se asigna en la pila. Sin embargo, ese marco de pila se ha reventado y no es necesariamente disponible una vez que la función retorna. En este caso, probablemente funcione y devuelva 9 como resultado (asumiendo una semántica de compilación sana), pero no hay forma de garantizarlo.

Si está evitando la recolección de basura, entonces estoy asumiendo que también permite la asignación explícita de montones frente a apilamiento y (probablemente) punteros. Si ese es el caso, entonces puedes hacer como C++ y simplemente asumir que los desarrolladores que usan tu lenguaje serán lo suficientemente inteligentes como para detectar los casos problemáticos con lambdas y copiarlos al montón explícitamente (como lo harías si estuvieras devolviendo un valor sintetizado en Una función).

Answer 5

Uso recuento de referencias y la basura recogen los ciclos (en realidad no me gusta este)

Es posible diseñar su idioma para que no haya ciclos: si sólo se puede hacer nuevos objetos y no mute los viejos, y si hacer un objeto no puede hacer un ciclo, entonces los ciclos nunca aparecen. Erlang funciona esencialmente de esta manera, aunque en la práctica usa GC.

Answer 6

¿Crear múltiples pilas?

Answer 7

Podría suponer que todos los cierres se llamarán finalmente y exactamente una vez. Ahora, cuando se llame al cierre, puede hacer la limpieza en el momento del cierre.

¿Cómo planeas tratar con la devolución de objetos? Deben limpiarse en algún momento, que es exactamente el mismo problema con los cierres.

Answer 8

He leído que las últimas versiones de ML utilizan GC solamente escasamente

Answer 9

This thread podría ayudar, aunque algunas de las respuestas aquí representan respuestas ya.

Un cartel hace un buen punto:

Parece que desea recolección de basura para cierres "en la ausencia de una verdadera recolección de basura". Tenga en cuenta que los cierres se pueden usar para implementar células cons.Así que su pregunta parece tratarse de la recolección de basura "en ausencia de una verdadera recolección de basura " - hay abundante literatura relacionada. Restringir el problema a los cierres realmente no lo cambia.

Así que la respuesta es: sin, no hay manera elegante de tener cierres y sin GC real. Lo mejor que puedes hacer es piratear para restringir tus cierres a un tipo particular de cierre. Todo esto es innecesario si tienes un GC apropiado.

Por lo tanto, mi pregunta refleja algunas de las otras aquí: ¿por qué no desea implementar GC? Una simple marca + barrido o parada + copia toma alrededor de 2-300 líneas de código (Scheme), y no es realmente tan malo en términos de esfuerzo de programación. En términos de hacer que sus programas sean más lentos:

1. Puede implementar un GC más complejo que tenga un mejor rendimiento.
2. Solo piense en todos los programas de pérdida de memoria en su idioma no sufrirán.
3. La codificación con un GC disponible es una bendición. (Piensa C#, Java, Python, Perl, etc. ... vs. C++ o C).

Answer 10

Entiendo que llegué muy tarde, pero me encontré con esta pregunta por accidente.

Creo que el soporte total de cierres requiere GC, pero en algunos casos especiales la asignación de pila es segura. La determinación de estos casos especiales requiere algún análisis de escape. Le sugiero que eche un vistazo al BitC language papers, como Closure Implementation in BitC. (Aunque dudo si los documentos reflejan los planes actuales.) Los diseñadores de BitC tenían el mismo problema que tú. Decidieron implementar un modo especial no recopilable para el compilador, que niega todos los cierres que podrían escapar. Si está activado, restringirá el idioma significativamente. Sin embargo, la función aún no está implementada.

Te aconsejo que uses un colector, es la forma más elegante. También debe considerar que un recolector de basura bien construido asigna memoria más rápido que malloc. La gente de BitC realmente valora el rendimiento y todavía piensan que GC está bien incluso para la mayor parte de su sistema operativo, Coyotos. Puede migitate las desventajas por medios sencillos:

• crear sólo una cantidad mínima de basura
• dejar que el control del programador del colector
• pila optimize/uso montón por análisis de escape
• utilizar un incremental o concurrente colector
• si de alguna manera posible, dividir la pila como Erlang hace

Muchos temen los recolectores de basura becau se de sus experiencias con Java. Java tiene un coleccionista fantástico, pero las aplicaciones escritas en Java tienen problemas de rendimiento debido a la gran cantidad de basura generada. Además, un tiempo de ejecución inflado y una compilación de JIT elegante no es realmente una buena idea para las aplicaciones de escritorio debido a los tiempos de inicio y respuesta más largos.

Answer 11

¿Mejor tarde que nunca?

Puede que te interese este: Differential Execution.

Es una estructura de control poco conocida, y su uso principal es la programación de interfaces de usuario, incluidas las que pueden cambiar dinámicamente durante el uso. Es una alternativa significativa al paradigma Modelo-Vista-Controlador.

Lo menciono porque uno podría pensar que dicho código dependería en gran medida de los cierres y la recolección de basura, pero un efecto secundario de la estructura de control es que elimina ambos, al menos en el código de UI.

Answer 12

Supongo que si el proceso es muy corto, lo que significa que no puede usar mucha memoria, entonces GC no es necesario. La situación es análoga a preocuparse por el desbordamiento de pila. No anide demasiado profundamente, y no puede desbordarse; no corras demasiado tiempo, y no puedes necesitar el GC. La limpieza se convierte en una cuestión de simplemente reclamar la gran región que ha asignado previamente. Incluso un proceso más largo se puede dividir en procesos más pequeños que tienen sus propios montones preasignados. Esto funcionaría bien con los controladores de eventos, por ejemplo. No funciona bien, si está escribiendo un compilador; en ese caso, un GC seguramente no es una gran desventaja.

Answer 13

Entonces, la pregunta: ¿Existe una forma elegante de implementar cierres sin tener que asignar el marco de pila en el montón y dejarlo en el recolector de basura?

GC es la única solución para el caso general.