Comment éviter les «spaghettis de pointeur de tas» dans les graphiques dynamics?

Le problème générique

Supposons que vous codiez un système constitué d’un graphe et de règles de réécriture de graphes pouvant être activées en fonction de la configuration des nœuds voisins. C’est-à-dire que vous avez un graphique dynamic qui augmente / diminue de façon imprévisible au cours de l’exécution. Si vous utilisez naïvement malloc , de nouveaux nœuds vont être alloués dans des positions aléatoires en mémoire; après assez de temps, votre tas sera un spaghetti de pointeur, vous donnant une efficacité terrible de cache. Existe-t-il une technique légère et incrémentielle permettant de faire en sorte que les nœuds reliés entre eux restnt proches en mémoire ?

Ce que j’ai essayé

La seule chose à laquelle je pouvais penser est d’intégrer les nœuds dans un espace cartésien avec une simulation physique élastique qui repousse / attire les nœuds. Cela permettrait de garder les nœuds câblés ensemble, mais semble stupide et je suppose que les frais généraux de la simulation seraient plus importants que l’accélération de l’efficacité du cache.

Le solide exemple

C’est le système que j’essaie de mettre en place. Voici un bref extrait du code que j’essaie d’optimiser en C. Ce référentiel est une implémentation prototype et fonctionnelle dans JS, avec une efficacité de cache incroyable (et du langage lui-même). Cette vidéo montre graphiquement le système en action.

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

Vous pourriez envisager cela en termes de collecte de déchets demi-espace. Ce n’est pas difficile à mettre en œuvre (je l’ai fait pour un interprète), d’autant plus que vous ne le faites que pour des structures de nœuds de taille fixe. Allouez à partir d’un gros bloc de mémoire (appelé demi-espace). Quand il est trop plein ou fragmenté, arrêtez et copiez le tout sur l’autre (ce que vous pouvez aussi agrandir). L’astuce consiste à mettre à jour tous les pointeurs. Pour cela, il existe un algorithme très élégant et efficace appelé scan copy. Il y a une bonne discussion à ce sujet chez Cornell . Essentiellement, il parcourt d’abord la largeur du graphique, en le copiant au fur et à mesure, sans autre espace que celui que vous copiez. Une propriété intéressante de l’algorithme est que les premiers niveaux de largeur finissent adjacents après chaque copie. Si le niveau de localité est suffisant, vous l’obtiendrez très efficacement avec cette méthode.

Si vous êtes vraiment préoccupé par la disposition de la mémoire, il peut être intéressant de la gérer vous-même.

Vous pouvez malloc un gros bloc de mémoire au démarrage, puis vous allouez de l’espace à partir de ce bloc. Vous aurez besoin d’une structure séparée pour garder une trace de ce qui a été alloué et de ce qui n’a pas été alloué. Si vous savez que toutes les structures allouées ont une certaine taille et peuvent simplifier la gestion de l’espace alloué / libre, c’est-à-dire un tableau d’index, vous pourriez utiliser une liste de pointeurs dans l’espace libre. Étant donné que vous allez probablement allouer des structures une à la fois, vous n’avez probablement pas à vous soucier de garder une trace du plus petit et / ou du plus grand bloc d’espace libre contigu.

Une chose à laquelle vous devez faire attention est l’alignement. Encore une fois, si vous allouez toujours de la mémoire par multiples de la taille d’une même structure, cela facilite les choses, sinon c’est probablement une bonne idée de s’assurer que toutes les allocations commencent avec une limite de 4 octets, c’est-à-dire la différence entre allouer et l’adresse de départ reçue de malloc est un multiple de 4.

Vous pouvez transmettre des parameters supplémentaires à vos fonctions d’allocation personnalisées pour donner des indications sur l’emplacement du bloc, telles que l’adresse d’un ou de plusieurs nœuds voisins.

Cela peut être considéré comme un problème de partitionnement de graphe , dans lequel vous essayez de regrouper des nœuds de graphe liés sur le même bloc de mémoire. METIS est un bon algorithme de partitionnement de graphes qui ne convient probablement pas à votre cas d’utilisation car il nécessite des opérations globales sur tout le graphe. Toutefois, deux algorithmes de partitionnement de graphes dissortingbués pouvant être modifiés pour s’appliquer à votre cas d’utilisation sont DIDIC et Ja-Be. Ja – le premier tente de minimiser le nombre d’arêtes traversant les partitions sans tenir compte de la taille de la partition, tandis que le second tente de créer des partitions de taille égale. Les deux algorithmes nécessitent uniquement une connaissance locale du graphe pour regrouper chaque nœud. Par conséquent, si vous disposez de cycles de réserve, vous pouvez les utiliser pour rééquilibrer le graphe de manière incrémentielle. Fennel est un algorithme associé qui fonctionne sur les graphiques en continu. Vous pouvez par exemple utiliser Fennel ou un algorithme similaire lors de l’allocation initiale d’un nœud de graphique, puis utiliser DIDIC / Ja-Be-Ja lors du rééquilibrage du graphique.