---

Mars 2017

Volume 32, numéro 3

Cet article a fait l'objet d'une traduction automatique.

.NET Framework - Collections immuables

Par Hadi Brais | Mars 2017

Effets de compromettre la compréhension et l’exactitude du code. Une méthode qui transforme les variables globales ou statiques a des effets secondaires. Une méthode qui modifie certains de ses paramètres a des effets secondaires. Si vous souhaitez comprendre un morceau de code, vous devez passer par le code de toutes les méthodes qui sont appelées et avoir des effets secondaires. Les méthodes ayant des effets requièrent la synchronisation de threads pour exécuter correctement lorsqu’il existe plusieurs threads.

Que se passe-t-il si vous écrivez des méthodes qui n’ont pas des effets secondaires ? Ce que le code ressemble et comment il effectue ? Vous trouverez en rendant les instances immuable afin que les effets secondaires ne peuvent pas se produire.

En général, lorsqu’une instance d’un type est décrite comme immuable, cela signifie que sa valeur ne change jamais. Immuabilité, comme souvent dans l’ingénierie logicielle, est un choix de conception. Vous ne devez utiliser, mais dans certains scénarios, vous pouvez en bénéficier en termes de performances du code ou la compréhension. Il est en fait souvent utile que c’est un des principes fondamentaux du paradigme de programmation fonctionnels réussi. Considérant que F # est un langage fonctionnel, toutes les instances sont immuables, sauf indication contraire. En revanche, c# est un langage de premier orientée objet dans lequel toutes les instances sont mutables sauf indication contraire. Dans cet article, je vous montrerai comment tirer parti d’immuabilité en c#. Mais tout d’abord, je vais définir immuabilité dans le contexte de cet article.

Définition d’immuabilité

Techniquement, il existe de nombreux types d’immuabilité. N’importe quel type qui limite quelque peu de modifications à son état ou de l’état de ses instances peut être décrit comme immuable dans un sens. Le type System.String est un type immuable dans le sens où la taille de la chaîne de caractères et leur ordre n’est pas modifiable. Le type System.MulticastDelegate, qui est le parent de tous les types délégués, est immuable comme System.String. Utiliser un tableau comme une structure de données sous-jacente et effectuer une copie de celle-ci pour répondre à une modification demandée, quelle que soit la taille de la modification est. Pour plus d’informations sur les types d’immuabilité, reportez-vous à l’article bit.ly/2kGVx4Z.

Le System.Collections.ObjectModel.ReadOnlyCollection<T> n’est pas immuable, mais il implémente une interface immuable pour un IList mutable donné<T> objet.</T> </T> Cette interface ne permet pas le consommateur modifier le nombre d’éléments dans la collection ou leur ordre relatif. Toutefois, il ne parle immuabilité des éléments individuels, ce qui dépend de la hiérarchie de type entier de T. Bien entendu, le code qui fait référence à la liste sous-jacente peut le modifier sans contraintes.

Les collections immuables abordées dans cet article fournissent encore un autre type d’immuabilité. Pour motiver le besoin, prenons l’exemple suivant :

Un éditeur de texte standard fournit plusieurs fonctionnalités ou outils (tels que l’analyse de code ou de vérification orthographique) analysent ou traitement le texte écrit par l’utilisateur. Avec la prédominance des ordinateurs multicœurs, ces outils peuvent être exécutés en arrière-plan pendant que l’utilisateur tape. Si vous ne faites pas attention, vous pouvez rencontrer des problèmes de sécurité des threads. L’analyseur en arrière-plan lit la mémoire tampon contenant le texte en même temps que l’utilisateur est en train de la modifier. Imaginez maintenant, au lieu d’une mémoire tampon, le processus d’arrière-plan obtenez logiquement un instantané du texte.

Comment pouvez-vous procéder correctement et efficacement ? À l’aide d’un type comme chaîne a correctement résolu le problème, mais pas efficacement. Cela permettrait l’utilisateur à modifier le texte en même temps que l’outil est en cours d’exécution, mais avec chaque modification, une nouvelle copie du texte est effectuée, ce qui peut être lente et une perte de mémoire pour les documents volumineux. Une autre bonne solution serait d’utiliser un type mutable, telles que System.Text.StringBuilder. Il s’agit également inefficace, car l’outil doit faire une copie sous un verrou acquis et de l’utilisateur ne seraient pas en mesure d’apporter des modifications jusqu'à ce qu’une copie est effectuée. À l’aide de ReadOnlyCollection<T> n’est d’aucune utilité, car la collection sous-jacente est mutable et partagées.</T>

Vous avez besoin d’un autre type d’immuabilité qui vous permet d’apporter des modifications en toute sécurité sans utiliser les mécanismes de synchronisation de thread coûteux, tout en partageant autant de données que possible entre les threads avec aucune ou peu copie requis. Collections immuables fournissent exactement ce genre d’immuabilité, appelé la persistance. Ils ne sont pas seulement utiles dans le scénario décrit précédemment, mais aussi dans d’autres scénarios multiple et monothread, comme vous le verrez plus loin dans cet article.

Cet article fournit une description détaillée de la conception, mise en œuvre et performances des collections immuables pour pouvoir les utiliser efficacement et même écrire vos propres collections immuables et types. Ces collections peuvent être utilisées sur toutes les plateformes .NET qui prend en charge la norme .NET 1.0 et versions ultérieure (ce qui signifie que vous pouvez les utiliser sur toutes les plates-formes Windows, Xamarin et .NET Core). Collections immuables sont relativement nouveaux et distribuée comme package NuGet, afin qu’elles ne sont pas utilisées par le .NET Framework, bien qu’il existe de nombreuses API de framework pour laquelle collections inaltérables aurait été utile. Au lieu de cela, ces API utilisent la ReadOnlyCollection potentiellement moins idéale<T> ou utiliser une copie d’une collection mutable.</T> Je vais utiliser la version du package 1.3.0. Le code source est disponible dans le cadre de CoreFX.

Notez qu’il est possible d’utiliser de code unsafe ou garantit la réflexion pour interrompre l’immuabilité presque n’importe quel. En général, lorsqu’un type est décrite comme immuable, il existe un inconvénient implicite effectuées que ces techniques peuvent contourner les garanties d’immuabilité. Cela s’applique aux collections immuables abordées dans cet article.

Définir des Collections immuables

Avant d’aborder les détails internes de collections inaltérables, je dois définir ce qu’elles sont. Une collection immuable est une collection d’instances qui conserve sa structure tout le temps et n’autorise pas les affectations de niveau élément, tout en offrant des API pour effectuer les mutations. J’entends par la structure d’une collection, le nombre d’éléments et leur ordre relatif (ce qui est déterminé par leur index dans le cas d’une structure de tableau et leurs liens dans le cas d’une structure liée).

Par exemple, si vous placez un élément sur un ImmutableStack<T>, vous obtiendrez deux piles immuables isolés : un avec le nouvel élément et l’autre sans.</T> En revanche, pousser un élément sur une pile mutable<T> modifie effectivement la pile et vous ne devez une pile qui contient le nouvel élément.</T> Notez que les collections immuables et mutables n’offrent pas les garanties concernant les éléments eux-mêmes. Si T a été Int32 ou chaîne, alors les éléments est immuables, également. Mais si T était quelque chose comme StringBuilder, puis les éléments sont très mutables.

Pour pouvoir créer un objet immuable, il doit être initialisé. Par conséquent, lors de l’initialisation, l’objet est mutable. Une fois une référence à l’objet a été publiée (à retourner à partir d’une méthode non privée), l’objet devient ainsi immuable pour le reste de sa durée de vie.

Les collections immuables sont conçues avec deux objectifs en tête. En premier lieu réutiliser autant de mémoire que possible, pour éviter de copier et de réduire la pression sur le garbage collector (implémentation de ce type est généralement appelée persistante). Le deuxième objectif consiste à prendre en charge les mêmes opérations offertes par des collections altérables complexités du temps sur la concurrence.

Piles immuables

La pile mutable<T> type est implémenté à l’aide d’un tableau.</T> Tableaux, toutefois, ne conviennent pas pour les collections immuables étant le seul moyen de conserver l’instance actuelle en copiant la totalité du tableau et en effectuant la modification sur ce nouveau tableau. Cela rendrait la pile immuable trop faibles. Listes liées élégante utilisable pour l’implémenter. Chaque élément contient un pointeur vers l’élément ci-dessous (ou null pour l’élément en bas). Une pile immuable est représentée comme un pointeur vers l’élément supérieur. De cette façon, vous pouvez push et pop des éléments d’une pile donnée sans le modifier, tandis que, en même temps tous ses éléments partage avec la pile qui en résulte. Cette conception simple permet à la pile immuable la plus simple collection immuable. J’ai illustrent les différences entre les piles modifiables et non modifiables davantage dans cet article.

Nous allons voir comment créer et utiliser des piles immuables. Le ImmutableStack<T> et toutes les autres collections immuables sont définies dans l’espace de noms System.Collections.Immutable.</T> Pour optimiser le partage de la mémoire, les collections immuables n’offrent pas de constructeurs publics. Pour créer une instance d’une collection immuable, vous devez utiliser une de le CreateXxx<T> méthodes définies dans un type statique qui correspond à la collection immuable.</T> Pour la pile immuable, ce type est appelé ImmutableStack et propose les méthodes de fabrique suivantes :

public static ImmutableStack<T> Create<T>();
public static ImmutableStack<T> Create<T>(T item);
public static ImmutableStack<T> Create<T>(params T[] items);
public static ImmutableStack<T> CreateRange<T>(IEnumerable<T> items);

Toutes les méthodes ont un paramètre de type générique T qui spécifie le type des éléments stockés dans la collection. La première méthode crée une pile immuable vide qui renvoie en interne simplement le singleton ImmutableStack<T>. Vide.</T> La seconde méthode crée une pile avec l’élément spécifié est placé, ce qui équivaut à ImmutableStack<T>. Empty.Push(item).</T> Les troisième et quatrième méthodes créent une pile avec les éléments spécifiés, il est placés dans l’ordre. Le CreateRange<T> méthode est implémentée comme suit :</T>

var stack = ImmutableStack<T>.Empty;
foreach (var item in items)
{
  stack = stack.Push(item);
}
return stack;

Toutes les méthodes de fabrique pour toutes les collections immuables sont fournis. En interne, toutes commençant par la collection vide et ajouter les éléments spécifiés. Les éléments sont toujours copiés shallowly.

Examinons à présent la séquence d’opérations à partir de la pile vide suivante :

ImmutableStack<Int32> s1 = ImmutableStack<Int32>.Empty;
ImmutableStack<Int32> s2 = s1.Push(1);
ImmutableStack<Int32> s3 = s2.Push(2);
ImmutableStack<Int32> s4 = s3.Push(3);
ImmutableStack<Int32> s5 = s4.Push(4);
ImmutableStack<Int32> s6 = s4.Pop();
ImmutableStack<Int32> s7 = s6.Pop();

Notez que les méthodes Push et Pop renvoient une référence à la pile immuable qui en résulte. En revanche, les méthodes Push et Pop de la pile mutable<T> retour void et T, respectivement.</T> Cette conception reflète le fait que modification d’une pile immuable conceptuellement provoque une toute autre pile, tandis que la modification d’une pile mutable change la pile. Si la même séquence d’opérations est effectuée sur une pile mutable, vous obtiendrez un résultat final différents, comme indiqué dans Figure 1. La pile immuable immuable le fait qu’il n’existe aucun moyen de modifier les pointeurs et les valeurs des nœuds.

Figure 1 une à une pile immuable entraîne une autre pile Contrairement aux piles Mutable

Notez que le nœud de la pile immuable vide stocke la valeur par défaut de T, qui est égal à 0 pour un Int32. Également, la pile mutable définit uniquement les valeurs des éléments dépilés à la valeur par défaut au lieu de réduction de la taille du tableau. La partie du tableau inoccupée est appelée espace libre.

Pour obtenir l’élément en haut d’une pile immuable, vous pouvez utiliser la méthode Peek ou une autre surcharge de Push qui a un paramètre de sortie par le biais duquel l’élément est retourné.

Listes immuables

La structure de données de liste est plus complexe que la pile principalement en raison de l’opération d’indexation. La structure de liste offre l’extraction d’éléments, ajout et suppression à l’index spécifié. À l’aide d’un tableau, comme dans la liste mutable<T>, serait raisonnable, mais, comme expliqué précédemment, serait inefficace pour obtenir la liste immuable à usage général.</T> À l’aide d’une liste liée est également pas appropriée parce que vous devrez éventuellement traverser de nombreux éléments afin d’atteindre l’élément à un index spécifique. Au lieu de cela, les arborescences binaires à charge équilibrée vous permettent d’implémenter toutes les opérations inflige davantage de performances. La plupart des collections immuables sont implémentées à l’aide des arborescences binaires à charge équilibrée. Les autres utilisent des listes liées et une seule, à savoir le tableau immuable, utilise des tableaux comme expliqué dans la section suivante.

Chaque nœud dans l’arborescence contient un élément de la liste et, par conséquent, a un index. Le ImmutableList<T> type organise l’arborescence tels qu’un parcours à profondeur prioritaire, dans l’ordre de l’arborescence correspond à un parcours de la liste dans l’ordre à partir de l’élément à l’index 0 au dernier élément.</T>

Prenons le programme suivant :

ImmutableList<Int32> l1 = ImmutableList.Create<Int32>();
ImmutableList<Int32> l2 = l1.Add(1);
ImmutableList<Int32> l3 = l2.Add(2);
ImmutableList<Int32> l4 = l3.Add(3);
ImmutableList<Int32> l5 = l4.Replace(2, 4);

Figure 2 montre ce qui arrive à l’arborescence binaire sous-jacent lors de l’exécution de la séquence d’opérations depuis la liste immuable vide. Chaque zone représente un nœud dans l’arborescence. La zone qui contient la lettre E représente le singleton arborescence vide (les flèches qui pointent nulle part doivent être interprétées comme pointant vers la zone). Les flèches sur le côté droit de la figure et les zones sont immuables, tandis que ceux situés à gauche sont temporairement mutables. Cela est indiqué par un indicateur booléen interne appelé figé. Cet indicateur sert deux objectifs, comme je l’expliquerai ci-après.

Figure 2 état interne d’arbres (à gauche) et l’état Accessible publiquement qui après avoir terminé les Mutations (à droite)

Pour ajouter le premier élément à l’arborescence, un nouveau nœud est créé avec les deux de ses pointeurs pointant vers le nœud vide. Tous les nouveaux créé nœuds démarrer avec l’indicateur figé défini sur false (temporairement mutable). À ce stade, rien ne doit plus être effectuée et, par conséquent, l’arborescence est rendue immuable en définissant l’indicateur figées sur « true » comme indiqué sur le côté droit de la figure. Cela rend l’arborescence immuable pour le reste de sa durée de vie.

Pour ajouter un deuxième élément, en raison de l’organisation de l’arborescence, de son nœud doit être l’enfant de droite du premier nœud. Mais étant donné que ce nœud est immuable, vous ne pouvez pas modifier les pointeurs. La seule façon d’ajouter le deuxième élément est non seulement créer un nœud pour elle, mais également créer un autre nœud pour le premier élément. C’est pourquoi l2 et l3 de pointe pour séparer totalement les arborescences.

De même, le troisième élément doit être l’enfant du deuxième nœud droit. La seule façon d’ajouter est en créant de nouveaux nœuds pour les premier et deuxième éléments. Toutefois, cette fois l’arborescence qui en résulte est déséquilibrée. Cette situation se produit lorsque la différence entre la hauteur des sous-arborescences gauche et droite de la racine est au moins 2. Pour conserver l’arborescence équilibrée, vous devez réorganiser afin qu’il devienne l’arborescence affichée dans le coin inférieur droit de Figure 2. Cela étant donné que l’arborescence est toujours mutable et aucun code en dehors de la ImmutableList<T> type permettre y accéder ou observer des mutations.</T> Avant une référence à l’arborescence est retournée, elle est figée en définissant l’indicateur figée de chaque nœud sur true pour rendre immuable. Ceci confirme que l’objectif premier de l’indicateur figé.

La dernière ligne de code appelle la fonction Replace, qui recherche l’élément spécifié et le remplace par un autre élément. Dans ce cas, un nœud est créé pour contenir le nouvel élément et les autres nœuds de la même arborescence sont réutilisés dans la nouvelle arborescence.

En raison de la façon dont l’arborescence est organisée, toute opération unique dans la liste, si son ajout, insertion, suppression ou la recherche a une complexité temporelle de O (log N) où N est le nombre d’éléments actuellement dans la liste. En revanche, les opérations sur la liste mutable<T> sont o (1) (où l’opération peut être effectuée en place) ou o (n) (où le tableau sous-jacent doit être copié).</T>

Vous pouvez effectuer rapidement une seule opération sur une liste immuable. Mais si vous souhaitez effectuer un grand nombre de M d’opérations consécutives, il faudra O (M log N). Faire mieux en tirant parti de l’indicateur figé et lumping ensemble tous les mutations. Cette optimisation est proposée par les fabricants.

La plupart des collections immuables, notamment ImmutableList<T> définissent les types appelés ceux qui utilise les mêmes structures de données sous-jacentes et offre les mêmes API.</T> La différence est qu’un générateur de ne définie l’indicateur figée après chaque opération. Il conserve tous les nœuds qui ont été créés dans un état mutable afin que vous pouvez effectuer de nombreuses opérations plus efficacement. Le type de générateur de rapports pour la liste immuable est ImmutableList<T>. Générateur.</T>

Pour créer une instance du Générateur de rapports, vous avez besoin d’une instance de collection immuable. Vous pouvez commencer avec une collection vide et utiliser le ImmutableList.CreateBuilder<T> méthode statique ou utiliser la méthode d’instance ToBuilder sur une collection immuable donnée.</T> Dans ce cas, tous les nœuds existants seront conservés, comme promis. Il est uniquement ces nouveaux nœuds seront mutables. Une fois que toutes les opérations sont effectuées, vous pouvez appeler la méthode d’instance ToImmutable pour figer tous les nœuds, et faire de la collection immuable. ImmutableList<T> fournit plusieurs méthodes, telles que AddRange et RemoveRange, qui prennent une référence IEnumerable d’instance<T> et utiliser un générateur en interne pour effectuer l’opération sur les éléments spécifiés.</T> </T>

Certaines opérations ne bénéficient d’intégrateurs et ils sont par nature coûteux. La méthode d’instance inverse doit copier tous les nœuds non terminaux dans l’arborescence pour inverser l’ordre des éléments. La méthode d’instance de tri est implémentée en copiant tous les éléments dans un tableau, trier le tableau puis en créant la liste immuable à partir du tableau trié.

La liste mutable<T> utilise un tableau interne.</T> Insertion ou suppression d’éléments à partir du milieu du tableau requiert la création d’un tableau et copie tous les autres éléments. En affectant des tableaux très volumineux peut-être pas dans un espace d’adressage fragmentés. LinkedList mutable<T> résout ces deux problèmes.</T> ImmutableList<T> offre les avantages des deux, mais rend les autres opérations moins efficace.</T> ImmutableList<T> est une collection immuable qui correspond à la liste<T> et LinkedList<T>.</T> </T> </T> Notez que StringBuilder est essentiellement List<Char>.</Char>

Tableaux immuables

Le ImmutableArray<T> type, comme ImmutableList<T>, implémente une liste immuable, mais d’une manière différente.</T> </T> ImmutableArray<T> est simplement un wrapper mince autour d’un tableau de [] de type T.</T> Il est « fine », car c’est un type valeur qui contient un champ unique de type de référence. Le tableau lui-même est alloué à partir du tas managé. Pour effectuer une opération de mutation, une copie de la totalité du tableau est créée et l’opération est effectuée sur celle-ci. À partir de ce point de vue, ImmutableArray<T> est une généralisation de chaîne, comme il peut représenter des chaînes d’éléments de tout type, pas seulement ' char '.</T>

Toutes les opérations de mutation du temps o (n) à l’aide de ImmutableArray<T>, mais le temps de O (log N) à l’aide de ImmutableList<T>.</T> </T> Toutefois, ImmutableArray<T> est supérieure de trois façons.</T> Tout d’abord, elle consomme du temps o (1) pour accéder à un élément donné son index à l’aide de ImmutableArray<T>: O (log N) lors de la durée à l’aide de ImmutableList<T>.</T> </T> Ensuite, bien que les deux implémentations offrent l’itération temps linéaire, ImmutableArray<T> est compatible avec cache, car tous les éléments sont stockées consécutivement.</T> Itération sur une ImmutableArray<T> peut être un nombre de fois plus rapidement que l’itération d’un ImmutableList<T>.</T> </T> Troisième, ImmutableArray<T> consomme moins de mémoire, car il n’utilise pas des pointeurs.</T> En règle générale, vous devrez peut-être mesurer pour déterminer celui que vous souhaitez utiliser dans une situation particulière. Les deux types implémentent l’IImmutableList<T> interface.</T> Vous pouvez utiliser cette interface dans votre code permet de basculer facilement entre les types.

Comme toujours, vous pouvez améliorer les performances et réduire la pression du garbage collection (GC) en effectuant des opérations en bloc et les objets de générateur de regroupement. Vous pouvez utiliser les méthodes d’opérations en bloc XxxRange ou ImmutableArray<T>. Le générateur, qui est implémenté de la même façon à la liste<T>.</T> </T>

Étant donné que la conception standard d’opérateurs LINQ fonctionne sur IEnumerable<T> références, leur application sur le type de valeur ImmutableArray<T> nécessite une conversion boxing.</T> </T> Le package NuGet de collections inaltérables inclut une implémentation de certains opérateurs LINQ conçu spécifiquement pour ImmutableArray<T> pour éviter le boxing.</T> Il peut trouver dans System.Linq.ImmutableArrayExtensions.

Dictionnaires immuables

Le ImmutableDictionary<TKey, tvalue=""> type utilise une arborescence binaire à charge équilibrée pour représenter le dictionnaire.</TKey,> Chaque nœud de l’arborescence contient un ImmutableList<><TKey, tvalue="">> (qui est également un arbre binaire à charge équilibrée) qui contient tous les éléments de la même valeur de hachage.</TKey,> En revanche, le dictionnaire mutable<TKey, tvalue=""> utilise un tableau de paires clé-valeur avec l’adressage ouvert pour la résolution de collision.</TKey,> Globalement, ImmutableDictionary<TKey, tvalue=""> est souvent plus lent et consomme plus de mémoire que Dictionary<TKey, tvalue="">.</TKey,> </TKey,> À l’aide du Générateur de dictionnaire uniquement permet un peu, car la structure sous-jacente est toujours une arborescence d’arborescences. Vous devez sans aucun doute mesurer les performances lors de l’utilisation de ImmutableDictionary<TKey, tvalue=""> pour déterminer s’il est acceptable ou non.</TKey,> Si elle n’est pas le cas, vous devrez peut-être écrire votre propre dictionnaire immuable personnalisé.

Performances et la consommation de mémoire des Collections immuables

Maintenant, même si l’utilisation d’une collection immuable est principalement idéale, qui ne peut pas entraîner de performances acceptables. C’est pourquoi il est important de comprendre leur implémentation et leur impact sur les performances.

Nous allons comparer les performances de la liste immuable par rapport à celle de l’équivalent mutable. Vous pouvez trouver les complexités de la durée des opérations courantes sur les collections immuables à bit.ly/2ko07HS. Ceci dit très peu, et il est recommandé d’en utiliser un peu plus pratique. J’ai écrit trois programmes simplement ajout au début ou entiers de 8 octets de 10 millions à une liste modifiable, une liste immuable et un générateur de liste immuable, respectivement. Figure 3 affiche les résultats. (Les nombres indiqués sont approximatifs. Heure est exprimée en secondes. La mémoire est en mégaoctets. Les optimisations JIT sont activées. Le constructeur par défaut est utilisé pour créer la liste mutable.)

Figure 3 quantité du temps et de mémoire utilisée par Mutable listes, listes immuables et tableaux immuables

	Mutable	ImmutableList	ILBuilder	ImmutableArray	IABuilder
Ajouter	0.2	12	8	Incroyable !	0.2
Ajoutez au début	Incroyable !	13.3	7.4	Incroyable !	Incroyable !
taille de 32 bits	128	320	320	128	128
taille de 64 bits	128	480	480	128	128

L’ajout à une liste mutable est bon marché, car elle est basée sur un tableau. Le tableau est doublé de taille occasionnellement et qui, après l’ajout d’un article est une opération rapide. En revanche, ajouter un élément à une liste immuable est beaucoup plus coûteuse, car elle est basée sur une arborescence. Même si vous utilisez le générateur, il est toujours environ 40 fois plus lent. C’est très important. Toutefois, cela n’est pas exactement une comparaison équitable. Une comparaison équitable serait entre la liste immuable et une liste mutable qui utilise la synchronisation de threads pour fournir une sémantique similaire instantané. Malgré tout, cela permet de collections inaltérables beaucoup moins intéressants dans les scénarios de modèle de thread unique. Bien que la complexité temporelle est O (log N), le facteur de constante masqué est assez volumineux. J’expliquerai pourquoi peu de temps.

Il est une toute autre histoire pour l’opération prepend. Il faudrait liste<T> plusieurs heures, car il doit allouer et copier des tableaux courtes de 10 millions de plus en plus volumineux.</T> La liste immuable et son générateur conservés plus ou moins les mêmes performances.

Figure 4 montre une partie du graphique de l’allocation de la mémoire managée généré à l’aide de Diagnostic Tools de Visual Studio 2015 lors de l’ajout d’éléments à une liste immuable. Les marqueurs en haut du graphique indiquent enregistrées GC de génération de tout. Le graphique montre que les catalogues globaux se produire fréquemment, sur toutes les millisecondes plusieurs dizaines. J’ai utilisé PerfView pour déterminer la quantité de temps passé à ces catalogues globaux peu. Sans l’aide du générateur, l’heure dans le catalogue global est environ 4 secondes. Il s’agit de la différence entre l’utilisation de la liste immuable directement à l’aide du générateur. Pour déterminer si cette différence est effectivement en raison des catalogues globaux ou si elle est simplement une coïncidence, j’ai également utilisé PerfView sur le programme qui utilise le générateur. Il s’avère que c’est effectivement le cas. Cela peut s’expliquer facilement en examinant le fonctionne de chacun. La liste immuable crée de nombreux objets éphémères et durée de vie moyenne, tandis que le générateur transforme les pointeurs d’objets existants. À l’aide de la liste immuable directement déclenchée 100 GC lors de l’utilisation du générateur et liste mutable déclenchée inférieure à 10.

Figure 4, le garbage collector s’exécute beaucoup plus souvent lors de l’ajout d’éléments à la liste immuable

Le générateur est beaucoup plus lent que la liste mutable. Il existe quatre raisons interdépendants. Tout d’abord, il utilise une structure liée qui implique de nombreuses erreurs dans le cache. Ensuite, après l’ajout des deux éléments, l’arborescence devient déséquilibrée et nécessite une rotation pour rééquilibrer il. Troisièmement, l’ajout d’un élément requiert des nœuds traversée (log N). Quatrièmement, chaque fois qu’un élément est ajouté, il déclenche une allocation de mémoire distincte pour le nœud d’hébergement.

Cela ne signifie pas que le garbage collector est une partie du problème. Au contraire, gestion automatique de la mémoire en fait beaucoup plus facile à écrire et d’utiliser des collections inaltérables. Il nettoie automatiquement les objets immuables personne n’utilise.

Nous allons comparer également la pile immuable avec la pile mutable. Cette comparaison vous permet de quantifier le coût des allocations d’objets et leurs absences dans le cache associé (qui sont uniquement une petite partie des total absences pouvant survenir ultérieurement) résultant de l’utilisation de structures de données liée. La pile immuable est GC puisqu’elle alloue uniquement les objets qui feront partie de la pile qui en résulte. Il est donc efficace qu’il n’a même un générateur. Exécuter un push des entiers de 8 octets de 10 millions sur une pile mutable prend environ version 0.17 secondes, de temps pousser le même dans une pile immuable prend environ 1 seconde. C’est sur un ralentissement de 6 x, qui n’est pas défectueux. Itération sur une importante pile immuable ou une structure lié peut être autant de fois plus lent que dans l’itération sur la collection mutable correspondante essentiellement en raison de cache absences et page erreurs (et les transferts entre les nœuds NUMA sur les architectures NUMA en raison du partage).

Cela dit, les collections altérables baie concernées par le gaspillage d’espace libre. Si vous supprimez la plupart des éléments d’une grande collection, le tableau sous-jacent pas réduire et continuent à occuper inutilement de mémoire. Collections immuables basés lié toujours conservent un objet par élément. Toutefois, c’est rarement un avantage pour les regroupements liés, envisagez les scénarios d’utilisation classiques.

Quand utiliser les Collections immuables

L’avantage majeur d’immuabilité est qu’il est beaucoup plus facile de raisonner sur son fonctionnement, ce qui vous permet d’écrire rapidement du code correct et élégant. Imaginez un programme monothread. Sur une ligne de code donnée, vous vous demandez peut-être sur l’état d’une collection immuable. Vous pouvez facilement déterminer qui en localisant ces emplacements dans le code où la collection a été créée. Il est généralement qu’une des quelques ces emplacements. En continuant cette procédure, vous allez obtenir soit une source mutable ou vider la collection. Peu importe si la collection immuable a été transmise aux méthodes, car sa structure est garantie être conservé, sans que vous ayez à prendre en compte ce qui se passe dans ces méthodes. Si les éléments ont été d’un type immuable, ainsi, vous pourrez examiner l’état complet de la collection. Il est tout aussi simple dans les programmes multithreads, mais devient beaucoup plus difficile lorsqu’à l’aide des collections mutables partagées. Par conséquent, l’immuabilité peut être un principe de conception comme il est dans fonctionnelle de programmation.

À présent, la signature de méthode suivante :

void Foo<T>(Stack<T> s);

Cette méthode possède un paramètre de la pile mutable, la pile peut être modifié par la méthode. Ce serait en effet, l’objectif de la méthode. Mais lorsqu’il ne modifie pas la pile, l’ancien état est perdu, sauf si l’appelant a effectué une copie de celle-ci. Notez que la méthode ne comporte pas à retourner une valeur, même si cette modification de la pile. Encore une chose qui transmet cette signature est qu’il n’offre pas les garanties de sécurité des threads.

Cela convient si la sécurité des threads n’est pas un problème et si la méthode est supposée modifier la pile et vous êtes intéressé par ces modifications. Si l’objectif de la méthode consiste à lire uniquement ou d’inspecter la pile (ou il peut le modifier, mais l’appelant ne se soucie ses modifications), cette signature peut être plus adaptée :

void Foo<T>(ReadOnlyCollection<T> s);

Il existe deux problèmes avec ce. Tout d’abord, ReadOnlyCollection<T> requiert une liste<T> être construit, par conséquent, l’appelant a copier la pile dans une liste.</T> </T> Rendre le paramètre de type d’interface IReadOnlyCollection<T> évite ce problème car pile<T> implémente, mais ensuite la méthode pourrait le reconvertir en pile<T> tout aussi facilement.</T> </T> </T> Deuxièmement, si la méthode généralement modifie la pile, il a tout d’abord copier dans une collection mutable. Cette signature n’offre également les garanties de sécurité des threads. Il est pratique uniquement lorsque la collection mutable d’origine est la liste<T> et la méthode ne change pas celui-ci.</T>

Dans les scénarios où il existe potentiellement plusieurs threads accèdent à la collection, cette signature peut être plus adaptée :

void Foo<T>(ConcurrentStack<T> s);

La pile simultanée est mutable, donc tous les threads seront affiche toutes les modifications. Cela convient seulement lorsqu’au moins une des deux conditions suivantes se produisent : La méthode doit prendre en compte les modifications éventuellement apportées par les autres threads dès que vous avez créé, ou d’autres threads ont besoin voir les modifications apportées par la méthode dès que vous avez créé. Notez que n’importe quel thread peut voir les modifications spécifiques apportées séparément. Dans le cas contraire, si des threads doivent voir uniquement un lot de modifications ou aucune des modifications, ils doivent acquérir un verrou global et effectuez une copie privée de la pile. Ces deux situations sont appelées la sémantique des instantanés.

Remarquez comment dans divers scénarios, différents types de collection doivent être utilisés. Une bonne documentation est également souhaitable d’expliquer le fonctionne de la méthode ou comment il doit être utilisé. Collections immuables simplifient tout cela. Les deux signatures suivantes répondent à la plupart des scénarios :

void Foo1<T>(ImmutableStack<T> s);
ImmutableStack<T> Foo2<T>(ImmutableStack<T> s);

Recherchez beau ces API sont. La première signature est utilisée lorsque la personne respecte les modifications apportées par la méthode. Dans le cas contraire, la deuxième signature peut être utilisée. Il existe seulement deux situations dans lesquelles les collections immuables sont inappropriées : débit (la vitesse à laquelle les éléments sont traités) et la sémantique de producteur-consommateur. Comme indiqué précédemment, les collections immuables à usage général ont un débit inférieur, en particulier dans les scénarios mono-thread. Sémantique de producteur-consommateur, des collections altérables simultanées sont plus élégantes et entraînent de meilleures performances. La différence entre la sémantique de producteur-consommateur et de la sémantique des instantanés est les agents de lecture ou de beaucoup de comportement. Dans le premier cas, les éléments obtient consommées (supprimé définitivement) while dans le dernier éléments traités et sont supprimées uniquement par les agents d’écriture ou de production. J’aimerais appelons sémantique des instantanés sémantique de changeur processeur car il subissent agents et traitement. Agents de traitement peut apporter des modifications tant que ces modifications sont conservées dans une copie distincte, ainsi que d’autres copies que nécessaire. Si ces modifications devait être rendu global, vous seriez dans le domaine de la sémantique de producteur-consommateur.

API et les Interfaces pratiques

Il existe de nombreuses méthodes d’extension ToXxx convertir à partir des collections altérables ou des interfaces de collections liées aux collections immuables. Ces méthodes copier la collection mutable plutôt que de les réutiliser pour maintenir l’immuabilité. Plusieurs collections inaltérables offrent des méthodes utiles, telles que celles de tri et de recherche, semblables à celles offertes par ceux mutable. Cela permet le mélange de code qui utilise les deux types de collections.

Pour faciliter l’utilisation des collections immuables dans les bases de code existant, certaines d'entre elles implémentent des interfaces de communes appropriés telles que IEnumerable<T>IList<T> et ICollection<T>.</T> </T> </T> Certaines méthodes déclarées comme IList<T>. INSERT sont destinées à muter de la collection.</T> Celles-ci sont implémentées en levant une exception NotSupportedException. Collections inaltérables également implémentent des interfaces immuables correspondantes qui sont définis dans le package NuGet.

Le type System.Collections.Immutable.ImmutableInterlocked offre plusieurs méthodes qui implémentent des mécanismes d’échange verrouillés pour mettre à jour correctement les éléments ou les références aux collections immuables. Par exemple, la méthode suivante prend une référence à un élément et le met à jour en fonction de la classe transformer spécifiée :

public static bool Update<T>(ref T location, Func<T, T> transformer) where T : class;

Alors que les effets de ces opérations sont observables par tous les threads, il garantit que le même élément est toujours appliqué par chacun d'entre eux.

Pour résumer

Cet article décrit les avantages des collections immuables et fourni une présentation détaillée de la conception et l’implémentation de piles immuables, les listes, les tableaux et les dictionnaires. Il existe de nombreuses autres collections inaltérables livrées avec le package NuGet. Presque chaque collection altérables a un correspondante parmi immuable, vous pouvez trouver là. J’espère que vous pouvez utiliser efficacement ces types dans votre code. Si vous aimez le modèle d’immuabilité et que vous aimeriez écrire vos propres types immuables, Andrew Arnott a écrit un outil Roslyn qui rend l’écriture des types immuables aussi simple que d’écrire des types mutables. Vous trouverez plus d’informations, consultez bit.ly/2ko2s5O.

---

Hadi Braisest un lettré doctorat à l’indien institut de technologie Delhi, recherche les optimisations du compilateur pour les systèmes de mémoire de nouvelle génération.  Il consacre la plupart de son temps à écrire du code C / C++ c++ / C# et Explorer runtimes, d’infrastructures de compilateur et d’ordinateur architectures. Il rédige sur hadibrais.wordpress.com et peut être contacté à hadi.b@live.com.

---

Merci aux experts techniques suivants d'avoir relu cet article : Andrew Arnott et Immo Landwerth

---