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.