L’immuabilité nuit-elle aux performances en JavaScript?

Il semble y avoir une tendance récente en JavaScript à considérer les structures de données comme immuables. Par exemple, si vous devez modifier une propriété unique d'un objet, il est préférable de créer un nouvel objet entier avec la nouvelle propriété et de copier toutes les autres propriétés de l'ancien objet, et de laisser le vieil objet récupéré. (C'est ce que je comprends quand même.)

Ma première réaction est que cela pourrait être mauvais pour la performance.

Mais les bibliothèques comme Immutable.js et Redux.js sont écrits par des gens plus intelligents que moi, et semblent avoir une forte préoccupation pour la performance, il me demande si ma compréhension des ordures (et son impact sur les performances) est erronée.

L'immuabilité me manque-t-elle en termes de performances et l'emporte-t-il sur les inconvénients liés à la création de tant de déchets?

Par exemple, si vous devez modifier une propriété unique d'un objet, il est préférable de créer un nouvel objet entier avec la nouvelle propriété et de copier toutes les autres propriétés de l'ancien objet, et de laisser le vieil objet récupéré.

Sans immuabilité, vous devrez peut-être faire passer un objet entre différentes portées et vous ne savez pas à l'avance si et quand l'objet sera modifié. Donc, pour éviter les effets secondaires indésirables, vous commencez à créer une copie complète de l'objet "au cas où" et à transmettre cette copie, même s'il s'avère qu'aucune propriété ne doit être modifiée du tout. Cela laissera beaucoup plus de déchets que dans votre cas.

Cela montre bien que si vous créez le scénario hypothétique approprié, vous pouvez tout prouver, notamment en matière de performance. Mon exemple, cependant, n’est pas aussi hypothétique que cela puisse paraître. Le mois dernier, j'ai travaillé sur un programme dans lequel nous sommes tombés sur ce problème, car nous avions initialement décidé de ne pas utiliser une structure de données immuable. Nous avons hésité à le reformuler plus tard, car cela ne valait pas la peine.

Ainsi, lorsque vous regardez des cas comme celui-ci dans un ancien billet SO , la réponse à vos questions devient probablement claire - cela dépend . Dans certains cas, l’immuabilité nuira aux performances, pour d’autres, le contraire pourrait être vrai. Dans de nombreux cas, cela dépendra de l’intelligence de votre implémentation et, dans bien d’autres cas, la différence sera négligeable.

Une dernière remarque: un problème réel que vous pourriez rencontrer est la nécessité de décider tôt pour ou contre l’immuabilité de certaines structures de données de base. Ensuite, vous construisez beaucoup de code à ce sujet, et plusieurs semaines ou mois plus tard, vous verrez si la décision est bonne ou mauvaise.

Ma règle personnelle pour cette situation est:

• Si vous concevez une structure de données avec seulement quelques attributs basés sur des types primitifs ou d'autres types immuables, essayez d'abord l'immutabilité.
• Si vous souhaitez concevoir un type de données impliquant des tableaux de grande taille (ou non définis), d'accès aléatoire et de modification du contenu, utilisez la mutabilité.

Pour les situations entre ces deux extrêmes, utilisez votre jugement. Mais YMMV.

Tout d’abord, votre caractérisation des structures de données immuables est imprécise. En général, la plupart des structures de données ne sont pas copiées, mais partagées , et seules les parties modifiées sont copiées. C'est ce qu'on appelle une structure de données persistante . La plupart des implémentations sont capables de tirer parti des structures de données persistantes la plupart du temps. Les performances sont suffisamment proches des structures de données modifiables que les programmeurs fonctionnels considèrent généralement comme négligeables.

Deuxièmement, je trouve que beaucoup de gens ont une idée assez erronée de la durée de vie typique des objets dans les programmes impératifs typiques. Cela est peut-être dû à la popularité des langages gérés par la mémoire. Asseyez-vous de temps en temps et examinez vraiment le nombre d'objets temporaires et de copies défensives que vous créez par rapport aux structures de données réellement pérennes. Je pense que vous serez surpris par le ratio.

Dans les cours de programmation fonctionnelle que j'enseigne, certaines personnes ont remarqué combien de déchets un algorithme créait, puis je montrais la version impérative typique du même algorithme qui en créait autant. Juste pour une raison quelconque, les gens ne le remarquent plus.

En encourageant le partage et en décourageant la création de variables jusqu'à ce que vous ayez une valeur valide à leur attribuer, l'immutabilité tend à encourager des pratiques de codage plus propres et des structures de données plus durables. Cela conduit souvent à des niveaux de déchets comparables, voire inférieurs, en fonction de votre algorithme.

Vous êtes arrivé tard dans cette séance de questions-réponses avec déjà d'excellentes réponses, mais je voulais m'immiscer en tant qu'étranger habitué à regarder les choses du point de vue inférieur des bits et des octets en mémoire.

Je suis très enthousiasmé par les conceptions immuables, même du point de vue du C, et par le fait de trouver de nouvelles façons de programmer efficacement ce matériel bestial que nous avons de nos jours.

Plus lent / plus rapide

Pour ce qui est de savoir si cela ralentit les choses, une réponse robotique le serait yes. À ce genre de niveau conceptuel très technique, l’immuabilité ne pourrait que ralentir les choses. Le matériel fonctionne mieux lorsqu'il n'alloue pas de mémoire de façon sporadique et qu'il peut simplement modifier la mémoire existante (pourquoi nous avons des concepts comme la localité temporelle).

Pourtant, une réponse pratique est maybe. La performance reste largement une mesure de la productivité dans toute base de code non triviale. En règle générale, nous ne pensons pas que les bases de code horribles à maintenir les plus efficaces, même si nous ne tenons pas compte des bogues, se démarquent par rapport aux conditions de concurrence. L'efficacité dépend souvent de l'élégance et de la simplicité. Le pic de micro-optimisations peut être quelque peu conflictuel, mais celles-ci sont généralement réservées aux sections de code les plus petites et les plus critiques.

Transformer les bits et octets immuables

En venant du point de vue de bas niveau, si nous xRay des concepts tels que objectset stringset ainsi de suite, au cœur de celui - ci est seulement bits et d' octets dans différentes formes de mémoire avec différentes caractéristiques vitesse / taille (vitesse et la taille du matériel de mémoire étant typiquement mutuellement exclusives).

La hiérarchie de la mémoire de l’ordinateur l’apprécie lorsque nous accédons de manière répétée au même bloc de mémoire, comme dans le diagramme ci-dessus, car il conserve le bloc de mémoire fréquemment utilisé dans la forme de mémoire la plus rapide (cache L1, par exemple). est presque aussi rapide qu'un registre). Nous pouvons accéder de manière répétée à la même mémoire (en la réutilisant plusieurs fois) ou de manière répétée, en accédant à différentes sections du fragment (par exemple, en parcourant les éléments dans un fragment contigu qui accède de manière répétée à différentes parties de ce fragment de mémoire).

Nous finissons par jeter une clé dans ce processus si la modification de cette mémoire finit par vouloir créer un tout nouveau bloc de mémoire sur le côté, comme suit:

... dans ce cas, l'accès au nouveau bloc de mémoire peut nécessiter des fautes de page obligatoires et des erreurs de cache pour le replacer dans les formes de mémoire les plus rapides (jusqu'au bout d'un registre). Cela peut être un véritable tueur de performance.

Il existe cependant des moyens de limiter ce problème en utilisant un pool de réserve de mémoire préallouée, déjà touché.

Gros agrégats

Un autre problème conceptuel découlant d'une vue légèrement supérieure consiste simplement à faire des copies inutiles de très grands agrégats en bloc.

Pour éviter un diagramme trop complexe, imaginons que ce simple bloc de mémoire soit assez coûteux (peut-être des caractères UTF-32 sur un matériel incroyablement limité).

Dans ce cas, si nous voulions remplacer "HELP" par "KILL" et que ce bloc de mémoire était immuable, nous devions créer un tout nouveau bloc dans son intégralité pour créer un nouvel objet unique, même si certaines parties seulement avaient changé. :

Allongeant un peu notre imagination, cette sorte de copie en profondeur de tout le reste, juste pour rendre une petite pièce unique, pourrait coûter assez cher (dans le cas réel, ce bloc de mémoire serait bien plus gros pour poser problème).

Cependant, malgré une telle dépense, ce type de conception aura tendance à être beaucoup moins sujet aux erreurs humaines. Quiconque a travaillé dans un langage fonctionnel avec des fonctions pures peut probablement l’apprécier, en particulier dans les cas multithreads où nous pouvons multithreader un tel code sans aucun souci. En général, les programmeurs humains ont tendance à trébucher sur les changements d'état, en particulier ceux qui provoquent des effets secondaires externes sur des états situés en dehors du cadre d'une fonction actuelle. Même récupérer d'une erreur externe (exception) dans un tel cas peut être incroyablement difficile avec des changements d'état externes modifiables dans le mix.

Une façon d'atténuer ce travail de copie redondant consiste à transformer ces blocs de mémoire en une collection de pointeurs (ou de références) sur des caractères, comme suit:

_{Toutes mes excuses, je n’ai pas réalisé que nous n’avions pas besoin de créer Lun diagramme unique.}

_{Le bleu indique des données copiées peu profondes.}

... malheureusement, cela coûterait incroyablement cher de payer un coût par pointeur / référence. De plus, nous pourrions disperser le contenu des caractères dans tout l’espace adresse et finir par le payer sous la forme d’un chargement de fautes de page et de cache manquants, rendant ainsi cette solution encore pire qu’une copie intégrale.

Même si nous avons pris soin d’attribuer ces caractères de manière contiguë, disons que la machine peut charger 8 caractères et 8 pointeurs sur un caractère dans une ligne de cache. Nous finissons par charger la mémoire comme ceci pour parcourir la nouvelle chaîne:

Dans ce cas, nous avons besoin de 7 lignes de cache différentes, chargées d’une mémoire contiguë, pour parcourir cette chaîne, alors que, dans l’idéal, nous n’en avons besoin que de 3.

Couper les données

Pour atténuer le problème ci-dessus, nous pouvons appliquer la même stratégie de base mais à un niveau plus grossier de 8 caractères, par exemple

Le résultat nécessite le chargement de 4 lignes de cache de données (1 pour les 3 pointeurs et 3 pour les caractères) afin de traverser cette chaîne qui n’est que de l’optimum théorique.

Donc ce n'est pas mal du tout. Il y a un peu de perte de mémoire, mais la mémoire est abondante et en utiliser davantage ne ralentit pas le processus si la mémoire supplémentaire devient simplement des données froides qui ne sont pas utilisées fréquemment. C'est seulement pour les données chaudes et contiguës où la réduction de l'utilisation de la mémoire et la rapidité vont souvent de pair lorsque nous souhaitons disposer de plus de mémoire dans une seule page ou ligne de cache et y accéder avant l'éviction. Cette représentation est plutôt conviviale en cache.

La vitesse

Donc, utiliser une représentation comme celle ci-dessus peut donner un bon équilibre de performances. Les utilisations les plus critiques en termes de performances des structures de données immuables consistent à modifier des données volumineuses et à les rendre uniques dans le processus, tout en copiant superficiellement des pièces non modifiées. Cela implique également une surcharge d'opérations atomiques pour référencer les éléments copiés peu profonds en toute sécurité dans un contexte multithread (éventuellement avec un comptage de références atomique en cours).

Pourtant, tant que ces données volumineuses sont représentées à un niveau assez grossier, cette surcharge diminue et est peut-être même banalisée, tout en nous offrant la sécurité et la facilité de codage et de multithreading avec davantage de fonctions dans une forme pure sans face extérieure effets.

Garder les anciennes et nouvelles données

Là où je vois l’immuabilité comme potentiellement la plus utile du point de vue de la performance (au sens pratique), c’est quand on peut être tenté de faire des copies complètes de données volumineuses afin de les rendre uniques dans un contexte modifiable où l’objectif est de produire quelque chose de nouveau à partir de. quelque chose qui existe déjà dans une manière où nous voulons garder les nouveaux et les anciens, quand nous pourrions simplement en faire des morceaux uniques avec un design soigné et immuable.

Exemple: Annuler le système

Un exemple de ceci est un système d'annulation. Nous pouvons modifier une petite partie d'une structure de données et vouloir conserver à la fois le formulaire d'origine que nous pouvons annuler et le nouveau formulaire. Avec ce type de conception immuable qui ne rend uniques que les petites sections modifiées de la structure de données, nous pouvons simplement stocker une copie des anciennes données dans une entrée annulée tout en ne payant que le coût en mémoire des données de parties uniques ajoutées. Ceci fournit un équilibre très efficace entre productivité (rendant la mise en œuvre d'un système d'annulation un jeu d'enfant) et performance.

Interfaces de haut niveau

Pourtant, quelque chose de bizarre se pose avec le cas ci-dessus. Dans un contexte de type de fonction local, les données mutables sont souvent les plus faciles et les plus simples à modifier. Après tout, le moyen le plus simple de modifier un tableau consiste souvent à le parcourir en boucle et à modifier un élément à la fois. Nous pouvons augmenter le temps de traitement intellectuel si nous avions le choix entre un grand nombre d’algorithmes de haut niveau pour transformer un tableau et si nous devions choisir celui qui était approprié pour que toutes ces copies peu profondes et volumineuses soient réalisées, tandis que les parties modifiées rendu unique.

Le moyen le plus simple dans ces cas est probablement d’utiliser des tampons modifiables localement dans le contexte d’une fonction (où ils ne nous échappent généralement pas), qui valident de manière atomique les modifications apportées à la structure de données pour obtenir une nouvelle copie immuable (je pense que certaines langues ces "transitoires") ...

... ou nous pourrions simplement modéliser des fonctions de transformation de niveau supérieur et supérieur sur les données afin de pouvoir masquer le processus de modification d'un tampon mutable et de son engagement dans la structure sans impliquer de logique mutable. En tout état de cause, ce n'est pas encore un territoire largement exploré et nous avons du pain sur la planche si nous adoptons des conceptions immuables pour créer des interfaces significatives sur la manière de transformer ces structures de données.

Structures de données

Une autre chose qui se pose ici est que l’immuabilité utilisée dans un contexte de performances critiques voudra probablement que les structures de données se décomposent en données volumineuses où les morceaux ne sont pas trop petits, mais pas trop volumineux.

Les listes chaînées pourraient vouloir changer un peu pour s'adapter à cela et se transformer en listes déroulées. De grands tableaux contigus peuvent se transformer en un tableau de pointeurs en blocs contigus avec index modulo pour un accès aléatoire.

Cela change potentiellement la façon dont nous examinons les structures de données de manière intéressante, tout en poussant les fonctions de modification de ces structures de données à ressembler à une nature plus volumineuse pour masquer la complexité supplémentaire de la copie superficielle de certains bits ici et de leur rendre uniques.

Performance

Quoi qu'il en soit, ceci est ma petite vue de bas niveau sur le sujet. Théoriquement, l'immuabilité peut avoir un coût allant de très grand à plus petit. Mais une approche très théorique ne permet pas toujours aux applications de passer rapidement. Cela peut les rendre évolutives, mais la vitesse réelle nécessite souvent de prendre en compte l’état d’esprit plus pratique.

D'un point de vue pratique, des qualités telles que la performance, la facilité de maintenance et la sécurité ont tendance à se transformer en un flou, en particulier pour une très grande base de code. Bien que la performance dans un sens absolu soit dégradée par l’immutabilité, il est difficile de discuter des avantages qu’elle offre en termes de productivité et de sécurité (y compris la sécurité des threads). Une augmentation de ces performances peut souvent entraîner une augmentation des performances pratiques, ne serait-ce que parce que les développeurs disposent de plus de temps pour ajuster et optimiser leur code sans être envahis par les bugs.

Je pense donc que, du point de vue pratique, des structures de données immuables pourraient effectivement améliorer les performances dans de nombreux cas, aussi étrange que cela puisse paraître. Un monde idéal pourrait rechercher un mélange de ces deux structures: des structures de données immuables et des structures mutables, les structures mutables étant généralement très sûres à utiliser dans un contexte très local (ex: local à une fonction), tandis que les structures immuables peuvent éviter le côté externe effectue les modifications et transforme toutes les modifications apportées à une structure de données en une opération atomique produisant une nouvelle version sans risque de concurrence.

ImmutableJS est en fait assez efficace. Si nous prenons un exemple:

var x = {
    Foo: 1,
    Bar: { Baz: 2 }
    Qux: { AnotherVal: 3 }
}

Si l'objet ci-dessus est rendu immuable, vous modifiez la valeur de la propriété 'Baz':

var y = x.setIn('/Bar/Baz', 3);
y !== x; // Different object instance
y.Bar !== x.Bar // As the Baz property was changed, the Bar object is a diff instance
y.Qux === y.Qux // Qux is the same object instance

Cela crée des améliorations de performances vraiment intéressantes pour les modèles d'objet profonds, dans lesquels il vous suffit de copier les types de valeur sur les objets situés sur le chemin d'accès à la racine. Plus le modèle d'objet est grand et plus les modifications que vous apportez sont petites, meilleures sont les performances de la mémoire et du CPU de la structure de données immuable, car elles finissent par partager un grand nombre d'objets.

Comme l’ont dit les autres réponses, si vous optez pour une tentative de fournir les mêmes garanties en effectuant une copie défensive xavant de la transmettre à une fonction susceptible de la manipuler, les performances sont nettement meilleures.

En ligne droite, le code immuable a la surcharge de la création d'objet, qui est plus lente. Cependant, il existe de nombreuses situations dans lesquelles le code mutable devient très difficile à gérer efficacement (ce qui entraîne beaucoup de copies défensives, ce qui est également coûteux), et il existe de nombreuses stratégies astucieuses pour atténuer le coût de la "copie" d'un objet. , comme mentionné par d'autres.

Si vous avez un objet tel qu'un compteur et qu'il s'incrémente plusieurs fois par seconde, le fait que ce compteur soit immuable ne vaut peut-être pas la pénalité de performance. Si vous avez un objet qui est lu par différentes parties de votre application et que chacun d'entre eux veut avoir son propre clone légèrement différent, vous aurez beaucoup plus de facilité à l'orchestrer de manière performante en utilisant un bon implémentation d'objet immuable.

Pour ajouter à cette question (déjà parfaitement répondue) la question:

La réponse courte est oui ; cela nuira aux performances, car vous ne créez que des objets au lieu de les transformer en mutants, ce qui entraîne une charge supplémentaire pour la création d'objets.

Cependant, la réponse longue n'est pas vraiment .

Du point de vue de l'exécution, en JavaScript, vous créez déjà pas mal d'objets d'exécution. Les fonctions et les littéraux des objets sont omniprésents en JavaScript et personne ne semble y penser à deux fois. Je dirais que la création d’objets est en réalité assez peu coûteuse, bien que je n’aie pas de citations à ce sujet, je ne l’utiliserais donc pas comme argument autonome.

Pour moi, la plus forte augmentation des «performances» ne concerne pas les performances d'exécution, mais les performances des développeurs . Une des premières choses que j'ai apprises en travaillant sur des applications Real World (tm) est que la mutabilité est vraiment dangereuse et déroutante. J'ai perdu de nombreuses heures à courir après un fil d'exécution (pas le type de concurrence) en essayant de comprendre ce qui cause un bogue obscur lorsqu'il s'avère être une mutation de l'autre côté de cette fichue application!

L'utilisation de l'immuabilité rend les choses beaucoup plus faciles à raisonner. Vous êtes en mesure de savoir immédiatement que l’objet X ne changera pas au cours de sa vie, et le seul moyen de le changer est de le cloner. J'attache beaucoup plus d'importance à cela (surtout dans les environnements d'équipe) qu'à toutes les micro-optimisations que la mutabilité pourrait apporter.

Il existe des exceptions, notamment des structures de données, comme indiqué ci-dessus. J'ai rarement rencontré un scénario dans lequel je souhaitais modifier une carte après sa création (bien que je parle certes de cartes pseudo-objets-littéraux plutôt que de cartes ES6), de même pour les tableaux. Lorsque vous avez affaire à de plus grandes structures de données, la mutabilité peut porter ses fruits. N'oubliez pas que chaque objet en JavaScript est passé comme référence plutôt que comme valeur.

Cela dit, l’un des points évoqués ci-dessus concerne le GC et son incapacité à détecter les doublons. C’est une préoccupation légitime, mais à mon avis, c’est seulement lorsque la mémoire est une préoccupation, et il existe des moyens bien plus simples de vous coder - par exemple, des références circulaires dans les fermetures.

En fin de compte, je préférerais avoir une base de code immuable avec très peu (le cas échéant) de sections mutables et être légèrement moins performant que d’avoir une mutabilité partout. Vous pouvez toujours optimiser plus tard si l’immuabilité, pour une raison quelconque, devient une préoccupation pour les performances.