Discussion :

[Nanoc]

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 !

[Lavock]

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.

[white_tentacle]

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...

[Nanoc]

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.

[white_tentacle]

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.

[Nanoc]

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.

[koala01]

Salut,

Pourquoi ne pas adapter, "simplement" le principe d'un arbre binaire

Je m'explique:
Au lieu de n'avoir, comme dans un arbre binaire, que deux références, respectivement vers un élément "plus petit" et un élément "plus grand", proche de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
classs BinaryNode
{
    public:
        BinaryNode(Type v):value_(v),less_(NULL),more_(NULL){}
       /*...*/
    private=
       Type value_;
       BinaryNode * less_;
       BinaryNode * more_;
}

tu aurais quatre (ou huit) références, sous une forme qui pourrait être proche de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
class OctTree
{
    public:
        OctTree(Type v):value_(v)
        {
            next_={NULL, NULL, NULL, NULL,
                       NULL, NULL, NULL, NULL};
        }
        /* ...*/
    private:
        OctTree * next_[0];
};

Tu obtiendrait la possibilité d'avoir tout à la fois un parcours au départ de la racine dont le temps d'accès n'est jamais égal qu'à la profondeur du noeud recherché (récursivité inside), celle de déplacer "facilement" un noeud vers un parent différent, celle de parcourir malgré tout transversalement ton arbre (même si, ici, cela ne t'importe que peu), le tout combiné avec, au final, une utilisation de la mémoire collant au mieux aux besoins d'un instant T

[Goten]

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.

Si t'alloues beaucoup beaucoup de petits objets (ça a l'air d'être ton cas) alors générique ou pas un allocateur autre que celui par défaut peut être très intéressant en terme de gain mémoire.

[Nanoc]

Salut,

Pourquoi ne pas adapter, "simplement" le principe d'un arbre binaire

Tu obtiendrait la possibilité d'avoir tout à la fois un parcours au départ de la racine dont le temps d'accès n'est jamais égal qu'à la profondeur du noeud recherché (récursivité inside), celle de déplacer "facilement" un noeud vers un parent différent, celle de parcourir malgré tout transversalement ton arbre (même si, ici, cela ne t'importe que peu), le tout combiné avec, au final, une utilisation de la mémoire collant au mieux aux besoins d'un instant T

C'est ce que je présentai comme ma solution 1. Et c'est ce que j'ai actuellement d'implémenté. L'alternative consistant à stocker les noeuds dans un tableau m'a été suggérée par une personne travaillant dans le même domaine. Mais il n'a pas pu me fournir d'arguments en faveur de sa version autre que "ça se fait comme ça".

Si t'alloues beaucoup beaucoup de petits objets (ça a l'air d'être ton cas) alors générique ou pas un allocateur autre que celui par défaut peut être très intéressant en terme de gain mémoire.

J'alloue effectivement des centaines de milliers d'objets.

Chaque noeud est une structure contenant un pointeur, deux double et un handle vers les 8 noeuds fils. Comment tu écrirais un allocateur différent d'un simple new pour ça ?

[white_tentacle]

C'est ce que décrit Alexandrescu dans « Modern C++ Design ». L'idée étant d'allouer des buffers d'une taille conséquente (de l'ordre de quelques ko), et de « placer » les objets nouvellement créés dans ce buffer. Vu la simplicité de mise en œuvre avec Loki, je pense que ça vaut la peine d'être essayé.

Le fait d'allouer dans un tableau/buffer a normalement pour effet de réduire la fragmentation mémoire, et donc les page faults, et donc peut effectivement grandement améliorer les performances.

[camboui]

Il y a peut-être des infos à tirer de cette autre discussion http://www.developpez.net/forums/d83...bleme-memoire/

Perso j'aurais probablement penché pour la solution 2 (un gros tableau alloué en vrac).
-Plus besoin de pointeurs fils/parent, gain de place (on peut donc en "gaspiller" ailleurs).
-Application probablement exclusive sur une machine: prendre toutes les resources hardwares pour une application seule n'est pas un problème.

Reste le problème de la dispersion des noeuds en mémoire.
Solution possible: Découper l'arbre en sous-arbres de profondeur N de sorte que chaque sous-arbre tienne dans un tableau de taille réduite (taille à calculer pour minimiser les page faults). Par exemple, si un sous-arbre a une profondeur de 4, qu'un élément fait 20 bytes et qu'un noeud contient 8 éléments, cela fait un bloc mémoire de 11700 bytes (=(1+8+64+512)*20).

[Lavock]

Faudrait déjà que tu détermines si tu a besoin d'avantage de perf à la lecture ou à l'écriture. Faire un tableau contigu, c'est bien si tu dois écrire rarement (car un redimensionnement, c'est lourd). Sinon, il vaut mieux segmenter ta mémoire, ce qui permettra une allocation plus rapide.
Après, tu à les choix hybride de faire des unités "arbre". C'est pratique car tes objets deviennes lourd, et tu peux utiliser efficacement les gestionnaires du C++.

[EDIT] Au temps pour moi !

[camboui]

Non non, je parlais bien d'octets
Il me semble que l'élément décrit par nanoc fait 16 octets et non pas 20 (2 doubles et rien d'autre puisque plus besoin de pointeur dans le cas d'une disposition en tableau). Un arbre de profondeur 4 se tient dans un buffer de 9360 octets.

[Nanoc]

L'arbre est construit une seule fois.

Les parcours suivants ont lieu:

- il est parcouru deux fois de la racine vers les feuilles.
- Une opération doit être effectuée sur chaque feuille.
- L'arbre est parcouru de la racine vers les feuilles autant de fois qu'il y a de feuilles.

Une solution mixe est intéressante. Je vais réfléchir à ça plus en détail.

Merci pour vos idées. N'hésitez-pas si vous pensez à autre chose.

[bacelar]

Les quadtree et les octree sont des structures très fréquemment utilisées dans les moteurs 3D.
Normalement, les concepteurs de ces moteurs graphiques ont déjà fait des expérimentations et optimisations mémoires.
La lecture des WhitePaper des moteurs 3D ne fournit pas le fruit de leurs recherches ?

[bretus]

Bonsoir,

Les quadtree et les octree sont des structures très fréquemment utilisées dans les moteurs 3D.
Normalement, les concepteurs de ces moteurs graphiques ont déjà fait des expérimentations et optimisations mémoires.
La lecture des WhitePaper des moteurs 3D ne fournit pas le fruit de leurs recherches ?

Bonne idée. Sinon Ogre3d, open source, présente une classe Octree... Peut-être qu'elle peut donner des pistes

[Klaim]

C'est une implémentation basique, suffisante la plupart des cas mais pas spécialement optimisée a ce que je sache.
De toutes manière, a part allouer un buffer dés le départ (vu que le tree en changera pas) je ne vois pas d'autres solution simple pour optimiser la mémoire.

[Nanoc]

Effectivement, l'octree de Ogre3D n'est pas génial et pas franchement adapté à ce que je fais (simulation numérique, pas rendu 3D).

Je pense en effet que je vais allouer un buffer et placer mes noeuds dedans.

Merci à tous pour vos réponses.

[Klaim]

Effectivement, l'octree de Ogre3D n'est pas génial et pas franchement adapté à ce que je fais (simulation numérique, pas rendu 3D).

Oui a la base c'était plutot une forme d'exemple, pour eux il vaut mieu se faire un scene manager adapté à son propre cas d'application que de chercher une solution généraliste.