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

C++ Discussion :

[Arbres] Gestion de la mémoire


Sujet :

C++

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre confirmé

    Inscrit en
    Juin 2008
    Messages
    49
    Détails du profil
    Informations forums :
    Inscription : Juin 2008
    Messages : 49
    Par défaut [Arbres] Gestion de la mémoire
    Bonjour,

    Je travaille actuellement sur les arbres utilisés dans le calcul scientifique pour calculer des interactions à longue distance entre des particules. Ce qu'on appelle quadtree et octree.

    Je cherche à tester différentes alternatives dans l'algorithme de calcul des forces, ce qui implique que je ne peux pas utiliser une bibliothèque déjà écrite (ou alors il faudrait que je modifie le code de cette lib, chose que je veux éviter).

    Mon problème consiste à choisir une option au niveau de la gestion de la mémoire. C'est presque de l'algorithmique mais je cherche une solution C++ pour l'instant.

    Je construis mon arbre à partir des positions des objets que je veux placer dedans. Si plusieurs objets sont situés sur un même noeud, je divise l'espace géré par ce noeud en 8 parties et je place les objets récursivement dans l'arbre jusqu'au moment où il n'y a plus qu'un objet par feuille.
    Durant la partie de calcul des forces, je dois parcourir l'arbre mais ceci se fait toujours en partant depuis la racine. i.e. pas de parcours transversal.

    J'ai imaginé deux manières de stocker mes noeuds en mémoire:

    La première consiste juste à utiliser "new" et ainsi à laisser l'ordinateur placer mes noeuds "aléatoirement" dans la mémoire sans réelle organisation. Avec cette méthode, on est obligé de parcourir l'arbre depuis la racine vers les feuilles. Il n'y a pas de mémoire perdue mais on ne peut pas accéder aux feuilles directement.

    La deuxième consiste à créer un tableau de nœuds puis à remplir ce tableau de manière logique si nécessaire. C'est-à-dire, placer d'abord la racine, puis ses 8 fils, puis les 64 petit-fils, etc... Avec cette méthode, on a un moyen d'accéder directement à n'importe quel noeud en O(1) . Le parcourt en descendant est toujours possible mais par contre on a besoin d'allouer de la mémoire "inutile" pour le tableau puisqu'à moins de redimensionner correctement le tableau à chaque insertion d'élément (ce qui serait désastreux niveau performances) on est obligé d'allouer un tableau plus grand que nécessaire.

    Entre ces deux options, mon coeur balance et je n'ai pas le temps d'implémenter les deux et de développer une batterie de tests afin de choisir la meilleure option.
    Quelqu'un aurait-il un retour d'expérience à ce sujet ?

    Ou alors, y aurait'il une troisième alternative à laquelle je n'ai pas pensé ?

    Merci d'avance !

  2. #2
    Membre chevronné Avatar de Lavock
    Profil pro
    Inscrit en
    Octobre 2009
    Messages
    560
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 560
    Par défaut
    Gérer ta mémoire à la façon de std::vector. Voir même l'utiliser en agrégat, et mettre l'interface voulu dessus.

  3. #3
    Membre Expert
    Avatar de white_tentacle
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    1 505
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2008
    Messages : 1 505
    Par défaut
    Quand tu parcours des arbres, ce qui est le plus coûteux, c'est souvent le page fault. Autrement dit, les noeuds proches du point de vue de ton doivent être proches en mémoire. Et surtout, tu ne dois pas faire d'aller-retours entre deux noeuds éloignés en mémoire.

    Ce qui veut dire que la structure mémoire adaptée est intrinsèquement dépendante de tes algorithmes et de la manière de parcourir les noeuds. Impossible de donner une réponse absolue. Il faut voir aussi le rapport de temps entre construction de l'arbre et utilisation de l'arbre : si tu peux te permettre une phase ""d'optimisation mémoire" sur la structure de ton arbre une fois celui-ci connu en entier ou pas.

    Ça dépend aussi de la taille des noeuds, évidemment...

  4. #4
    Membre confirmé

    Inscrit en
    Juin 2008
    Messages
    49
    Détails du profil
    Informations forums :
    Inscription : Juin 2008
    Messages : 49
    Par défaut
    Merci pour vos réponses.

    Les noeuds sont légers (les pointeurs sur les fils + 2 double).

    Une phase d'optimisation serait une face qui transforme l'ensemble de blocs mémoires éparpillés en un tableau, c'est ça ?
    Ca peut être intéressant ça. La phase de construction étant pour l'instant une partie minime du temps de calcul total. Je vais y réfléchir.

  5. #5
    Membre Expert
    Avatar de white_tentacle
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    1 505
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2008
    Messages : 1 505
    Par défaut
    J'y pense, si tu en as l'occasion, regarde aussi comment est fait le "small object allocator" de loki (il y a un chapitre qui lui est dédié dans "modern c++ design"). Il y a clairement du bon à prendre là dedans.

  6. #6
    Membre confirmé

    Inscrit en
    Juin 2008
    Messages
    49
    Détails du profil
    Informations forums :
    Inscription : Juin 2008
    Messages : 49
    Par défaut
    Je ne cherche pas à faire quelque chose de générique. Je ne pense donc pas que récrire un allocateur soit nécessaire à ce stade.

Discussions similaires

  1. Réponses: 17
    Dernier message: 02/02/2006, 12h03
  2. gestion de la mémoire
    Par moldavi dans le forum C++
    Réponses: 17
    Dernier message: 04/02/2005, 23h18
  3. Réponses: 11
    Dernier message: 26/12/2004, 22h50
  4. Gestion de la mémoire entre plusieurs DLL
    Par Laurent Gomila dans le forum C++
    Réponses: 7
    Dernier message: 27/07/2004, 15h28
  5. Gestion des variables - mémoire ?
    Par RIVOLLET dans le forum Langage
    Réponses: 4
    Dernier message: 26/10/2002, 12h44

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