Re: Structures non mutables performantes

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.

What every programmer should know about memory est une lecture vivement conseillée dans ce cas.

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. [...]

Il est vrai qu'une suite de set vas créer une cascade de Diff qu'il faudra résoudre lors du premier get. En gros, le premier get est en O(n) avec n le nombre de set fait pendant ce temps. Mais en analyse amortie, je pense que c'est équivalent, puisque le temps "gagné" à ne pas faire le reroot lors de chaque set sera "utilisé" lors du premier get.

Par contre, cela change pas mal le comportement en mémoire. Dans mon cas, le garbage collector ne vas pas supprimer les n Diff intermédiaires, tant qu'il n'y aura pas de reroot, même si les vecteurs précédents ne sont pas utilisés.

Quoi qu'il arrive, cette structure se comporte très mal quand tu utilises les anciennes copies. cela coûte très chère si tu essayes d’accéder consécutivement à deux version assez éloignées, car il faut reroot en permanence entre les deux, avec un O(n), n étant le nombre d'étape séparant les deux.

En Haskell, dans mon implémentation paresseuse, c'est encore plus drôle si tu met à jour des cases avec le contenu d'un vecteur précédant (voir futur si tu as envie, c'est la beauté d'Haskell). Imagine le code suivant :

vec = ... -- on a un vecteur initialisé
vec2 = update vec 0 (index vec 0 + 1) -- incremente la case 0
vec3 = update vec2 0 (index vec2 0 + 1) -- incrémente encore la case 0
print vec3

chaque opération est paresseuse, donc en fait, vec2 et vec3 ne sont que des opérations paresseuses. Quand tu vas vouloir afficher vec3, il vas d'abord construire le Diff sur vec2 qui est un Diff sur vec. Puis, pour afficher la case 0, il va reroot sur vec3 jusqu'à réaliser que la case 0 c'est index vec2 0 + 1, donc il va reroot sur vec2, pour réaliser que c'est une fonction de vec, donc il vas reroot sur vec. Fin de l'évaluation paresseuse de la case 0. Pour passer à la case 1, il doit de nouveau reroot sur vec3, et là c'est bon. On peut bien évidemment contrôler ce comportement en forçant l'évaluation paresseuse judicieusement, mais quoi qu'il arrive il y aura des comportements tordus.

Par contre, j'ai benché mon code en ajoutant des lectures, puisque sinon la seule chose que on faisait c'est empiler des création de Diff, et il est clair qu'il y a une différence non négligeable de performance car le reroot doit être effectué, et en fonction du pattern d'utilisation, les performances peuvent être catastrophiques.

En gros, nous avons une structure persistante qui remplace un vecteur, mais dont les performances se cassent la gueule en fonction du nombre de versions partagées, et dont la place mémoire dépend du nombre de versions partagées et du nombre d'étapes entre les versions partagées. Bref, j'en arrive à conclure que c'est une structure amusante, mais pas si performante que cela. Je pense que on peut faire beaucoup mieux avec un HAMT qui conserve des propriétés de modification / insertion en O(log n) avec une très grosse base pour le log. La librairie unordered-containers utilise une base 16 pour le trie.

Après, j'utiliserais sans doute un vecteur mutable, ou, quand cela sortira, des vecteurs en type "linéaires".