Re: Structures non mutables performantes

La réciproque est fausse, à savoir qu'il existe des structures de données persistantes faisant usage d'effets de bord.

J'ai eu cette révélation quand j'ai commencé à faire de la Memoization en Haskell.

Tu as bien compris ce que je raconte, la liste l partagée entre l1 et l2 peut être vue comme un shared_ptr. Sauf que en Haskell (et je crois en OCaml), la gestion de la mémoire est faite avec un GC traçant, alors que là en C++ c'est un comptage de référence, avec ses avantages et inconvénients.

Tu as bien compris l'usage de shared_ptr, sauf que dans ce cas de figure c'est loin d’être trivial puisque en fait il faut garder un weak_ptr sur chaque shared_ptr... Bref, je me suis amusé un peu et cela donne ça :

https://gist.github.com/guibou/73c33d9e511385f4c52b313cb3d4d0e6

Version C++ et Haskell.

La version C++ est peu propre, il y aurait pas mal de choses à traiter pour faire un vrai truc qui marche. La version Haskell et pas mal mais fait peur car en Haskell il faut faire un choix :

• Pas d'effet de bord, c'est facile
• Des effets de bord, ils sont alors visible par le biais de :
  • IO, des effets de bords
  • ST, des effets de bords qui sont limités à une fonction et que le compilateur peu garantir comme étant limités à une fonction.
  • unsafePerformIO, des effets de bords qui ne sont pas limités à une fonction et pour lequel c'est ton boulot de développeur de garantir que tu ne fais pas n'importe quoi. C'est ce que j'ai essayé de faire, mais sans garantie ;)

Note, si mon benchmark n'est pas faux (j'ai des doutes quand je manipule des effets de bords de ce type), alors :

• modifier un vecteur non mutable (i.e.: créer une copie) c'est super rapide sur des petits vecteurs, mais cela devient linéairement lent avec la taille du vecteur qui augmente
• modifier un vecteur avec ta technique c'est en O(1)
• modifier un vecteur "vraiment" mutable vue de l’extérieur est un poil plus rapide.

Merci pour la discussion, je me suis amusé.