Question Lequel est le plus rapide: allocation de pile ou allocation de tas


Cette question peut sembler assez élémentaire, mais c'est un débat que j'ai eu avec un autre développeur avec qui je travaille.

Je faisais attention à empiler les choses là où je pouvais, au lieu de les allouer en tas. Il me parlait et veillait par-dessus mon épaule et a fait remarquer que ce n’était pas nécessaire parce qu’il s’agissait des mêmes performances.

J'ai toujours eu l'impression que la croissance de la pile était constante et que la performance de l'allocation de tas dépendait de la complexité actuelle du tas pour l'allocation (trouver un trou de la bonne taille) et la désallocation (effondrement des trous pour réduire la fragmentation). de nombreuses implémentations de bibliothèques standard prennent le temps de le faire pendant les suppressions si je ne me trompe pas).

Cela me semble être quelque chose qui dépendrait probablement beaucoup du compilateur. Pour ce projet en particulier, j'utilise un Metrowerks compilateur pour le PPC architecture. 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 n'est-elle pas aussi performante que l'allocation de pile? N'y a-t-il aucune différence? Ou sont les différences si minuscules qu'il devient une micro-optimisation inutile.


448
2017-10-02 06:06


origine


Réponses:


L'allocation de pile est beaucoup plus rapide car tout ce qu'elle fait est de déplacer le pointeur de la pile. À l'aide de pools de mémoire, vous pouvez obtenir des performances comparables à partir de l'allocation de tas, mais cela vient avec une légère complexité ajoutée et ses propres maux de tête.

En outre, pile vs tas n'est pas seulement une considération de performance; il vous en dit aussi beaucoup sur la durée de vie prévue des objets.


446
2017-10-02 06:09



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

sub esp, 0x10

(Cela fait descendre le pointeur de pile de 0x10 octets et ainsi "alloue" ces octets pour une utilisation par une variable.)

Bien sûr, la taille de la pile est très, très finie, car vous découvrirez rapidement si vous surutilisez l'allocation de pile ou si vous essayez de faire de la récursivité :-)

En outre, il y a peu de raisons d'optimiser les performances du code qui n'en ont pas besoin, comme cela a été démontré par le profilage. "L'optimisation prématurée" cause souvent plus de problèmes que cela en vaut la peine.

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


153
2017-10-02 06:16



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

#include <ctime>
#include <iostream>

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 que une consistance stupide est le hobgoblin des petits esprits. Les compilateurs apparemment optimisateurs sont les hobgoblins des esprits de beaucoup de programmeurs. Cette discussion se trouvait au bas de la réponse, mais les gens ne semblent pas se préoccuper de lire aussi loin, alors je vais le faire pour éviter d'avoir des questions auxquelles j'ai déjà répondu.

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

Je recommande de compiler ce code avec l'optimisation désactivée car il n'y a aucun moyen de tromper chaque optimiseur actuellement utilisé ou qui sera utilisé dans le futur.

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 de la nanoseconde, je n'utiliserais pas std::clock(). Si je voulais publier les résultats sous forme de 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 autres compilateurs. En fait, l’allocation de tas prend des centaines de fois plus de temps que l’allocation de pile, et je ne vois rien d’autre à étudier la question plus avant.

L'optimiseur a pour mission de se débarrasser du code que je suis en train de tester. Je ne vois aucune raison de dire à l'optimiseur de s'exécuter, puis d'essayer de tromper l'optimiseur pour qu'il n'optimise pas vraiment. Mais si je voyais la valeur en faisant cela, je ferais un ou plusieurs de ce qui suit:

  1. Ajouter un membre de données à emptyet 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 uniquement dans le membre de données, l'optimiseur peut ignorer toutes les dernières itérations de la boucle. De plus, la question n'était pas "l'allocation de pile et l'accès aux données par rapport à l'allocation de tas et l'accès aux données".

  2. Déclarer e  volatile, mais volatile est souvent compilé incorrectement (PDF)

  3. Prenez l'adresse de e à l'intérieur de la boucle (et peut-être l'affecter à une variable qui est déclarée extern et défini dans un autre fichier). Mais même dans ce cas, le compilateur peut remarquer que - sur la pile au moins - e sera toujours alloué à la même adresse mémoire, puis effectuera un pliage constant comme dans (1) ci-dessus. J'obtiens toutes les itérations de la boucle, mais l'objet n'est jamais réellement alloué.

Au-delà de l'évidence, ce test est erroné en ce qu'il mesure à la fois l'allocation et la désallocation, et la question initiale ne portait pas sur la désallocation. Bien sûr, les variables allouées sur la pile sont automatiquement désallouées à la fin de leur portée, donc ne pas appeler delete (1) inclinerait les nombres (la désallocation de pile est incluse dans les nombres concernant l'allocation de pile, donc il est juste de mesurer la désallocation de tas) et (2) causera une mauvaise fuite de mémoire, sauf si nous gardons une référence au nouveau pointeur delete après nous avons notre mesure du temps.

Sur ma machine, en utilisant g ++ 3.4.4 sous Windows, j'obtiens des «0 ticks» pour les allocations de pile et de tas pour tout ce qui est inférieur à 100000 allocations, et même alors j'obtiens des «0 ticks» pour l'allocation des piles et 15 ticks "pour l'allocation de tas. Lorsque je mesure 10 000 000 allocations, l'allocation de pile prend 31 ticks d'horloge et l'allocation de tas prend 1562 ticks d'horloge.


Oui, un compilateur d'optimisation peut éviter de créer les objets vides. Si je comprends bien, il peut même élider toute la première boucle. Lorsque j'ai grimpé les itérations à 10 000 000, l'allocation de pile 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 g ++ pour optimiser l'exécutable, g ++ n'a pas élidé 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 lorsque vous ne voulez pas que ce code soit optimisé. Il me semble être très similaire à payer un supplément pour le service de voiturier, mais refusant de remettre les clés. Dans ce cas particulier, je ne souhaite pas que l'optimiseur soit en cours d'exécution.

Utiliser une version légèrement modifiée du benchmark (pour corriger le point que le programme original n'a pas alloué quelque chose sur la pile à chaque fois dans la boucle) et compiler sans optimisations mais relier aux librairies de release (pour adresser le point valide que nous ne voulez pas inclure de ralentissement causé par la liaison aux bibliothèques de débogage):

#include <cstdio>
#include <chrono>

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<double>(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<double>(end - begin).count());
    return 0;
}

affiche:

on_stack took 2.070003 seconds
on_heap took 57.980081 seconds

sur mon système lorsqu'il est compilé 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

Ce n’est pas parce que l’allocation de la pile est 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 aussi:

on_stack took 0.000003 seconds
on_heap took 0.000002 seconds

108
2018-03-02 01:55



Une chose intéressante que j'ai apprise à propos de Stack vs Heap Allocation sur le processeur Xbox 360 Xenon, qui peut également s'appliquer à d'autres systèmes multicœurs, est que l'allocation sur le tas provoque une section critique pour arrêter tous les autres noyaux. 't conflit. Ainsi, dans une boucle serrée, l'allocation de pile é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 à considérer si vous codez pour multicore / multiproc, en ce que votre allocation de pile ne sera visible que par le noyau qui exécute votre fonction étendue, et cela n'affectera pas les autres cœurs / processeurs.


27
2017-10-02 06:08



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

Je suis également d'accord avec Torbjörn Gyllebring sur la durée de vie des objets. Bon point!


17
2017-10-02 06:12



Je ne pense pas que l'allocation de pile 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 portée de l'allocation. Pour les gros objets, le tas est probablement nécessaire.

Sur les systèmes d'exploitation 32 bits qui ont plusieurs threads, la pile est souvent plutôt limitée (bien que généralement au moins quelques mb), car l'espace d'adressage doit être découpé et, tôt ou tard, une pile de threads se lancera 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 pile 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 piles de threads soient volumineuses.


6
2017-10-02 06:18



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

Parfois, l'allocation de pile nécessite l'ajout d'une ou de plusieurs pages de mémoire virtuelle. L'ajout d'une nouvelle page de mise à zéro de la mémoire ne nécessite pas de lire une page à partir du disque, donc cela sera toujours beaucoup plus rapide que de chercher un tas (surtout si une partie du tas a été paginée aussi). Dans une situation rare, et vous pourriez construire un tel exemple, assez d'espace est disponible dans une partie du tas qui est déjà dans la RAM, mais l'allocation d'une nouvelle page pour la pile doit attendre qu'une autre page soit écrite sur le disque. Dans cette situation rare, le tas est plus rapide.


6
2017-10-26 17:36



Mis à part l'avantage de performance de l'ordre de grandeur sur l'allocation de tas, l'allocation de pile est préférable pour les applications de serveur à exécution longue. Même les tas les mieux gérés finissent par être tellement fragmentés que les performances des applications se dégradent.


6
2017-10-02 06:43