IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

  1. #1
    Membre confirmé
    Avatar de ABD-Z
    Homme Profil pro
    Pro
    Inscrit en
    septembre 2016
    Messages
    191
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 24
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Pro

    Informations forums :
    Inscription : septembre 2016
    Messages : 191
    Points : 475
    Points
    475
    Par défaut Consommation de la mémoire d'une unordered_map
    Bonjour les devs,
    Ce qui me fait aimer le C++ à d'autres langages c'est son côté bas niveau. En effet, on peut calculer l'espace en octet d'une variable avec sizeof(<var ou type>).
    Comme je suis indécis quant au choix de ma structure de données, j'hésite entre un tableau pur ou une unordered_map. La rapidité d'accès n'est pas un soucis dans mon cas, ce qui me préoccupe le plus c'est l'espace mémoire.
    J'ai tenté de comparer un tableau de N structures bidons avec une unordered_map qui a comme clef un entier et comme valeur une structure bidon.
    En faisant sizeof(unordered_map), j'obtiens une valeur inférieur à sizeof(tableau_normal) ce qui me paraît bizarre mais surtout une valeur fixé sur 56 quelque soit la taille de la hashmap.

    J'ai déniché un code qui apparemment calcule la mémoire utilisé par une unordered_map, mais je ne suis pas très convaincu :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    #include <iostream>
    #include <unordered_map>
    using namespace std;
     
    struct S{
    char a;
    };
     
    #define SIZE 1000
    int main() {
      S array[SIZE];
      cout << "size array " << sizeof(array)<<endl;
      std::unordered_map<int, S> u;
      for(int i = 0; i< SIZE; ++i){
          S s;
          u[i] = s;
      }
      cout << "1)size unordered map " << sizeof(u)<<endl;
     
     
      size_t count = 0;
      for (unsigned i = 0; i < u.bucket_count(); ++i) {
        size_t bucket_size = u.bucket_size(i);
        if (bucket_size == 0) {
          count++;
        }
        else {
          count += bucket_size;
        }
      }
     
      cout << "2)size unordered map " << count<<endl;
     
      return 0;
    }
    Pour une taille de 1000 j'ai naturellement un tableau qui occupe 1000 octets (structure d'un char..), pour l'unordered map 1109.
    Ma question :
    Comment déterminer facilement et efficacement la taille mémoire de n'importe quelle variable de n'importe quel type?

  2. #2
    Rédacteur/Modérateur


    Homme Profil pro
    Network game programmer
    Inscrit en
    juin 2010
    Messages
    6 696
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 33
    Localisation : Canada

    Informations professionnelles :
    Activité : Network game programmer

    Informations forums :
    Inscription : juin 2010
    Messages : 6 696
    Points : 30 555
    Points
    30 555
    Billets dans le blog
    4
    Par défaut
    Citation Envoyé par ABD-Z Voir le message
    Comment déterminer facilement et efficacement la taille mémoire de n'importe quelle variable de n'importe quel type?
    C'est impossible.
    Pensez à consulter la FAQ ou les cours et tutoriels de la section C++.
    Un peu de programmation réseau ?
    Aucune aide via MP ne sera dispensée. Merci d'utiliser les forums prévus à cet effet.

  3. #3
    Membre expérimenté Avatar de Astraya
    Homme Profil pro
    Consommateur de café
    Inscrit en
    mai 2007
    Messages
    911
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 35
    Localisation : France

    Informations professionnelles :
    Activité : Consommateur de café
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : mai 2007
    Messages : 911
    Points : 1 739
    Points
    1 739
    Par défaut
    Pour compléter la response de @Bousk, c'est très compliqué voir impossible. Cela rentre dans le détail d'implémentation et ne sera pas directement consultable.
    En effet, le sizeof te retourne la taille d'un type sur la pile (stack) et non sur le tas (heap). Sizeof retourne une constante de compilation égale à la taille du type en octets.
    Cela marche bien mais tu ne peut pas obtenir la taille de l'allocation faite sur le tas car elle est dynamique ( grossie ou diminue en fonctionne du nombre d'élément dans ta std::unordered_map par exemple) et cette allocation dynamique n'est pas récupérable sauf si le containeur/class/struct te retourne exactement la taille qu'elle a alloué dynamiquement.
    Dans le cas d'un sizeof(std::unordered_map), le sizeof te retournera la taille du ou des pointeurs qui pointent vers l'allocation dynamique.
    Homer J. Simpson


  4. #4
    Membre confirmé
    Avatar de ABD-Z
    Homme Profil pro
    Pro
    Inscrit en
    septembre 2016
    Messages
    191
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 24
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Pro

    Informations forums :
    Inscription : septembre 2016
    Messages : 191
    Points : 475
    Points
    475
    Par défaut
    Bon d'accord, donc ce n'est pas trop faisable...
    Cependant je suis tomber sur ça : http://jsteemann.github.io/blog/2016...container-use/
    Et apparemment l'unordered map n'est pas très souhaitable pour mon cas car elle prend trop de place.
    Vous en pensez quoi de l'article?

  5. #5
    Membre régulier
    Homme Profil pro
    Étudiant
    Inscrit en
    juillet 2018
    Messages
    52
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Tarn (Midi Pyrénées)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : juillet 2018
    Messages : 52
    Points : 83
    Points
    83
    Par défaut override de new / delete
    Bonjour,

    Je ne poste pas pour donner mon avis sur l'article (je ne saurais pas quoi dire dessus), mais juste parce que je me disais que pour ta question de test de mémoire d'un objet quelconque, on peut chercher à overrider les opérateurs new et delete.
    En effet, l'allocation dans le tas se fait principalement avec ces deux opérateurs new / delete en C++. On peut toujours utiliser également malloc / free, mais je compte sur le fait que les objets de la STL ne les utilisent pas (j'espère).

    Du coup, pour connaître l'usage de la mémoire directement dans ton code, on peut se débrouiller avec un code comme celui qui suit (qui ne permet pas de calculer l'usage de la mémoire d'un objet spécifiquement, mais plutot celui entre deux lignes de code):
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
     
    #include <iostream>
    #include <unordered_map>
     
    static std::unordered_map<void*, int> alloc_sizes;
    static bool use_overrided_new_delete = false;
    static size_t heap_usage = 0;
    void* operator new(size_t size) {
        void* ptr = malloc(size);
        if (use_overrided_new_delete) {
            use_overrided_new_delete = false;
            //std::cout << "allocation of size: " << size << std::endl;
            alloc_sizes[ptr] = size;
            heap_usage += size;
            use_overrided_new_delete = true;
        }
        return ptr;
    }
    void operator delete(void* ptr) {
        if (use_overrided_new_delete) {
            size_t size = alloc_sizes[ptr];
            //std::cout << "deallocation of size " << size << std::endl;
            heap_usage -= size;
        }
        free(ptr);
    }
     
    #define SIZE 1000
     
    int main(int, char**) {
        use_overrided_new_delete = true;
        std::unordered_map<int, char> u;
        for(int i = 0; i < SIZE; ++i){
            u[i] = 0;
        }
        std::cout << "stack size: " << sizeof(u) << std::endl;
        std::cout << "heap usage: " << heap_usage << std::endl;
        //  On doit désactiver les overrides pour permettre la désallocation de
        // alloc_sizes sans seg fault
        use_overrided_new_delete = false;
        return 0;
    }
    Puisqu'on ne connaît pas "à haut niveau" la taille de l'objet lors d'un delete, je dois l'enregistrer (ici dans alloc_sizes) dans une map lors du new. Par contre, puisque la manipulation de cette map entraine également l'usage du new, j'utilise le booléen use_overrided pour éviter des appels infinis.

    Et j'obtiens pour la création d'un std::unordered_map<int, char> de 1000 éléments une taille de 27944 octets, ce qui est nettement plus que tes 1109 octets

  6. #6
    Membre expert
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    juin 2011
    Messages
    696
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : juin 2011
    Messages : 696
    Points : 3 362
    Points
    3 362
    Par défaut
    Citation Envoyé par AbsoluteLogic Voir le message
    Et j'obtiens pour la création d'un std::unordered_map<int, char> de 1000 éléments une taille de 27944 octets, ce qui est nettement plus que tes 1109 octets
    En même temps, le type de la clef et de la valeur ne sont pas les mêmes: int/char vs void*/int. Mais le calcul de ABD-Z est foireux, il prend en compte le nombre d'élément, mais pas leur taille.

    Sinon, pour calculer à peu près la taille utilisée, il faut mettre un allocateur personnalisé au container (paramètre template) et faire la somme. Ça ne prendra pas en compte la mémoire utilisée par les fonctions d'allocations, car cela dépend de l'implémentation, mais ce sera au moins une approximation.

  7. #7
    Membre régulier
    Homme Profil pro
    Étudiant
    Inscrit en
    juillet 2018
    Messages
    52
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Tarn (Midi Pyrénées)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : juillet 2018
    Messages : 52
    Points : 83
    Points
    83
    Par défaut
    Citation Envoyé par jo_link_noir Voir le message
    En même temps, le type de la clef et de la valeur ne sont pas les mêmes: int/char vs void*/int.
    On teste tous les deux un map int/char. Le void*/int est là juste pour l'enregistrement des tailles des allocations.

    Citation Envoyé par jo_link_noir Voir le message
    Mais le calcul de ABD-Z est foireux, il prend en compte le nombre d'élément, mais pas leur taille.
    Effectivement, c'est le nombre d'éléments. Du coup, il faut bien prendre en compte qu'un élément correspond à l'objet std::pair<int, char>.
    Dans mon cas :
    - le count calculé par son code est 1493
    - sizeof(char) est 1
    - sizeof(int) est 4
    - sizeof(std::pair<char, int>) est 8 (à cause de l'alignement des données j'imagine)
    - count * sizeof(std::pair<char, int>) est 11944
    Alors que heap usage est quand même à 27944.
    Donc il y a certainement des références vers les buckets qui prennent une place d'ordre linéaire également.

  8. #8
    Modérateur

    Avatar de Bktero
    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    juin 2009
    Messages
    4 371
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 33
    Localisation : France, Loire Atlantique (Pays de la Loire)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués

    Informations forums :
    Inscription : juin 2009
    Messages : 4 371
    Points : 13 180
    Points
    13 180
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par AbsoluteLogic Voir le message
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    int main(int, char**) {
        use_overrided_new_delete = true;
        std::unordered_map<int, char> u;
        for(int i = 0; i < SIZE; ++i){
            u[i] = 0;
        }
        std::cout << "stack size: " << sizeof(u) << std::endl;
        std::cout << "heap usage: " << heap_usage << std::endl;
        //  On doit désactiver les overrides pour permettre la désallocation de
        // alloc_sizes sans seg fault
        use_overrided_new_delete = false;
        return 0;
    }
    Et j'obtiens pour la création d'un std::unordered_map<int, char> de 1000 éléments une taille de 27944 octets, ce qui est nettement plus que tes 1109 octets
    Ca donne quoi en faisant les std::cout << après use_overrided_new_delete = false; ?

  9. #9
    Membre régulier
    Homme Profil pro
    Étudiant
    Inscrit en
    juillet 2018
    Messages
    52
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Tarn (Midi Pyrénées)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : juillet 2018
    Messages : 52
    Points : 83
    Points
    83
    Par défaut
    Citation Envoyé par Bktero Voir le message
    Ca donne quoi en faisant les std::cout << après use_overrided_new_delete = false; ?
    Si tu parles des couts dans les new / delete, ça donne ça avec 10 éléments (je t'épargne les 1000 éléments dont on parlait avant):
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    allocation of size: 16
    allocation of size: 24
    allocation of size: 16
    allocation of size: 16
    allocation of size: 56
    deallocation of size 24
    allocation of size: 16
    allocation of size: 16
    allocation of size: 16
    allocation of size: 16
    allocation of size: 136
    deallocation of size 56
    allocation of size: 16
    allocation of size: 16
    allocation of size: 16
    stack size: 56
    heap usage: 296
    On peut reconnaître les 10 ajouts d'éléments de 16 octets (8 pour la paire clé/valeur + 8 pour le pointeur vers l'élément suivant du bucket). On voit également que pour la "base" des buckets, des allocations de 24, puis 56, puis 136 octets sont faites en désallouant à chaque fois la base précédente.

  10. #10
    Rédacteur/Modérateur


    Homme Profil pro
    Network game programmer
    Inscrit en
    juin 2010
    Messages
    6 696
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 33
    Localisation : Canada

    Informations professionnelles :
    Activité : Network game programmer

    Informations forums :
    Inscription : juin 2010
    Messages : 6 696
    Points : 30 555
    Points
    30 555
    Billets dans le blog
    4
    Par défaut
    Oui tu peux jouer en surchargeant les allocations. Ce sera pas mal la seule solution, mais ce n'est pas une solution simple.
    Le mieux étant sûrement d'utiliser les paramètres template pour remplacer les allocateurs plutôt que de modifier l'allocateur global.
    Pensez à consulter la FAQ ou les cours et tutoriels de la section C++.
    Un peu de programmation réseau ?
    Aucune aide via MP ne sera dispensée. Merci d'utiliser les forums prévus à cet effet.

  11. #11
    Membre régulier
    Homme Profil pro
    Étudiant
    Inscrit en
    juillet 2018
    Messages
    52
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Tarn (Midi Pyrénées)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : juillet 2018
    Messages : 52
    Points : 83
    Points
    83
    Par défaut
    Mais l'allocateur personnalisé du template ne permet de considérer que l'allocation des pairs. L'allocateur global permet de compter également tout ce qui est nécessaire au fonctionnement de la structure, donc, pour l'exemple de l'unordered_map, les "pointeurs" entre éléments du bucket, et la base des buckets.
    Ensuite, l'allocateur global est je pense la seule réponse à la question de ABD-Z...
    Comment déterminer facilement et efficacement la taille mémoire de n'importe quelle variable de n'importe quel type?
    ... non seulement pour la raison ci-dessus, mais aussi parce qu'un objet ne permet pas forcément de définir son allocateur.
    J'admets cependant que la réponse n'est pas parfaite puisqu'elle ne permet pas d'isoler les allocations / désallocations pour un objet spécifiquement, si on manipule plusieurs objets à la fois.

  12. #12
    Membre expert
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    juin 2011
    Messages
    696
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : juin 2011
    Messages : 696
    Points : 3 362
    Points
    3 362
    Par défaut
    Citation Envoyé par AbsoluteLogic Voir le message
    Mais l'allocateur personnalisé du template ne permet de considérer que l'allocation des pairs. L'allocateur global permet de compter également tout ce qui est nécessaire au fonctionnement de la structure, donc, pour l'exemple de l'unordered_map, les "pointeurs" entre éléments du bucket, et la base des buckets.
    L'allocateur prend en compte toutes les allocations effectuées par le container

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    #include <unordered_map>
    #include <cstdio>
     
    template<class T>
    struct MyAllocator 
    {
      using value_type = T;
     
      MyAllocator() = default;
      template <class U> constexpr MyAllocator(MyAllocator<U> const&) noexcept {}
     
      [[nodiscard]] T* allocate(std::size_t n) {
        puts(__PRETTY_FUNCTION__);
        return std::allocator<T>().allocate(n);
      }
     
      void deallocate(T* p, std::size_t n) noexcept {
        puts(__PRETTY_FUNCTION__);
        std::allocator<T>().deallocate(p, n);
      }
    };
     
    template <class T, class U>
    bool operator==(const MyAllocator<T>&, const MyAllocator<U>&) { return true; }
    template <class T, class U>
    bool operator!=(const MyAllocator<T>&, const MyAllocator<U>&) { return false; }
     
    int main()
    {
      std::unordered_map<int,int, std::hash<int>, std::equal_to<int>, MyAllocator<std::pair<const int, int>>>
    m;
      m.emplace(0,0);
    }
    T* MyAllocator<T>::allocate(std::size_t) [with T = std::__detail::_Hash_node<std::pair<const int, int>, false>; std::size_t = long unsigned int]
    T* MyAllocator<T>::allocate(std::size_t) [with T = std::__detail::_Hash_node_base*; std::size_t = long unsigned int]
    void MyAllocator<T>::deallocate(T*, std::size_t) [with T = std::__detail::_Hash_node<std::pair<const int, int>, false>; std::size_t = long unsigned int]
    void MyAllocator<T>::deallocate(T*, std::size_t) [with T = std::__detail::_Hash_node_base*; std::size_t = long unsigned int]
    Il y a bien une allocation des paires et des pointeurs, mais dans 2 allocateurs différents dont le second est construit depuis le premier (ctor template).

  13. #13
    Membre confirmé
    Avatar de ABD-Z
    Homme Profil pro
    Pro
    Inscrit en
    septembre 2016
    Messages
    191
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 24
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Pro

    Informations forums :
    Inscription : septembre 2016
    Messages : 191
    Points : 475
    Points
    475
    Par défaut
    Citation Envoyé par AbsoluteLogic Voir le message
    Bonjour,

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
     
    #include <iostream>
    #include <unordered_map>
     
    static std::unordered_map<void*, int> alloc_sizes;
    static bool use_overrided_new_delete = false;
    static size_t heap_usage = 0;
    void* operator new(size_t size) {
        void* ptr = malloc(size);
        if (use_overrided_new_delete) {
            use_overrided_new_delete = false;
            //std::cout << "allocation of size: " << size << std::endl;
            alloc_sizes[ptr] = size;
            heap_usage += size;
            use_overrided_new_delete = true;
        }
        return ptr;
    }
    void operator delete(void* ptr) {
        if (use_overrided_new_delete) {
            size_t size = alloc_sizes[ptr];
            //std::cout << "deallocation of size " << size << std::endl;
            heap_usage -= size;
        }
        free(ptr);
    }
     
    #define SIZE 1000
     
    int main(int, char**) {
        use_overrided_new_delete = true;
        std::unordered_map<int, char> u;
        for(int i = 0; i < SIZE; ++i){
            u[i] = 0;
        }
        std::cout << "stack size: " << sizeof(u) << std::endl;
        std::cout << "heap usage: " << heap_usage << std::endl;
        //  On doit désactiver les overrides pour permettre la désallocation de
        // alloc_sizes sans seg fault
        use_overrided_new_delete = false;
        return 0;
    }
    Puisqu'on ne connaît pas "à haut niveau" la taille de l'objet lors d'un delete, je dois l'enregistrer (ici dans alloc_sizes) dans une map lors du new. Par contre, puisque la manipulation de cette map entraine également l'usage du new, j'utilise le booléen use_overrided pour éviter des appels infinis.

    Et j'obtiens pour la création d'un std::unordered_map<int, char> de 1000 éléments une taille de 27944 octets, ce qui est nettement plus que tes 1109 octets
    Cette réponse me convient, ça a l'air d'être bien plus simple à comprendre que les Allocator même si c'est pas top de modifier les opérateurs globaux new et delete.
    En tout cas, là j'ai bien un ordre de grandeur quant aux unordered_map... Ça prend trop de place!
    Après l'avantage, peut-être, des unordered_map dans mon application c'est qu'il se peut que le tableau soit très peux remplis.
    Si je prends le cas où la taille maximale du tableau est de 255, il se peut que le tableau ne contienne rien! C'est une possibilité, et donc j'aurais quand même 255 * sizeof(<type dans le tableau>) alors que dans une unordered_map, j'aurais une consommation de la mémoire qui serait bien moindre.
    D'ailleurs en farfouillant sur Internet, j'ai appris que l'accès au tas est bien plus coûteux en temps comparé à la pile, ce qui semble être bien normal. Donc, comme les unordered_map allouent dynamiquement de la mémoire, comme une bonne majorité des structures de données de la STL, il me semble vrai de dire que l'accès direct à un tableau nature est bien plus rapide que l'accès direct à une unordered_map.
    Soit t un tableau de N éléments et u une unordered_map de N éléments aussi, l'accès à l'élément se trouvant à n par t[n] est plus rapide que u[n]. Mon affirmation est-elle vraie?

  14. #14
    Expert éminent
    Homme Profil pro
    Ingénieur développement matériel électronique
    Inscrit en
    décembre 2015
    Messages
    1 259
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Ingénieur développement matériel électronique
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : décembre 2015
    Messages : 1 259
    Points : 6 106
    Points
    6 106
    Par défaut
    Citation Envoyé par ABD-Z Voir le message
    Cette réponse me convient, ça a l'air d'être bien plus simple à comprendre que les Allocator même si c'est pas top de modifier les opérateurs globaux new et delete.
    En tout cas, là j'ai bien un ordre de grandeur quant aux unordered_map... Ça prend trop de place!
    Après l'avantage, peut-être, des unordered_map dans mon application c'est qu'il se peut que le tableau soit très peux remplis.
    Si je prends le cas où la taille maximale du tableau est de 255, il se peut que le tableau ne contienne rien! C'est une possibilité, et donc j'aurais quand même 255 * sizeof(<type dans le tableau>) alors que dans une unordered_map, j'aurais une consommation de la mémoire qui serait bien moindre.
    D'ailleurs en farfouillant sur Internet, j'ai appris que l'accès au tas est bien plus coûteux en temps comparé à la pile, ce qui semble être bien normal. Donc, comme les unordered_map allouent dynamiquement de la mémoire, comme une bonne majorité des structures de données de la STL, il me semble vrai de dire que l'accès direct à un tableau nature est bien plus rapide que l'accès direct à une unordered_map.
    Soit t un tableau de N éléments et u une unordered_map de N éléments aussi, l'accès à l'élément se trouvant à n par t[n] est plus rapide que u[n]. Mon affirmation est-elle vraie?
    Les allocations dynamiques plus couteuses que sur la pile, oui. Une réservation pile c'est de 0 à 2 instructions, ça prend moins de 0,3ns, une allocation dynamique ça doit faire environ 5ns (et plus en multi-thread). Mais si le but est de réserver un tableau de 1000 entiers à initialiser, ça fait 200+0,3ns par rapport à 200+5ns, l'écart relatif est ridicule.
    Le problème dépend du taux d'éléments qui seront présents dans le tableau. S'il s'agit de moins de quelques pourcents l'unordered_map peut être optimale, s'il s'agit de plus de 20% le tableau sera meilleur (j'ai donné des % mais c'est à valider en fonction des cas.)
    Accéder à un tableau est normalement plus rapide qu'à une unordered_map. Mais si le tableau est très grand et très vide, il y a un grand risque d'avoir des "caches mises", et alors l'unordered_map sera plus finalement plus rapide. En voulant estimer la taille de l'unordered_map tu es sur une bonne piste. Le plus petit à des chances d'être le plus optimal.

  15. #15
    Membre régulier
    Homme Profil pro
    Étudiant
    Inscrit en
    juillet 2018
    Messages
    52
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Tarn (Midi Pyrénées)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : juillet 2018
    Messages : 52
    Points : 83
    Points
    83
    Par défaut
    Citation Envoyé par jo_link_noir Voir le message
    L'allocateur prend en compte toutes les allocations effectuées par le container

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    #include <unordered_map>
    #include <cstdio>
     
    template<class T>
    struct MyAllocator 
    {
      using value_type = T;
     
      MyAllocator() = default;
      template <class U> constexpr MyAllocator(MyAllocator<U> const&) noexcept {}
     
      [[nodiscard]] T* allocate(std::size_t n) {
        puts(__PRETTY_FUNCTION__);
        return std::allocator<T>().allocate(n);
      }
     
      void deallocate(T* p, std::size_t n) noexcept {
        puts(__PRETTY_FUNCTION__);
        std::allocator<T>().deallocate(p, n);
      }
    };
     
    template <class T, class U>
    bool operator==(const MyAllocator<T>&, const MyAllocator<U>&) { return true; }
    template <class T, class U>
    bool operator!=(const MyAllocator<T>&, const MyAllocator<U>&) { return false; }
     
    int main()
    {
      std::unordered_map<int,int, std::hash<int>, std::equal_to<int>, MyAllocator<std::pair<const int, int>>>
    m;
      m.emplace(0,0);
    }


    Il y a bien une allocation des paires et des pointeurs, mais dans 2 allocateurs différents dont le second est construit depuis le premier (ctor template).
    Ah oui, effectivement, je me suis mépris sur l'usage des allocateurs fournis aux structures de la STL. J'ai donc pu tester en remplaçant le puts(__PRETTY_FUNCTION__) par std::cout << "allocation of size: " << n * sizeof(T) << std::endl;, et on obtient bien le même résultat.
    Cette méthode est donc meilleure si l'objet accepte un allocateur personnalisé qu'il utilise bien partout. De plus, s'il acceptait une instance d'allocateur plutôt qu'une classe en template, on aurait même pu compter la mémoire utilisée réellement associée à un objet. Mais j'imagine là qu'on doit quand même utiliser une variable static pour compter, et qu'on ne peut donc quand même pas distinguer les objets.

  16. #16
    Rédacteur/Modérateur


    Homme Profil pro
    Network game programmer
    Inscrit en
    juin 2010
    Messages
    6 696
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 33
    Localisation : Canada

    Informations professionnelles :
    Activité : Network game programmer

    Informations forums :
    Inscription : juin 2010
    Messages : 6 696
    Points : 30 555
    Points
    30 555
    Billets dans le blog
    4
    Par défaut
    Citation Envoyé par AbsoluteLogic Voir le message
    De plus, s'il acceptait une instance d'allocateur plutôt qu'une classe en template, on aurait même pu compter la mémoire utilisée réellement associée à un objet. Mais j'imagine là qu'on doit quand même utiliser une variable static pour compter, et qu'on ne peut donc quand même pas distinguer les objets.
    Quelle chance, il suffit de lire la doc pour y voir un constructeur qui... prend un allocateur en paramètre.

    Y'a-t-il un vrai cas concret ou c'est juste pour jaser ?
    Parce que si tu veux vraiment faire un truc performant, alors oui tu peux créer ton propre allocateur, celui-ci peut allouer dans de la mémoire contigüe et limiter les cache-miss quand tu itères sur la collection.
    Mais dans ce cas-là, on est sencé connaître ce que sont les allocateurs et savoir les utiliser. Je n'en ai personnellement jamais écrit, j'ai des collègues qui font ça mieux que moi.
    Et il faut profiler un peu plus précisément qu'au doigt mouillé lequel est le plus rapide ou non, et dans quels conditions.
    Les options ne sont pas "tableau dans la stack vs unordered_map dans la heap".
    Pensez à consulter la FAQ ou les cours et tutoriels de la section C++.
    Un peu de programmation réseau ?
    Aucune aide via MP ne sera dispensée. Merci d'utiliser les forums prévus à cet effet.

  17. #17
    Membre régulier
    Homme Profil pro
    Étudiant
    Inscrit en
    juillet 2018
    Messages
    52
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Tarn (Midi Pyrénées)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : juillet 2018
    Messages : 52
    Points : 83
    Points
    83
    Par défaut
    Citation Envoyé par Bousk Voir le message
    Quelle chance, il suffit de lire la doc pour y voir un constructeur qui... prend un allocateur en paramètre. .
    Bon, il semblerait que je sois plus là pour apprendre que pour aider

    Du coup, j'ai repris le code de jo_link_noir pour le rendre "dynamique". On obtient l'allocateur suivant :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    template<class T>
    struct UsageAllocator
    {
        using value_type = T;
     
        size_t& usage;
     
        UsageAllocator(size_t& usage) : usage(usage) {}
        template <class U> constexpr UsageAllocator(UsageAllocator<U> const& other) noexcept : usage(other.usage) {}
     
        [[nodiscard]] T* allocate(std::size_t n) {
            usage += n * sizeof(T);
            return std::allocator<T>().allocate(n);
        }
     
        void deallocate(T* p, std::size_t n) noexcept {
            usage -= n * sizeof(T);
            std::allocator<T>().deallocate(p, n);
        }
    };
     
    template <class T, class U>
    bool operator==(const UsageAllocator<T>&, const UsageAllocator<U>&) { return true; }
    template <class T, class U>
    bool operator!=(const UsageAllocator<T>&, const UsageAllocator<U>&) { return false; }
    Qui s'utilise comme suit :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    // Initialisation de l'objet
    size_t u_usage = 0;
    UsageAllocator<std::pair<const int, char>> u_alloc(u_usage);
    std::unordered_map<int, char, std::hash<int>, std::equal_to<int>, UsageAllocator<std::pair<const int, char>>> u(u_alloc);
    // On fait des trucs avec l'objet
    for(int i = 0; i < SIZE; ++i){
        u[i] = 0;
    }
    // Et on peut accéder à tout moment à la place allouée dans le tas pour cet objet
    std::cout << "heap usage object: " << u_usage << std::endl;
    Ainsi, on peut connaître la mémoire qu'occupe une variable spécifiquement, même si on utilise plusieurs instances à la fois, s'il s'agit de structures acceptant des allocateurs personnalisés.

  18. #18
    Rédacteur/Modérateur


    Homme Profil pro
    Network game programmer
    Inscrit en
    juin 2010
    Messages
    6 696
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 33
    Localisation : Canada

    Informations professionnelles :
    Activité : Network game programmer

    Informations forums :
    Inscription : juin 2010
    Messages : 6 696
    Points : 30 555
    Points
    30 555
    Billets dans le blog
    4
    Par défaut
    C'est mieux. Je vois pas par contre pourquoi usage serait une variable externe référencée quand elle peut être simplement interne à l'allocateur.
    Pensez à consulter la FAQ ou les cours et tutoriels de la section C++.
    Un peu de programmation réseau ?
    Aucune aide via MP ne sera dispensée. Merci d'utiliser les forums prévus à cet effet.

  19. #19
    Membre expert
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    juin 2011
    Messages
    696
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : juin 2011
    Messages : 696
    Points : 3 362
    Points
    3 362
    Par défaut
    Il n'est pas possible de récupérer tous les allocateurs instanciés par le container (pour rappel, il y en a 2), seul celui de base est accessible via std::unordered_map::get_allocator(). On peut magouiller pour que allocator::rebind crée un allocateur qui référence le premier pour partager le compteur, mais ici, ce que fait AbsoluteLogic est plus simple.

  20. #20
    Membre confirmé
    Avatar de ABD-Z
    Homme Profil pro
    Pro
    Inscrit en
    septembre 2016
    Messages
    191
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 24
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Pro

    Informations forums :
    Inscription : septembre 2016
    Messages : 191
    Points : 475
    Points
    475
    Par défaut
    Citation Envoyé par dalfab Voir le message
    Les allocations dynamiques plus couteuses que sur la pile, oui. Une réservation pile c'est de 0 à 2 instructions, ça prend moins de 0,3ns, une allocation dynamique ça doit faire environ 5ns (et plus en multi-thread). Mais si le but est de réserver un tableau de 1000 entiers à initialiser, ça fait 200+0,3ns par rapport à 200+5ns, l'écart relatif est ridicule.
    Ce qui me préoccupe surtout c'est pas vraiment le temps de réservation ou d'allocation mais surtout le temps d'accès.




    Citation Envoyé par dalfab Voir le message
    Le problème dépend du taux d'éléments qui seront présents dans le tableau. S'il s'agit de moins de quelques pourcents l'unordered_map peut être optimale, s'il s'agit de plus de 20% le tableau sera meilleur (j'ai donné des % mais c'est à valider en fonction des cas.).
    Tu parles ici du temps d'accès?




    Citation Envoyé par dalfab Voir le message
    Accéder à un tableau est normalement plus rapide qu'à une unordered_map. Mais si le tableau est très grand et très vide, il y a un grand risque d'avoir des "caches mises", et alors l'unordered_map sera plus finalement plus rapide. En voulant estimer la taille de l'unordered_map tu es sur une bonne piste. Le plus petit à des chances d'être le plus optimal.
    Donc si le tableau est en général plus rapide en accès, ça veut dire qu'il faut que je privilégie absolument les tableaux statiques. Mais j'ai pas compris l'histoire du cache, en quoi le fait de mettre le tableau vide et grand dans le cache soit contre performant?
    En tout cas on est bien d'accord, l'accès à un tableau nature est bien plus rapide qu'un tableau alloué dynamiquement avec new contenant des éléments alloués dynamiquement.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
     
    #define PLACE 255
    //tableau statique
    <type> tab_nature[PLACE ]; //réservation
    tab_nature[PLACE -1] = <valeur>;//écriture 
    <type> e = tab_nature[PLACE -1];//accès
     
    //tableau dynamique
    <type>** tab_dynam = new <type>*[PLACE]; //allocation dynamique
    tab_dynam = new <type>(<valeur>); //écriture
    <type> e = *tab_dynam[PLACE - 1];//accès
    En tout cas il me semble que le tableau statique soit meilleur dans ce cas de figure que cela soit pour la réservation, l'écriture et même l'accès.
    Si je pose toutes ces questions c'est parce que je me suis rendu compte qu'en privilégiant l'allocation dynamique pour tout et n'importe quoi, ceci a un impact sur les performances vérifiable par le taux d'utilisation du CPU.
    Mon projet consiste à pouvoir écrire sa musique en C++, il reprend un peu les fonctionnalités des trackers (comme FamiTracker ou Deflemask) sauf qu'au lieu de rentrer les instructions dans une interface graphique, ceci se fait directement dans le code (d'où C0deTracker : https://github.com/ABD-Z/C0deTracker).
    Un track (musique) peut jouer simultanément N sons grâce à l'intermédiaire de N canaux. Chaque canal possède ses propres instructions, possédant chacune un tableau dynamique crée si besoin pour stocker les codes d'effets audio, stockés dans des tableaux dynamiques stockés dans des structures de paternes dynamiques aussi.. bref tout est pointeurs de pointeurs.
    Quand je fais tourner de la musique en temps réel via SFML (j'ai implémenté une classe qui hérite de sf::SoundStream), le programme rempli un buffer d'échantillons cadencés à 48 kHz. La durée du buffer étant de 0.5 ou 1 seconde, sa taille est donc de 24000 ou 48000 respectivement (en réalité deux fois plus car je gère l'audio en stéréo).
    Et pour chaque échantillon, à chaque tour je joue le track ce qui consiste à jouer des instruments dans chaque canal et faire les traitements audio qu'il faut pour ensuite à la fin additionner tous les échantillons ensembles.
    Pour résumer, si le buffer est de 1 seconde et qu'on a N canal, le programme doit donc effectuer 48000*N*<traitement dans chaque canal soit accès aux éléments dans les tableaux dynamiques> toutes les secondes.
    Avec un nombre de canal inférieur à 5, l'usage du CPU est acceptable, plus ou moins. C'est à partir de 8 canaux que ça commence à devenir un souci car le processus tape dans les 20-25% voire mêmes les 30%.
    Si je vous parle de tous ça, c'était pour en être sûr si en changeant les structures de données de manière à ce qu'elles soient le plus statiques possible j'aurais de meilleurs performances et ainsi réduire le % du CPU, sans multi threading dans un premier temps (ça sera pour la prochaine étape : un canal = un thread).

Discussions similaires

  1. Réponses: 2
    Dernier message: 21/10/2017, 22h14
  2. Une lecture de fichier midi qui consomme trop de mémoire
    Par padodanle51 dans le forum Général Java
    Réponses: 6
    Dernier message: 12/04/2008, 11h52
  3. [Images] Erreur liée à une consommation excessive de mémoire
    Par cyrill.gremaud dans le forum Bibliothèques et frameworks
    Réponses: 15
    Dernier message: 04/11/2007, 22h55
  4. Utilisation Mémoire d'une application
    Par scorplex dans le forum Composants VCL
    Réponses: 8
    Dernier message: 21/05/2005, 03h01
  5. Problème mémoire avec une dll par chargement dynamique
    Par widze19 dans le forum C++Builder
    Réponses: 6
    Dernier message: 15/12/2003, 13h20

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo