¿Es posible predecir estáticamente cuándo desasignar memoria --- solo del código fuente?

27

La memoria (y los bloqueos de recursos) se devuelven al sistema operativo en puntos deterministas durante la ejecución de un programa. El flujo de control de un programa por sí solo es suficiente para saber dónde, con seguridad, se puede desasignar un recurso dado. Al igual que un programador humano sabe dónde escribir fclose(file)cuando el programa termina con él.

Los GC resuelven esto resolviéndolo directamente durante el tiempo de ejecución cuando se ejecuta el flujo de control. Pero la verdadera fuente de verdad sobre el flujo de control es la fuente. Entonces, en teoría, debería ser posible determinar dónde insertar las free()llamadas antes de la compilación analizando la fuente (o AST).

El conteo de referencias es una forma obvia de implementar esto, pero es fácil encontrar situaciones en las que todavía se hace referencia a los punteros (todavía en el alcance) pero ya no son necesarios. Esto solo convierte la responsabilidad de desasignar manualmente punteros en una responsabilidad de administrar manualmente el alcance / referencias a esos punteros.

Parece que es posible escribir un programa que pueda leer la fuente de un programa y:

  1. predecir todas las permutaciones del flujo de control del programa --- con una precisión similar a la de ver la ejecución en vivo del programa
  2. rastrear todas las referencias a los recursos asignados
  3. para cada referencia, recorra todo el flujo de control posterior para encontrar el primer punto en el que se garantiza que la referencia nunca se desreferenciará
  4. en ese punto, inserte una declaración de desasignación en esa línea de código fuente

¿Hay algo por ahí que ya haga esto? No creo que los punteros inteligentes Rust o C ++ / RAII sean lo mismo.

zelcon
fuente
57
busca el problema de detención. Es el abuelo de por qué la pregunta "¿No puede un compilador averiguar si un programa hace X?" siempre se responde con "No en el caso general".
monstruo de trinquete
18
La memoria (y los bloqueos de recursos) se devuelven al sistema operativo en puntos deterministas durante la ejecución de un programa. No.
Eufórico
99
@ratchetfreak Gracias, nunca es saber cosas como este problema de detención lo que me hace desear obtener mi título en ciencia ficción en lugar de química.
zelcon
15
@ zelcon5, ahora sabes acerca de la química y el problema de detención ... :)
David Arno
77
@Euphoric a menos que la estructura de su programa por lo que los límites de cuando se utiliza un recurso es muy claro que con RAII o tratar -con-recursos
trinquete monstruo

Respuestas:

23

Tome este ejemplo (artificial):

void* resource1;
void* resource2;

while(true){

    int input = getInputFromUser();

    switch(input){
        case 1: resource1 = malloc(500); break;
        case 2: resource2 = resource1; break;
        case 3: useResource(resource1); useResource(resource2); break;
    }
}

¿Cuándo debería llamarse gratis? antes de malloc y asignar a resource1no podemos porque podría copiarse resource2, antes de asignar a resource2no podemos porque podríamos haber recibido 2 del usuario dos veces sin una intervención 1.

La única forma de asegurarse es probar resource1 y resource2 para ver si no son iguales en los casos 1 y 2 y liberar el valor anterior si no lo fueran. Esto es esencialmente un recuento de referencias donde sabe que solo hay 2 referencias posibles.

monstruo de trinquete
fuente
En realidad esa no es la única forma; la otra forma es permitir que solo exista una copia. Esto, por supuesto, viene con sus propios problemas.
Jack Aidley
27

RAII no es automáticamente lo mismo, pero tiene el mismo efecto. Proporciona una respuesta fácil a la pregunta "¿cómo sabes cuándo ya no se puede acceder a esto?" mediante el uso de alcance para cubrir el área cuando se utiliza un recurso en particular.

Es posible que desee considerar el problema similar "¿cómo puedo saber que mi programa no sufrirá un error de tipo en tiempo de ejecución?". La solución a esto no es predecir todas las rutas de ejecución a través del programa, sino mediante el uso de un sistema de anotación de tipo e inferencia para demostrar que no puede haber tal error. Rust es un intento de extender esta propiedad de prueba a la asignación de memoria.

Es posible escribir pruebas sobre el comportamiento del programa sin tener que resolver el problema de detención, pero solo si usa anotaciones de algún tipo para restringir el programa. Ver también pruebas de seguridad (sel4 etc.)

pjc50
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
maple_shaft
13

Sí, esto existe en la naturaleza. ML Kit es un compilador de calidad de producción que tiene la estrategia descrita (más o menos) como una de sus opciones de administración de memoria disponibles. También permite el uso de un GC convencional o hibridación con recuento de referencias (puede usar un generador de perfiles de montón para ver qué estrategia realmente producirá los mejores resultados para su programa).

Una retrospectiva sobre la gestión de memoria basada en la región es un artículo de los autores originales del ML Kit que explica sus éxitos y fracasos. La conclusión final es que la estrategia es práctica cuando se escribe con la ayuda de un perfilador de montón.

(Esta es una buena ilustración de por qué generalmente no debería buscar en el Problema de detención una respuesta a preguntas prácticas de ingeniería: no queremos o necesitamos resolver el caso general de la mayoría de los programas realistas).

Leushenko
fuente
55
Creo que este es un excelente ejemplo de la aplicación adecuada del problema de detención. El problema de detención nos dice que el problema no se puede resolver en el caso general, por lo que debe buscar escenarios limitados en los que el problema sea solucionable.
Taemyr
Tenga en cuenta que el problema se vuelve mucho más solucionable cuando hablamos de lenguajes puros o casi puros, funcionales y sin efectos secundarios como Standard ML y Haskell
cat
10

predecir todas las permutaciones del flujo de control del programa

Aquí es donde radica el problema. La cantidad de permutaciones es tan grande (en la práctica es infinita) para cualquier programa no trivial, que el tiempo y la memoria necesarios lo harían completamente impracticable.

Eufórico
fuente
buen punto. Supongo que los procesadores cuánticos son la única esperanza, si es que hay alguna
zelcon
44
@ zelcon5 Jaja, no. La computación cuántica hace que esta peor , no mejor. Agrega variables adicionales ("ocultas") al programa y mucha más incertidumbre. El código de control de calidad más práctico que he visto se basa en "quantum para cómputo rápido, clásico para confirmación". Apenas he arañado la superficie de la computación cuántica, pero me parece que las computadoras cuánticas pueden no ser muy útiles sin las computadoras clásicas para respaldarlas y verificar sus resultados.
Luaan
8

El problema de detención demuestra que esto no es posible en todos los casos. Sin embargo, todavía es posible en muchos casos, y de hecho, lo hacen casi todos los compiladores para probablemente la mayoría de las variables. Así es como un compilador puede decir que es seguro simplemente asignar una variable en la pila o incluso un registro, en lugar de un almacenamiento dinámico a largo plazo.

Si tiene funciones puras o una semántica de propiedad realmente buena, puede ampliar ese análisis estático aún más, aunque se vuelve prohibitivamente más costoso hacerlo mientras más ramas tome su código.

Karl Bielefeldt
fuente
Bueno, el compilador cree que puede liberar la memoria; pero puede que no sea así. Piense en el error común del principiante al devolver un puntero o una referencia a una variable local. El compilador capta los casos triviales, cierto; los menos triviales no lo son.
Peter - Restablece a Monica el
Ese error es hecho por los programadores en los idiomas en que los programadores deben gestionar manualmente la asignación de memoria @Peter. Cuando el compilador maneja la asignación de memoria, ese tipo de errores no ocurren.
Karl Bielefeldt
Bueno, usted hizo una declaración muy general que incluye la frase "casi todos los compiladores" que debe incluir compiladores C.
Peter - Restablece a Monica
2
Los compiladores de C lo usan para determinar qué variables temporales se pueden asignar a los registros.
Karl Bielefeldt
4

Si un solo programador o equipo escribe todo el programa, es razonable que se puedan identificar los puntos de diseño donde se debe liberar la memoria (y otros recursos). Por lo tanto, sí, el análisis estático del diseño puede ser suficiente en contextos más limitados.

Sin embargo, cuando tiene en cuenta las DLL, API, marcos de trabajo de terceros (y también agrega hilos), puede ser muy difícil (es decir, imposible en todos los casos) para los programadores que usan razonar correctamente sobre qué entidad posee qué memoria y cuando el último uso es. Nuestro sospechoso habitual de idiomas no documenta suficientemente la transferencia de propiedad de memoria de objetos y matrices, superficial y profunda. Si un programador no puede razonar sobre eso (¡estática o dinámicamente!), Entonces un compilador probablemente tampoco. Nuevamente, esto se debe al hecho de que las transferencias de propiedad de memoria no se capturan en llamadas a métodos o por interfaces, etc., por lo tanto, no, no es posible predecir estáticamente cuándo o dónde en el código liberar memoria.

Como este es un problema tan grave, muchos idiomas modernos eligen la recolección de basura, que recupera automáticamente la memoria en algún momento después de la última referencia en vivo. Sin embargo, GC tiene un costo de rendimiento significativo (especialmente para aplicaciones en tiempo real), por lo que no es una cura universal para todos. Además, aún puede tener pérdidas de memoria con GC (por ejemplo, una colección que solo crece). Aún así, esta es una buena solución para la mayoría de los ejercicios de programación.

Hay algunas alternativas (algunas emergentes).

El lenguaje Rust lleva a RAII a un extremo. Proporciona construcciones lingüísticas que definen la transferencia de propiedad en métodos de clases e interfaces con más detalle, por ejemplo, objetos transferidos a prestados entre una persona que llama y una persona que llama, o en objetos de mayor duración. Proporciona un alto nivel de seguridad en el tiempo de compilación para la gestión de la memoria. Sin embargo, no es un lenguaje trivial para aprender, y tampoco está exento de problemas (por ejemplo, no creo que el diseño sea completamente estable, ciertas cosas todavía se están experimentando y, por lo tanto, están cambiando).

Swift y Objective-C siguen otra ruta, que es el conteo de referencias en su mayoría automáticas. El recuento de referencias entra en problemas con los ciclos y existen desafíos importantes para los programadores, por ejemplo, especialmente con los cierres.

Erik Eidt
fuente
3
Claro, GC tiene costos, pero también tiene beneficios de rendimiento. Por ejemplo, en .NET, la asignación desde el montón es casi gratuita, porque utiliza el patrón de "asignación de pila": simplemente incremente un puntero, y eso es todo. He visto aplicaciones que se ejecutan más rápidamente reescritas en el .NET GC de lo que han estado utilizando la asignación manual de memoria, realmente no es claro. Del mismo modo, el recuento de referencias es realmente bastante costoso (solo en diferentes lugares de un GC), y es algo que no desea pagar si puede evitarlo. Si desea un rendimiento en tiempo real, la asignación estática suele ser la única forma.
Luaan
2

Si un programa no depende de ninguna entrada desconocida, entonces sí, debería ser posible (con la advertencia de que puede ser una tarea compleja y puede llevar mucho tiempo; pero eso también sería cierto para el programa). Dichos programas serían completamente solucionables en tiempo de compilación; en términos de C ++, podrían estar (casi) completamente compuestos de constexprs. Ejemplos simples serían calcular los primeros 100 dígitos de pi o clasificar un diccionario conocido.

Peter - Restablece a Monica
fuente
2

La liberación de memoria, en general, es equivalente al problema de detención: si no puede determinar estáticamente si un programa se detendrá (estáticamente), tampoco puede determinar si liberará memoria (estáticamente).

function foo(int a) {
    void *p = malloc(1);
    ... do something which may, or may not, halt ...
    free(p);
}

https://en.wikipedia.org/wiki/Halting_problem

Dicho esto, Rust es muy agradable ... https://doc.rust-lang.org/book/ownership.html

fadedbee
fuente