541 votes

C++ Qui est plus rapide: l'allocation de Pile ou le Tas de répartition

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

J'ai été en prenant soin de pile allouer des choses où j'ai pu, au lieu de tas de leur attribution. Il était en train de parler de moi et regarder par-dessus mon épaule et a fait observer qu'il n'était pas nécessaire parce qu'ils sont de la même performance sage.

J'ai toujours été sous l'impression que la croissance de la pile de la constante de temps, et de l'allocation de tas de performance dépendait de la complexité actuelle du tas pour les deux allocation (pour trouver un trou de la bonne taille) et de l'allocation (l'effondrement des trous afin de réduire la fragmentation, comme de nombreux standard de la bibliothèque implémentations de prendre le temps de le faire pendant supprime si je ne me trompe pas).

Ce qui me frappe comme quelque chose qui serait probablement très dépendant du compilateur. Pour ce projet en particulier, je suis à l'aide d'un Metrowerks compilateur pour le PPC de l'architecture. Aperçu sur cette combinaison serait la plus utile, mais en général, pour GCC, et MSVC++, ce qui est le cas? Est d'allocation de tas pas aussi performante que l'allocation de pile? Il n'y a pas de différence? Ou sont les différences afin de minute, il devient inutile de micro-optimisation.

535voto

Torbjörn Gyllebring Points 8180

L'allocation de pile est beaucoup plus rapide puisqu'il n'a vraiment est de déplacer le pointeur de pile. À l'aide de pools de mémoire, vous pouvez obtenir des performances comparables hors de l'allocation de tas, mais qui vient avec une légère ajouté de la complexité et de ses propres maux de tête.

Aussi, pile vs tas n'est pas seulement un facteur de performance; il dit aussi beaucoup sur la durée de vie prévue des objets.

177voto

Dan Points 18831

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

sub esp, 0x10

(Qui se déplace le pointeur de pile vers le bas par 0x10 octets et donc "alloue" ces octets pour une utilisation par une variable.)

Bien sûr, la taille de tapis est très, très limitée, comme vous allez rapidement découvrir si vous abusez de l'allocation de pile ou essayer de faire une récursion infinie :-)

Aussi, il y a peu de raison pour optimiser les performances de code qui n'est pas vérifiable en a besoin, comme démontré par le profilage. "L'optimisation prématurée" pose souvent plus de problèmes qu'elle en vaut la peine.

Ma règle d'or: si je sais que je vais avoir besoin de quelques données au moment de la compilation, et c'est en vertu de quelques centaines d'octets de taille, je pile-l'attribuer. Sinon je tas attribuer.

126voto

Max Lybbert Points 11822

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

#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";
}

Il est dit qu' un idiot de cohérence est le lutin de petits esprits. Apparemment, l'optimisation des compilateurs sont les lutins de nombreux programmeurs de l'esprit. Cette discussion utilisé pour être à la base de la réponse, mais les gens ne peuvent apparemment pas être pris la peine de lire de loin, donc je suis en déplacement jusqu'ici pour éviter de se faire des questions que j'ai déjà répondu.

Un compilateur optimisant peut remarquer que ce code ne fait rien, et peut optimiser tout de suite. C'est l'optimiseur de faire des trucs comme ça, et la lutte contre l'optimiseur est sans issue.

Je recommande la compilation de ce code avec l'optimisation éteint car il n'y a pas de bonne façon de tromper tous optimiseur actuellement en cours d'utilisation ou qui sera utilisé dans l'avenir.

Quelqu'un qui fait de la optimizer, puis se plaint de combat qu'il doit être soumis au ridicule public.

Si je souciait une précision à la nanoseconde je ne voudrais pas utiliser std::clock(). Si je voulais publier les résultats d'une thèse de doctorat, je voudrais faire une plus grosse affaire à ce sujet, et je serais probablement comparer GCC, je vais avoir/Ten15, LLVM, Watcom, Borland, Visual C++, Numérique de Mars, de la CPI et d'autres compilateurs. Comme il est, allocation de tas prend des centaines de fois plus que l'allocation de pile, et je ne vois rien d'utile pour enquêter sur la question.

L'optimiseur a pour mission de débarrasser le code je suis en essais. Je ne vois pas de raison de dire que l'optimiseur à exécuter, puis essayer de tromper l'optimiseur en a pas en fait de l'optimisation. Mais si j'ai vu de la valeur en faisant cela, je ferais un ou plusieurs des éléments suivants:

  1. Ajouter un membre de données de empty, et accéder à ses données, membre de la boucle; mais si je n'avais jamais lu du membre de données de l'optimiseur peut faire de constantes et de supprimer la boucle; si je ne jamais écrire pour le membre de données, l'optimiseur peut passer tous les mais la dernière itération de la boucle. En outre, la question n'était pas "pile de répartition et d'accès aux données vs tas de répartition et d'accès aux données."

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

  3. Prendre l'adresse de l' e à l'intérieur de la boucle (et peut-être l'attribuer à une variable qui est déclarée extern et définie dans un autre fichier). Mais même dans ce cas, le compilateur peut remarquer que, sur la pile au moins -- e seront toujours attribués à la même adresse mémoire, et puis faire de constantes comme dans (1) ci-dessus. Je reçois toutes les itérations de la boucle, mais l'objet n'est jamais réellement allouée.

Au-delà de l'évident, ce test est erronée, car elle permet de mesurer à la fois l'allocation et la libération, et la question d'origine ne m'a pas demandé de libération de la mémoire. Bien sûr, les variables allouées sur la pile sont automatiquement libéré à la fin de leur portée, de sorte de ne pas appeler delete (1) biaiser les chiffres (pile de libération de la mémoire est inclus dans les chiffres sur l'allocation de pile, il est donc juste de mesurer tas de libération de la mémoire) et (2) la cause d'un assez mauvais souvenir de la fuite, à moins que nous de conserver une référence à la nouvelle pointeur et appelez - delete après nous avons eu notre mesure du temps.

Sur ma machine, à l'aide de g++ 3.4.4 sur Windows, j'obtiens un "0 tops d'horloge" à la fois la pile et le tas de l'allocation de rien de moins que de 100000 allocations, et même alors, j'ai "0 tops d'horloge" pour l'allocation de pile et "15 ticks" pour l'allocation de tas. Lorsque je mesure 10 000 000 d'allocations, l'allocation de pile prend le 31 tops d'horloge et de tas d'allocation prend 1562 tops d'horloge.


Oui, un compilateur optimisant peut éluder créer le vide d'objets. Si je comprends bien, il peut éluder l'ensemble de la première boucle. Quand j'ai heurté les itérations de 10 000 000 allocation de pile pris 31 tops d'horloge et d'allocation de tas a pris 1562 tops d'horloge. Je pense qu'il est sûr de dire que sans le dire à g++ pour optimiser l'exécutable, g++ n'a pas éluder les constructeurs.


Dans les années depuis que j'ai écrit cela, la préférence sur Stack Overflow a été de performance par l'optimisation des builds. En général, je pense que c'est correct. Cependant, je pense toujours que c'est idiot de demander au compilateur d'optimiser le code, quand en fait, vous ne voulez pas que le code optimisé. Il me frappe comme étant très similaire à payer un supplément pour service de voiturier, mais refusant de remettre les clés. Dans ce cas particulier, je ne veux pas que l'optimiseur en cours d'exécution.

À l'aide d'une version légèrement modifiée de l'indice de référence (à l'adresse de point valide que l'original n'a pas allouer quelque chose sur la pile à chaque passage dans la boucle) et de la compilation sans optimisations, mais en les reliant à la libération des bibliothèques (à l'adresse valide point que nous ne voulons pas comprendre tout ralentissement causé par les reliant à des 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 ne pouvez pas d'accord avec ma démarche pour l'obtention d'un non-optimisé construire. C'est très bien: n'hésitez pas à modifier l'indice de référence autant que vous le souhaitez. Quand j'allume l'optimisation, j'obtiens:

on_stack took 0.000000 seconds
on_heap took 51.608723 seconds

Non pas parce que l'allocation de pile est en fait instantané, mais parce que toute demi-décent compilateur peut remarquer qu' on_stack ne pas faire quelque chose d'utile et peut être optimisé à l'écart. GCC sur mon Linux ordinateur portable aussi d'avis qu' on_heap ne pas faire quelque chose d'utile, et optimise l'éloignant ainsi:

on_stack took 0.000003 seconds
on_heap took 0.000002 seconds

31voto

Furious Coder Points 609

Une chose intéressante, j'ai appris à propos de la Pile vs Allocation de Tas sur la Xbox 360 Xenon processeur, ce qui peut également s'appliquer à d'autres systèmes multicœurs, c'est que l'allocation sur le Tas provoque une Section Critique entrer pour mettre fin à toutes les autres cœurs, afin que l'alloc n'entre pas en conflit. Ainsi, dans une boucle serrée, l'Allocation de Pile était la voie à suivre pour fixe la taille des tableaux, car elle empêchait les étals.

Cela peut être un autre facteur à considérer si vous êtes codant pour le multicœur/multiproc, dans votre pile de répartition ne seront visibles que par la base en cours d'exécution de votre fonction de l'étendue, et qui n'affectera pas les autres cores/Cpu.

19voto

Chris Jester-Young Points 102876

Vous pouvez créer un segment de l'allocateur pour certaines dimensions des objets qui est très performant. Cependant, le général de tas allocateur n'est pas particulièrement performant.

Aussi je suis d'accord avec Torbjörn Gyllebring sur la durée de vie prévue des objets. Bon point!

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X