Est-il possible de prédire statiquement quand désallouer la mémoire --- à partir du code source uniquement?

27

La mémoire (et les verrous de ressources) sont retournés au système d'exploitation à des points déterministes pendant l'exécution d'un programme. Le flux de contrôle d'un programme suffit à lui seul à savoir où, à coup sûr, une ressource donnée peut être désallouée. Tout comme la façon dont un programmeur humain sait où écrire fclose(file)lorsque le programme en a fini avec lui.

Les GC résolvent ce problème en le résolvant directement pendant l'exécution lorsque le flux de contrôle est exécuté. Mais la véritable source de vérité sur le flux de contrôle est la source. Donc, théoriquement, il devrait être possible de déterminer où insérer les free()appels avant la compilation en analysant la source (ou AST).

Le comptage de références est un moyen évident d'implémenter cela, mais il est facile de rencontrer des situations où les pointeurs sont toujours référencés (toujours dans la portée) mais ne sont plus nécessaires. Cela convertit simplement la responsabilité de désallouer manuellement les pointeurs en une responsabilité de gérer manuellement la portée / les références à ces pointeurs.

Il semble qu'il soit possible d'écrire un programme capable de lire la source d'un programme et:

  1. prévoir toutes les permutations du flux de contrôle du programme --- avec une précision similaire à celle de l'exécution en direct du programme
  2. suivre toutes les références aux ressources allouées
  3. pour chaque référence, parcourez tout le flux de contrôle suivant afin de trouver le premier point où la référence est garantie de ne jamais être déréférencée
  4. à ce stade, insérez une instruction de désallocation à cette ligne de code source

Y a-t-il quelque chose qui le fait déjà? Je ne pense pas que Rust ou les pointeurs intelligents C ++ / RAII soient la même chose.

zelcon
la source
57
rechercher le problème d'arrêt. C'est le grand-père de la raison pour laquelle la question "Un compilateur ne peut-il pas savoir si un programme fait X?" est toujours répondu par "Pas dans le cas général."
monstre à cliquet
18
La mémoire (et les verrous de ressources) sont retournés au système d'exploitation à des points déterministes pendant l'exécution d'un programme. Non.
Euphoric
9
@ratchetfreak Merci, ce n'est jamais de savoir des choses comme ce problème d'arrêt qui me fait souhaiter d'avoir mon diplôme en science-fiction comp au lieu de la chimie.
zelcon
15
@ zelcon5, vous connaissez maintenant la chimie et le problème d'arrêt ... :)
David Arno
7
@Euphoric à moins que vous ne structuriez votre programme afin que les limites de l'utilisation d'une ressource soient très claires comme avec RAII ou try-with-resources
ratchet freak

Réponses:

23

Prenons cet exemple (artificiel):

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;
    }
}

Quand appeler gratuitement? avant malloc et assigner à resource1nous ne pouvons pas parce qu'il pourrait être copié resource2, avant d'affecter à resource2we ne peut pas parce que nous pouvons avoir obtenu 2 de l'utilisateur deux fois sans intervenir 1.

La seule façon d'être sûr est de tester resource1 et resource2 pour voir si elles ne sont pas égales dans les cas 1 et 2 et libérer l'ancienne valeur si elles ne l'étaient pas. Il s'agit essentiellement du comptage de références où vous savez qu'il n'y a que 2 références possibles.

monstre à cliquet
la source
En fait, ce n'est pas le seul moyen; l'autre manière consiste à ne permettre qu'une seule copie d'exister. Bien sûr, cela s'accompagne de ses propres problèmes.
Jack Aidley
27

RAII n'est pas automatiquement la même chose, mais il a le même effet. Il fournit une réponse simple à la question "comment savoir quand on ne peut plus y accéder?" en utilisant la portée pour couvrir la zone lorsqu'une ressource particulière est utilisée.

Vous voudrez peut-être considérer le problème similaire "comment puis-je savoir que mon programme ne subira pas d'erreur de type lors de l'exécution?". La solution à cela n'est pas de prédire tous les chemins d'exécution à travers le programme mais en utilisant un système d'annotation et d'inférence de type pour prouver qu'il ne peut pas y avoir une telle erreur. Rust est une tentative d'étendre cette propriété de preuve à l'allocation de mémoire.

Il est possible d'écrire des preuves sur le comportement du programme sans avoir à résoudre le problème d'arrêt, mais uniquement si vous utilisez des annotations de quelque sorte pour contraindre le programme. Voir aussi les preuves de sécurité (sel4 etc.)

pjc50
la source
Les commentaires ne sont pas pour une discussion approfondie; cette conversation a été déplacée vers le chat .
maple_shaft
13

Oui, cela existe à l'état sauvage. Le kit ML est un compilateur de qualité de production qui a la stratégie décrite (plus ou moins) comme l'une de ses options de gestion de mémoire disponibles. Il permet également l'utilisation d'un GC conventionnel ou l'hybridation avec un comptage de référence (vous pouvez utiliser un profileur de tas pour voir quelle stratégie produira réellement les meilleurs résultats pour votre programme).

Une rétrospective sur la gestion de la mémoire basée sur les régions est un article des auteurs originaux du kit ML qui décrit ses succès et ses échecs. La conclusion finale est que la stratégie est pratique lors de l'écriture avec l'aide d'un profileur de tas.

(C'est une bonne illustration de la raison pour laquelle vous ne devriez généralement pas vous tourner vers le problème de l'arrêt pour trouver une réponse à des questions d'ingénierie pratiques: nous ne voulons pas ou n'avons pas besoin de résoudre le cas général de la plupart des programmes réalistes.)

Leushenko
la source
5
Je pense que c'est un excellent exemple d'application correcte du problème de l'arrêt. Le problème d'arrêt nous indique que le problème est insoluble dans le cas général, vous recherchez donc des scénarios limités dans lesquels le problème est résoluble.
Taemyr
Notez que le problème devient beaucoup plus résoluble lorsque nous parlons de langages fonctionnels purs ou presque purs, sans effets secondaires comme Standard ML et Haskell
cat
10

prédire toutes les permutations du flux de contrôle du programme

Là est le problème. La quantité de permutations est si énorme (en pratique, elle est infinie) pour tout programme non trivial, que le temps et la mémoire nécessaires rendraient cela complètement impossible.

Euphorique
la source
bon point. Je suppose que les processeurs quantiques sont le seul espoir, s'il y en a du tout
zelcon
4
@ zelcon5 Haha, non. L'informatique quantique aggrave cela , pas mieux. Il ajoute des variables supplémentaires ("cachées") au programme et beaucoup plus d'incertitude. Le code QC le plus pratique que j'ai vu repose sur "quantique pour un calcul rapide, classique pour la confirmation". J'ai à peine effleuré la surface de l'informatique quantique moi-même, mais il me semble que les ordinateurs quantiques peuvent ne pas être très utiles sans les ordinateurs classiques pour les sauvegarder et vérifier leurs résultats.
Luaan
8

Le problème d'arrêt prouve que ce n'est pas possible dans tous les cas. Cependant, il est toujours possible dans un grand nombre de cas, et en fait, est fait par presque tous les compilateurs pour probablement la majorité des variables. C'est ainsi qu'un compilateur peut dire qu'il est sûr d'allouer simplement une variable sur la pile ou même un registre, au lieu d'un stockage en tas à plus long terme.

Si vous avez des fonctions pures ou une sémantique de propriété vraiment bonne, vous pouvez étendre cette analyse statique plus loin, même si cela devient beaucoup plus coûteux de le faire plus le code prend de branches.

Karl Bielefeldt
la source
Eh bien, le compilateur pense qu'il peut libérer de la mémoire; mais ce n'est peut-être pas le cas. Pensez à l'erreur courante du débutant pour renvoyer un pointeur ou une référence à une variable locale. Les cas triviaux sont capturés par le compilateur, true; les moins triviaux ne le sont pas.
Peter - Rétablir Monica
Cette erreur est commise par les programmeurs dans les langues où les programmeurs doivent gérer manuellement l'allocation de mémoire @Peter. Lorsque le compilateur gère l'allocation de mémoire, ce genre d'erreurs ne se produit pas.
Karl Bielefeldt
Eh bien, vous avez fait une déclaration très générale comprenant l'expression "presque tous les compilateurs" qui doit inclure les compilateurs C.
Peter - Rétablir Monica
2
Les compilateurs C l'utilisent pour déterminer quelles variables temporaires peuvent être allouées aux registres.
Karl Bielefeldt
4

Si un seul programmeur ou une seule équipe écrit l'ensemble du programme, il est raisonnable que des points de conception puissent être identifiés où la mémoire (et d'autres ressources) doivent être libérées. Ainsi, oui, une analyse statique de la conception peut être suffisante dans des contextes plus limités.

Cependant, lorsque vous tenez compte des DLL, API, frameworks tiers (et ajoutez des threads également), il peut être très difficile (voire impossible dans tous les cas) pour les programmeurs utilisateurs de raisonner correctement sur quelle entité possède quelle mémoire et lors de la dernière utilisation. Notre suspect habituel des langues ne documente pas suffisamment le transfert de propriété de la mémoire des objets et des tableaux, peu profonds et profonds. Si un programmeur ne peut pas raisonner là-dessus (statiquement ou dynamiquement!), Alors un compilateur ne peut probablement pas non plus. Encore une fois, cela est dû au fait que les transferts de propriété de mémoire ne sont pas capturés dans les appels de méthode ou par les interfaces, etc., donc, il n'est pas possible de prédire statiquement quand et où dans le code pour libérer de la mémoire.

Comme il s'agit d'un problème si grave, de nombreuses langues modernes choisissent la récupération de place, qui récupère automatiquement la mémoire quelque temps après la dernière référence en direct. Le GC a un coût de performance important (en particulier pour les applications en temps réel), cependant, ce n'est pas un remède universel. De plus, vous pouvez toujours avoir des fuites de mémoire en utilisant GC (par exemple une collection qui ne fait que croître). Pourtant, c'est une bonne solution pour la plupart des exercices de programmation.

Il existe des alternatives (certaines émergentes).

La langue rouille pousse RAII à l'extrême. Il fournit des constructions linguistiques qui définissent le transfert de propriété dans les méthodes de classes et d'interfaces plus en détail, par exemple les objets transférés vers ou empruntés entre un appelant et l'appelé, ou dans des objets à durée de vie plus longue. Il offre un niveau élevé de sécurité au moment de la compilation pour la gestion de la mémoire. Cependant, ce n'est pas un langage trivial à prendre en compte et n'est pas sans poser de problèmes (par exemple, je ne pense pas que la conception soit entièrement stable, certaines choses sont encore en cours d'expérimentation et donc changent).

Swift et Objective-C vont encore une autre voie, qui est le comptage de référence principalement automatique. Le comptage des références pose des problèmes avec les cycles et, par exemple, il y a des défis importants pour les programmeurs, en particulier avec les fermetures.

Erik Eidt
la source
3
Bien sûr, GC a des coûts, mais il présente également des avantages en termes de performances. Par exemple, sur .NET, l'allocation à partir du tas est presque gratuite, car elle utilise le modèle «stack-allocation» - il suffit d'incrémenter un pointeur, et c'est tout. J'ai vu des applications qui s'exécutent plus rapidement autour du GC .NET qu'elles n'ont utilisé l'allocation de mémoire manuelle, ce n'est vraiment pas clair. De même, le comptage de références est en fait assez cher (juste à des endroits différents d'un GC), et quelque chose que vous ne voulez pas payer si vous pouvez l'éviter. Si vous voulez des performances en temps réel, l'allocation statique est souvent toujours le seul moyen.
Luaan
2

Si un programme ne dépend d'aucune entrée inconnue, alors oui, cela devrait être possible (avec la mise en garde que cela peut être une tâche complexe et peut prendre du temps; mais ce serait également vrai pour le programme). Ces programmes seraient complètement résolubles au moment de la compilation; en termes C ++, ils pourraient être (presque) entièrement composés de constexprs. Des exemples simples seraient de calculer les 100 premiers chiffres de pi ou de trier un dictionnaire connu.

Peter - Rétablir Monica
la source
2

La libération de mémoire, en général, équivaut au problème d'arrêt - si vous ne pouvez pas dire statiquement si un programme va s'arrêter (statiquement), vous ne pouvez pas non plus dire s'il libérera de la mémoire (statiquement).

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

Cela dit, Rust est très gentil ... https://doc.rust-lang.org/book/ownership.html

fadedbee
la source