¿Por qué los compiladores no insertan automáticamente las desasignaciones?

63

En lenguajes como C, se espera que el programador inserte llamadas gratis. ¿Por qué el compilador no hace esto automáticamente? Los humanos lo hacen en un tiempo razonable (ignorando los errores), por lo que no es imposible.

EDITAR: Para referencia futura, aquí hay otra discusión que tiene un ejemplo interesante.

Milton Silva
fuente
125
Y eso, niños, es por eso que les enseñamos la teoría de la computabilidad. ;)
Raphael
77
Este no es un problema de computabilidad ya que los humanos tampoco pueden decidir en todos los casos. Es un problema de integridad; Las declaraciones de desasignación contienen información que, si se elimina, no puede recuperarse completamente mediante análisis a menos que ese análisis incluya información sobre el entorno de implementación y la operación esperada, que el código fuente de C no contiene.
Nat
41
No, es un problema de computabilidad. Es indecidible si un trozo de memoria dado debe ser desasignado. Para un programa fijo, no hay entrada del usuario u otra interferencia externa.
Andrej Bauer el
1
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat . Todos los comentarios que no aborden específicamente la pregunta y cómo se puede mejorar se eliminarán a la vista.
Raphael
2
@ BorisTreukhov, por favor llévelo a la sala de chat. No, no creo que Andrej esté diciendo que el análisis de escape es "imposible" (aunque para mí no es claro determinar exactamente qué significa eso en este contexto). El análisis de escape perfectamente preciso es indecidible. A todos: por favor llévelo a la sala de chat . Por favor, solo publique comentarios aquí que tengan como objetivo mejorar la pregunta; otras discusiones y comentarios deben publicarse en la sala de chat.
DW

Respuestas:

81

Porque no se puede decidir si el programa usará la memoria nuevamente. Esto significa que ningún algoritmo puede determinar correctamente cuándo llamar free()en todos los casos, lo que significa que cualquier compilador que intentó hacer esto necesariamente produciría algunos programas con pérdidas de memoria y / o algunos programas que continuaron utilizando la memoria que se había liberado. Incluso si se aseguró de que su compilador nunca hizo el segundo y permitió que el programador inserte llamadas para free()corregir esos errores, saber cuándo llamar free()a ese compilador sería aún más difícil que saber cuándo llamar free()cuando se usa un compilador que no intentó ayudar.

David Richerby
fuente
12
Tenemos una pregunta que cubre la capacidad de los humanos para resolver problemas indecidibles . No puedo darle un ejemplo de un programa que se compilaría incorrectamente porque eso depende del algoritmo que use el compilador. Pero cualquier algoritmo producirá resultados incorrectos para infinitos programas diferentes.
David Richerby
1
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
Gilles 'SO- deja de ser malvado'
2
Chicos, tómenlo para chatear . Todo lo que no se relacione directamente con la respuesta en sí y cómo se puede mejorar se eliminará.
Raphael
2
Muchas cosas que los compiladores hacen felizmente son indecidibles en general; no llegaríamos a ninguna parte en el mundo del compilador si siempre cediéramos al teorema de Rice.
Tikhon Jelvis
3
Esto es irrelevante. Si es indecidible para todos los compiladores, también es indecidible para todos los humanos. Sin embargo, esperamos que los humanos se inserten free()correctamente.
Paul Draper el
53

Como David Richerby señaló correctamente, el problema es indecidible en general. La vida del objeto es una propiedad global del programa y, en general, puede depender de los aportes al programa.

¡Incluso la recolección de basura dinámica precisa es un problema indecidible! Todos los recolectores de basura del mundo real usan la accesibilidad como una aproximación conservadora a si se necesitará o no un objeto asignado en el futuro. Es una buena aproximación, pero no obstante es una aproximación.

Pero eso solo es cierto en general. Una de las evasiones más notorias en el negocio de la informática es "es imposible en general, por lo tanto, no podemos hacer nada". Por el contrario, hay muchos casos en los que es posible avanzar.

Las implementaciones basadas en el recuento de referencias están muy cerca del "compilador que inserta las desasignaciones", por lo que es difícil notar la diferencia. El conteo automático de referencia de LLVM (utilizado en Objective-C y Swift ) es un ejemplo famoso.

Inferencia región y la recolección de basura en tiempo de compilación son áreas actuales de investigación activos. Resulta mucho más fácil en lenguajes declarativos como ML y Mercury , donde no puedes modificar un objeto después de que se haya creado.

Ahora, sobre el tema de los humanos, hay tres formas principales en que los humanos manejan las vidas de asignación manualmente:

  1. Al comprender el programa y el problema. Los humanos pueden poner objetos con vidas similares en el mismo objeto de asignación, por ejemplo. Los compiladores y los recolectores de basura deben inferir esto, pero los humanos tienen información más precisa.
  2. Mediante el uso selectivo de la contabilidad no local (por ejemplo, el recuento de referencias) u otras técnicas especiales de asignación (por ejemplo, zonas) solo cuando sea necesario. Una vez más, un humano puede saber esto donde un compilador debe inferirlo.
  3. Mal. Todos saben de los programas implementados en el mundo real que tienen fugas lentas, después de todo. O si no lo hacen, a veces los programas y las API internas deben reestructurarse en función de la vida útil de la memoria, lo que disminuye la reutilización y la modularidad.
Seudónimo
fuente
Los comentarios no son para discusión extendida. Si desea hablar sobre declarativo versus funcional, hágalo en el chat .
Gilles 'SO- deja de ser malvado'
2
Esta es, con mucho, la mejor respuesta a la pregunta (que muchas respuestas ni siquiera abordan). Podría haber agregado una referencia al trabajo pionero de Hans Boehm en GC conservador : en.wikipedia.org/wiki/Boehm_garbage_collector . Otro punto interesante es que la vida de los datos (o utilidad en un sentido extendido) se puede definir con respecto a una semántica abstracta o un modelo de ejecución. Pero el tema es realmente amplio.
babou
29

Es un problema de incompletitud, no un problema de indecidibilidad.

Si bien es cierto que la ubicación óptima de las declaraciones de desasignación es indecidible, ese no es el problema aquí. Dado que es indecidible tanto para humanos como para compiladores, es imposible seleccionar a sabiendas la ubicación óptima de desasignación, independientemente de si se trata de un proceso manual o automático. Y dado que nadie es perfecto, un compilador suficientemente avanzado debería ser capaz de superar a los humanos al adivinar ubicaciones aproximadamente óptimas. Por lo tanto, la indecidibilidad no es la razón por la que necesitamos declaraciones de asignación explícitas .

Hay casos en los que el conocimiento externo informa la colocación de la declaración de desasignación. Eliminar esas declaraciones es equivalente a eliminar parte de la lógica operativa, y pedirle a un compilador que genere automáticamente esa lógica es equivalente a pedirle que adivine lo que estás pensando.

Por ejemplo, supongamos que está escribiendo un Read-Evaluate-Print-Loop (REPL) : el usuario escribe un comando y su programa lo ejecuta. El usuario puede asignar / desasignar memoria escribiendo comandos en su REPL. Su código fuente especificará qué debe hacer el REPL para cada posible comando de usuario, incluida la desasignación cuando el usuario escribe el comando para ello.

Pero si el código fuente C no proporciona un comando explícito para la desasignación, entonces el compilador necesitaría inferir que debe realizar la deslocalización cuando el usuario ingresa el comando apropiado en el REPL. ¿Es ese comando "desasignar", "libre" o algo más? El compilador no tiene forma de saber cuál quiere que sea el comando. Incluso si programa en lógica para buscar esa palabra de comando y el REPL la encuentra, el compilador no tiene forma de saber que debe responder con desasignación a menos que se lo indique explícitamente en el código fuente.

tl; dr El problema es que el código fuente C no proporciona al compilador conocimientos externos. La indecidibilidad no es el problema porque está ahí si el proceso es manual o automatizado.

Nat
fuente
3
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat . Todos los comentarios adicionales que no aborden específicamente las deficiencias de esta respuesta y cómo se pueden solucionar se eliminarán a la vista.
Raphael
23

Actualmente, ninguna de las respuestas publicadas es totalmente correcta.

¿Por qué los compiladores no insertan automáticamente las desasignaciones?

  1. Algunos lo hacen. (Lo explicaré más tarde).

  2. Trivialmente, puede llamar free()justo antes de que salga el programa. Pero hay una necesidad implícita en su pregunta de llamar free()lo antes posible.

  3. El problema de cuándo llamar free()a cualquier programa C tan pronto como no se pueda acceder a la memoria es indecidible, es decir, para cualquier algoritmo que proporcione la respuesta en un tiempo finito, hay un caso que no cubre. Esto, y muchas otras imposibilidades de los programas arbitrarios, se pueden probar a partir del Problema de detención .

  4. Un problema indecidible no siempre puede ser resuelto en tiempo finito por ningún algoritmo, ya sea un compilador o un humano.

  5. Los humanos (intentan) escribir en un subconjunto de programas en C que pueden verificarse para la corrección de la memoria por su algoritmo (ellos mismos).

  6. Algunos idiomas logran el n. ° 1 al incorporar el n. ° 5 en el compilador. No permiten programas con usos arbitrarios de asignación de memoria, sino un subconjunto decidible de ellos. Foth y Rust son dos ejemplos de lenguajes que tienen una asignación de memoria más restrictiva que los C malloc(), que pueden (1) detectar si un programa está escrito fuera de su conjunto decidible (2) insertar automáticamente desasignaciones.

Paul Draper
fuente
1
Entiendo cómo lo hace Rust. Pero nunca escuché de un Forth que hiciera esto. ¿Puedes elaborar?
Milton Silva el
2
@MiltonSilva, Forth, al menos su implementación más básica y original, solo tiene una pila, no un montón. Hace que la asignación / desasignación mueva el puntero de la pila de llamadas, una tarea que el compilador puede hacer fácilmente. Forth fue diseñado para apuntar a hardware muy simple, y a veces la memoria no dinámica es todo lo que es viable. Obviamente no es una solución viable para programas no triviales.
Paul Draper
10

"Los humanos lo hacen, así que no es imposible" es una falacia bien conocida. No necesariamente entendemos (y mucho menos controlamos) las cosas que creamos: el dinero es un ejemplo común. Tendemos a sobreestimar (a veces dramáticamente) nuestras posibilidades de éxito en asuntos tecnológicos, especialmente cuando los factores humanos parecen estar ausentes.

El rendimiento humano en la programación de computadoras es muy pobre , y el estudio de la informática (que carece de muchos programas de educación profesional) ayuda a comprender por qué este problema no tiene una solución simple. Algún día, quizás no muy lejos, seremos reemplazados por inteligencia artificial en el trabajo. Incluso entonces, no habrá un algoritmo general que haga que la desasignación sea correcta, automáticamente, todo el tiempo.

André Souza Lemos
fuente
1
La falacia de aceptar la premisa de la falibilidad humana y, sin embargo, suponer que las máquinas de pensamiento creadas por el hombre pueden ser infalibles (es decir, mejores que los humanos) es menos conocida pero más intrigante. La única suposición a partir de la cual puede proceder la acción es que la mente humana tiene el potencial de computar perfectamente.
Comodín el
1. Nunca dije que las máquinas pensantes pudieran ser infalibles. Mejor que los humanos es lo que ya son, en muchos casos. 2. La expectativa de perfección (incluso potencial) como requisito previo para la acción es un absurdo.
André Souza Lemos
"Algún día, quizás no muy lejos, seremos reemplazados por inteligencia artificial en el trabajo". Esto, en particular, no tiene sentido. Los humanos son la fuente de la intención en el sistema. Sin humanos, no hay ningún propósito para el sistema. La "Inteligencia Artificial" podría definirse como la apariencia de una decisión inteligente en el presente por parte de las máquinas, provocada de hecho por las decisiones inteligentes de un programador o diseñador de sistemas en el pasado. Si no hay mantenimiento (que debe ser realizado por una persona), la IA (o cualquier sistema que no se haya inspeccionado y sea completamente automático) fallará.
Comodín el
La intención, tanto en humanos como en máquinas, siempre proviene del exterior .
André Souza Lemos
Completamente falso. (Y también, "afuera" no define una fuente ) . O estás afirmando que la intención como tal en realidad no existe, o estás afirmando que la intención existe pero que no proviene de ninguna parte. ¿Quizás crees que la intención puede existir independientemente del propósito? En cuyo caso, no entiende la palabra "intención". De cualquier manera, una demostración en persona pronto cambiaría su opinión sobre este tema. Después de este comentario, me iré, ya que las palabras por sí solas no pueden lograr una comprensión de la "intención", por lo que una discusión adicional aquí no tiene sentido.
Comodín el
9

La falta de administración automática de memoria es una característica del lenguaje.

Se supone que C no es una herramienta para escribir software fácilmente. Es una herramienta para hacer que la computadora haga lo que le diga. Eso incluye asignar y desasignar memoria en el momento de su elección. C es un lenguaje de bajo nivel que utiliza cuando desea controlar la computadora con precisión, o cuando desea hacer las cosas de una manera diferente a la que esperaban los diseñadores de lenguaje / biblioteca estándar.

Jouni Sirén
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
DW
2
¿Cómo es esta una respuesta a la (CS parte de la pregunta)?
Raphael
66
@Raphael La informática no significa que debamos buscar respuestas técnicas oscuras. Los compiladores hacen muchas cosas que son imposibles en el caso general. Si queremos una gestión automática de la memoria, podemos implementarla de muchas maneras. C no lo hace, porque se supone que no debe hacerlo.
Jouni Sirén
9

El problema es principalmente un artefacto histórico, no una imposibilidad de implementación.

La forma en que la mayoría de los compiladores de C construyen código es para que el compilador solo vea cada archivo fuente a la vez; nunca ve todo el programa a la vez. Cuando un archivo fuente llama a una función desde otro archivo fuente o una biblioteca, todo lo que ve el compilador es el archivo de encabezado con el tipo de retorno de la función, no el código real de la función. Esto significa que cuando hay una función que devuelve un puntero, el compilador no tiene forma de saber si la memoria a la que apunta el puntero necesita liberarse o no. La información para decidir que no se muestra al compilador en ese momento. Un programador humano, por otro lado, es libre de buscar el código fuente de la función o la documentación para averiguar qué debe hacerse con el puntero.

Si observa lenguajes de bajo nivel más modernos como C ++ 11 o Rust, encontrará que en su mayoría resolvieron el problema al hacer explícita la propiedad de la memoria en el tipo de puntero. En C ++, usaría un en unique_ptr<T>lugar de un plano T*para mantener la memoria y unique_ptr<T>se asegura de que la memoria se libere cuando el objeto llegue al final del alcance, a diferencia del plano T*. El programador puede pasar la memoria de uno unique_ptr<T>a otro, pero solo puede haber uno unique_ptr<T>apuntando a la memoria. Por lo tanto, siempre está claro quién posee la memoria y cuándo debe liberarse.

C ++, por razones de compatibilidad con versiones anteriores, todavía permite la gestión de memoria manual de estilo antiguo y, por lo tanto, la creación de errores o formas de eludir la protección de a unique_ptr<T>. Rust es aún más estricto ya que impone las reglas de propiedad de la memoria a través de errores del compilador.

En cuanto a la indecidibilidad, el problema de detención y similares, sí, si se adhiere a la semántica en C, no es posible decidir para todos los programas cuándo se debe liberar la memoria. Sin embargo, para la mayoría de los programas reales, no para ejercicios académicos o software con errores, sería absolutamente posible decidir cuándo liberar y cuándo no. Después de todo, esa es la única razón por la cual los humanos pueden decidir cuándo liberarse o no en primer lugar.

Grumbel
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
Raphael
6

Otras respuestas se han centrado en si es posible recolectar basura, algunos detalles de cómo se hace y algunos de los problemas.

Sin embargo, un problema que aún no se ha cubierto es la demora inevitable en la recolección de basura. En C, cuando un programador llama a free (), esa memoria está inmediatamente disponible para su reutilización. (¡Al menos en teoría!) De modo que un programador puede liberar su estructura de 100 MB, asignar otra estructura de 100 MB un milisegundo más tarde y esperar que el uso general de la memoria siga siendo el mismo.

Esto no es cierto con la recolección de basura. Los sistemas recolectados de basura tienen algún retraso en devolver la memoria no utilizada al montón, y esto puede ser significativo. Si su estructura de 100 MB se sale del alcance, y un milisegundo después su programa configura otra estructura de 100 MB, puede esperar razonablemente que su sistema use 200 MB por un período corto. Ese "período corto" puede ser milisegundos o segundos dependiendo del sistema, pero todavía hay un retraso.

Si está ejecutando en una PC con gigas de RAM y memoria virtual, por supuesto, probablemente nunca lo note. Sin embargo, si está ejecutando en un sistema con recursos más limitados (por ejemplo, un sistema integrado o un teléfono), esto es algo que debe tomar en serio. Esto no es solo teórico: personalmente he visto que esto crea problemas (como al bloquear el tipo de problemas del dispositivo) cuando se trabaja en un sistema WinCE utilizando .NET Compact Framework y se desarrolla en C #.

Graham
fuente
En teoría, podría ejecutar un GC antes de cada asignación.
adrianN
44
@adrianN Pero en la práctica esto no se hace porque sería mental. El punto de Graham sigue en pie: los GC siempre incurren en una sobrecarga sustancial, ya sea en términos de tiempo de ejecución o en términos de memoria excedente requerida. Puede ajustar este equilibrio hacia cualquier extremo, pero fundamentalmente no puede eliminar la sobrecarga.
Konrad Rudolph el
El "retraso" en cuando la memoria se libera es más un problema en un sistema de memoria virtual que en un sistema con recursos limitados. En el primer caso, puede ser mejor que un programa use 100 MB que 200 MB incluso si el sistema tiene 200 MB disponibles , pero en el último caso no habrá ningún beneficio al ejecutar el GC antes de lo necesario a menos que los retrasos sean más aceptables durante algunos partes del código que durante otras.
supercat
No veo cómo esto intenta responder la (parte CS de la) pregunta.
Raphael
1
@Raphael He explicado un problema bien reconocido con el principio de recolección de basura, que se enseña (o debería) en CS como una de sus desventajas básicas. Incluso he dado mi experiencia personal de haber visto esto en la práctica, para demostrar que no es un problema puramente teórico. Si no entendió algo sobre esto, me alegra hablar con usted para mejorar su conocimiento del tema.
Graham
4

La pregunta supone que una desasignación es algo que el programador debe deducir de otras partes del código fuente. No es. "En este punto del programa, la referencia de memoria FOO ya no es útil" es información que solo el programador conoce hasta que se codifica en (en lenguajes de procedimiento) una declaración de desasignación.

Teóricamente no es diferente de ninguna otra línea de código. ¿Por qué los compiladores no insertan automáticamente "En este punto del programa, verifique el registro BAR para entrada" o "si la llamada de función devuelve un valor distinto de cero, salga de la subrutina actual" ? Desde el punto de vista del compilador, la razón es la "incompletitud", como se muestra en esta respuesta . Pero cualquier programa sufre de incompletitud cuando el programador no le ha contado todo lo que sabe.

En la vida real, las desasignaciones son trabajo duro o repetitivo; nuestros cerebros los llenan automáticamente y se quejan al respecto, y el sentimiento "el compilador podría hacerlo igual o mejor" es cierto. En teoría, sin embargo, ese no es el caso, aunque afortunadamente otros lenguajes nos dan más opciones de teoría.

Travis Wilson
fuente
44
"'En este punto del programa, la referencia de memoria FOO ya no es útil' es información que solo el programador conoce", eso es claramente incorrecto. a) Para muchos FOO, es trivial resolver esto, por ejemplo, variables locales con semántica de valores. b) Sugieres que el programador sepa esto, siempre, lo cual es claramente una suposición demasiado optimista; si fuera cierto, no tendríamos errores graves debido al mal manejo de la memoria, es un software crítico para la seguridad. Lo cual, por desgracia, hacemos.
Raphael
Sólo estoy sugiriendo que el lenguaje fue diseñado para los casos en que el programador no sabe FOO ya no es útil. Estoy de acuerdo, claramente, esto no suele ser cierto, y es por eso que necesitamos tener un análisis estático y / o recolección de basura. Lo cual, hurra, lo hacemos. Pero la pregunta del OP es, ¿cuándo esas cosas no son tan valiosas como los deallocs codificados a mano?
Travis Wilson
4

Qué se hace: hay recolección de basura, y hay compiladores que usan el conteo de referencias (Objective-C, Swift). Aquellos que hacen recuento de referencias necesitan ayuda del programador al evitar ciclos de referencia fuertes.

La verdadera respuesta al "por qué" es que los escritores de compiladores no han descubierto una forma que sea lo suficientemente buena y rápida como para poder utilizarla en un compilador. Dado que los escritores de compiladores suelen ser bastante inteligentes, se puede concluir que es muy, muy difícil encontrar una forma lo suficientemente buena y rápida.

Una de las razones por las que es muy, muy difícil es, por supuesto, que es indecidible. En informática, cuando hablamos de "capacidad de decisión" nos referimos a "tomar la decisión correcta". Por supuesto, los programadores humanos pueden decidir fácilmente dónde desasignar la memoria, porque no se limitan a las decisiones correctas . Y a menudo toman decisiones que están mal.

gnasher729
fuente
No veo una contribución aquí.
babou
3

En lenguajes como C, se espera que el programador inserte llamadas gratis. ¿Por qué el compilador no hace esto automáticamente?

Porque la vida útil de un bloque de memoria es decisión del programador, no del compilador.

Eso es. Este es el diseño de C. El compilador no puede saber cuál era la intención de asignar un bloque de memoria. Los humanos pueden hacerlo, porque conocen el propósito de cada bloque de memoria y cuándo se cumple este propósito para que pueda liberarse. Eso es parte del diseño del programa que se está escribiendo.

C es un lenguaje de bajo nivel, por lo que las instancias de pasar un bloque de su memoria a otro proceso o incluso a otro procesador son bastante frecuentes. En casos extremos, un programador puede asignar intencionalmente una porción de memoria y nunca volver a usarla solo para ejercer presión sobre otras partes del sistema. El compilador no tiene forma de saber si el bloque aún es necesario.

Agent_L
fuente
-1

En lenguajes como C, se espera que el programador inserte llamadas gratis. ¿Por qué el compilador no hace esto automáticamente?

En C y en muchos otros lenguajes, existe una posibilidad de hacer que el compilador haga el equivalente de esto en aquellos casos en los que está claro en el momento de la compilación cuándo debe hacerse: uso de variables de duración automática (es decir, variables locales ordinarias) . El compilador es responsable de organizar el espacio suficiente para tales variables y de liberar ese espacio cuando finaliza su vida útil (bien definida).

Dado que las matrices de longitud variable son una característica de C desde C99, los objetos de duración automática cumplen, en principio, sustancialmente todas las funciones en C que hacen los objetos asignados dinámicamente de duración computable. En la práctica, por supuesto, las implementaciones de C pueden establecer límites prácticos significativos en el uso de VLA, es decir, su tamaño puede estar limitado como resultado de su asignación en la pila, pero esto es una consideración de implementación, no una consideración de diseño de lenguaje.

Aquellos objetos cuyo uso previsto impide darles una duración automática son precisamente aquellos cuya vida útil no puede determinarse en tiempo de compilación.

PellMel
fuente