Au sujet de la gestion automatique de la mémoire, je dois dire que je n'y connais pas grand chose. Tout comme sur le fonctionnement interne des CPU et de leur cache.
En revanche, j'ai reréfléchi à ton implémentation de update et je doute qu'elle soit optimale pour l'usage de cette structure. Déjà on perd totalement l'intérêt d'avoir un tableau modifiable en interne : tu n'utilises jamais son set en O(1). Et comme tu ne rerootes pas sur le V.IOVector avant de modifier le valeur à un index donné, au fur et à mesure tu ajoutes des indirections à coup de Diff par rapport au tableau : au prochain get sur un tableau nouvellement créé, tu te retrouves à aller chercher l'équivalent du dernier élément d'une liste chaînée dont le temps sera proportionnel au nombre de set que tu auras fait (tu as une chose du genre Diff Diff Diff ... (Array v)). Là où avec l'implémentation proposée en OCaml le nombre de Diff reste petit : le nouveau tableau est juste une référence sur un tableau boxé (ref (Arr a)) et l'ancien (celui passé en entrée) et maintenant un Diff sur le nouveau et reste donc à une distance 1 d'un « véritable » tableau (Diff (idx,v,ref (Arr a))). Ton code risque d'en pâtir sur la complexité en temps des get.
Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
[^] # Re: Structures non mutables performantes
Posté par kantien . En réponse à la dépêche Sortie de GHC 8.2.1. Évalué à 2.
Au sujet de la gestion automatique de la mémoire, je dois dire que je n'y connais pas grand chose. Tout comme sur le fonctionnement interne des CPU et de leur cache.
En revanche, j'ai reréfléchi à ton implémentation de
updateet je doute qu'elle soit optimale pour l'usage de cette structure. Déjà on perd totalement l'intérêt d'avoir un tableau modifiable en interne : tu n'utilises jamais sonseten O(1). Et comme tu ne rerootes pas sur leV.IOVectoravant de modifier le valeur à un index donné, au fur et à mesure tu ajoutes des indirections à coup deDiffpar rapport au tableau : au prochaingetsur un tableau nouvellement créé, tu te retrouves à aller chercher l'équivalent du dernier élément d'une liste chaînée dont le temps sera proportionnel au nombre desetque tu auras fait (tu as une chose du genreDiff Diff Diff ... (Array v)). Là où avec l'implémentation proposée en OCaml le nombre deDiffreste petit : le nouveau tableau est juste une référence sur un tableau boxé (ref (Arr a)) et l'ancien (celui passé en entrée) et maintenant unDiffsur le nouveau et reste donc à une distance 1 d'un « véritable » tableau (Diff (idx,v,ref (Arr a))). Ton code risque d'en pâtir sur la complexité en temps desget.Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.