Pourrait-il être plus efficace pour les systèmes en général de supprimer les piles et d'utiliser simplement Heap pour la gestion de la mémoire?

14

Il me semble que tout ce qui peut être fait avec une pile peut être fait avec le tas, mais tout ce qui peut être fait avec le tas ne peut pas être fait avec la pile. Est-ce exact? Alors pour des raisons de simplicité, et même si nous perdons un peu de performances avec certaines charges de travail, ne pourrait-il pas être préférable de ne choisir qu'une seule norme (c'est-à-dire le tas)?

Pensez au compromis entre modularité et performances. Je sais que ce n'est pas la meilleure façon de décrire ce scénario, mais en général, il semble que la simplicité de compréhension et de conception pourrait être une meilleure option même s'il existe un potentiel pour de meilleures performances.

Templier noir
la source
1
En C et C ++, vous devez désallouer explicitement la mémoire allouée sur le tas. Ce n'est pas plus simple.
user16764
J'ai utilisé une implémentation C # où le profilage a révélé que les objets de pile étaient alloués dans une zone semblable à un tas avec une terrible collecte de déchets. Ma solution? Déplacez tout ce qui est possible (par exemple les variables de boucle, les variables temporaires, etc.) vers la mémoire de tas persistante. Faites en sorte que le programme consomme 10 fois plus de RAM et fonctionne à 10 fois la vitesse.
imallett
@IanMallett: Je ne comprends pas votre explication du problème et de la solution. Avez-vous un lien avec plus d'informations quelque part? En général, je trouve que l'allocation basée sur la pile est plus rapide.
Frank Hileman
@FrankHileman, le problème de base était le suivant: l'implémentation de C # que j'utilisais avait une vitesse de collecte des ordures extrêmement médiocre. La "solution" était de rendre toutes les variables persistantes de sorte qu'au moment de l'exécution, aucune opération de mémoire ne se produise. Il y a quelque temps, j'ai écrit un article d'opinion sur le développement C # / XNA en général qui traite également d'une partie du contexte.
imallett
@IanMallett: merci. En tant qu'ancien développeur C / C ++ qui utilise principalement C # ces jours-ci, mon expérience a été très différente. Je trouve que les bibliothèques sont le plus gros problème. Il semble que la plate-forme XBox360 ait été à moitié cuite pour les développeurs .net. Habituellement, lorsque j'ai des problèmes de GC, je passe au pooling. Ça aide.
Frank Hileman

Réponses:

30

Les tas sont mauvais pour l'allocation et la désallocation rapides de la mémoire. Si vous souhaitez récupérer de très petites quantités de mémoire pour une durée limitée, un tas n'est pas votre meilleur choix. Une pile, avec son algorithme d'allocation / désallocation super simple, excelle naturellement dans ce domaine (encore plus si elle est intégrée au matériel), c'est pourquoi les gens l'utilisent pour des choses comme passer des arguments aux fonctions et stocker des variables locales - le plus L'inconvénient important est qu'il a un espace limité, et donc garder de gros objets dedans, ou essayer de l'utiliser pour des objets à longue durée de vie, sont deux mauvaises idées.

Se débarrasser complètement de la pile dans le but de simplifier un langage de programmation est la mauvaise façon OMI - une meilleure approche serait de résumer les différences, laissez le compilateur déterminer le type de stockage à utiliser, tandis que le programmeur met en place plus haut- des constructions de niveau plus proches de la façon dont les humains pensent - et en fait, des langages de haut niveau comme C #, Java, Python etc. font exactement cela. Ils offrent une syntaxe presque identique pour les objets alloués en tas et les primitives allouées par pile («types de référence» vs «types de valeur» dans le jargon .NET), soit entièrement transparents, soit avec quelques différences fonctionnelles que vous devez comprendre pour utiliser le langage correctement (mais vous n'avez pas réellement besoin de savoir comment une pile et un tas fonctionnent en interne).

tdammers
la source
2
WOW C'ÉTAIT BON :) Vraiment concis et instructif pour un débutant!
Dark Templar
1
Sur de nombreux processeurs, la pile est gérée dans le matériel, ce qui est un problème en dehors du langage mais il joue un grand rôle au moment de l'exécution.
Patrick Hughes,
@Patrick Hughes: Oui, mais le tas se trouve également dans le matériel, n'est-ce pas?
Dark Templar
@Dark Ce que Patrick veut probablement dire, c'est que les architectures comme x86 ont des registres spéciaux pour gérer la pile et des instructions spéciales pour mettre ou supprimer quelque chose sur / de la pile. Cela le rend assez rapide.
FUZxxl
3
@Donal Fellows: Tout à fait vrai. Mais le fait est que les piles et les tas ont leurs points forts et leurs points faibles, et les utiliser en conséquence donnera le code le plus efficace.
tdammers
8

Autrement dit, une pile n'est pas un peu de performance. C'est des centaines ou des milliers de fois plus rapide que le tas. De plus, la plupart des machines modernes prennent en charge le matériel pour la pile (comme x86) et cette fonctionnalité matérielle, par exemple pour la pile d'appels, ne peut pas être supprimée.

DeadMG
la source
Que voulez-vous dire lorsque vous dites que les machines modernes ont un support matériel pour la pile? La pile elle-même est déjà dans le matériel, n'est-ce pas?
Dark Templar
1
x86 a des registres spéciaux et des instructions pour gérer la pile. x86 ne prend pas en charge les tas - ces choses sont créées par le système d'exploitation.
Pubby
8

Non

La zone de pile en C ++ est incroyablement rapide en comparaison. Je suppose qu'aucun développeur C ++ expérimenté ne serait disposé à désactiver cette fonctionnalité.

Avec C ++, vous avez le choix et vous avez le contrôle. Les concepteurs n'étaient pas particulièrement enclins à introduire des fonctionnalités qui ajoutaient un temps ou un espace d'exécution important.

Exercer ce choix

Si vous souhaitez créer une bibliothèque ou un programme qui nécessite que chaque objet soit alloué dynamiquement, vous pouvez le faire avec C ++. Il s'exécuterait relativement lentement, mais vous pourriez alors avoir cette «modularité». Pour le reste d'entre nous, la modularité est toujours facultative, introduisez-la au besoin car les deux sont nécessaires pour des implémentations bonnes / rapides.

Alternatives

Il existe d'autres langages qui nécessitent que le stockage de chaque objet soit créé sur le tas; il est assez lent, de sorte qu'il compromet les conceptions (programmes du monde réel) d'une manière pire que d'avoir à apprendre les deux (OMI).

Les deux sont importants, et C ++ vous donne la puissance à utiliser efficacement pour chaque scénario donné. Cela dit, le langage C ++ peut ne pas être idéal pour votre conception, si ces facteurs dans votre OP sont importants pour vous (par exemple, lisez sur les langages de niveau supérieur).

Justin
la source
Le tas a en fait la même vitesse que la pile, mais n'a pas le support matériel spécialisé pour l'allocation. D'un autre côté, il existe des moyens d'accélérer beaucoup les tas (sous réserve d'un certain nombre de conditions qui en font des techniques réservées aux experts).
Donal Fellows
@DonalFellows: la prise en charge matérielle des piles n'est pas pertinente. Ce qui est important, c'est de savoir que chaque fois que quelque chose est publié, on peut libérer tout ce qui est alloué après. Certains langages de programmation n'ont pas de tas qui peuvent libérer indépendamment des objets, mais ont seulement une méthode "libérer tout alloué après".
supercat
6

Alors pour des raisons de simplicité, et même si nous perdons un peu de performances avec certaines charges de travail, ne pourrait-il pas être préférable de ne choisir qu'une seule norme (c'est-à-dire le tas)?

En fait, la performance est probablement considérable!

Comme d'autres l'ont souligné, les piles sont une structure extrêmement efficace pour gérer les données qui obéissent aux règles LIFO (dernier entré premier sorti). L'allocation / libération de mémoire sur la pile est généralement juste une modification d'un registre sur le CPU. La modification d'un registre est presque toujours l'une des opérations les plus rapides qu'un processeur puisse effectuer.

Le tas est généralement une structure de données assez complexe et l'allocation / libération de mémoire prendra de nombreuses instructions pour effectuer toute la comptabilité associée. Pire encore, dans les implémentations courantes, chaque appel à travailler avec le tas peut entraîner un appel au système d'exploitation. Les appels du système d'exploitation prennent beaucoup de temps! Le programme doit généralement passer du mode utilisateur au mode noyau, et chaque fois que cela se produit, le système d'exploitation peut décider que d'autres programmes ont des besoins plus urgents et que votre programme devra attendre.

Charles E. Grant
la source
5

Simula a utilisé le tas pour tout. Tout mettre sur le tas induit toujours un niveau d'indirection supplémentaire pour les variables locales, et cela met une pression supplémentaire sur le garbage collector (vous devez tenir compte du fait que les garbage collector étaient vraiment aspirés à l'époque). C'est en partie pourquoi Bjarne a inventé le C ++.

fredoverflow
la source
Donc, en gros, C ++ utilise uniquement le tas?
Dark Templar
2
@Dark: Quoi? Non. Le manque de stack dans Simula a été une inspiration pour le faire mieux.
fredoverflow
Ah je vois ce que tu veux dire maintenant! Merci +1 :)
Dark Templar
3

Les piles sont extrêmement efficaces pour les données LIFO, telles que les métadonnées associées aux appels de fonction, par exemple. La pile exploite également les caractéristiques de conception inhérentes au processeur. Étant donné que les performances à ce niveau sont fondamentales pour à peu près tout le reste dans un processus, prendre ce "petit" coup à ce niveau se propagera très largement. De plus, la mémoire de tas est déplaçable par le système d'exploitation, ce qui serait mortel pour les piles. Bien qu'une pile puisse être implémentée dans le tas, elle nécessite des frais généraux qui affecteront littéralement chaque élément d'un processus au niveau le plus granulaire.

kylben
la source
2

«efficace» en termes d'écriture de code peut-être, mais certainement pas en termes d'efficacité de votre logiciel. Les allocations de pile sont essentiellement gratuites (il suffit de quelques instructions machine pour déplacer le pointeur de pile et réserver de l'espace sur la pile pour les variables locales).

Étant donné que l'allocation de pile ne prend presque pas de temps, une allocation, même sur un tas très efficace, sera 100k (sinon 1M +) de fois plus lente.

Imaginez maintenant combien de variables locales et d'autres structures de données une application typique utilise. Chaque petit «i» que vous utilisez comme compteur de boucle est alloué un million de fois plus lentement.

Bien sûr, si le matériel est assez rapide, vous pouvez écrire une application qui utilise uniquement le tas. Mais imaginez maintenant quel type d'application vous pourriez écrire si vous profitiez du tas et utilisiez le même matériel.

DXM
la source
Lorsque vous dites "imaginez combien de variables locales et d'autres structures de données une application type utilise", à quelles autres structures de données faites-vous spécifiquement référence?
Dark Templar
1
Les valeurs "100k" et "1M +" sont-elles en quelque sorte scientifiques? Ou est-ce juste une façon de dire "beaucoup"?
Bruno Reis
@Bruno - À mon humble avis, les nombres de 100K et 1M que j'ai utilisés sont en fait une estimation prudente pour prouver un point. Si vous connaissez VS et C ++, écrivez un programme qui alloue 100 octets sur la pile et écrivez-en un qui alloue 100 octets sur le tas. Passez ensuite à la vue de désassemblage et comptez simplement le nombre d'instructions d'assemblage que prend chaque allocation. Les opérations de tas sont généralement plusieurs appels de fonction dans la DLL Windows, il y a des compartiments et des listes liées, puis il y a la coalescence et d'autres algorithmes. Avec la pile, il peut se résumer à une instruction de montage "add esp, 100" ...
DXM
2
"100k (sinon 1M +) de fois plus lent"? C'est un peu exagéré. Que ce soit deux ordres de grandeur plus lentement, peut-être trois, mais c'est tout. Au moins, mon Linux est capable de faire 100M d'allocations de tas (+ quelques instructions environnantes) en moins de 6 secondes sur un Core i5, cela ne peut pas dépasser quelques centaines d'instructions par allocation - en fait, c'est presque certainement moins. Si c'est six ordres de grandeur plus lent que la pile, il y a quelque chose de grave avec l'implémentation du tas du système d'exploitation. Bien sûr, il y a beaucoup de problèmes avec Windows, mais cela ...
leftaroundabout
1
les modérateurs sont probablement sur le point de tuer tout ce fil de commentaires. Alors voici l'affaire, je concède que les chiffres réels ont été retirés de mon ...., mais convenons que le facteur est vraiment, vraiment gros et ne fait pas plus de commentaires :)
DXM
2

Vous pourriez avoir un intérêt pour "La collecte des ordures est rapide, mais une pile est plus rapide".

http://dspace.mit.edu/bitstream/handle/1721.1/6622/AIM-1462.ps.Z

Si je l'ai lu correctement, ces gars-là ont modifié un compilateur C pour allouer des "cadres de pile" sur le tas, puis utilisent la récupération de place pour désallouer les cadres au lieu de faire sauter la pile.

Les "trames de pile" allouées par pile surpassent de manière décisive les "trames de pile" allouées par tas.

Bruce Ediger
la source
1

Comment la pile d'appels va-t-elle fonctionner sur un tas? Essentiellement, vous devrez allouer une pile sur le tas dans chaque programme, alors pourquoi ne pas faire le matériel OS + pour vous?

Si vous voulez que les choses soient vraiment simples et efficaces, donnez simplement à l'utilisateur sa partie de mémoire et laissez-le s'en occuper. Bien sûr, personne ne veut tout implémenter et c'est pourquoi nous avons une pile et un tas.

Pubby
la source
À proprement parler, une «pile d'appels» n'est pas une fonctionnalité requise d'un environnement d'exécution de langage de programmation. Par exemple, une implémentation simple d'un langage fonctionnel évalué paresseusement par réduction de graphe (que j'ai codé) n'a pas de pile d'appels. Mais la pile d'appels est une technique très largement utile et largement utilisée, d'autant plus que les processeurs modernes supposent que vous l'utilisez et sont optimisés pour son utilisation.
Ben
@Ben - bien qu'il soit vrai (et une bonne chose) d'abstraire des choses comme l'allocation de mémoire à partir d'une langue, cela ne change pas l'architecture informatique actuelle. Par conséquent, votre code de réduction de graphique utilisera toujours la pile lors de l'exécution, que cela vous plaise ou non.
Ingo
@Ingo Pas vraiment dans un sens. Bien sûr, le système d'exploitation initialisera une section de mémoire traditionnellement appelée "la pile", et il y aura un registre pointant vers elle. Mais les fonctions du langage source ne sont pas représentées sous forme de trames de pile dans l'ordre des appels. L'exécution des fonctions est entièrement représentée par la manipulation des structures de données dans le tas. Même sans utiliser l'optimisation du dernier appel, il n'est pas possible de «déborder la pile». C'est ce que je veux dire quand je dis qu'il n'y a rien de fondamental à propos de "la pile d'appels".
Ben
Je ne parle pas des fonctions de la langue source mais des fonctions de l'interpréteur (ou autre) qui effectuent réellement la réduction du graphe. Ceux-ci auront besoin d'une pile. Cela est évident, car le matériel contemporain ne fait pas de réduction de graphique. Par conséquent, votre algorithme de réduction de graphe est finalement mappé sur l'ode machine, et je parie qu'il y a des appels de sous-programme parmi eux. QED.
Ingo
1

La pile et le tas sont requis. Ils sont utilisés dans différentes situations, par exemple:

  1. L'allocation de tas a une limitation que sizeof (a [0]) == sizeof (a [1])
  2. L'allocation de pile a une limitation que sizeof (a) est constante au moment de la compilation
  3. L'allocation de tas peut faire des boucles, des graphiques, etc. des structures de données complexes
  4. L'allocation de pile peut faire des arbres de taille au moment de la compilation
  5. Le tas nécessite un suivi de la propriété
  6. L'allocation et la désallocation des piles sont automatiques
  7. La mémoire de tas peut être facilement transmise d'une étendue à une autre via des pointeurs
  8. La mémoire de la pile est locale à chaque fonction et les objets doivent être déplacés vers l'étendue supérieure pour prolonger leur durée de vie (ou stockés à l'intérieur des objets au lieu des fonctions membres internes)
  9. Le tas est mauvais pour les performances
  10. La pile est assez rapide
  11. Les objets de tas sont renvoyés des fonctions via des pointeurs qui en prennent possession. Ou shared_ptrs.
  12. Les objets de pile sont renvoyés des fonctions via des références qui ne prennent pas possession.
  13. Le tas nécessite de faire correspondre chaque nouveau avec le type correct de suppression ou de suppression []
  14. Les objets de pile utilisent RAII et les listes d'initialisation du constructeur
  15. Les objets de segment de mémoire peuvent être initialisés n'importe quel point à l'intérieur d'une fonction et ne peuvent pas utiliser les paramètres du constructeur
  16. Les objets de pile utilisent des paramètres de constructeur pour l'initialisation
  17. Le tas utilise des tableaux et la taille du tableau peut changer lors de l'exécution
  18. La pile est destinée à des objets uniques et la taille est fixée au moment de la compilation

Fondamentalement, les mécanismes ne peuvent pas être comparés du tout car tant de détails sont différents. La seule chose commune avec eux est qu'ils gèrent tous les deux la mémoire d'une manière ou d'une autre.

tp1
la source
1

Les ordinateurs modernes disposent de plusieurs couches de mémoire cache en plus d'un système de mémoire principal volumineux mais lent. On peut faire des dizaines d'accès à la mémoire cache la plus rapide dans le temps requis pour lire ou écrire un octet à partir du système de mémoire principal. Ainsi, accéder à un emplacement mille fois est beaucoup plus rapide que d'accéder à 1000 (ou même 100) emplacements indépendants une fois chacun. Étant donné que la plupart des applications allouent et désallouent de façon répétée de petites quantités de mémoire près du haut de la pile, les emplacements en haut de la pile sont utilisés et réutilisés énormément, de sorte que la grande majorité (99% + dans une application typique) des accès de pile peuvent être gérés à l'aide de la mémoire cache.

En revanche, si une application devait créer et abandonner à plusieurs reprises des objets de segment de mémoire pour stocker des informations de continuation, chaque version de chaque objet de pile jamais créé devrait être écrite dans la mémoire principale. Même si la grande majorité de ces objets seraient complètement inutiles au moment où le processeur voudrait recycler les pages de cache dans lesquelles ils ont commencé, le processeur n'aurait aucun moyen de le savoir. Par conséquent, le processeur devrait perdre beaucoup de temps à effectuer des écritures de mémoire lentes d'informations inutiles. Pas exactement une recette pour la vitesse.

Une autre chose à considérer est que, dans de nombreux cas, il est utile de savoir qu'une référence d'objet passée à une routine ne sera pas utilisée une fois la routine terminée. Si les paramètres et les variables locales sont passés via la pile, et si l'inspection du code de la routine révèle qu'il ne persiste pas une copie de la référence transmise, alors le code qui appelle la routine peut être sûr que si aucune référence externe à la l'objet existait avant l'appel, aucun n'existera après. En revanche, si des paramètres étaient passés via des objets de tas, des concepts comme "après le retour d'une routine" deviennent un peu plus nébuleux, car si le code conservait une copie de la suite, il serait possible pour la routine de "retourner" plus d'une fois après un appel unique.

supercat
la source