Pourquoi avons-nous besoin d'un tas si tout peut être fait beaucoup plus efficacement sur la pile?

Ceci est en fait quelque peu lié à la question que j'ai posée hier sur pourquoi à la fois une pile et un tas sont nécessaires dans les applications que nous utilisons aujourd'hui (et pourquoi nous ne pouvons pas simplement aller avec un tas au lieu des deux, afin d'avoir un simple & norme singulière).

Cependant, de nombreuses réponses indiquent qu'une pile est irremplaçable car elle est plusieurs centaines (ou milliers) fois plus rapide que d'essayer d'allouer / référencer le tas. Je sais qu'il y a un problème avec l'allocation de stockage dynamique si nous supprimons le tas, mais n'y a-t-il pas un moyen de contourner cela, ou peut-être un moyen d'améliorer la pile afin qu'elle puisse gérer l'allocation de mémoire dynamique?

Le problème avec les piles est que vous ne pouvez pas "libérer" de la mémoire à moins qu'elle ne soit au-dessus de la pile. Par exemple, supposons que vous ayez alloué 3 choses de tailles différentes:

a = allocate(2000000); // 2000000 bytes
b = allocate(1);
c = allocate(5000000);

La pile aurait aen bas, bau milieu et cen haut. Cela devient problématique si nous voulons libérer b:

free(b); // b is not on top! We have to wait until c is freed!

La solution de contournement consiste à déplacer toutes les données après bet à les déplacer si tel est le cas a. Cela fonctionne, mais nécessitera 5000000 copies dans ce cas - quelque chose qui sera beaucoup plus lent qu'un tas.

C'est pourquoi nous avons un tas. Alors que l'allocation peut être plus lente qu'une pile ( O(log n)vs O(1)), les tas permettent de libérer rapidement de la mémoire à un emplacement arbitraire - O(log n), par rapport à une pileO(n)

La pile est par thread, le tas est à l'échelle du processus

Si 100 threads traitent tous les éléments de travail que j'ai mis dans une file d'attente, où dois-je exactement allouer les éléments de travail de sorte que l'un des 100 threads puisse les voir?

Il existe également d'autres types de mémoire

Par exemple, fichiers mappés en mémoire, mémoire partagée, E / S mappées (mode noyau). L'argument de l'efficacité est un peu théorique dans ces situations.

Une pile est une structure LIFO (dernier entré, premier sorti), au sommet de laquelle un pointeur de référence est conservé (généralement pris en charge par le matériel). Cela dit, tout ce que vous essayez d'allouer sur la pile au lieu du tas devrait être une variable locale dans chaque fonction, en haut de cette pile. Ainsi, la principale raison contre une pile est que votre routine main () devrait préallouer toutes les structures de données que votre programme utilise (qui sont censées être présentes pendant toute la durée de votre programme) à l'avance car toutes les structures de données allouées dans les appels de fonction seront finalement supprimés lorsque ces appels de fonction reviendront et que leurs trames ou enregistrements d'activation seront extraits de la pile.

Les piles fonctionnent très bien pour les allocations de mémoire qui obéissent aux règles Last in First out (LIFO), c'est-à-dire que vous libérez la mémoire dans l'ordre inverse exact que vous lui allouez. LIFO est un modèle d'allocation de mémoire très courant, peut-être le plus courant. Mais ce n'est pas le seul modèle, ni même le seul modèle commun. Pour écrire un programme efficace qui peut s'attaquer à une grande variété de problèmes, nous devons tenir compte des schémas les moins courants, même si cela signifie une infrastructure plus complexe.

Si je peux obtenir toutes les méta pour un paragraphe: vous êtes un débutant, en tant que débutant, vous appréciez la simplicité et les règles en noir et blanc. Cependant, en tant que débutant, vous n'avez qu'un aperçu de la gamme des problèmes et des contraintes qui doivent être pris en compte par les programmes informatiques. Vous entrez dans une technologie en développement actif depuis 75 ans. Il n'y a rien de mal à demander pourquoi les choses sont comme elles sont, mais la réponse sera généralement "Ouais, nous avons essayé la méthode simple et directe il y a 50 ans, et il s'est avéré que cela ne fonctionnait pas très bien pour des classes entières. de problèmes, nous avons donc dû faire quelque chose de plus compliqué ". À mesure qu'une technologie progresse, la simplicité doit généralement céder la place à l'efficacité et à la flexibilité.

Pour un autre exemple, les fermetures. Si vous empilez de la pop, vous pouvez perdre le dossier d'activation de votre fermeture. Donc, si vous voulez que cette fonction anonyme et ses données persistent, vous devez la stocker ailleurs que dans la pile d'exécution.

Parmi de nombreuses autres raisons pour l'allocation de stockage en tas.

Si vous souhaitez transmettre l'adresse d'un objet à un programme appelant, vous ne devez pas transmettre l'adresse d'une variable de pile, car le stockage de la pile sera réutilisé et éventuellement écrasé par la prochaine fonction appelée. Vous devez obtenir le stockage requis à l'aide de malloc () pour vous assurer qu'il ne sera pas remplacé par les appels aux fonctions suivantes.

Vous pouvez transmettre des adresses d'éléments de pile de votre fonction aux fonctions que vous appelez, car vous pouvez garantir qu'elles existeront jusqu'à ce que votre programme "retourne ()". Mais dès que votre fonction revient, tout le stockage de la pile est disponible.