Utilisation de structures de données persistantes dans des langages non fonctionnels

Les langages purement fonctionnels ou presque purement fonctionnels bénéficient de structures de données persistantes car ils sont immuables et correspondent bien au style sans état de la programmation fonctionnelle.

Mais de temps en temps, nous voyons des bibliothèques de structures de données persistantes pour les langages (basés sur l'état, OOP) comme Java. Une revendication souvent entendue en faveur des structures de données persistantes est que, parce qu'elles sont immuables, elles sont thread-safe .

Cependant, la raison pour laquelle les structures de données persistantes sont thread-safe est que si un thread devait "ajouter" un élément à une collection persistante, l'opération renvoie une nouvelle collection comme l'original mais avec l'élément ajouté. D'autres fils voient donc la collection originale. Les deux collections partagent beaucoup d'état interne, bien sûr - c'est pourquoi ces structures persistantes sont efficaces.

Mais comme différents threads voient des états de données différents, il semblerait que les structures de données persistantes ne soient pas en elles-mêmes suffisantes pour gérer des scénarios dans lesquels un thread effectue une modification visible pour les autres threads. Pour cela, il semble que nous devons utiliser des dispositifs tels que des atomes, des références, de la mémoire transactionnelle logicielle, ou même des verrous classiques et des mécanismes de synchronisation.

Pourquoi alors, l'immuabilité des PDS est-elle présentée comme quelque chose de bénéfique pour la «sécurité des threads»? Existe-t-il de vrais exemples où les PDS aident à la synchronisation ou à la résolution de problèmes de concurrence? Ou les PDS sont-ils simplement un moyen de fournir une interface sans état à un objet à l'appui d'un style de programmation fonctionnel?

Les structures de données persistantes / immuables ne résolvent pas seules les problèmes de concurrence, mais elles les résolvent beaucoup plus facilement.

Considérons un thread T1 qui transmet un ensemble S à un autre thread T2. Si S est mutable, T1 a un problème: il perd le contrôle de ce qui se passe avec S. Le thread T2 peut le modifier, donc T1 ne peut pas du tout s'appuyer sur le contenu de S. Et vice versa - T2 ne peut pas être sûr que T1 ne modifie pas S pendant que T2 opère dessus.

Une solution consiste à ajouter une sorte de contrat à la communication de T1 et T2 afin qu'un seul des threads soit autorisé à modifier S. Ceci est sujet aux erreurs et pèse à la fois sur la conception et la mise en œuvre.

Une autre solution est que T1 ou T2 clone la structure de données (ou les deux, si elles ne sont pas coordonnées). Cependant, si S n'est pas persistant, il s'agit d'une opération O (n) coûteuse .

Si vous avez une structure de données persistante, vous êtes libre de ce fardeau. Vous pouvez passer une structure à un autre thread et vous n'avez pas à vous soucier de ce qu'elle en fait. Les deux threads ont accès à la version d'origine et peuvent y effectuer des opérations arbitraires - cela n'influence pas ce que l'autre thread voit.

Voir aussi: structure de données persistante vs immuable .

Pourquoi alors, l'immuabilité des PDS est-elle présentée comme quelque chose de bénéfique pour la «sécurité des threads»? Existe-t-il de vrais exemples où les PDS aident à la synchronisation ou à la résolution de problèmes de concurrence?

Le principal avantage d'un PDS dans ce cas est que vous pouvez modifier une partie des données sans tout rendre unique (sans tout copier en profondeur, pour ainsi dire). Cela a de nombreux avantages potentiels en plus de vous permettre d'écrire des fonctions bon marché sans effets secondaires: instancier des données copiées et collées, des systèmes d'annulation triviaux, des fonctionnalités de relecture triviales dans les jeux, une édition non destructive triviale, une sécurité d'exception triviale, etc. etc. etc.

On peut imaginer une structure de données qui serait persistante mais modifiable. Par exemple, vous pouvez prendre une liste liée, représentée par un pointeur sur le premier nœud, et une opération de pré-ajout qui retournerait une nouvelle liste, composée d'un nouveau nœud principal plus la liste précédente. Puisque vous avez toujours la référence à la tête précédente, vous pouvez accéder et modifier cette liste, qui est entre-temps également intégrée à la nouvelle liste. Bien que possible, un tel paradigme n'offre pas les avantages de structures de données persistantes et immuables, par exemple, il n'est certainement pas sûr pour les threads par défaut. Cependant, il peut avoir son utilité tant que le développeur sait ce qu'il fait, par exemple pour économiser de l'espace. Notez également que bien que la structure puisse être modifiable au niveau du langage dans la mesure où rien n'empêche le code de le modifier,

Donc, pour faire court, sans immuabilité (imposée par le langage ou par convention), la persistance des structures de données perd certains de ses avantages (sécurité des threads) mais pas d'autres (efficacité de l'espace pour certains scénarios).

Quant aux exemples de langages non fonctionnels, Java String.substring()utilise ce que j'appellerais une structure de données persistante. La chaîne est représentée par un tableau de caractères plus les décalages de début et de fin de la plage du tableau qui est réellement utilisée. Lorsqu'une sous-chaîne est créée, le nouvel objet réutilise le même tableau de caractères, uniquement avec des décalages de début et de fin modifiés. Étant donné qu'il Stringest immuable, il s'agit (par rapport à l' substring()opération, pas aux autres) d'une structure de données persistante immuable.

L'immuabilité des structures de données est la partie pertinente pour la sécurité des threads. Leur persistance (réutilisation des morceaux existants lorsqu'une nouvelle structure est créée) est pertinente pour l'efficacité lorsque vous travaillez avec de telles collections. Puisqu'ils sont immuables, une opération comme l'ajout d'un élément ne modifie pas la structure existante mais en renvoie une nouvelle, avec l'élément supplémentaire ajouté. Si chaque fois que la structure entière était copiée, en commençant par une collection vide et en ajoutant 1000 éléments un par un pour finir avec une collection de 1000 éléments, créerait des objets temporaires avec 0 + 1 + 2 + ... + 999 = 500000 éléments au total ce qui serait un énorme gaspillage. Avec des structures de données persistantes, cela peut être évité car la collection à 1 élément est réutilisée dans celle à 2 éléments, qui est réutilisée dans celle à 3 éléments et ainsi de suite,

Je suis certes biaisé en tant qu'appliquant de tels concepts en C ++ par le langage et sa nature, ainsi que mon domaine, et même la façon dont nous utilisons le langage. Mais étant donné ces choses, je pense que les conceptions immuables sont l'aspect le moins intéressant lorsqu'il s'agit de récolter une grande partie des avantages associés à la programmation fonctionnelle, comme la sécurité des threads, la facilité de raisonnement sur le système, la recherche de plus de réutilisation pour les fonctions (et la conclusion que nous pouvons les combiner dans n'importe quel ordre sans mauvaises surprises), etc.

Prenez cet exemple C ++ simpliste (certes pas optimisé pour la simplicité pour éviter de m'embarrasser devant des experts en traitement d'image):

// Inputs an image and outputs a new one with the specified size.
Image resized_image(const Image& src, int new_w, int new_h)
{
     Image dst(new_w, new_h);
     for (int y=0; y < new_h; ++y)
     {
         for (int x=0; x < new_w; ++x)
              dst[y][x] = src.sample(x / (float)new_w, y / (float)new_h);
     }
     return dst;
}

Bien que la mise en œuvre de cette fonction mute l'état local (et temporaire) sous la forme de deux variables de compteur et d'une image locale temporaire à produire, elle n'a pas d'effets secondaires externes. Il entre une image et en sort une nouvelle. Nous pouvons le multithread au contenu de nos cœurs. Il est facile de raisonner, de tester en profondeur. C'est exceptionnellement sûr car si quelque chose se déclenche, la nouvelle image est automatiquement supprimée et nous n'avons pas à nous soucier de faire reculer les effets secondaires externes (il n'y a pas d'images externes modifiées en dehors de la portée de la fonction, pour ainsi dire).

Je vois peu à gagner, et potentiellement beaucoup à perdre, en rendant Imageimmuable dans le contexte ci-dessus, en C ++, sauf pour rendre potentiellement la fonction ci-dessus plus difficile à mettre en œuvre, et peut-être un peu moins efficace.

Pureté

Les fonctions pures (sans effets secondaires externes ) sont donc très intéressantes pour moi, et je souligne l'importance de les privilégier souvent aux membres de l'équipe même en C ++. Mais les conceptions immuables, appliquées dans un contexte et des nuances généralement absents, ne sont pas aussi intéressantes pour moi car, étant donné la nature impérative de la langue, il est souvent utile et pratique de pouvoir muter certains objets temporaires locaux dans le processus de manière efficace (à la fois pour développeur et matériel) implémentant une fonction pure.

Copie bon marché de structures lourdes

La deuxième propriété la plus utile que je trouve est la possibilité de copier à moindre coût les structures de données vraiment lourdes lorsque le coût de le faire, comme cela serait souvent encouru pour rendre les fonctions pures compte tenu de leur nature stricte d'entrée / sortie, ne serait pas trivial. Ce ne seraient pas de petites structures pouvant tenir sur la pile. Ce seraient de grandes structures lourdes, comme l'ensemble Scenepour un jeu vidéo.

Dans ce cas, la surcharge de copie pourrait empêcher des opportunités de parallélisme efficace, car il pourrait être difficile de paralléliser la physique et de rendre efficacement sans se verrouiller et se goulotter mutuellement si la physique mute la scène que le moteur de rendu tente simultanément de dessiner, tout en ayant une physique profonde copier la scène de jeu entière juste pour sortir une image avec la physique appliquée pourrait être également inefficace. Cependant, si le système physique était `` pur '' en ce sens qu'il ne faisait qu'entrer une scène et en produire une nouvelle avec la physique appliquée, et qu'une telle pureté ne se faisait pas au détriment des frais généraux de copie astronomique, il pouvait fonctionner en toute sécurité parallèlement à la rendu sans que l'un n'attende l'autre.

Ainsi, la possibilité de copier à moindre coût les données vraiment lourdes de l'état de votre application et de produire de nouvelles versions modifiées avec un coût de traitement et d'utilisation de la mémoire minimal peut vraiment ouvrir de nouvelles portes pour la pureté et le parallélisme efficace, et là je trouve beaucoup de leçons à apprendre de la façon dont les structures de données persistantes sont mises en œuvre. Mais tout ce que nous créons en utilisant de telles leçons ne doit pas être entièrement persistant ou offrir des interfaces immuables (il peut utiliser la copie sur écriture, par exemple, ou un "constructeur / transitoire"), pour atteindre cette capacité à être très bon marché copier et modifier uniquement des sections de la copie sans doubler l'utilisation de la mémoire et l'accès à la mémoire dans notre quête de parallélisme et de pureté dans nos fonctions / systèmes / pipeline.

Immutabilité

Enfin, il y a l'immuabilité que je considère comme la moins intéressante de ces trois, mais elle peut imposer, avec une poigne de fer, lorsque certains modèles d'objet ne sont pas destinés à être utilisés comme temporaires locaux pour une fonction pure, et au lieu de cela dans un contexte plus large, un précieux sorte de "pureté au niveau de l'objet", comme dans toutes les méthodes ne provoquent plus d'effets secondaires externes (ne mutent plus les variables membres en dehors de la portée locale immédiate de la méthode).

Et bien que je le considère comme le moins intéressant de ces trois dans des langages comme C ++, il peut certainement simplifier les tests et la sécurité des threads et le raisonnement des objets non triviaux. Cela peut être une charge de travailler avec la garantie qu'un objet ne peut recevoir aucune combinaison d'états unique en dehors de son constructeur, par exemple, et que nous pouvons le faire circuler librement, même par référence / pointeur sans s'appuyer sur la constance et la lecture. seuls les itérateurs et les poignées et autres, tout en garantissant (enfin, au moins autant que possible dans la langue) que son contenu d'origine ne sera pas modifié.

Mais je trouve cela la propriété la moins intéressante parce que la plupart des objets que je vois aussi bénéfiques que d'être utilisés temporairement, sous une forme mutable, pour implémenter une fonction pure (ou même un concept plus large, comme un "système pur" qui pourrait être un objet ou une série de fonctionne avec l'effet ultime de simplement entrer quelque chose et de sortir quelque chose de nouveau sans toucher à rien d'autre), et je pense que l'immuabilité poussée aux extrémités dans un langage largement impératif est un objectif plutôt contre-productif. Je l'appliquerais avec parcimonie pour les parties de la base de code où cela aide vraiment le plus.

Finalement:

[...] il semblerait que les structures de données persistantes ne soient pas en elles-mêmes suffisantes pour gérer des scénarios où un thread apporte une modification visible aux autres threads. Pour cela, il semble que nous devons utiliser des dispositifs tels que des atomes, des références, de la mémoire transactionnelle logicielle, ou même des verrous classiques et des mécanismes de synchronisation.

Naturellement, si votre conception nécessite que les modifications (au sens de la conception de l'utilisateur) soient visibles simultanément par plusieurs threads au fur et à mesure qu'elles se produisent, nous revenons à la synchronisation ou au moins à la planche à dessin pour trouver des moyens sophistiqués de gérer cela ( J'ai vu des exemples très élaborés utilisés par des experts traitant de ce genre de problèmes en programmation fonctionnelle).

Mais j'ai trouvé qu'une fois que vous obtenez ce type de copie et la capacité de produire des versions partiellement modifiées de structures lourdes à bon marché, comme vous le feriez avec des structures de données persistantes à titre d'exemple, cela ouvre souvent beaucoup de portes et d'opportunités que vous pourriez n'avais pas pensé auparavant à paralléliser du code qui peut s'exécuter complètement indépendamment les uns des autres dans une sorte stricte d'E / S de pipeline parallèle. Même si certaines parties de l'algorithme doivent être de nature sérielle, vous pouvez reporter ce traitement à un seul thread mais constater que s'appuyer sur ces concepts a ouvert des portes pour paralléliser facilement et sans souci 90% du travail lourd, par exemple