Existe-t-il une documentation comparant / contrastant les implémentations de bibliothèques standard C ++? [fermé]

16

(Ce n'est pas une programmation de jeu en soi, mais je suis certain que si je le demandais sur SO, on me dirait de ne pas optimiser prématurément, même si l'histoire nous dit que chaque grand jeu finit par s'inquiéter de ces choses.)

Existe-t-il un document quelque part qui résume les différences de performances, et en particulier d'utilisation de la mémoire, entre les différentes implémentations de bibliothèques standard C ++? Les détails de certaines implémentations sont protégés par NDA, mais une comparaison entre STLport vs libstdc ++ vs libc ++ vs MSVC / Dinkumware (vs EASTL?) Semble être extrêmement utile.

Je recherche en particulier des réponses à des questions telles que:

  • Quelle quantité de mémoire supplémentaire est associée aux conteneurs standard?
  • Quels conteneurs, le cas échéant, font des allocations dynamiques simplement en étant déclarés?
  • Est-ce que std :: string fait une copie sur écriture? Optimisation de chaîne courte? Cordes?
  • Est-ce que std :: deque utilise un tampon en anneau ou est-ce de la merde?

la source
J'avais l'impression que dequec'était toujours implémenté dans la STL avec un vecteur.
Tetrad
@Tetrad: Jusqu'à il y a quelques semaines, je l'étais aussi, mais j'ai lu que cela était souvent implémenté par une structure en forme de corde - et cela semble être ce qui se trouve dans STLport.
La STL a un projet de travail ouvert , qui peut être utilisé pour trouver des informations concernant les différentes structures de données (séquentielles et associatives), les algorithmes et les classes d'assistance mis en œuvre. Cependant, il semble que le surdébit de mémoire soit spécifique à l'implémentation plutôt qu'à la spécification définie.
Thomas Russell
3
@Duck: Le développement de jeux est le seul endroit à ma connaissance qui utilise régulièrement des fonctionnalités C ++ de haut niveau, mais doit suivre méticuleusement les allocations de mémoire car il s'exécute sur des systèmes sans mémoire virtuelle à faible mémoire. Chaque réponse unique sur SO serait "n'optimisez pas prématurément, la STL va bien, utilisez-la!" - 50% des réponses ici jusqu'à présent le sont - et pourtant le test de Maik montre clairement une préoccupation majeure pour les jeux souhaitant utiliser std :: map, et la confusion de Tetrad et la mienne à propos des implémentations std :: deque courantes de la même manière.
2
@Joe Wreschnig Je ne veux pas vraiment voter pour clore parce que je suis intéressé par le résultat. : p
The Communist Duck

Réponses:

6

Si vous ne trouvez pas un tel tableau de comparaison, l'alternative consiste à injecter un propre allocateur aux classes STL en question et à ajouter une journalisation.

L'implémentation que j'ai testée (VC 8.0) n'utilise aucune allocation de mémoire simplement en déclarant une chaîne / vecteur / deque, mais pour cela, elle liste et mappe. La chaîne a une optimisation de chaîne courte, car l'ajout de 3 caractères n'a pas déclenché d'allocation. La sortie est ajoutée sous le code.

// basic allocator implementation used from here
// http://www.codeguru.com/cpp/cpp/cpp_mfc/stl/article.php/c4079

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <map>

template <class T> class my_allocator;

// specialize for void:
template <> 
class my_allocator<void> 
{
public:
    typedef void*       pointer;
    typedef const void* const_pointer;
    // reference to void members are impossible.
    typedef void value_type;
    template <class U> 
    struct rebind 
    { 
        typedef my_allocator<U> other; 
    };
};

#define LOG_ALLOC_SIZE(call, size)      std::cout << "  " << call << "  " << std::setw(2) << size << " byte" << std::endl

template <class T> 
class my_allocator 
{
public:
    typedef size_t    size_type;
    typedef ptrdiff_t difference_type;
    typedef T*        pointer;
    typedef const T*  const_pointer;
    typedef T&        reference;
    typedef const T&  const_reference;
    typedef T         value_type;
    template <class U> 
    struct rebind 
    { 
        typedef my_allocator<U> other; 
    };

    my_allocator() throw() : alloc() {}
    my_allocator(const my_allocator&b) throw() : alloc(b.alloc) {}

    template <class U> my_allocator(const my_allocator<U>&b) throw() : alloc(b.alloc) {}
    ~my_allocator() throw() {}

    pointer       address(reference x) const                    { return alloc.address(x); }
    const_pointer address(const_reference x) const              { return alloc.address(x); }

    pointer allocate(size_type s, 
               my_allocator<void>::const_pointer hint = 0)      { LOG_ALLOC_SIZE("my_allocator::allocate  ", s * sizeof(T)); return alloc.allocate(s, hint); }
    void deallocate(pointer p, size_type n)                     { LOG_ALLOC_SIZE("my_allocator::deallocate", n * sizeof(T)); alloc.deallocate(p, n); }

    size_type max_size() const throw()                          { return alloc.max_size(); }

    void construct(pointer p, const T& val)                     { alloc.construct(p, val); }
    void destroy(pointer p)                                     { alloc.destroy(p); }

    std::allocator<T> alloc;
};

int main(int argc, char *argv[])
{

    {
        typedef std::basic_string<char, std::char_traits<char>, my_allocator<char> > my_string;

        std::cout << "===============================================" << std::endl;
        std::cout << "my_string ctor start" << std::endl;
        my_string test;
        std::cout << "my_string ctor end" << std::endl;
        std::cout << "my_string add 3 chars" << std::endl;
        test = "abc";
        std::cout << "my_string add a huge number of chars chars" << std::endl;
        test += "d df uodfug ondusgp idugnösndögs ifdögsdoiug ösodifugnösdiuödofu odsugöodiu niu od unoudö n nodsu nosfdi un abc";
        std::cout << "my_string copy" << std::endl;
        my_string copy = test;
        std::cout << "my_string copy on write test" << std::endl;
        copy[3] = 'X';
        std::cout << "my_string dtors start" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "vector ctor start" << std::endl;
        std::vector<int, my_allocator<int> > v;
        std::cout << "vector ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            v.push_back(i);
        }
        std::cout << "vector dtor starts" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "deque ctor start" << std::endl;
        std::deque<int, my_allocator<int> > d;
        std::cout << "deque ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            std::cout << "deque insert start" << std::endl;
            d.push_back(i);
            std::cout << "deque insert end" << std::endl;
        }
        std::cout << "deque dtor starts" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "list ctor start" << std::endl;
        std::list<int, my_allocator<int> > l;
        std::cout << "list ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            std::cout << "list insert start" << std::endl;
            l.push_back(i);
            std::cout << "list insert end" << std::endl;
        }
        std::cout << "list dtor starts" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "map ctor start" << std::endl;
        std::map<int, float, std::less<int>, my_allocator<std::pair<const int, float> > > m;
        std::cout << "map ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            std::cout << "map insert start" << std::endl;
            std::pair<int, float> a(i, (float)i);
            m.insert(a);
            std::cout << "map insert end" << std::endl;
        }
        std::cout << "map dtor starts" << std::endl;
    }

    return 0;
}

Jusqu'à présent, VC8 et STLPort 5.2 ont été testés, voici la comparaison (incluse dans le test: chaîne, vecteur, deque, liste, carte)

                    Allocation on declare   Overhead List Node      Overhead Map Node

VC8                 map, list               8 Byte                  16 Byte
STLPort 5.2 (VC8)   deque                   8 Byte                  16 Byte
Paulhodge's EASTL   (none)                  8 Byte                  16 Byte

Chaîne de sortie VC8 / vecteur / deque / list / map:

===============================================
my_string ctor start
my_string ctor end
my_string add 3 chars
my_string add a huge number of chars chars
  my_allocator::allocate    128 byte
my_string copy
  my_allocator::allocate    128 byte
my_string copy on write test
my_string dtors start
  my_allocator::deallocate  128 byte
  my_allocator::deallocate  128 byte

===============================================
vector ctor start
vector ctor end
  my_allocator::allocate     4 byte
  my_allocator::allocate     8 byte
  my_allocator::deallocate   4 byte
  my_allocator::allocate    12 byte
  my_allocator::deallocate   8 byte
  my_allocator::allocate    16 byte
  my_allocator::deallocate  12 byte
  my_allocator::allocate    24 byte
  my_allocator::deallocate  16 byte
vector dtor starts
  my_allocator::deallocate  24 byte

===============================================
deque ctor start
deque ctor end
deque insert start
  my_allocator::allocate    32 byte
  my_allocator::allocate    16 byte
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
  my_allocator::allocate    16 byte
deque insert end
deque dtor starts
  my_allocator::deallocate  16 byte
  my_allocator::deallocate  16 byte
  my_allocator::deallocate  32 byte

===============================================
list ctor start
  my_allocator::allocate    12 byte
list ctor end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list dtor starts
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte

===============================================
map ctor start
  my_allocator::allocate    24 byte
map ctor end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map dtor starts
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte

STLPort 5.2. sortie compilée avec VC8

===============================================
my_string ctor start
my_string ctor end
my_string add 3 chars
my_string add a huge number of chars chars
  my_allocator::allocate    115 byte
my_string copy
  my_allocator::allocate    115 byte
my_string copy on write test
my_string dtors start
  my_allocator::deallocate  115 byte
  my_allocator::deallocate  115 byte

===============================================
vector ctor start
vector ctor end
  my_allocator::allocate     4 byte
  my_allocator::deallocate   0 byte
  my_allocator::allocate     8 byte
  my_allocator::deallocate   4 byte
  my_allocator::allocate    16 byte
  my_allocator::deallocate   8 byte
  my_allocator::allocate    32 byte
  my_allocator::deallocate  16 byte
vector dtor starts
  my_allocator::deallocate  32 byte

===============================================
deque ctor start
  my_allocator::allocate    32 byte
  my_allocator::allocate    128 byte
deque ctor end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque dtor starts
  my_allocator::deallocate  128 byte
  my_allocator::deallocate  32 byte

===============================================
list ctor start
list ctor end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list dtor starts
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte

===============================================
map ctor start
map ctor end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map dtor starts
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte

Résultats EASTL , pas de déque disponible

===============================================
my_string ctor start
my_string ctor end
my_string add 3 chars
  my_allocator::allocate     9 byte
my_string add a huge number of chars chars
  my_allocator::allocate    115 byte
  my_allocator::deallocate   9 byte
my_string copy
  my_allocator::allocate    115 byte
my_string copy on write test
my_string dtors start
  my_allocator::deallocate  115 byte
  my_allocator::deallocate  115 byte

===============================================
vector ctor start
vector ctor end
  my_allocator::allocate     4 byte
  my_allocator::allocate     8 byte
  my_allocator::deallocate   4 byte
  my_allocator::allocate    16 byte
  my_allocator::deallocate   8 byte
  my_allocator::allocate    32 byte
  my_allocator::deallocate  16 byte
vector dtor starts
  my_allocator::deallocate  32 byte

===============================================
list ctor start
list ctor end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list dtor starts
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte

===============================================
map ctor start
map ctor end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map dtor starts
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
Maik Semder
la source
Ceci est utile pour obtenir les détails des allocations sous-jacentes, mais ne nous dit malheureusement rien sur la surcharge et les performances de cache attendues.
@Joe, c'est difficile de répondre à toutes vos questions en une seule réponse. Je ne sais pas exactement ce que tu veux dire par "frais généraux" et de plus, par rapport à quoi? Je pensais par frais généraux que vous entendiez la consommation de mémoire.
Maik Semder
Par "frais généraux", j'entendais plus la taille des instances vides des structures et tous leurs itérateurs associés, et comment les plus complexes gèrent l'allocation - par exemple, std :: list alloue-t-il en interne plus d'un nœud à la fois, ou dois-je payer le coût d'allocation de base pour chaque nœud, etc.?
1
La question n'est pas tant "Veuillez faire cette comparaison" que "où est une ressource pour cette comparaison" - je ne pense pas que SO soit un bon endroit pour la "maintenir". Vous devriez peut-être commencer à le lancer sur un site Google ou un wiki ou quelque chose.
1
@Joe bien maintenant c'est ici: p Je ne suis pas très intéressé à le déplacer vers un autre site, j'étais juste intéressé par les résultats.
Maik Semder
8

std::stringne copie pas en écriture. CoW était une optimisation, mais dès que plusieurs threads entrent dans l'image, c'est au-delà d'une pessimisation - cela peut ralentir le code par des facteurs massifs. C'est tellement mauvais que la norme C ++ 0x l'interdit activement en tant que stratégie d'implémentation. Non seulement cela, mais la permissivité de std::stringfaire des itérations et des références de caractères modifiables signifie que «écrire» pour std::stringimplique presque toutes les opérations.

L'optimisation de chaîne courte est d'environ 6 caractères, je crois, ou quelque chose dans cette région. Les cordes ne sont pas autorisées - std::stringdoivent stocker de la mémoire contiguë pour la c_str()fonction. Techniquement, vous pouvez conserver à la fois une corde contiguë et une corde dans la même classe, mais personne ne l'a jamais fait. De plus, d'après ce que je sais des cordes, les manipuler sans fil serait incroyablement lent, peut-être aussi mauvais ou pire que CoW.

Aucun conteneur ne fait d'allocation de mémoire en étant déclaré dans des STL modernes. Les conteneurs basés sur les nœuds, comme la liste et la carte, le faisaient auparavant, mais ils ont maintenant une optimisation de fin intégrée et n'en ont plus besoin. Il est courant d'effectuer une optimisation appelée "swaptimization" où vous échangez avec un conteneur vide. Considérer:

std::vector<std::string> MahFunction();
int main() {
    std::vector<std::string> MahVariable;
    MahFunction().swap(MahVariable);
}

Bien sûr, en C ++ 0x, cela est redondant, mais en C ++ 03, alors lorsque cela était couramment utilisé, si MahVariable alloue de la mémoire lors de la déclaration, cela réduit l'efficacité. Je sais vectorpertinemment que cela a été utilisé pour des réallocations plus rapides de conteneurs comme dans le MSVC9 STL, ce qui a supprimé le besoin de copier les éléments.

dequeutilise quelque chose appelé une liste chaînée non déroulée. Il s'agit essentiellement d'une liste de tableaux, généralement de taille fixe dans le nœud. En tant que tel, pour la plupart des utilisations, il conserve les avantages des deux structures de données - l'accès contigu et la suppression de O (1) amorti et la possibilité d'ajouter à la fois avant et arrière et une meilleure invalidation d'itérateur que vector. dequene peut jamais être implémenté par vecteur en raison de sa complexité algorithmique et des garanties d'invalidation de l'itérateur.

Quelle quantité de mémoire supplémentaire est associée? Eh bien, honnêtement, c'est une question sans valeur à poser. Les conteneurs STL sont conçus pour être efficaces, et si vous deviez répliquer leurs fonctionnalités, vous vous retrouveriez soit avec quelque chose de moins performant, soit au même endroit. En connaissant leurs structures de données sous-jacentes, vous pouvez connaître la surcharge de mémoire qu'ils utilisent, donnent ou prennent, et ce ne sera plus que pour une bonne raison, telle que l'optimisation de petites chaînes.

DeadMG
la source
"C'est tellement mauvais que la norme C ++ 0x l'interdit activement comme stratégie d'implémentation." Et ils l'interdisent parce que les implémentations précédentes l'ont utilisé ou ont essayé de l'utiliser. Vous vivez apparemment dans un monde où tout le monde utilise en permanence la dernière STL mise en œuvre de manière optimale. Cette réponse n'est pas du tout utile.
Je suis également curieux de savoir quelles propriétés de std :: deque vous pensez empêcher un stockage sous-jacent contigu - les itérateurs ne sont valides qu'après les suppressions au début / fin, pas au milieu ni après les insertions, ce qui peut facilement être fait avec un vecteur. Et l'utilisation d'un tampon circulaire semble répondre à toutes les garanties algorithmiques - O (1) inséré et supprimé amorti aux extrémités, O (n) supprimé au milieu.
3
@Joe: Je pense que CoW est considéré comme une mauvaise chose depuis la fin des années 90. Il y a des implémentations de chaînes qui l'ont utilisé - notamment CString - mais cela ne signifie pas que ce soit std::stringle cas à l'époque. Pour cela, vous n'avez pas besoin d'utiliser les dernières et meilleures implémentations STL. msdn.microsoft.com/en-us/library/22a9t119.aspx dit "Si un élément est inséré à l'avant, toutes les références restent valides". Vous ne savez pas comment vous comptez l'implémenter avec un tampon circulaire, car vous devrez redimensionner lorsqu'il sera plein.
DeadMG
Je ne vais certainement pas défendre COW en tant que technique de mise en œuvre, mais je ne suis pas non plus naïf quant à la fréquence à laquelle les logiciels continuent d'être mis en œuvre en utilisant de mauvaises techniques bien après qu'ils ont été identifiés comme pauvres. Par exemple, le test de Maik ci-dessus révèle un stdlib moderne qui alloue sur déclaration. Merci pour le pointeur sur la validité de référence deque. (Pour simplifier, un vecteur peut répondre à toutes les garanties concernant l'invalidation de l'itérateur et la complexité algorithmique; cette exigence n'est ni l'une ni l'autre.) Au contraire, je vois cela comme un besoin supplémentaire d'un document comme ma question le demande.
2

La question n'est pas tant "Veuillez faire cette comparaison" que "où est une ressource pour cette comparaison"

Si c'est vraiment votre question (qui n'est certainement pas ce que vous avez dit dans le texte de votre question, qui s'est terminé par 4 questions, dont aucune ne demandait où trouver une ressource), alors la réponse est simplement:

Il n'y en a pas.

La majorité des programmeurs C ++ n'ont pas à se soucier autant des frais généraux des structures de bibliothèque standard, de leurs performances de cache (qui dépendent de toute façon fortement du compilateur), ou de ce genre de choses. Sans oublier, vous n'avez généralement pas la possibilité de choisir votre implémentation de bibliothèque standard; vous utilisez ce qui vient avec votre compilateur. Donc, même si cela fait des choses désagréables, les options pour les alternatives sont limitées.

Il y a bien sûr des programmeurs qui se soucient de ce genre de choses. Mais ils ont tous juré d'utiliser la bibliothèque standard il y a longtemps.

Vous avez donc un groupe de programmeurs qui s'en fout tout simplement. Et un autre groupe de programmeurs qui se soucieraient s'ils l'utilisaient, mais comme ils ne l'utilisent pas, ils s'en moquent. Puisque personne ne s'en soucie, il n'y a pas de véritable information sur ce genre de chose. Il y a des correctifs informels ici et là (Effective C ++ a une section sur les implémentations std :: string et les grandes différences entre eux), mais rien de complet. Et certainement rien n'a été mis à jour.

Nicol Bolas
la source
Réponse spéculative. +1 pour probablement vrai, -1 pour aucun moyen de le prouver.
deceleratedcaviar
J'ai vu de nombreuses comparaisons très bonnes et détaillées dans le passé, mais elles sont toutes dépassées. Tout ce qui se passe avant l'introduction du mouvement est à peu près hors de propos de nos jours.
Peter - Unban Robert Harvey