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

Langage C++ Discussion :

Optimisation usage mémoire cache et fuite mémoire


Sujet :

Langage C++

  1. #1
    Membre régulier
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    septembre 2006
    Messages
    37
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

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

    Informations forums :
    Inscription : septembre 2006
    Messages : 37
    Points : 71
    Points
    71
    Par défaut Optimisation usage mémoire cache et fuite mémoire
    Bonjour,

    J'ai effectué une optimisation de la vitesse de calcul d'une opération en optimisant la mémoire cache et je me pose des questions sur la libération de la mémoire cache pour éviter des fuites mémoires.

    J'ai une liste d'objet de types différents qui héritent d'une classe commune. En temps normal, j'utiliserais une liste de pointeur vers cette classe commune et je ferrais un simple parcours de la liste. Cela signifie que l'on a une liste d'adresse mémoire, cette liste d'adresse est elle même allouée à un emplacement particulier.

    En terme de gestion de la mémoire, cela signifie que le programme va faire un accès à adresse mémoire de la liste, ce qui enclenche un chargement dans la mémoire cache d'une portion de la RAM qui contient cette liste d'adresse. Ensuite lorsque l'on accede à un élément de la liste, on va charger dans la mémoire cache la portion qui concerne cet objet. Enfin, une fois l'objet traité, on accède de nouveau à la liste en chargeant de nouveau la mémoire cache. Ainsi à chaque changement de portion de mémoire, on perd du temps. Sans compter que le traitement d'un objet peut dépendre d'un objet voisin ce qui demande d'autres mise à jour de la mémoire cache.

    La solution que j'ai implémenté consiste à utiliser une liste chaînée dont les objets sont placés de manière consécutive dans la mémoire, ainsi les chargements de la mémoire cache deviennent plus rare.

    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
     
    // exemple de trois objets de type différents qui héritent de ClassP
    // 1) taille de chaque type de classe
    uint sizeA = sizeof(ClassA);
    uint sizeB = sizeof(ClassB);
    uint sizeC = sizeof(ClassC);
    // 2) allocation de l'espace mémoire et calcul des adresses des futurs objets 
    void* address = malloc(sizeA+sizeB+sizeC);
    void* addressA = address;
    void* addressB = addressA+sizeA; // l'addition n'étant pas valable pour le void* en réalité je passe par un cast vers char*, je n'écris pas ces opérations par soucis de lisibilité
    void* addressC = addressB+sizeB;
    // 3) creation des objets aux addresses définies
    ClassA* a = new(addressA) ClassA(); // a == addressA == address
    ClassB* b = new(addressB) ClassB(); // b == addressB
    ClassC* c = new(addressC) ClassC(); // c == addressC
    // 4) paramétrage des objets
    a->next = b;
    b->next = c;
    c->next = nullptr;
    // 5) traitement
    ClassP *current = a;
    do
    {
      a->exec();
      current = current->next;
    }
    while(current != nullptr)
    // 6) liberation de l'espace mémoire
    delete a;
    delete b,
    delete c;
    free(address);
    tout d'abord, ai-je réinventé la roue et existe t'il un type standard de liste permettant d'effectuer la même opération?

    ensuite, ce qui me gène est la libération de l'espace mémoire:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
     
    delete a; // a == address
    free(address);
    je fais appel à 'delete a' pour accéder au destructeur avant de désallouer, mais dans les faits je désalloue deux fois la même adresse mémoire (ce qui ne fonctionne pas).

    j'imagine que lors de l'allocation, il existe une liste dans le système de gestion du programme qui fait le lien entre les addresses et la taille des objets alloués. De cette manière si j'alloue l'emplacement pour un objet le programme est capable d’empêcher une allocation sur cet espace mémoire et de désallouer la bonne taille.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
     
    char* c = (char*) malloc(15);
    free(c) // on n'indique pas la taille à la libération, cela signifie que le programme connait la taille de l'allocation d'une autre manière
     
    ClassP* p = new ClassA();
    delete(p) // on a perdu l'information de la classe d'origine: sizeof(ClassA) != sizeof(classP),
              // donc le programme connait la taille de l'allocation sans avoir besoin de connaitre le type
    Dans mon exemple plus haut, j'effectue une sorte de double allocation et je désalloue deux fois.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     
    void* address = malloc(size)
    ClassA* a = new(address) ClassA();
    delete a;
    free(address);
    - Est ce que `delete a` seul ne désalloue pas en même temps le pointeur address?
    - Est ce que `free(address)` est il suffisant pour désallouer en même temps `a`, `b` et `c`? quid du destructeur?

    merci d'avance

  2. #2
    Membre averti

    Profil pro
    Inscrit en
    décembre 2013
    Messages
    322
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : décembre 2013
    Messages : 322
    Points : 425
    Points
    425
    Par défaut
    > tout d'abord, ai-je réinventé la roue et existe t'il un type standard de liste permettant d'effectuer la même opération?

    Non, mais ce que tu veux faire ressemble au pattern Object Pool. Cf par exemple https://gameprogrammingpatterns.com/object-pool.html

    > je fais appel à 'delete a' pour accéder au destructeur avant de désallouer, mais dans les faits je désalloue deux fois la même adresse mémoire (ce qui ne fonctionne pas).
    > Est ce que `delete a` seul ne désalloue pas en même temps le pointeur address?
    > Est ce que `free(address)` est il suffisant pour désallouer en même temps `a`, `b` et `c`? quid du destructeur?

    Oui. C'est un des rares cas où appeler directement le destructeur (donc sans passer par delete) est valide. Cf les codes d'exemple de la doc : https://en.cppreference.com/w/cpp/la...#Placement_new

    Dans tous les cas, mesures bien les performances. Parce que c'est typiquement le genre d'optimisation qui peut avoir un gain nul (ou négligeable) si ce n'est pas nécessaire. D'ailleurs, as tu décidé de faire cela parce que tu as observer une perte de performance due au cache en faisant du profiling ? Ou c'est juste une optimisation random ?

  3. #3
    Membre expert
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    juin 2011
    Messages
    628
    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 : 628
    Points : 3 093
    Points
    3 093
    Par défaut
    Cela me fait penser à Boost.intrusive, le pool d'allocation en moins. La liste ne gère pas l'allocation qui se fait à l'extérieur, même si celle-ci peut contenir des nœuds de pointeur comme unique_ptr et contenir des types différents (manipulé sous la forme d'un pointeur commun).

    Pour le pool, mon avis que std::pmr::unsynchronized_pool_resource fait le taf. Voir carrément un std::list avec cet allocateur.

    Le faire à la main impose pas mal de piège et manipulation manuelle. Par exemple, ici tu ne prends pas en compte l'alignement des classes, cela peut fonctionner au prix d'un surcoût sur certaines architectures et un plantage sur d'autres.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
     
    struct A{char c;};
    struct B{int i;};
    struct C{A a; B; };
     
    sizeof(A) == 1
    sizeof(B) == 4
    sizeof(C) == 8
     
    new(addr + sizeA) B => l'instance n'est pas aligné sur la frontière d'un int.
    Chose qui peut être corrigé avec std::align.

  4. #4
    Membre régulier
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    septembre 2006
    Messages
    37
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

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

    Informations forums :
    Inscription : septembre 2006
    Messages : 37
    Points : 71
    Points
    71
    Par défaut
    Bonjour, merci pour vos réponse, j'ai été négligeant de ne pas répondre plus tôt, je vous prie de m'en excuser.

    Dans tous les cas, mesures bien les performances. Parce que c'est typiquement le genre d'optimisation qui peut avoir un gain nul (ou négligeable) si ce n'est pas nécessaire. D'ailleurs, as tu décidé de faire cela parce que tu as observer une perte de performance due au cache en faisant du profiling ? Ou c'est juste une optimisation random ?
    D'après les tests que j'ai effectué, j'arrive à obtenir des gains entre 2 et 3 (mais il ne s'agit pas du code final). Comme il s'agit de passer de très nombreuses fois dans cette boucle (2^N), l'effet n'est pas si négligeable que ça d'autant que je suis contraint en terme de réaction du système (calcul < 1 minute).
    Pourquoi, ai-je tenter cette optimisation? Tout simplement parce que je cherchais des moyens de réduire les temps de calculs et que je connaissais la théorie de la mémoire cache. Je voulais savoir si cela pouvait m'apporter quelque chose, j'ai effectué quelques recherches sur les performances des listes et j'ai tenté ce test. Après j'ai d'autres solutions d'optimisation: tenter de déterminer par avance les passages qui auront peu d'impacts sur la solution et les éliminer, décomposer la liste des éléments en groupe plus ou moins indépendant (2^N1+2^N2 avec N1+N2 = N mais interaction des groupes est à gérer en plus), usage du multi-threading sur CPU voir GPU.

    Oui. C'est un des rares cas où appeler directement le destructeur (donc sans passer par delete) est valide
    intéressant, je ne savais pas qu'il était permit d’appeler directement le destructeur.

    Le faire à la main impose pas mal de piège et manipulation manuelle. Par exemple, ici tu ne prends pas en compte l'alignement des classes,
    Ok, il faut tout avoir en tête quand on fait ce genre de chose, maintenant que tu le dis, cette histoire d’alignement me semble évidente.

    Je vais voir si je peux faire une une version non optimisé pour comparer les performances, en faisant cette fois-ci attention à l’alignement.

    Sinon, pour les solutions, il faut que je regarde.

    Je vous remercie encore

  5. #5
    Expert éminent sénior
    Avatar de koala01
    Homme Profil pro
    aucun
    Inscrit en
    octobre 2004
    Messages
    11 336
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : Belgique

    Informations professionnelles :
    Activité : aucun

    Informations forums :
    Inscription : octobre 2004
    Messages : 11 336
    Points : 28 719
    Points
    28 719
    Par défaut
    Salut,
    Citation Envoyé par vingt sens Voir le message
    Bonjour, merci pour vos réponse, j'ai été négligeant de ne pas répondre plus tôt, je vous prie de m'en excuser.
    C'est bon pour une fois, nous ne t'en tiendrons pas rigueur

    Plus sérieusement: cela arrive très souvent, on a l'habitude, et on ne t'en tiendra pas rigueur
    D'après les tests que j'ai effectué, j'arrive à obtenir des gains entre 2 et 3 (mais il ne s'agit pas du code final). Comme il s'agit de passer de très nombreuses fois dans cette boucle (2^N), l'effet n'est pas si négligeable que ça d'autant que je suis contraint en terme de réaction du système (calcul < 1 minute).
    En fait, jo_link n'a jamais dit que tu avais tord de le faire. Il t'a juste mis en garde -- et à juste titre -- sur un point que les gens ont beaucoup trop facilement tendance à oublier:
    Citation Envoyé par Knuth
    Premature optimisation is the root for all evill
    Il est clair qu'une boucle présentant une complexité en O(2N) est une candidate plus que plausible aux optimisations, mais ca, il ne pouvait pas le deviner, vu que tu ne l'avais pas dit

    Et, dans de telles conditions, mieux vaux prévenir que guérir en faisant une "piqûre de rappel" que de se retrouver face à quelqu'un qui finit avec un code completement illisible et qui ... se plaint toujours de problèmes de performance, parce qu'il a essayer d'optimiser tous les points qui n'en valaient pas la peine, mais n'a rien fait pour optimiser ceux qui auraient pu apporter les meilleurs gains

    Pourquoi, ai-je tenter cette optimisation?
    Oh, mais on ne doute absolument pas de tes raisons. On sait bien qu'elles sont de toutes façons parfaitement justifiées à tes yeux.

    On n'est d'ailleurs pas opposé par principe aux optimisations, pour autant qu'elles soient soutenues par des mesures qui prouvent leur efficacité, ou, à tout le moins, par une analyse démontrant que l'on va clairement agir sur l'un des points du code sur lequel on passe le plus de temps.

    Tu sais sans doute que, de manière tout à fait empirique, considère généralement que 80 à 90% du temps d'exéction est utilisé par 10 à 20 % du code seulement. Encore une fois, si une des boucles principales s'effectue selon une complexité en O(2N), elle part effectivement favorite pour l'optimisation

    En l'occurrence, un gain de l'ordre de 1:2 ou 1:3 la justifie pleinement

    Tout simplement parce que je cherchais des moyens de réduire les temps de calculs et que je connaissais la théorie de la mémoire cache. Je voulais savoir si cela pouvait m'apporter quelque chose, j'ai effectué quelques recherches sur les performances des listes et j'ai tenté ce test.
    Effectivement, les cache misses, dans les boucles dans lesquelles on passe le plus de temps, sont une des causes principales de diminution des performances.

    Si tu ne parlais pas d'objets polymorphes (qui impliquent souvent le recours à l'allocation dynamique de la mémoire), le simple fait de remplacer une liste par un tableau, pour lequel on réserve directement une taille suffisante, fait souvent des miracles sur ce point
    Après j'ai d'autres solutions d'optimisation: tenter de déterminer par avance les passages qui auront peu d'impacts sur la solution et les éliminer, décomposer la liste des éléments en groupe plus ou moins indépendant (2^N1+2^N2 avec N1+N2 = N mais interaction des groupes est à gérer en plus), usage du multi-threading sur CPU voir GPU.
    Cela peut effectivement être tenté, mais, encore une fois, rappelle toi ce qu'a dit knuth, parce que tu pars sur des possibilités qui vont te compliquer énormément la vie, en termes de débuggage entre autres

    Avant de te lancer dans de telles démarche, veille d'abord et avant tout à avoir quelque chose qui fonctionne correctement, et à t'assurer que tu as vraiment besoin d'améliorer les performances. Car, si, en l'état, tu peux déjà obtenir ton résultat en 59 secondes ou moins, tu restes "dans les clous" non

    En plus, l'idée du multi-threading est souvent largement surfaite

    intéressant, je ne savais pas qu'il était permit d’appeler directement le destructeur.
    Ah, oui, on évoque très rarement le placement new, parce que c'est une approche "de haut vol", qui ne se justifie réellement que lorsque l'on part, justement, vers un système d'allocation des ressources personnalisées

    Mais c'est l'un des grands avantages de C++: il fourmille littéralement de possibilités peu / mal connues, dont on ne fait pas la publicité car elles pointent un fusil chargé sur ton pied, mais qui s'avèrent, dans certaines circonstances, particulièrement utiles
    Je vais voir si je peux faire une une version non optimisé pour comparer les performances, en faisant cette fois-ci attention à l’alignement.
    Ce que tu pourrait aussi envisager, vu que tu as créé ton propre allocateur (et, en toute logique, ton propre déallocateur, vu qu'ils vont par paire), c'est utiliser la classe std::unique_ptr pour stocker les éléments dans ta liste, en précisant le deuxième paramètre template, celui qui utilise std::default_delete par defaut, de manière à profiter pleinement du RAII
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  6. #6
    Expert éminent sénior
    Avatar de Luc Hermitte
    Homme Profil pro
    Développeur informatique
    Inscrit en
    août 2003
    Messages
    5 272
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : août 2003
    Messages : 5 272
    Points : 10 813
    Points
    10 813
    Par défaut
    Petite piqûre de rappel au cas où: A moins qu'une structure chaînée soit absolument ce dont tu as besoin, en général, même et surtout avec des milliers d'éléments un vecteur écrase à plate couture une liste chaînée pour les raisons de cache justement. Et ce même quand on s'amuse à ajouter et retirer en plein milieu -- à fréquence raisonnable par rapport au parcours séquentiel.
    Blog|FAQ C++|FAQ fclc++|FAQ Comeau|FAQ C++lite|FAQ BS|Bons livres sur le C++
    Les MP ne sont pas une hotline. Je ne réponds à aucune question technique par le biais de ce média. Et de toutes façons, ma BAL sur dvpz est pleine...

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. optimiser java mémoire, charge
    Par cdm1024 dans le forum Général Java
    Réponses: 3
    Dernier message: 24/02/2009, 18h17
  2. Optimiser la mémoire pour réduire le temp d'import
    Par Bourak dans le forum Administration
    Réponses: 20
    Dernier message: 03/11/2008, 11h23
  3. taux d'usage mémoire et processeur
    Par dc.sara dans le forum C++
    Réponses: 2
    Dernier message: 14/02/2008, 16h20
  4. Optimiser la mémoire d'une app VB 2005
    Par Diabless6 dans le forum VB.NET
    Réponses: 34
    Dernier message: 21/08/2007, 20h18
  5. Optimisation de mémoire / rapiditée
    Par Zenol dans le forum C++
    Réponses: 9
    Dernier message: 25/09/2005, 12h18

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