Discussion :

[Uncaught_exception]

Bonsoir,


Je suis étudient en classe préparatoire MP et dans le cadre du TIPE, j'ai programmé avec mon binôme le programme HashLife en Ocaml. Du moins la première partie car nous butons désormais sur de gros problèmes de mémoire (on passera les problèmes d'optimisations liés à notre programmation très certainement naïve…).

D'où nos question : comment, dans un table de hachage, supprimer des entrées peu fréquemment utilisées ? Le module Gc a t-il un rapport avec notre problème ? Notre méconnaissance de la gestion de la RAM a rendu toutes nos recherches sur le sujet infructueuses…

Merci d'avance pour votre aide.


PS : On « débute » en Ocaml, après deux ans de CamlLight.

[gasche]

Supprimer des entrées dans un cache, c'est assez galère. Je te conseille plutôt de commencer par faire un régime, en regardant comment stocker de façon plus compacte ce que tu mets dans ta table, et surtout en t'assurant que tu ne consommes pas trop de mémoire par ailleurs (hors de la table).

Si tu montres ton code on pourra en dire du mal et donner des conseils pour la mémoire.

Pour les caches, tu peux assez facilement implémenter une heuristique du style "en cas de manque de mémoire, je vire les trucs qui n'ont pas été utilisés depuis le plus longtemps". L'idée est d'avoir une référence globale (à la table) initialisée à 0; c'est le "moment d'accès".
Quand tu crées une clé dans la table, tu lui associes (en plus de la valeur que tu veux mettre) une référence fraîche initialisée au moment d'accès courant.À chaque accès dans la table, tu récupères la valeur associée à la clé et la référence, que tu mets à jour pour lui mettre le moment d'accès courant. Quand tu veux supprimer des éléments de la table, tu retires ceux dont le moment d'accès est inférieur au moment d'accès courant, et tu incrémentes le moment d'accès.

[Cacophrene]

Bonjour,

Sans garantie que ce soit pertinent pour ton problème, as-tu regardé du côté du module Weak ? Concernant le module Gc il y a clairement des choses qui sont envisageables pour adapter son fonctionnement à ton programme, mais comme le dit gasche, pas avant d'avoir regardé ton code et cherché s'il n'y a pas quelque chose de plus évident à faire. Ensuite, avant de modifier quoi que ce soit avec le module Gc, il faut faire du profiling avec gprof et regarder attentivement le listing.

Cordialement,
Cacophrène

[Uncaught_exception]

Bonjour,


Merci beaucoup pour vos réponse — et désolé pour mon temps de réponse. Nous allons étudiez vos propositions qui sont déjà très nombreuses. Nous avons quand même déjà une une petite question : concernant la gestion d'un compteur, l'idée est bien, mais je ne sais pas trop comment l'implémenter sans sacrifier trop de ressources ; peut on avoir plus de détail sur ce point ?

Puisque vous le demandez, voici notre code avec de « brefs » commentaires sur les différentes fonctions. N'hésitez pas si vous avez besoin d'explications, tout n'est sans doute pas fait dans les règles de l'art et certaine fonctions sont peut-être assez obscures...

Encore merci pour votre aide.


Bonne fin de week end à tous.

[Cacophrene]

Bonjour,

Je viens de regarder votre code et, en effet, beaucoup de choses sont à discuter. Je suis quasi sûr que certaines d'entre elles sont responsables des problèmes de mémoire que vous rencontrez. Je vous suggère donc de reprendre ensemble les points de votre code à partir des remarques suivantes :

• Il faut apprendre à utiliser les fonctions d'ordre supérieur. Je pense notamment à ces deux cas évidents :

Code :

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

1
2
let tab = Array.init (degre - 1) (fun k -> Hashtbl.create (1 lsl (k + 2)))
let clear_all = Array.iter Hashtbl.clear

• Chaque fois que c'est possible, utilisez des boucles pour éviter le maximum d'erreurs. Évitez les optimisations a priori en remplaçant les boucles par de longues sommes, vous éviterez des erreurs. L'optimisation fine sera faite à la fin avec gprof quand le programme sera complet et fonctionnel. Vous identifierez alors les goulots d'étranglement. À l'inverse, il faut faire quelque chose pour la montagne de boucles qu'on trouve au milieu du code pour la gestion des cas de base...
• Interrogez-vous sur la pertinence des chaînes de caractères pour vos clefs de hachage. De façon générale, la concaténation des chaînes (opérateur ( ^ )) est peu efficace. Regardez du côté du module Printf (notamment la fonction sprintf). Mieux, réfléchissez à un autre type de données ! Vous vous créez des problèmes énormes et vous utilisez abondamment String.sub qui est aussi très inefficace dans vos fonctions horizontal, vertical, centre et centrecentre. Regardez aussi le module Buffer, le module Scanf et la fonction sscanf. Pourquoi pas des booléens ? Songez à ceci qui est alors immédiat à écrire et à comprendre :

Code :

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

1
2
let suivant cel voisin = 
  not cel && (voisin = 3) || cel && (voisin = 2 || voisin = 3)

• Traditionnellement, on programme efficacement l'algorithme Hashlife à l'aide d'une structure appelée quadtree. Vous pouvez très bien le faire en OCaml... renseignez vous sur les types récursifs. En l'état actuel, vous manipulez des chaînes de caractères qui deviennent rapidement énormes et il ne faut pas s'étonner d'avoir des problèmes de mémoire et de performance.
• Évitez d'écrire du code hors d'une déclaration de type let foo = .... C'est très important pour écrire en style fonctionnel, ça force à regrouper les effets de bord et ça n'incite pas à avoir trop de variables globales.

Remarque finale : l'algorithme Hashlife n'est pas trivial. C'est un bon sujet de TIPE et je vous engage à vous soucier autant de l'algorithme lui-même que de votre style de programmation. Si vous voulez obtenir une implémentation efficace sur des univers immenses, il est indispensable de faire attention à la complexité des fonctions utilisées, au choix des types de données, etc. bien plus que pour un autre projet. Comme vous avez montré que vous avancez dans votre projet et que vous y avez réfléchi, je pense pouvoir dire que nous serons tous très heureux de vous aider !

Cordialement,
Cacophrène

[gasche]

Les commentaires de Cacophrènes sont tout en finesse, mais je me permets un commentaire plus global et plus direct : utiliser des chaînes de caractères pour encoder de l'information est une idée horrible, qu'il faut abandonner au plus vite.

[Uncaught_exception]

Merci à vous pour l'honnêteté et la qualité de vos réponses, qui devraient beaucoup nous aider à avancer. Concernant les fonctions d'ordre supérieur, c'est noté, nous allons essayer d'en utiliser le plus possible.

À propos de la « montagne de boucles » au milieu, ou encore du fait que nous n'utilisons pas des booléens, c'est par ce que nous souhaiterions appliquer le programme à d'autres automates qui ont si possible plus de deux états. On en est loin, certes, mais le but c'est bien que le code soit « prêt » à recevoir un automates à priori quelconque par la suite. *Nous avons commencé avec le Jeu de la vie pour la simplicité des règles et les deux seuls états, principalement, mais il nous sert simplement de base de travail. Dans l'idéal, et quitte à restreindre la taille du plan de travail, on vise l'emploie de 8, puis 16 états.

Mais le cœur du problème n'est pas là, il s'agit bien sur de la structure en quadtree, en lien avec l'utilisation de chaîne de caractères. Nous avons longtemps patiné là dessus pour diverses raisons. Sur le papier, nous pensons avoir correctement appréhendé la structure et la gestion des quadtree dans la récursivité, mais nous avons eu du mal au moment de passer à Caml. Une des raisons qui nous a poussé à prendre des chaînes de caractères, c'est qu'avec cette méthode nous pouvons retrouver les sous-arbres directement à partir du nom de l'arbre principal ; c'est important puisque nous devons ensuite chercher ces sous-arbres dans la table de hachage. Nous n'étions nous même pas très convaincu de la méthode, et ce n'est d'ailleurs pas l'option que nous avions choisie au début (nous avions créé un type), mais c'est pourtant la seule façon que nous avons dénichée pour arriver au résultat voulus. On se doutait bien que les chaînes de caractères n'étaient une méthode efficace de gestion de l'information, mais à défaut de connaître une autre structure permettant un accès facile à ses éléments intérieurs, on s'est résolu à les utiliser.

Du coup, si vous avez la moindre info (des liens vers des articles de références peuvent suffire) concernant la structure en quadtree et son implémentation efficace en Caml, principalement, nous sommes preneurs.

Encore merci pour vos réponses et votre temps.


Bonne fin de week-end à tous.

[gasche]

Je connais mal la structure de quadtree et pas du tout l'algorithme HashLife (enfin son principe oui, mais je ne l'ai jamais codé; je trouve ça amusant et j'ai envisagé d'en faire un exercice), mais à la lecture de votre code il semble effectivement que tu puisses créer un type ainsi:

Code :

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

1
2
3
4
5
6
7
 
  (* une cellule (bool: vivante ou morte) ou un nœud de niveau supérieur *)
  type quadtree =
    | Base of bool array array (* matrice de niveau 2 *)
    | Node of quadnode
  and quadnode = quadtree array
    (* un tableau de taille 4 plutôt qu'un record pour favoriser la factorisation du code *)

OCaml sait hacher des données complexes comme les types `quadtree` ou `quadnode` ci-dessus, donc tu peux l'utiliser tel quel comme clé de hachage. En pratique la fonction de hachage utilisée peut être un peu gourmande et dans un second temps vous pourrez vous poser la question d'en choisir une spécialisée, et peut-être de stocker des informations en plus dans le type quadnode (en en faisant un record/enregistrement) pour ça, mais il faut tester pour savoir si ça en vaut la peine, et en première approche il vaut mieux faire simple.

PS: je n'ai pas stocké le "niveau" dans cette représentation, car je n'ai pas l'impression que ce soit si utile.

[Cacophrene]

Bonsoir,

Quelques pistes suite à votre dernier message.

À propos de la « montagne de boucles » au milieu, ou encore du fait que nous n'utilisons pas des booléens, c'est par ce que nous souhaiterions appliquer le programme à d'autres automates qui ont si possible plus de deux états.

Effectivement, il est préférable de ne pas trop spécialiser le code si vous voulez ensuite l'utiliser avec des automates plus raffinés. Je vous donne néanmoins un exemple d'astuces possibles avec 2 états., avec ce bout de code pas testé. Ce n'est probablement pas beaucoup plus rapide que la version avec boucles. Le principal intérêt : on ne manipule que des entiers, pas de matrice intermédiaire et pas de boucles imbriquées.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
(*      
  Au niveau 2, un carré de 4 x 4
     NW           NE
  n11  n12     n13  n14
  n21  n22     n23  n24
     SW           SE 
  n31  n32     n33  n34
  n41  n42     n43  n44

  Sous la forme d'un seul entier (16 bits) :
  0b n11 n12 n13 n14 n21 n22 n23 n24 n31 n32 n33 n34 n41 n42 n43 n44
*)

type dir = NW | NE | SW | SE

(* On ne garde que les huit cases adjacentes. *)
let mask = function
  | NW -> 0b1110101011100000
  | NE -> 0b0111010101110000
  | SW -> 0b0000111010101110
  | SE -> 0b0000011101010111

(* État d'une cellule à la génération N. *)
let state dir sq =
  let n = match dir with 
    | NW -> 10 | NE -> 9 
    | SW -> 6  | SE -> 5
  in (sq lsr n) land 1

(* Compte le nombre de cellules adjacentes en vie. *)
let count =
  let rec loop k = function
    | 0 -> k
    | i -> loop (k + 1) (i land (i - 1))
  in loop 0

let neighbors dir sq = count (sq land mask dir)

(* Détermine l'état à la génération N + 1. *)
let next dir sq =
  let n = neighbors dir sq and s = state dir sq in
  (s = 0 && n = 3) || (s = 1 && (n = 2 || n = 3))

let evolve sq = next NW sq, next NE sq, next SW sq, next SE sq

(* Tous les cas de base. *)
let base () = Array.init 65536 evolve

Mais le cœur du problème n'est pas là, il s'agit bien sur de la structure en quadtree, en lien avec l'utilisation de chaîne de caractères. Nous avons longtemps patiné là dessus pour diverses raisons. Sur le papier, nous pensons avoir correctement appréhendé la structure et la gestion des quadtree dans la récursivité, mais nous avons eu du mal au moment de passer à Caml.

En fait, le quadtree en question semble perdre sa profondeur parce que chaque niveau fait l'objet d'un stockage dans une table de hachage, de sorte que deux arbres de même niveaux contenant des cellules dans la même configuration sont remplacés par un même "lien" vers cet arbre, ce qui permet de "factoriser l'espace".

Une des raisons qui nous a poussé à prendre des chaînes de caractères, c'est qu'avec cette méthode nous pouvons retrouver les sous-arbres directement à partir du nom de l'arbre principal ; c'est important puisque nous devons ensuite chercher ces sous-arbres dans la table de hachage.

Vous avez besoin d'une fonction de hachage assez performante, mais aussi d'un moyen efficace pour trouver les clefs de hachage des sous-arbres... comment faire ? Selon moi, en découpant le problème en sous-problèmes plus simples. Je verrai bien :

• Implémenter l'algorithme avec un type quadtree classique (comme celui donné par gasche ci-dessus). Le tester sur de petits univers.
• S'attaquer au problème du hachage.
• Généraliser le code à des automates quelconques.

Cordialement,
Cacophrène

[Uncaught_exception]

En fait, le quadtree en question semble perdre sa profondeur parce que chaque niveau fait l'objet d'un stockage dans une table de hachage, de sorte que deux arbres de même niveaux contenant des cellules dans la même configuration sont remplacés par un même "lien" vers cet arbre, ce qui permet de "factoriser l'espace".

C'est ce que nous avons voulu faire en stockant les arbres dans différentes tables de hachage, en fonction du degré.

PS: je n'ai pas stocké le "niveau" dans cette représentation, car je n'ai pas l'impression que ce soit si utile.

D'où la présence du degré qui permettait de savoir dans quelle table chercher et donc de ne pas avoir à chercher dans une table commune. Un pré-tri en quelque sorte. Mais l'utilisation des chaines de caractère à fait perdre un peu d'intérêt à la méthode. Avec le type de Gasche, ne serait-il pas bon de réutiliser cette méthode ou est-ce inutile ?
De plus nous aurions besoin de savoir comment Caml gère les clefs de hachage. Y a-t-il injectivité, i.e. ne risque-t-il pas d'y avoir « superposition » au niveau des clefs dû au grand nombre d'arbre à stocker ?

Pour l'utilisation des entiers, on y avait réfléchie mais rejeté cette solution pour je ne sais quelle raison que le code de Cacophrene semble dépasser. Qui plus est, elle doit pouvoir se généraliser sans trop de difficultés à un plus grand nombre d'état en utilisant une base octale ou hexadécimale.

On va essayer de recoder tout ça en utilisant le type de Gasche et l'astuce de Cacophrene. On vous tient au courant !

[Uncaught_exception]

Premier essai ; premiers échecs.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
type quadtree =
| Base of int array array
| Node of quadnode
and quadnode = quadtree array;;
 
let horizontal a1 a2 = match (a1, a2) with
    | (Base a, Base b) -> Base [|a.(1); b.(0); a.(3); b.(2)|]
    | (Node a, Node b) -> Node [|a.(1); b.(0); a.(3); b.(2)|]
    | _ -> failwith "Horizontal";;
 
let vertical a1 a2 = match (a1, a2) with
    | (Base a, Base b) -> Base [|a.(2); a.(3); b.(0); b.(1)|]
    | (Node a, Node b) -> Node [|a.(2); a.(3); b.(0); b.(1)|]
    | _ -> failwith "Vertical";;

En utilisant le type de Gasche, on arrive à coder assez simplement les fonctions horizontal et vertical, mais ça se complique pour la fonction centre. Pour rappel, la transformation est la suivante :

Code :

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

1
2
3
4
5
6
7
 
   NO          NE
n11  n12    n21  n22
n13  n14    n23  n24               n14  n23
   SO          SE          —> 
n31  n32    n41  n42               n32  n41
n33  n34    n43  n44

Le problème est que l'on doit par exemple accéder à n14 de deux niveaux inférieur, ce qui semble assez lourd s'il faut utiliser des match a with | Base -> etc. Du coup on se demande si on ne rate pas une astuce d'écriture. Des idées ?

[gasche]

J'ai proposé ce type comme une approximation, il faut peut-être l'améliorer un peu. Par exemple il faudrait peut-être des constructeurs de base pour les niveau 1 et 2, à voir.

Dans le cas de la fonction "centre", il me semble (mais je me trompe peut-être) que tu ne l'appelles de toute façon que sur des arbres de niveau au moins deux, donc tu n'as pas besoin de filtrer le cas de base:

Code :

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

1
2
3
4
5
6
 
exception Not_deep_enough
 
let rec centre = function
  | Node [|Node n0; Node n1; Node n2; Node n3|] -> Node [|n0.(3); n1.(2); n2.(1); n3.(0)|]
  | _ -> raise Not_deep_enough

(Question pour les experts: profiterait-t-on de l'utilisation d'un type récursif non régulier ici ?)

[Uncaught_exception]

Bonsoir,


On vient de réimplémenter le code avec vos suggestions. Si le gain de temps est important pour la création des cas de base, l'utilisation du type quadtree à la place des chaines de caractère rend l'exécution du programme beaucoup plus longue ! Mais vraiment beaucoup plus longue. Ce n'était pas vraiment le but cherché… Du plus, si on le lance avec des espaces de dimension supérieure à 128x128, on obtient Exception: Invalid_argument "index out of bounds", alors que l'on pouvait aller jusqu'à 1024x1024 avec les chaines de caractère. De plus, le programme ralentit au cours de l'exécution, chose étrange car contraire à la logique du programme.

Voici le nouveau code, à comparer avec l'ancien code aussi fourni.

[gasche]

C'est clairement la table de hachage qui pose problème, en remplaçant la fonction "h" pour ne plus mémoriser le résultat vient très vite (chez moi, c'est plus rapide que la version précédente avec chaînes et mémoisation).

Je pense qu'il va donc falloir définir votre propre technique de hachage avec Hashtbl.Make.

[Cacophrene]

Bonsoir,

J'ai survolé le code. Ça me paraît déjà mieux construit.

J'ai l'impression que vous perdez beaucoup de temps à convertir le cas de base en entier à partir d'un tableau... il y a un souci avec la fonction numerote qui, effectivement, si elle travaille avec des entiers à tous les niveaux de l'arbre, va finir par renvoyer des valeurs inattendues...

Pour la suite, il faut que je regarde plus précisément.

Pour gasche : tu suggères une structure avec un type 'a pour les arbres de la génération N et un type 'b pour ceux de la génération N + 1, qui permettrait de chercher dans un sens et dans l'autre ?

Cordialement,
Cacophrène

[Cacophrene]

Bonjour,

Le matin aide mieux à réfléchir... essayez ceci :

Code :

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

1
2
3
4
5
6
and h d arb =
  let h = Hashtbl.hash arb in
  match try Some (Hashtbl.find tab.(d-2) h) with _ -> None with
  | Some a -> a
  | None -> let a = traite arb in Hashtbl.add tab.(d - 2) h a; a

Grosso modo, au lieu d'avoir une table de type (quadtree, quadtree) Hashtbl.t, on a une table de type (int, quadtree) Hashtbl.t.
Reste à voir si le résultat final est bon et s'il y a des collisions... au besoin, il faudra réécrire une version personnalisée...

Cordialement,
Cacophrène

[Ptival]

Code :

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

1
2
3
4
5
6
and h d arb =
  let h = Hashtbl.hash arb in
  match try Some (Hashtbl.find tab.(d-2) h) with _ -> None with
  | Some a -> a
  | None -> let a = traite arb in Hashtbl.add tab.(d - 2) h a; a

Je ne vois pas l'intérêt du passage par une option ici.

Code :

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

1
2
3
4
5
and h d arb =
  let h = Hashtbl.hash arb in
  try Hashtbl.find tab.(d-2) h with
  | _ -> let a = traite arb in Hashtbl.add tab.(d - 2) h a; a

[Cacophrene]

Bonjour,

Je ne vois pas l'intérêt du passage par une option ici.

Cette écriture à base d'option n'est clairement pas le point central de la fonction. Il s'agit avant tout pour moi de mettre le focus sur l'utilisation de Hashtbl.hash. Cependant, pour des questions pédagogiques, je préfère toujours la deuxième forme. En effet, cette écriture en apparence alambiquée permet de ne pas perdre un tail rec de façon subtile à cause du try...with. Nous avons souvent rencontré ce genre de souci sur ce forum. Puis, justement, si ça suscite la question...

Cordialement,
Cacophrène

[Cacophrene]

Bonsoir,

Je me permets d'ajouter un nouveau message à ce fil de discussion pour apporter un peu plus d'explications sur l'intérêt de remplacer le type quadtree par un type int dans les tables de hachage. Si on exécute le programme sur 200 générations (1000 c'est trop long) avec les deux versions de la fonction de mémorisation h, le programme gprof nous donne les indications suivantes :

Pour la version initiale à base de tables de type (quadtree, quadtree) Hashtbl.t

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 time   seconds   seconds    calls   s/call   s/call  name    
 95.27    180.06   180.06 536377159     0.00     0.00  compare_val
  1.88    183.62     3.56   180860     0.00     0.00  camlHashtbl__find_rec_1088
  1.52    186.49     2.87 536377109     0.00     0.00  caml_compare
  0.88    188.15     1.66                             caml_c_call
  0.12    188.37     0.22                             compare_stack_overflow
  0.09    188.54     0.17                             caml_equal
  0.06    188.65     0.11   324155     0.00     0.00  hash_aux
  0.05    188.74     0.09   181032     0.00     0.00  camlHashtbl__find_1093
  0.02    188.78     0.04   450580     0.00     0.00  camlBefore__centre_1114
  0.02    188.82     0.04      139     0.00     0.00  mark_slice

Pour la version modifiée à base de tables de type (int, quadtree) Hashtbl.t

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
 time   seconds   seconds    calls  ms/call  ms/call  name    
 50.00      0.03     0.03       14     2.14     2.14  mark_slice
 16.67      0.04     0.01   262258     0.00     0.00  caml_fl_allocate
 16.67      0.05     0.01    65536     0.00     0.00  camlAfter__calcul_1063
 16.67      0.06     0.01       13     0.77     0.77  sweep_slice
  0.00      0.06     0.00   262319     0.00     0.00  caml_oldify_one
  0.00      0.06     0.00   262252     0.00     0.00  allocate_block
  0.00      0.06     0.00   262252     0.00     0.00  caml_alloc_shr
  0.00      0.06     0.00   262145     0.00     0.00  caml_curry2_1
  0.00      0.06     0.00   262144     0.00     0.00  camlAfter__auxi_1052
  0.00      0.06     0.00   262144     0.00     0.00  camlAfter__etat_1047

Ces listings nous indiquent que la version initiale passe l'immense majorité de son temps à comparer des arbres. Et pour cause, si on regarde l'implémentation de la fonction Hashtbl.find, on trouve ceci :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
let rec find_rec key = function
    Empty ->
      raise Not_found
  | Cons(k, d, rest) ->
      if compare key k = 0 then d else find_rec key rest

let find h key =
  match h.data.((hash key) mod (Array.length h.data)) with
    Empty -> raise Not_found
  | Cons(k1, d1, rest1) ->
      if compare key k1 = 0 then d1 else
      match rest1 with
        Empty -> raise Not_found
      | Cons(k2, d2, rest2) ->
          if compare key k2 = 0 then d2 else
          match rest2 with
            Empty -> raise Not_found
          | Cons(k3, d3, rest3) ->
              if compare key k3 = 0 then d3 else find_rec key rest3

En clair, pour obtenir de bonnes performances, on doit rendre la comparaison des clefs aussi rapide que possible. On comprend naturellement que la comparaison d'entiers est beaucoup plus rapide que la comparaison de quadtrees.

Reste un problème pour lequel je n'ai pas vraiment d'idées : existe-t-il deux quadtrees x et y tels que x <> y et Hashtbl.hash x = Hashtbl.hash y ? Ce genre de collisions existe sûrement puisque toute "bonne" voire "excellente" fonction de hachage est un compromis entre la performance du calcul et le nombre de collisions.. je ne sais pas dans quelle mesure ça arrive en pratique dans ce contexte mais ça me semble une question cruciale pour garantir le bon déroulement du programme. On doit peut-être ajuster les paramètres avec Hashtbl.hash_param... à voir.

Cordialement,
Cacophrène

[gasche]

Oui, je pense que tu rencontreras des collisions.

As-tu testé les performances contre la version qui ne hache rien du tout, et se passe complètement de mise en cache ?

(Je pense que la seule façon de faire plus rapide, en évitant les comparaisons en profondeur, est de faire du hash-consing propre dès le début. Cf. par exemple cet article.