Comment éviter les "spaghettis de pointeur de tas" dans les graphiques dynamiques?

Question

Le problème générique

Supposons que vous êtes le codage d'un système qui se compose d'un graphique, plus graphique des règles de réécriture qui peut être activé en fonction de la configuration des nœuds voisins. C'est, vous avez un graphique dynamique qui augmente/réduit de façon imprévisible au cours de l'exécution. Si vous naïvement utiliser malloc, les nouveaux nœuds sont va être affecté dans des positions aléatoires dans la mémoire, après d'assez de temps, votre tas sera un pointeur spaghetti, vous donnant la terrible efficacité de la mémoire cache. Est-il léger, technique incrémentale à faire des nœuds fils ensemble, de rester à proximité de la mémoire?

Ce que j'ai essayé

La seule chose que je pouvais penser, c'est l'incorporation de nœuds dans un espace cartésien avec de l'élastique de la simulation repoussé/a attiré les nœuds. Que garderais filaire noeuds, mais c'est idiot et je suppose que les frais généraux de la simulation serait plus grand que le cache de l'efficacité de l'accélération.

L'exemple solide

C' est le système que je suis en train de mettre en œuvre. Ceci est un bref extrait du code, je suis en train de l'optimiser en C. Ce repo est un prototypes, de travail mise en œuvre en JS, avec la terrible efficacité de la mémoire cache (et de la langue elle-même). Cette vidéo montre le système en action graphiquement.

Answer 1

Ce que vous cherchez à résoudre, c'est le problème de l'arrangement linéaire . Les solutions parfaites sont considérées comme NP-difficiles, mais il existe de bonnes approximations. Voici un document qui devrait être un bon point de départ.

Answer 2

Vous pourriez regarder cette en termes de halfspace la collecte des ordures. Ce n'est pas difficile à mettre en oeuvre (je l'ai fait pour un interprète), en particulier puisque vous êtes les seuls à le faire pour une taille fixe nœud structures. Allouer à partir d'un grand bloc (appelé halfspace) de la mémoire. Quand elle est trop pleine ou fragmentées, d'arrêter et de tout copier sur les autres (que vous pouvez également faire de plus grosses). Le truc, c'est la mise à jour de tous les liens. Pour cela, il est un très élégant et efficace algorithme appelé scan copie. Il y a une belle discussion à ce sujet à l'université de Cornell. Essentiellement, il parcourt le graphe en largeur d'abord, la copie comme il va, sans aucun espace supplémentaire autre que ce que vous êtes à la copie. Une belle propriété de l'algorithme est que la largeur des niveaux de fin adjacent après chaque copie. Si c'est un assez bon niveau de localité, vous aurez très efficacement avec cette méthode.

Answer 3

Si vous êtes vraiment préoccupé par la mise en page de la mémoire, il pourrait être intéressant de gérer vous-même.

Vous pouvez malloc un grand bloc de mémoire au démarrage, alors vous allouer de l'espace de ce bloc. Vous aurez besoin d'une structure distincte pour garder une trace de ce qui a et ce qui n'a pas été alloué. Si vous savez que toutes les structures attribuées sont d'une certaine taille, qui peuvent simplifier alloué/libre de gestion de l'espace, c'est à dire un tableau d'index, sinon vous pouvez utiliser une liste de pointeurs dans l'espace libre. Étant donné que vous aurez probablement être en allouant des structs un à la fois, vous n'avez probablement pas besoin de vous soucier de garder une trace de la plus petite et/ou du plus grand bloc contigu de l'espace libre.

Une chose que vous devez faire attention est de l'alignement. Encore une fois, si vous serez toujours en mesure d'allouer de la mémoire dans des multiples de la taille d'une seule structure, qui rend les choses plus facile, sinon, c'est probablement une bonne idée de s'assurer que toutes les allocations de départ à une frontière d'octet 4, c'est à dire la différence entre l'adresse que vous allouer et de l'adresse de début reçu d' malloc est un multiple de 4.

Vous pouvez passer des paramètres supplémentaires à votre personnalisé des fonctions d'allocation de donner des indications sur l'endroit où le bloc doit être placé, comme l'adresse d'un ou de plusieurs à proximité des nœuds.

Answer 4

Cela peut être vu comme un graphe de partitionnement problème, où vous êtes en essayant de cluster liés noeuds d'un graphe sur le même bloc de mémoire. METIS est un bon partitionnement de graphe algorithme qui n'est probablement pas approprié pour votre cas d'utilisation, car il nécessite des opérations mondiales à travers l'ensemble du graphique, cependant deux distribué graphique des algorithmes de partitionnement qui peut être modifié afin d'être applicables à votre cas d'utilisation sont DIDIC et Ja-Être-Ja - l'ex tente de minimiser le nombre d'arêtes que de la croix de partitions sans égard à la taille de la partition, alors que ce dernier tente de créer également de la taille des partitions. Les deux algorithmes ne nécessitent une connaissance locale de la courbe pour chaque nœud de cluster, donc si vous avez des cycles de rechange que vous pouvez utiliser pour rééquilibrer progressivement le graphique. Le fenouil est un algorithme qui fonctionne en flux continu, de graphiques, de sorte que par exemple, vous pouvez utiliser le Fenouil ou un algorithme similaire initialement lors de l'attribution d'un graphique nœud, puis utilisez DIDIC/Ja-Être-Ja lorsque le rééquilibrage de la graphique.