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

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.

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.

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.)

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.)

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.

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.

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.

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.

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