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

24

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?

Templier noir
la source
4
Deux extraits de votre question précédente: "l'inconvénient le plus important est qu'il a un espace limité, et donc y garder de gros objets, ou essayer de l'utiliser pour des objets à longue durée de vie, sont à la fois de mauvaises idées" et "les piles sont un moyen extrêmement efficace structure de gestion des données qui respecte les règles LIFO (dernier entré, premier sorti) ".
Cascabel
2
Votre prémisse est défectueuse - tout ne peut pas être fait beaucoup plus efficacement sur la pile. Ce n'est pas en contradiction avec les réponses que vous avez reçues - que ce qui peut être fait sur la pile peut y être fait beaucoup plus rapidement.
Ingo
... en supposant que votre matériel possède une pile ou un adressage relatif à la pile.
Ritch Melton,
3
Je suis convaincu. Je dis fais-le.
JeffO

Réponses:

25

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)

Pubby
la source
4
Lié à cela, Facebook ne supprime pas le contenu de son disque lorsque vous lui demandez de le supprimer, il supprime simplement le pointeur sur celui-ci. Évidemment, les frais généraux liés à la défragmentation ou à la recherche de l'écart équivalent sur le disque prennent trop de temps aux taux d'écriture des données, ils ajoutent donc tout à la limite supérieure du disque.
Paul Tomblin
Eh bien, les disques de Facebook peuvent être vus comme des tas. Et je suis quasiment sûr qu'ils ont une sorte de ramasse-miettes pour ces disques.
deadalnix
2
@deadalnix En fait, c'est un exemple d'utilisation d'une énorme pile au lieu du tas qui est normalement utilisé pour de plus grandes quantités de mémoire. Facebook est cependant un cas particulier. Les données sont ajoutées tellement plus rapidement qu'elles ne sont supprimées que la désallocation ne fait pas une différence significative sur le taux de croissance - vous pouvez délibérément inclure des fuites de mémoire dans la conception pour obtenir cette allocation O (1).
Tom Clarkson
7
@PaulTomblin La principale raison pour laquelle FB ne supprime pas le contenu est qu'ils puissent l'exploiter à leur profit ...
quant_dev
5
Facebook doesn't remove content from its disk when you ask it to remove it, it just removes the pointer to it- C'est essentiellement ce qui se produit lorsque vous effectuez une suppression ordinaire d'un fichier sur n'importe quel système d'exploitation.
Robert Harvey
5

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.

JBRWilkinson
la source
4

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.

Alex
la source
3
LIFO, pas FIFO.
Pubby
parfois aussi appelé FILO;)
oenone
3

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

Charles E. Grant
la source
0

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.

anon
la source
0

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.

James Anderson
la source