Discussion :

[Cacophrene]

Bonjour,

Mais ça ne rentre pas tout à fait dans le cadre de ce que nous voulions faire à la base, à savoir trouver un moyen efficace d'afficher ce que sort notre programme, pour vérifier que le résultat est correct. Sauf s'il existe un moyen assez simple de convertir nos structures OCaml en .dot pour qu'elles soit lisibles par GraphViz, mais j'en doute. Non, nous pensons vraiment à une fonction à coté ou mieux en parallèle du programme qui affiche l'évolution de l'arbre au cours de son exécution.

Ça dépend de ce que vous voulez montrer : l'évolution de l'univers ou celle de la structure arborescente. Dans le premier cas, il vous faut juste une fonction matrix_of_quadtree et vous dessinez ensuite l'état de votre automate de façon classique : sous forme de grille avec des cellules colorées. Dans le second cas, il vous faut une fonction string_of_quadtree qui convertit une structure quadtree en fichier dot. Je vous donnerai un exemple bientôt si vous voulez.

De plus, pourriez vous revenir sur une petite présentation de gprof ? Cela pourrai nous permettre d'avoir des données intéressantes tant pour l'optimisation du programme que pour la présentation du TIPE, mais nous n'avons pas vraiment compris son utilisation et son fonctionnement.

Rapidement : avant tout, il faut compiler votre programme avec l'option -p. Ensuite, exécutez votre programme (attention : il sera plus lent). Ensuite, lancez la commande gprof mon_prog > listing.gprof puis ouvrez ce fichier avec l'éditeur de votre choix. Le début du fichier contient la liste des fonctions les plus utilisées par le programme. Pour l'installation, vous travaillez sous Linux ? Windows ?

Il faut avouer que nous faisons un peu du surplace, à défaut d'avoir de nouvelles idées pour le programme. Avoir découvert que la version naïve et bourine est bien plus rapide ne nous a pas vraiment rassuré...

Le profiling avec gprof devrait vous donner des pistes. Implémenter une version efficace d'un algorithme efficace peut avoir des aspects frustrants. Mais pas de panique, je suis sûr que les performances vont s'améliorer.

Cordialement,
Cacophrène

[gasche]

J'ai refait des essais et les résultats sont encore frustrants.

J'ai commencé par changer la structure de donnée pour retirer des couches d'indirection. Comme je le pensais, il est inutile de stocker le degré, et par ailleurs on peut utiliser une structure plus plate pour les données (éviter le tableau, qui permet d'écrire du code plus concis mais ajoute une couche):

Code :

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

1
2
3
4
 
type quadtree =
  | Base of int * int * int * int
  | Node of quadtree * quadtree * quadtree * quadtree

Avec cette structure et le code adapté, les performances sont multipliées par 4 environ.

La mauvaise nouvelle c'est que la versions sans mémoization (la mise en cache des résultats) est *toujours* plus rapide que la version mémoizée. Remplacer simplement la définition de h par "and h arb = traite arb" multiplie les performances d'un facteur 10 à vue de nez. Par ailleurs, une fois qu'on a viré la mémoization, les gains de l'optimisation ci-dessus sont plus faibles (mais les performances gagnent quand même un facteur 2).

Quand je retire la mémoization et avec cette optimisation, je peux calculer 100 générations sur un arbre de degré 12 en 104 secondes, sur mon ordinateur qui est très modeste. Est-ce que ça suffit côté performances ?

J'ai quelques idées pour faire mieux, mais je pense que vous pourriez aussi dire que ça suffit.
- utiliser du vrai hash-consing comme dans l'article de Filliâtre que je vous ai montré (mais à ce moment là on retourne à un schéma avec comparaison linéaire des éléments dans un bucket, donc pas sûr qu'on y gagne)
- stocker le résultat de la génération suivante dans l'arbre directement, au lieu de passer par une structure de cache externe

[Uncaught_exception]

Le profiling avec gprof devrait vous donner des pistes. Implémenter une version efficace d'un algorithme efficace peut avoir des aspects frustrants. Mais pas de panique, je suis sûr que les performances vont s'améliorer.

On l'espère !

Pour l'installation, vous travaillez sous Linux ? Windows ?

Windows et Mac pour nous, et possibilité d'avoir accès à Linux au lycée.

Ça dépend de ce que vous voulez montrer : l'évolution de l'univers ou celle de la structure arborescente. Dans le premier cas, il vous faut juste une fonction matrix_of_quadtree et vous dessinez ensuite l'état de votre automate de façon classique : sous forme de grille avec des cellules colorées. Dans le second cas, il vous faut une fonction string_of_quadtree qui convertit une structure quadtree en fichier dot. Je vous donnerai un exemple bientôt si vous voulez.

On veut obtenir une séquence d'image représentant l'évolution de l'univers au cours des générations. On veut bien voir ton exemple. Mais sinon on essaiera de stocker les résultats successifs dans un stream que l'on enverra via un pipe dans un programme de conversion quadtree -> BMP. On voulait surtout savoir si vous connaissiez une solution efficace, mais au pire on se contentera de ça.

Le profiling avec gprof devrait vous donner des pistes. Implémenter une version efficace d'un algorithme efficace peut avoir des aspects frustrants. Mais pas de panique, je suis sûr que les performances vont s'améliorer.

Ne peut-on pas combiner ce type avec un type à enregistrement, qui permettrait de faciliter l'accès ? C'est une proposition comme ça, on ne sait absolument si c'est utile. On va déjà modifier le code avec ce type.

J'ai quelques idées pour faire mieux, mais je pense que vous pourriez aussi dire que ça suffit.
- utiliser du vrai hash-consing comme dans l'article de Filliâtre que je vous ai montré (mais à ce moment là on retourne à un schéma avec comparaison linéaire des éléments dans un bucket, donc pas sûr qu'on y gagne)
- stocker le résultat de la génération suivante dans l'arbre directement, au lieu de passer par une structure de cache externe

Pour l'utilisation d'un vrai hash-consing, on veut bien mais là il va nous falloir énormément d'aide. Comme dit plus haut, dès la première page, il y a de nombreux concepts dont on n'a jamais entendu parlé (lambda-calcul et coefficients de Bruijn par exemple) et pour lesquels on ne trouve pas d'explications suffisamment accessibles sur internet.

Pour ce qui est du stockage dans l'arbre, c'est une solution et nous y avions pensé au début. Mais nous avions eu le problème suivant : lorsque dans traite on effectue le découpage des arbres, comment déterminer le résultat de la génération suivante à mettre dans les arbres créés ? Pour cela il faudrait pouvoir vérifier rapidement si un arbre similaire a déjà était calculé, i.e. le chercher dans une table de hachage.

On poste ensuite un passage de la description de Hashlife par le programmeur de Golly. En fait, on vient juste de comprendre le deuxième « trick » utilisé dans le code. Apparemment, « it is where the bulk of the power of the program comes from » ce qui veut dire que l'on pourrait avoir une amélioration des performances en l'implémentant.

I mentioned there were two tricks, and that's only the first. The second trick is to cache the `results' of the LIFE calculation, but in a way that looks ahead farther in time as you go higher in the tree, much like the tree nodes themselves scan larger distances in space. This trick is just a little subtle, but it is where the bulk of the power of the program comes from.

Consider once again the 8-squares. We want to cache the result of executing LIFE on that area. We could cache the result of looking ahead just one generation; that would yield a 6x6 square. (Note that we cannot calculate an 8-square, because we are using the single instance of the 8-square to represent all the different places that 8x8 arrangement occurs, and those different places might be surrounded by different border cells. But we
can say for sure that the central 6-square will evolve in a unique way in the next generation.)

We could also calculate the 4-square that is two generations hence, and the 3-square that is three generations hence, and the 2-square that is four generations hence. We choose the 4-square that is two generations hence; why will be clear in a moment.

Now let's consider the 16-square. We would like to look farther ahead for this square (if we always only looked two generations ahead, our runtime would be at "least" linear in the number of generations, and we want to beat that.) So let's look 4 generations ahead, and cache the resulting 8-square. So we do.

Enfin, il y a ces histoires de pointeurs. En fait, si l'on pense avoir bien compris quel rôle ils jouent dans l'algorithme original, on est pas sûr de saisir comment on doit les faire intervenir dans notre programme Caml. Leur rôle fait l'objet du premier « trick » dans Hashlife. Premièrement, l'espace est décomposé en quadtrees (ça c'est ok), et deuxièmement, on ne stocke les différentes configurations qu'une fois, et chaque fils d'un quadtree ne fait ensuite que pointer vers l'une de ces configurations.

Du coup, avec du recule, on a bien l'impression de n'utiliser ni l'un ni l'autre des deux grandes idées du programme, c'est à dire que l'on en est au point au l'algorithme récursif est nécessairement plus lent que la méthode naïve. Ce qui est cohérent avec nos résultats...

[gasche]

Filliâtre a aussi écrit un sujet sur Hashlife pour ses étudiants: le jeu de la vie.

[Cacophrene]

Bonsoir,

J'ai refait des essais et les résultats sont encore frustrants

Est-ce que le type suivant donnerait encore une amélioration des perfs, avec le cas de base stocké comme un entier 16 bits correspondant à une grille 4x4 cases ?

Code :

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

1
2
3
4
 
type quadtree = 
  | Base of int 
  | Node of quadtree * quadtree * quadtree * quadtree

Je vais peut-être tester de mon côté.

Cordialement,
Cacophrène

[gasche]

Ce week-end j'ai décidé de prendre le taureau par les cornes et comprendre vraiment, et implémenter moi-même, l'algorithme HashLife. C'est intéressant et je me suis bien sûr rendu compte que la compréhension très superficielle que j'en avais acquise dans ce topic est à revoir complètement.

De cette implémentation j'ai tiré des doutes sur l'implémentation discutée dans le présent topic; je ne la comprenais pas avant mais trouvais ça normal, mais je ne la comprends toujours pas maintenant et ça me surprend. Je ne comprends pas par exemple pourquoi la fonction "traite" semble se rappeler récursivement une seule fois, alors que dans mon code elle est appliquée deux fois (pour obtenir 2^n pas dans le futur a partir de deux calculs de 2^(n-1) pas). Je ne sais pas non plus ce que fait la fonction "generation".

Niveau performance, j'ai eu du mal comme ici à obtenir une implémentation de la mise en cache qui améliore les performances au lieu de les dégrader; j'en suis resté aux comparaisons relatives; pour ce qui de l'implémentation elle-même je pense qu'elle est sans doute moins optimisée que celle discutée ici, je me suis intéressé à la lisibilité plutôt qu'aux performances.

J'ai finalement obtenu un schéma où la mémoisation améliore les performances. Par contre j'ai du mal à savoir comment le tester. En particulier, les cartes générées aléatoirement (avec une chance sur deux pour chaque case d'être vivante) semblent très difficiles, beaucoup plus difficiles que les exemples réels de motifs à tester, qui contiennent beaucoup plus de cases vides. Contrairement à la présente implémentation, je n'arrive pas à faire grand chose sur les cartes aléatoires de degré 22 (je me limite au degré 11 pour lequel l'implémentation calcule 512 itérations en environ une minute); en même temps je ne comprends pas ce que l'implémentation présente teste réellement (calculer 100 fois la génération suivante ?), donc je ne sais pas si les tests correspondent.


Je ne veux pas non plus polluer ce topic avec une autre implémentation (pour ça il y a un autre topic mis en lien plus haut), mais c'était pour faire un retour d'expérience sur ce sujet qui m'a motivé à essayer moi-même d'implémenter cet algorithme inutile mais assez amusant.

[Uncaught_exception]

Je ne comprends pas par exemple pourquoi la fonction "traite" semble se rappeler récursivement une seule fois, alors que dans mon code elle est appliquée deux fois

C'est ce que l'on disait dans notre précédent post. Pour une raison x ou y ce passage a été oublié dans l'implémentation à nos début, et l'erreur s'est propagée de versions en versions. Notre dernière version corrige cela. Mais il n'y a aucuns gains de vitesse...

Je ne sais pas non plus ce que fait la fonction "generation".

Pour éliminer les effets de bord, on a décidé de travailler sur un tore. La fonction generation crée un arbre de dimension supérieure à celui calculer de sorte à refermer l'espace sous forme d'un tore.

On a lu le code trouvé sur un autre site. Voici quelques questions sur celui-ci :

• L'idée essentielle est bien de passer par deux tableaux intermédiaires, un permettant d'associer à un arbre une id et l'autre à une id un arbre ? Ne risque-t-il pas d'y avoir deux arbres ayant exactement la même id ?
• Une partie du code sert à calculer un certain nombre générations plus loin, différent d'une puissance de 2. Dans notre cas, c'est tout les résultats intermédiaires qu'il nous faut. Ne serait-il pas possible de les obtenir directement sans cette fonction en passant par un cache ?
• Que sont les labels ? On ne comprend pas trop l'utilisation de ~ et ?.
• Enfin la fonction fresh_id sert de compteur global. Cependant on ne comprend pas comment elle marche fondamentalement. Pour nous la variable compt étant locale, cette fonction devrait repartir à 1 à chaque appel.

mais c'était pour faire un retour d'expérience sur ce sujet qui m'a motivé à essayer moi-même d'implémenter cet algorithme inutile mais assez amusant.

Inutile...

[gasche]

L'idée essentielle est bien de passer par deux tableaux intermédiaires, un permettant d'associer à un arbre une id et l'autre à une id un arbre ? Ne risque-t-il pas d'y avoir deux arbres ayant exactement la même id ?

On regarde dans la table id_of_data pour chercher l'identifiant d'un nœud. Si on en trouve un, on le prend, sinon (Not_found) on utilise fresh_id() pour en obtenir un nouveau, distinct des précédents. Il ne peut pas y avoir des conflits... à moins d'un integer overflow où le compteur d'identifiants boucle à partir de max_int (environ 2^30 sur 32 bits et 2^62 sur 64 bits). Il y a de la marge cependant, pour les tests que j'ai fait on avait de l'ordre du million de nœuds différents, pas du milliard (2^30), et sinon on peut passer sur un ordinateur 64 bits pour faire les calculs sur de grosses profondeur.

Une partie du code sert à calculer un certain nombre générations plus loin, différent d'une puissance de 2. Dans notre cas, c'est tout les résultats intermédiaires qu'il nous faut.

Je me demande un peu à quoi ça sert puisqu'on peut calculer à la demande seulement ce dont on a besoin. Mais pourquoi pas; ça risque d'être un peu gourmand en stockage par contre.

Que sont les labels ? On ne comprend pas trop l'utilisation de ~ et ?.

Documentation du manuel officiel

J'utilise des labels quand il y a trop d'arguments de même type et que j'ai peur d'en inverser deux sans m'en rendre compte. Les labels optionnels sont un peu gadgets.

Enfin la fonction fresh_id sert de compteur global. Cependant on ne comprend pas comment elle marche fondamentalement. Pour nous la variable compt étant locale, cette fonction devrait repartir à 1 à chaque appel.

Le code est:

Code :

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

1
2
3
4
let fresh_id =
  let count = ref 0 in
  fun () ->
    incr count; !count

Elle évalue une variable "count" qui vaut le résultat de (ref 0), puis renvoie une fonction de type (unit -> int) qui, à chaque appel, incrémente "count" et renvoie le résultat (donc à partir de 1 effectivement).

Attention à ne pas confondre avec le code suivant qui marche comme tu le décris :

Code :

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

1
2
3
4
let constant_1 =
  fun () ->
    let count = ref 0 in
    incr count; !count

Dans le même genre, c'est la différence entre les deux fonctions suivantes:

Code :

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

1
2
3
4
5
6
7
let hello = 
  fun () ->
    print_endline "hello"
 
let hello =
  let print = print_endline "hello" in
  fun () -> print

[Uncaught_exception]

Cela fait quelque temps que nous ne donnons plus signe de vie. Mais même si nous n'avons pas répondu au dernier message de Gasche, nous l'avons bien pris en compte. Cependant, nous risquons d'être très peu présents pendant la période des concours qui va bientôt commencer. Néanmoins, nous restons à l'écoute de ce qu'il se passe ici et comptons bien revenir fin mai, une fois les écrits terminés.

[Theo Dupond]

Salut forum
Du coup je me demandais ce que donnait le corps du programme final genre le programme entier 🤔 Quelqu'un parmi vous l'aurait fait ?

Bonne soirée !! 😆