Ce qui est plus rapide: allocation de stack ou allocation de tas

Cette question peut paraître assez élémentaire, mais c’est un débat que j’ai eu avec un autre développeur avec lequel je travaille.

Je prenais soin d’emstackr les choses là où je pouvais, au lieu de les allouer. Il me parlait et veillait par-dessus mon épaule et a fait remarquer que ce n’était pas nécessaire parce que c’était la même performance.

J’ai toujours eu l’impression que la croissance de la stack était un temps constant et que les performances de l’allocation de tas dépendaient de la complexité actuelle du tas à la fois pour l’allocation (trouver un trou de la taille appropriée) et la beaucoup d’implémentations de bibliothèques standard prennent du temps pour le faire pendant les suppressions si je ne me trompe pas).

Cela me frappe comme quelque chose qui serait probablement très dépendant du compilateur. Pour ce projet en particulier, j’utilise un compilateur Metrowerks pour l’architecture PPC . Un aperçu de cette combinaison serait très utile, mais en général, pour GCC et MSVC ++, quel est le cas? L’allocation de tas est-elle moins performante que l’allocation de stack? N’y a-t-il pas de différence? Ou les différences sont-elles si minimes que cela devient une micro-optimisation inutile.

L’allocation de stack est beaucoup plus rapide car tout ce qu’elle fait est de déplacer le pointeur de stack. En utilisant des pools de mémoire, vous pouvez obtenir des performances comparables en termes d’allocation de segment de mémoire, mais cela s’accompagne d’une légère complexité supplémentaire et de ses propres problèmes.

En outre, la stack et le tas ne sont pas seulement une considération de performance; il vous en dit aussi beaucoup sur la durée de vie attendue des objects.

La stack est beaucoup plus rapide. Il n’utilise littéralement qu’une seule instruction sur la plupart des architectures, dans la plupart des cas, par exemple sur x86:

sub esp, 0x10 

(Cela déplace le pointeur de stack vers le bas de 0x10 octets et “alloue ainsi” ces octets pour une utilisation par une variable.)

Bien sûr, la taille de la stack est très très limitée, car vous saurez rapidement si vous utilisez trop l’allocation de stack ou si vous essayez de faire de la récursivité 🙂

De plus, il y a peu de raisons d’optimiser les performances du code qui n’en ont pas besoin de manière vérifiable, comme le montre le profilage. “L’optimisation prématurée” provoque souvent plus de problèmes que sa valeur.

Ma règle de base: si je sais que je vais avoir besoin de données au moment de la compilation , et que sa taille est inférieure à quelques centaines d’octets, je l’alloue. Sinon, je l’alloue.

Honnêtement, il est sortingvial d’écrire un programme pour comparer la performance:

 #include  #include  namespace { class empty { }; // even empty classes take up 1 byte of space, minimum } int main() { std::clock_t start = std::clock(); for (int i = 0; i < 100000; ++i) empty e; std::clock_t duration = std::clock() - start; std::cout << "stack allocation took " << duration << " clock ticks\n"; start = std::clock(); for (int i = 0; i < 100000; ++i) { empty* e = new empty; delete e; }; duration = std::clock() - start; std::cout << "heap allocation took " << duration << " clock ticks\n"; } 

On dit qu'une consistance stupide est le hobgoblin des petits esprits . Apparemment, l'optimisation des compilateurs est la clé de voûte de nombreux programmeurs. Cette discussion se trouvait au bas de la réponse, mais les gens ne peuvent apparemment pas prendre la peine de lire aussi loin, alors je la propose ici pour éviter de me poser des questions.

Un compilateur optimisant peut remarquer que ce code ne fait rien et peut tout optimiser. C'est le travail de l'optimiseur de faire des choses comme ça, et lutter contre l'optimiseur est une course idiote.

Je recommanderais de comstackr ce code avec l'optimisation désactivée car il n'y a pas de moyen de tromper tous les optimiseurs actuellement utilisés ou qui seront utilisés à l'avenir.

Toute personne qui allume l'optimiseur et se plaint de la combattre devrait être ridiculisée par le public.

Si je me souciais de la précision à la nanoseconde, je n'utiliserais pas std::clock() . Si je voulais publier les résultats en tant que thèse de doctorat, je ferais une plus grande affaire à ce sujet et je comparerais probablement GCC, Tendra / Ten15, LLVM, Watcom, Borland, Visual C ++, Digital Mars, ICC et d'autres compilateurs. En réalité, l’allocation de tas prend des centaines de fois plus de temps que l’allocation de stack, et je ne vois rien d’autre à étudier la question.

L’optimiseur a pour mission de se débarrasser du code que je teste. Je ne vois aucune raison de demander à l'optimiseur de s'exécuter, puis d'essayer de tromper l'optimiseur pour qu'il n'optimise pas réellement. Mais si je voyais un intérêt à le faire, je ferais une ou plusieurs des choses suivantes:

  1. Ajoutez un membre de données à empty et accédez à ce membre de données dans la boucle; mais si je lis seulement à partir du membre de données, l'optimiseur peut faire un pliage constant et supprimer la boucle; Si j'écris seulement sur le membre de données, l'optimiseur peut ignorer toutes les itérations sauf la toute dernière. De plus, la question n'était pas "l'allocation de la stack et l'access aux données par rapport à l'allocation du tas et à l'access aux données".

  2. Déclarez- e volatile , mais volatile est souvent compilé de manière incorrecte (PDF).

  3. Prenez l'adresse de e dans la boucle (et assignez-la à une variable déclarée extern et définie dans un autre fichier). Mais même dans ce cas, le compilateur peut remarquer que - sur la stack au moins - e sera toujours alloué à la même adresse mémoire, puis effectuera un pliage constant comme dans (1) ci-dessus. Je reçois toutes les itérations de la boucle, mais l'object n'est jamais réellement alloué.

Au-delà de l’évidence, ce test est imparfait en ce qu’il mesure à la fois l’allocation et la désallocation, et que la question initiale ne portait pas sur la désallocation. Bien sûr, les variables allouées sur la stack sont automatiquement désallouées à la fin de leur étendue, donc ne pas appeler delete (1) fausserait les nombres (la désallocation de la stack est incluse dans les nombres sur l'allocation de stack, donc il est juste de mesurer la désallocation du tas) (2) provoque une fuite de mémoire assez importante, sauf si nous conservons une référence au nouveau pointeur et à la delete appel après avoir effectué notre mesure du temps.

Sur ma machine, en utilisant g ++ 3.4.4 sous Windows, j'obtiens "0 ticks d'horloge" pour l'allocation de stack et de tas pour tout ce qui est inférieur à 100000 allocations, et j'obtiens "0 ticks d'horloge" pour l'allocation de stack et "15 ticks d'horloge" "pour l'allocation de tas. Lorsque je mesure 10 000 000 d'allocations, l'allocation de stack prend 31 tics d'horloge et l'allocation de tas prend 1562 coups d'horloge.


Oui, un compilateur optimisant peut créer des objects vides. Si je comprends bien, cela pourrait même éliminer toute la première boucle. Lorsque j'ai grimpé les itérations à 10 000 000, l'allocation de stack a pris 31 tics d'horloge et l'allocation de tas a pris 1562 tics d'horloge. Je pense qu'il est prudent de dire que sans dire à g ++ d'optimiser l'exécutable, g ++ n'a pas éliminé les constructeurs.


Dans les années qui ont suivi mon écriture, la préférence pour Stack Overflow a été de publier des performances à partir de versions optimisées. En général, je pense que c'est correct. Cependant, je pense toujours qu'il est idiot de demander au compilateur d'optimiser le code alors que vous ne voulez pas que ce code soit optimisé. Cela me semble très similaire à payer un supplément pour le service de voiturier, mais refuser de remettre les clés. Dans ce cas particulier, je ne veux pas que l'optimiseur soit en cours d'exécution.

Utiliser une version légèrement modifiée du benchmark (pour corriger le point valide selon lequel le programme original n’allouait pas quelque chose sur la stack à chaque fois) et comstackr sans optimisations, mais en reliant les librairies (pour corriger le point ne voulez pas inclure de ralentissement causé par la liaison aux bibliothèques de débogage):

 #include  #include  namespace { void on_stack() { int i; } void on_heap() { int* i = new int; delete i; } } int main() { auto begin = std::chrono::system_clock::now(); for (int i = 0; i < 1000000000; ++i) on_stack(); auto end = std::chrono::system_clock::now(); std::printf("on_stack took %f seconds\n", std::chrono::duration(end - begin).count()); begin = std::chrono::system_clock::now(); for (int i = 0; i < 1000000000; ++i) on_heap(); end = std::chrono::system_clock::now(); std::printf("on_heap took %f seconds\n", std::chrono::duration(end - begin).count()); return 0; } 

affiche:

 on_stack took 2.070003 seconds on_heap took 57.980081 seconds 

sur mon système lors de la compilation avec la ligne de commande cl foo.cc /Od /MT /EHsc .

Vous n'êtes peut-être pas d'accord avec mon approche pour obtenir une version non optimisée. C'est bien: n'hésitez pas à modifier le benchmark autant que vous le souhaitez. Quand j'active l'optimisation, j'obtiens:

 on_stack took 0.000000 seconds on_heap took 51.608723 seconds 

Non pas parce que l’allocation de la stack est en fait instantanée mais parce que tout compilateur à moitié décent peut remarquer que on_stack ne fait rien d’utile et peut être optimisé. GCC sur mon ordinateur portable Linux remarque également que on_heap ne fait rien d’utile et l’optimise également:

 on_stack took 0.000003 seconds on_heap took 0.000002 seconds 

Une chose intéressante que j’ai apprise à propos de l’allocation stack / tas sur le processeur Xbox 360 Xenon, qui peut également s’appliquer à d’autres systèmes multicœurs, est que l’allocation sur le tas entraîne la saisie d’une section critique pour arrêter tous les autres cœurs. t conflit Ainsi, dans une boucle serrée, l’allocation de stack était la voie à suivre pour les baies de taille fixe car elle empêchait les arrêts.

Cela peut être une autre accélération à prendre en compte si vous codez pour multicœur / multiproc, car votre allocation de stack ne sera visible que par le cœur exécutant votre fonction étendue, et cela n’affectera pas les autres cœurs / processeurs.

Vous pouvez écrire un allocateur de tas spécial pour des tailles spécifiques d’objects très performants. Cependant, l’allocateur de tas général n’est pas particulièrement performant.

Je suis également d’accord avec Torbjörn Gyllebring sur la durée de vie prévue des objects. Bon point!

Je ne pense pas que l’allocation de stack et l’allocation de tas soient généralement interchangeables. J’espère également que les performances des deux sont suffisantes pour un usage général.

Je recommande fortement pour les petits articles, celui qui convient le mieux à la scope de l’allocation. Pour les gros articles, le tas est probablement nécessaire.

Sur les systèmes d’exploitation 32 bits dotés de plusieurs threads, la stack est souvent assez limitée (généralement au moins quelques Mo), car l’espace d’adressage doit être découpé et, tôt ou tard, une stack de threads s’exécutera dans une autre. Sur les systèmes à un seul thread (Linux à un seul thread, de toute façon), la limitation est beaucoup moins importante car la stack peut simplement croître et croître.

Sur les systèmes d’exploitation 64 bits, il y a suffisamment d’espace d’adressage pour que les stacks de threads soient volumineuses.

Habituellement, l’allocation de stack consiste simplement à soustraire du registre de pointeur de stack. C’est beaucoup plus rapide que de chercher un tas.

Parfois, l’allocation de la stack nécessite l’ajout d’une ou de plusieurs pages de mémoire virtuelle. L’ajout d’une nouvelle page de mémoire à zéro ne nécessite pas de lire une page à partir du disque, ce qui signifie que cela va toujours être beaucoup plus rapide que de chercher un tas (surtout si une partie du tas a également été extraite). Dans un cas rare, et si vous pouviez construire un tel exemple, il suffit qu’un espace soit déjà disponible dans une partie du tas qui se trouve déjà dans la RAM, mais l’atsortingbution d’une nouvelle page à la stack doit attendre que d’autres pages soient écrites. sur le disque. Dans cette situation rare, le tas est plus rapide.

Outre l’avantage des performances par ordre de grandeur par rapport à l’allocation des segments, l’allocation de la stack est préférable pour les applications serveur à exécution longue. Même les tas les mieux gérés deviennent si fragmentés que les performances des applications se dégradent.

Une stack a une capacité limitée, tandis qu’un tas ne l’est pas. La stack typique d’un processus ou d’un thread est d’environ 8K. Vous ne pouvez pas changer la taille une fois allouée.

Une variable de stack suit les règles de cadrage, contrairement à une stack. Si votre pointeur d’instruction dépasse une fonction, toutes les nouvelles variables associées à la fonction disparaissent.

Surtout, vous ne pouvez pas prédire la chaîne d’appel de la fonction globale à l’avance. Une simple allocation de 200 octets de votre part peut donc provoquer un débordement de stack. Ceci est particulièrement important si vous écrivez une bibliothèque, pas une application.

Je pense que la durée de vie est cruciale et que la chose à atsortingbuer doit être construite de manière complexe. Par exemple, dans la modélisation pilotée par transaction, vous devez généralement remplir et transmettre une structure de transaction avec un ensemble de champs aux fonctions d’opération. Regardez la norme OSCI SystemC TLM-2.0 pour un exemple.

Les allouer à la stack près de l’appel à l’opération a tendance à entraîner des frais généraux énormes, car la construction est coûteuse. La bonne méthode consiste à allouer sur le tas et à réutiliser les objects de transaction soit par regroupement, soit par une stratégie simple comme “ce module n’a besoin que d’un object de transaction”.

C’est beaucoup plus rapide que d’allouer l’object à chaque appel d’opération.

La raison en est simplement que l’object a une construction coûteuse et une durée de vie utile assez longue.

Je dirais: essayez les deux et voyez ce qui fonctionne le mieux dans votre cas, car cela peut vraiment dépendre du comportement de votre code.

Probablement le plus gros problème de l’allocation de tas par rapport à l’allocation de stack, c’est que l’allocation de tas dans le cas général est une opération sans limite, et vous ne pouvez donc pas l’utiliser là où le timing est un problème.

Pour les autres applications où le timing n’est pas un problème, cela n’a pas d’importance, mais si vous chargez beaucoup, cela affectera la vitesse d’exécution. Essayez toujours d’utiliser la stack pour une mémoire de courte durée et souvent allouée (par exemple dans des boucles) et aussi longtemps que possible – faites une allocation de tas pendant le démarrage de l’application.

Ce n’est pas l’allocation de stack jsut qui est plus rapide. Vous gagnez également beaucoup en utilisant des variables de stack. Ils ont une meilleure localisation de référence. Et enfin, la désallocation coûte beaucoup moins cher.

L’allocation de stack sera presque toujours aussi rapide ou plus rapide que l’allocation de tas, bien qu’il soit certainement possible qu’un allocateur de stack utilise simplement une technique d’allocation basée sur la stack.

Cependant, il existe des problèmes plus importants lorsque l’on traite de la performance globale de l’allocation par stack ou par couche (ou, en termes légèrement meilleurs, d’allocation locale ou externe). En général, l’allocation de mémoire (externe) est lente car elle traite de nombreux types d’allocations et de modèles d’allocation. La réduction de la scope de l’allocateur que vous utilisez (le rendant local à l’algorithme / code) aura tendance à augmenter les performances sans aucun changement majeur. En ajoutant une meilleure structure à vos modèles d’allocation, par exemple, forcer un ordre LIFO sur des paires d’allocation et de désallocation peut également améliorer les performances de votre allocateur en utilisant l’allocateur de manière plus simple et plus structurée. Ou bien, vous pouvez utiliser ou écrire un allocateur adapté à votre modèle d’allocation particulier; Comme la plupart des programmes allouent fréquemment quelques tailles discrètes, un tas basé sur une mémoire tampon de quelques tailles fixes (de préférence connues) fonctionnera extrêmement bien. Windows utilise son segment de mémoire à faible fragmentation pour cette raison même.

D’autre part, l’allocation basée sur la stack sur une plage de mémoire de 32 bits est également périlleuse si vous avez trop de threads. Les stacks ont besoin d’une plage de mémoire contiguë. Ainsi, plus vous aurez de threads, plus vous aurez besoin d’espace d’adressage virtuel sans débordement de stack. Ce ne sera pas un problème (pour le moment) avec le 64-bit, mais cela peut certainement causer des ravages dans les programmes de longue durée avec beaucoup de threads. Manquer d’espace d’adressage virtuel en raison de la fragmentation est toujours difficile à gérer.

L’allocation de stack est un couple d’instructions alors que l’allocateur de stack rtos le plus rapide que je connaisse (TLSF) utilise en moyenne 150 instructions. De plus, les allocations de stack ne nécessitent pas de verrou, car elles utilisent le stockage local de threads, ce qui représente un autre gain de performances considérable. Les allocations de stack peuvent donc être de deux ou trois ordres de grandeur plus rapides, selon le niveau de multithread de votre environnement.

En général, l’allocation de tas est votre dernier recours si vous vous souciez des performances. Une option viable entre les deux peut être un allocateur de pool fixe, qui ne contient que quelques instructions et dont la surcharge par allocation est très faible, ce qui est idéal pour les petits objects de taille fixe. En revanche, il ne fonctionne qu’avec des objects de taille fixe, n’est pas insortingnsèquement sécurisé et présente des problèmes de fragmentation de bloc.

Il y a un point général à faire sur ces optimisations.

L’optimisation que vous obtenez est proportionnelle à la durée pendant laquelle le compteur de programme est réellement dans ce code.

Si vous échantillonnez le compteur du programme, vous découvrirez où il passe son temps, et c’est généralement dans une petite partie du code, et souvent dans les routines de la bibliothèque, vous n’avez aucun contrôle.

Ce n’est que si vous passez beaucoup de temps dans l’allocation de tas de vos objects qu’il sera nettement plus rapide de les allouer.

l’allocation de stack est beaucoup plus rapide.

Comme d’autres l’ont dit, l’allocation des stacks est généralement beaucoup plus rapide.

Cependant, si la copie de vos objects est coûteuse, l’allocation sur la stack peut entraîner un énorme impact sur les performances plus tard lorsque vous utilisez les objects si vous ne faites pas attention.

Par exemple, si vous allouez quelque chose sur la stack et que vous le placez ensuite dans un conteneur, il aurait été préférable d’allouer le tas et de stocker le pointeur dans le conteneur (par exemple, avec un std :: shared_ptr <>). La même chose est vraie si vous transmettez ou renvoyez des objets par valeur et d’autres scénarios similaires.

Le fait est que, bien que l’allocation de stack soit généralement meilleure que l’allocation de tas dans de nombreux cas, parfois, si vous n’emstackz pas l’allocation quand elle ne correspond pas au modèle de calcul, cela peut causer plus de problèmes qu’elle ne résout.

 class Foo { public: Foo(int a) { } } int func() { int a1, a2; std::cin >> a1; std::cin >> a2; Foo f1(a1); __asm push a1; __asm lea ecx, [this]; __asm call Foo::Foo(int); Foo* f2 = new Foo(a2); __asm push sizeof(Foo); __asm call operator new;//there's a lot instruction here(depends on system) __asm push a2; __asm call Foo::Foo(int); delete f2; } 

Ce serait comme ça dans asm. Lorsque vous êtes en mode func , le f1 et le pointeur f2 ont été alloués sur la stack (stockage automatisé). Et au fait, Foo f1(a1) n’a pas d’effet d’instruction sur le pointeur de stack ( esp ), il a été alloué, si func veut obtenir le membre f1 , ses instructions sont comme ceci: lea ecx [ebp+f1], call Foo::SomeFunc() . Une autre chose que l’allocation de stack peut donner à quelqu’un pense que la mémoire est quelque chose comme FIFO , la FIFO juste arrivée quand vous allez dans une fonction, si vous êtes dans la fonction et allouez quelque chose comme int i = 0 , rien n’est arrivé.

Il a été mentionné avant que l’allocation de stack ne fait que déplacer le pointeur de stack, c’est-à-dire une instruction unique sur la plupart des architectures. Comparez cela à ce qui se produit généralement dans le cas de l’allocation de tas.

Le système d’exploitation conserve des parties de la mémoire libre sous la forme d’une liste liée avec les données de charge utile consistant en le pointeur vers l’adresse de départ de la partie libre et la taille de la partie libre. Pour allouer X octets de mémoire, la liste des liens est parcourue et chaque note est visitée en séquence, pour vérifier si sa taille est au moins égale à X. Lorsqu’une partie de taille P> = X est trouvée, P est divisé en deux parties avec tailles X et PX. La liste chaînée est mise à jour et le pointeur sur la première partie est renvoyé.

Comme vous pouvez le voir, l’allocation de tas dépend de facteurs tels que la quantité de mémoire demandée, la fragmentation de la mémoire, etc.

En général, l’allocation de stack est plus rapide que l’allocation de stack, comme le mentionnent presque toutes les réponses ci-dessus. Un push ou un pop de stack est O (1), alors que l’allocation ou la libération d’un tas peut nécessiter un passage des allocations précédentes. Cependant, vous ne devriez généralement pas allouer des boucles serrées et à forte intensité de performance. Le choix se résume généralement à d’autres facteurs.

Il pourrait être bon de faire cette distinction: vous pouvez utiliser un “allocateur de stack” sur le tas. Ssortingctement parlant, je prends l’allocation de la stack pour désigner la méthode réelle d’affectation plutôt que l’emplacement de l’allocation. Si vous allouez beaucoup de choses sur la stack de programmes, cela peut être mauvais pour diverses raisons. D’un autre côté, utiliser une méthode de stack pour allouer le tas lorsque cela est possible est le meilleur choix que vous puissiez faire pour une méthode d’allocation.

Puisque vous avez mentionné Metrowerks et PPC, je suppose que vous voulez dire Wii. Dans ce cas, la mémoire est une priorité, et l’utilisation d’une méthode d’allocation de stack permet de ne pas perdre de mémoire sur les fragments. Bien sûr, cela nécessite beaucoup plus d’attention que les méthodes d’allocation de tas “normales”. Il est sage d’évaluer les compromis pour chaque situation.

Remarquez que les considérations ne concernent généralement pas la vitesse et les performances lors de la sélection de l’allocation de stack ou de tas. La stack agit comme une stack, ce qui signifie qu’elle est bien adaptée pour pousser des blocs et les ré-ouvrir, dernier entré, premier sorti. L’exécution des procédures est également semblable à une stack, la dernière procédure saisie doit d’abord être sortie. Dans la plupart des langages de programmation, toutes les variables nécessaires à une procédure ne seront visibles que lors de l’exécution de la procédure. Elles seront donc poussées lors de la saisie d’une procédure et extraites de la stack à la sortie ou au retour.

Maintenant, pour un exemple où la stack ne peut pas être utilisée:

 Proc P { pointer x; Proc S { pointer y; y = allocate_some_data(); x = y; } } 

Si vous allouez de la mémoire dans la procédure S et la placez sur la stack, puis quittez S, les données allouées seront extraites de la stack. Mais la variable x dans P pointe également vers cette donnée, donc x pointe maintenant vers un endroit sous le pointeur de la stack (supposons que la stack augmente vers le bas) avec un contenu inconnu. Le contenu peut toujours être présent si le pointeur de la stack est simplement déplacé vers le haut sans effacer les données en dessous, mais si vous commencez à allouer de nouvelles données sur la stack, le pointeur x peut en fait pointer vers ces nouvelles données.

Ne faites jamais d’hypothèses prématurées car d’autres codes d’application et leur utilisation peuvent avoir une incidence sur votre fonction. Donc, en regardant la fonction, l’isolement ne sert à rien.

Si vous êtes sérieux avec l’application, réglez-la ou utilisez un outil de profilage similaire et examinez les zones sensibles.

Ketan

Je voudrais dire que le code généré par GCC (je me souviens aussi de VS) n’a pas d’effet sur la stack .

Dites pour la fonction suivante:

  int f(int i) { if (i > 0) { int array[1000]; } } 

Voici le code généré:

  __Z1fi: Leh_func_begin1: pushq %rbp Ltmp0: movq %rsp, %rbp Ltmp1: subq $**3880**, %rsp <--- here we have the array allocated, even the if doesn't excited. Ltmp2: movl %edi, -4(%rbp) movl -8(%rbp), %eax addq $3880, %rsp popq %rbp ret Leh_func_end1: 

Alors, quelle que soit la variable locale que vous avez (même à l’intérieur ou en cas de changement), seule la valeur 3880 changera. À moins que vous n'ayez pas de variable locale, cette instruction doit simplement être exécutée. Donc, l'allocation de la variable locale n'a pas de surcharge.