März 2017

Band 32, Nummer 3

.NET Framework: unveränderliche Sammlungen

Von Hadi Brais | März 2017

Durch Nebenwirkungen werden die Verständlichkeit und Richtigkeit des Codes beeinträchtigt. Eine Methode, die globale oder statische Variablen mutiert, besitzt Nebenwirkungen. Eine Methode, die einige ihrer Parameter mutiert, besitzt Nebenwirkungen. Wenn Sie einen Codeausschnitt verstehen möchten, müssen Sie den Code für alle Methoden berücksichtigen, die aufgerufen werden und Nebenwirkungen besitzen. Methoden mit Nebenwirkungen erfordern, dass die Threadsynchronisierung ordnungsgemäß ausgeführt wird, wenn mehrere Threads vorhanden sind.

Was geschieht, wenn Sie Methoden schreiben, die keine Nebenwirkungen besitzen? Wie würde dieser Code aussehen, und wie wäre sein Verhalten? Sie können Antworten auf diese Fragen erhalten, indem Sie Instanzen unveränderlich machen, damit keine Nebenwirkungen auftreten können.

Wenn eine Instanz eines Typs als unveränderlich beschrieben wird, bedeutet dies, dass sich ihr Wert niemals ändert. Unveränderlichkeit ist (wie viele Aspekte bei der Softwareentwicklung) eine Entwurfsentscheidung. Sie müssen dieses Verfahren nicht verwenden. In einigen Szenarien kann es jedoch im Hinblick auf Codeleistung bzw. -verständlichkeit vorteilhaft sein. Dieses Verfahren ist in der Tat häufig sinnvoll, weil es eines der fundamentalen Prinzipien des erfolgreichen funktionalen Programmierungsparadigmas darstellt. Wenn Sie bedenken, dass F# eine Sprache ist, bei der die Funktion vorrangig ist, sind alle Instanzen unveränderlich, wenn nicht explizit ein anderes Verhalten angegeben wird. Andererseits ist C# eine vorrangig objektorientierte Sprache, bei der alle Instanzen veränderlich sind, wenn nicht explizit ein anderes Verhalten angegeben wird. In diesem Artikel zeige ich, wie die Unveränderlichkeit in C# genutzt werden kann. Zuerst definiere ich jedoch Unveränderlichkeit im Kontext dieses Artikels.

Definition von Unveränderlichkeit

Unter technischen Aspekten gibt es viele Arten von Unveränderlichkeit . Jeder Typ, der auf irgendeine Weise Änderungen an seinem Zustand oder dem Zustand seiner Instanzen einschränkt, kann in gewisser Weise als unveränderlich beschrieben werden. Der Typ „System.String“ ist insofern ein unveränderlicher Typ, weil sich die Größe der Zeichenfolge, die Zeichen und die Reihenfolge nicht ändern können. Der Typ „System.MulticastDelegate“, der das übergeordnete Element aller Delegattypen ist, ist ebenso unveränderlich wie „System.String“. Beide Typen verwenden ein Array als zugrunde liegende Datenstruktur und erstellen eine Kopie dieses Arrays, um eine angeforderte Änderung zu ermöglichen. Dies gilt unabhängig davon, wie klein die Änderung ist. Weitere Informationen zu den verschiedenen Arten von Unveränderlichkeit finden Sie im Artikel unter bit.ly/2kGVx4Z.

„System.Collections.ObjectModel.ReadOnlyCollection<T>“ ist nicht unveränderlich, implementiert aber eine unveränderliche Schnittstelle für ein angegebenes veränderliches IList<T>-Objekt. Diese Schnittstelle erlaubt dem Consumer nicht das Ändern der Anzahl der Elemente in der Sammlung oder deren relativer Reihenfolge. Dies sagt aber nichts über die Unveränderlichkeit der einzelnen Elemente aus, die von der gesamten Typhierarchie von T abhängt. Code, der einen Verweis auf die zugrunde liegende Liste enthält, kann natürlich ohne Einschränkungen Änderungen ausführen.

Die unveränderlichen Sammlungen, die in diesem Artikel behandelt werden, stellen eine noch andere Art von Unveränderlichkeit bereit. Sehen Sie sich das folgende Beispiel an, um besser zu verstehen, warum sie erforderlich sind:

Ein typischer Text-Editor stellt verschiedene Features oder Tools (z. B. Rechtschreibprüfung oder Codeanalyse) zur Verfügung, die Text analysieren oder verarbeiten, den der Benutzer eingegeben hat. Da zurzeit vorwiegend Multi-Core-Computer eingesetzt werden, können diese Tools im Hintergrund ausgeführt werden, während der Benutzer Text eingibt. Wenn Sie nicht aufpassen, können ggf. Probleme mit der Threadsicherheit auftreten. Die Hintergrundanalyse liest den Puffer, der den Text enthält, während der Benutzer diesen ändert. Stellen Sie sich nun vor, dass der Hintergrundprozess anstelle eines Puffers logisch eine Momentaufnahme des Texts abruft.

Wie kann dies richtig und effizient erreicht werden? Durch die Verwendung eines Typs wie „String“ wird das Problem zwar richtig, aber nicht effizient gelöst. Bei dieser Lösung kann der Benutzer den Text zur gleichen Zeit ändern, während das Tool ausgeführt wird. Mit jeder Änderung wird aber eine neue Kopie des Texts erstellt. Dies kann bei großen Dokumenten langsam sein und Arbeitsspeicher vergeuden. Eine weitere richtige Lösung wäre die Verwendung eines änderbaren Typs, z. B. „System.Text.StringBuilder“. Dies ist jedoch auch ineffizient, weil das Tool mithilfe einer abgerufenen Sperre eine Kopie erstellen müsste. Der Benutzer könnte keine Änderungen vornehmen, bevor eine Kopie erstellt wurde. Auch die Verwendung von „ReadOnlyCollection<T>“ wäre nicht hilfreich, weil die zugrunde liegende Sammlung änderbar und freigegeben ist.

Sie benötigen eine andere Art von Unveränderlichkeit, die es ermöglicht, auf sichere Weise Änderungen vorzunehmen, ohne teure Threadsynchronisierungsmechanismen einzusetzen. Gleichzeitig müssen so viele Daten wie möglich zwischen den Threads ohne Kopiervorgänge oder mit nur wenigen Kopiervorgängen freigegeben werden. Unveränderliche Sammlungen stellen genau diese Art von Unveränderlichkeit bereit, die als „Persistenz“ bezeichnet wird. Sie sind nicht nur im oben beschriebenen Szenario sinnvoll, sondern auch anderen Multi- und Singlethreadszenarien, wie Sie weiter unten in diesem Artikel sehen werden.

Dieser Artikel enthält eine ausführliche Beschreibung des Entwurfs, der Implementierung und der Leistung unveränderlicher Sammlungen, damit Sie diese effektiv verwenden und sogar eigene unveränderliche Sammlungen und Typen schreiben können. Diese Sammlungen können für jede beliebige .NET-Plattform verwendet werden, die den .NET-Standard 1.0 oder höher unterstützt (d. h. sie können für alle Windows-Plattformen, Xamarin und .NET Core verwendet werden). Unveränderliche Sammlungen sind relativ neu und werden als NuGet-Pakete bereitgestellt. Sie werden daher nicht von .NET Framework selbst verwendet, auch wenn Sie für viele Framework-APIs sinnvoll wären. Solche APIs verwenden stattdessen die möglicherweise weniger gut geeignete „ReadOnlyCollection<T>“ oder eine Kopie einer unveränderlichen Sammlung. Ich werde die Paketversion 1.3.0 verwenden. Der Quellcode ist als Teil von CoreFX verfügbar.

Beachten Sie, dass es möglich ist, unsicheren Code oder Reflektion zu verwenden, um beinahe jede Unveränderlichkeitsgarantie zu umgehen. Wenn ein Typ als unveränderlich beschrieben wird, besteht im Allgemeinen ein impliziter Vorbehalt, dass mit diesen Techniken Unveränderlichkeitsgarantien umgangen werden können. Dies gilt auch für die unveränderlichen Sammlungen, die in diesem Artikel beschrieben werden.

Definieren unveränderlicher Sammlungen

Bevor ich mich mit den Interna unveränderlicher Sammlungen beschäftige, muss ich definieren, was unveränderliche Sammlungen sind. Eine unveränderliche Sammlung ist eine Sammlung von Instanzen, die ihre Struktur immer beibehält und Zuweisungen auf Elementebene nicht zulässt, dennoch aber APIs zum Ausführen von Mutationen bereitstellt. Mit der „Struktur“ einer Sammlung meine ich die Anzahl der Elemente und deren relative Reihenfolge (die durch ihre Indizes im Fall einer Arraystruktur und durch ihre Links im Fall einer verknüpften Struktur bestimmt wird).

Wenn Sie z. B. ein Element mithilfe von Push auf einen „ImmutableStack<T>“ übertragen, erhalten Sie zwei isolierte unveränderliche Stapel: einen Stapel mit dem neuen Element und einen ohne dieses. Andererseits ändert das Übertragen eines Element auf einen veränderlichen „Stack<T>“ effektiv den Stapel, und Sie erhalten nur einen Stapel, der das neue Element aufweist. Beachten Sie, dass unveränderliche und veränderliche Sammlungen keine Garantien bezüglich der Elemente selbst bereitstellen. Wenn T den Typ „Int32“ oder „String“ aufweist, sind die Element ebenfalls unveränderlich. Wenn T jedoch einen Typ wie etwa „StringBuilder“ aufweist, sind die Elemente sehr wohl veränderlich.

Damit ein unveränderliches Objekt generiert werden kann, muss es initialisiert werden. Aus diesem Grund ist das Objekt während der Initialisierung veränderlich. Nachdem ein Verweis auf das Objekt (durch Rückgabe des Objekts aus einer nicht privaten Methode) veröffentlicht wurde, bleibt das Objekt effektiv für den Rest seiner Lebensdauer unveränderlich.

Der Entwurf unveränderlicher Sammlungen verfolgt zwei Ziele. Auf der einen Seite soll zum Vermeiden von Kopiervorgängen sowie zum Verringern des Drucks auf den Garbage Collector so viel Arbeitsspeicher wie möglich wiederverwendet werden (eine solche Implementierung wird normalerweise als „persistent“ bezeichnet). Das zweite Ziel ist die Unterstützung der gleichen Vorgänge, die von veränderlichen Sammlungen mit konkurrenzfähiger Zeitkomplexität bereitgestellt werden.

Unveränderliche Stapel

Der veränderliche Typ „Stack<T>“ wird mithilfe eines Arrays implementiert. Arrays eignen sich jedoch nicht für unveränderliche Sammlungen, weil die einzige Möglichkeit zum Beibehalten der aktuellen Instanz im Kopieren des gesamten Arrays und Ausführen der Änderung für dieses neue Array besteht. Der unveränderliche Stapel würde auf diese Weise unzumutbar langsam. Verknüpfte Listen können auf elegante Weise für die Implementierung verwendet werden. Jedes Element enthält einen Zeiger auf das darunter liegende Element (oder NULL für das unterste Element). Ein unveränderbarer Stapel wird als ein Zeiger auf das oberste Element dargestellt. Auf diese Weise können Elemente eines bestimmten Stapels mithilfe von Push übertragen bzw. Pop entfernt werden, ohne ihn zu ändern. Gleichzeitig werden alle seine Elemente mit dem sich ergebenden Stapel gemeinsam verwendet. Durch diesen einfachen Entwurf wird der unveränderliche Stapel zur einfachsten unveränderlichen Sammlung. Ich werde an späterer Stelle in diesem Artikel die Unterschiede zwischen veränderlichen und unveränderlichen Stapeln aufzeigen.

Sehen wir uns nun an, wie unveränderliche Stapel erstellt und verwendet werden. Der „ImmutableStack<T>“ und alle anderen unveränderlichen Sammlungen werden im System.Collections.Immutable-Namespace definiert. Damit die gemeinsame Verwendung des Arbeitsspeichers maximiert wird, bieten unveränderliche Sammlungen keine öffentlichen Konstruktoren. Zum Erstellen einer Instanz einer unveränderlichen Sammlung müssen Sie eine der CreateXxx<T>-Methoden verwenden, die in einem statischen Typ definiert ist, der der unveränderlichen Sammlung entspricht. Für den unveränderlichen Stapel wird dieser Typ als „ImmutableStack“ bezeichnet. Er stellt die folgenden Factorymethoden zur Verfügung:

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);

Alle Methoden besitzen einen generischen Typparameter „T“, der den Typ der in der Sammlung gespeicherten Elemente angibt. Die erste Methode erstellt einen leeren unveränderlichen Stapel, der intern einfach das Singleton-Element „ImmutableStack<T>.Empty“ zurückgibt. Die zweite Methode erstellt einen Stapel, auf den das angegebene Element mithilfe von Push übertragen wurde. Dies entspricht „ImmutableStack<T>.Empty.Push(item)“. Die dritte und die vierte Methode erstellen einen Stapel, auf den die angegebenen Elemente mithilfe von Push in der entsprechenden Reihenfolge übertragen wurden. Die CreateRange<T>-Methode wird wie folgt implementiert:

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

Alle Factorymethoden für alle unveränderlichen Sammlungen werden der Einfachheit halber bereitgestellt. Intern beginnen sie alle mit der leeren Sammlung und fügen dieser dann die angegebenen Elemente hinzu. Die Elemente werden immer flach kopiert.

Sehen Sie sich nun die folgende Sequenz von Vorgängen an, die mit dem leeren Stapel beginnt:

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();

Beachten Sie, dass die Push- und Pop-Methoden einen Verweis auf den sich ergebenden unveränderlichen Stapel zurückgeben. Im Gegensatz dazu geben die Push- und Pop-Methoden des veränderlichen „Stack<T>“ die Werte „void“ bzw. „T“ zurück. Dieser Entwurf spiegelt die Tatsache, dass das Ändern eines unveränderlichen Stapels konzeptionell zu einem ganz anderen Stapel führt, während das Ändern eines veränderlichen Stapels den Stapel tatsächlich verändert. Wenn die gleiche Sequenz von Vorgängen für einen veränderlichen Stapel ausgeführt wird, erhalten Sie ein anderes Endergebnis. Abbildung 1 zeigt dies. Der Stapel ist unveränderlich, weil keine Möglichkeit besteht, die Zeiger und Werte von Knoten zu ändern.

Abbildung 1A: Eine Änderung an einem unveränderlichen Stapel führt im Vergleich zu veränderlichen Stapeln zu einem anderen Stapel

Beachten Sie, dass der leere unveränderliche Stapelknoten den Standardwert von „T“ speichert (der für „Int32“ 0 ist). Der veränderliche Stapel legt außerdem nur die Werte von mit Pop entfernten Elementen auf den Standardwert fest, anstatt die Größe des Arrays zu verkleinern. Der nicht belegte Teil des Arrays wird als „Schlupfspeicher“ bezeichnet.

Zum Abrufen des obersten Elements eines unveränderlichen Stapels können Sie die Peek-Methode oder eine andere Überladung von „Push“ verwenden, die einen out-Parameter besitzt, über den das Element zurückgegeben wird.

Unveränderliche Listen

Die Listendatenstruktur ist komplexer als der Stapel. Dies liegt hauptsächlich am Indizierungsvorgang. Die Listenstruktur bietet Elementabruf, Hinzufügung und Entfernung an einem angegebenen Index. Die Verwendung eines Arrays (wie in der veränderlichen „List<T>“ geschehen) wäre vertretbar. Wie jedoch schon weiter oben erläutert, ist dies für eine unveränderliche Liste für allgemeine Zwecke ineffizient. Die Verwendung einer verknüpften Liste ist ebenfalls ungeeignet, weil Sie ggf. viele Elemente traversieren müssen, um das Element am angegebenen Index zu erreichen. Sie können stattdessen alle Vorgänge durch ausgeglichene Binärbäume mit vertretbarer Leistung implementieren. Die meisten unveränderlichen Sammlungen werden mithilfe ausgeglichener Binärbäume implementiert. Die restlichen Sammlungen verwenden verknüpfte Listen, und nur eine Sammlung (das unveränderliche Array) verwendet Arrays, wie im nächsten Abschnitt erläutert wird.

Jeder Knoten im Baum enthält ein Element der Liste und besitzt daher einen Index. Der Typ „ImmutableList<T>“ organisiert den Baum so, dass ein Durchlauf des Baums beginnend mit dem tiefsten Element in der entsprechenden Reihenfolge einem Durchlauf der Liste in der entsprechenden Reihenfolge vom Element am Index 0 bis zum letzten Element entspricht.

Betrachten wir folgendes Programm:

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);

Abbildung 2 zeigt, was im zugrunde liegenden Binärbaum geschieht, während die Sequenz der Vorgänge beginnend mit der leeren unveränderlichen Liste ausgeführt wird. Jedes Kästchen stellt einen Knoten im Baum dar. Das Kästchen, das den Buchstaben E enthält, stellt das leere Singleton-Baumelement dar (die Pfeile, die ins Nichts zeigen, müssen so interpretiert werden, dass sie auf das Kästchen mit dem Buchstaben E zeigen). Die Kästchen und Pfeile auf der rechten Seite der Abbildung sind unveränderlich, während die Kästchen und Pfeile auf der linken Seite vorübergehend veränderlich sind. Dies wird durch eine interne boolesche Kennzeichnung namens „frozen“ angegeben. Diese Kennzeichnung dient zwei Aufgaben, wie ich gleich erläutern werde.

Abbildung 2: Interner Zustand der Bäume (linke Seite) und Zustand nach dem Abschluss der Mutationen, auf den öffentlich zugegriffen werden kann (rechte Seite)

Zum Hinzufügen des ersten Elements zum Baum wird ein neuer Knoten erstellt, bei dem beide Zeiger auf den leeren Knoten zeigen. Bei allen neu erstellten Knoten ist die Kennzeichnung „frozen“ zu Beginn auf „false“ (vorübergehend veränderlich) festgelegt. Zu diesem Zeitpunkt sind keine weiteren Aktionen erforderlich. Der Baum wird daher durch Festlegen der Kennzeichnung „frozen“ auf „true“ unveränderlich. Dies wird auf der rechten Seite der Abbildung dargestellt. Auf diese Weise bleibt der Baum für seine restliche Lebensdauer unveränderlich.

Wenn ein zweites Element hinzugefügt werden soll, muss aufgrund der Organisation des Baums dessen Knoten das rechte untergeordnete Element des ersten Knotens sein. Da dieser Knoten jedoch unveränderlich ist, können Sie seine Zeiger nicht ändern. Die einzige Möglichkeit, das zweite Element hinzuzufügen, besteht darin, nicht nur einen Knoten für dieses Element zu erstellen, sondern auch einen weiteren Knoten für das erste Element. Aus diesem Grund zeigen l2 und l3 auf zwei völlig separate Bäume.

Analog dazu muss das dritte Element das rechte untergeordnete Element des zweiten Knotens sein. Es kann nur durch Erstellen neuer Knoten für das erste und das zweite Element hinzugefügt werden. Dieses Mal ist der sich ergebende Knoten jedoch nicht ausgeglichen. Dieser Fall tritt ein, wenn die Differenz der Höhe der linken und rechten Unterbäume des Stamms mindestens den Wert 2 besitzt. Damit der Baum ausgeglichen bleibt, müssen Sie ihn erneut so organisieren, dass er zu dem Baum wird, der unten rechts in Abbildung 2 gezeigt wird. Dies ist möglich, weil der Baum noch veränderlich ist und kein Code außerhalb des Typs „Immutable­List<T>“ darauf zugreifen oder die Mutationen beobachten kann. Bevor ein Verweis auf den Baum zurückgegeben wird, wird er gesperrt, indem die Kennzeichnung „frozen“ jedes Knotens auf „true“ festgelegt wird, damit er unveränderlich wird. Dies zeigt die erste Aufgabe der Kennzeichnung „frozen“.

Die letzte Codezeile ruft die Replace-Funktion auf, die nach dem angegebenen Element sucht und dieses dann durch ein anderes Element ersetzt. In diesem Fall wird ein neuer Knoten zum Speichern des neuen Elements erstellt, und die anderen Knoten des gleichen Baums werden im neuen Baum wiederverwendet.

Aufgrund der Organisation des Baums besitzt jeder einzelne Vorgang für die Liste (Hinzufügung, Einfügung, Entfernung oder Suche) eine Zeitkomplexität von O(log N). Dabei ist N die Anzahl der zurzeit in der Liste enthaltenen Elemente. Im Gegensatz dazu sind Vorgänge für die veränderliche Liste „List<T>“ entweder O(1) (wenn der Vorgang lokal ausgeführt werden kann) oder O(N) (wenn das zugrunde liegende Array kopiert werden muss).

Sie können einen einzelnen Vorgang für eine unveränderliche Liste schnell ausführen. Wenn Sie jedoch eine große Anzahl M von Vorgängen nacheinander ausführen möchten, dauert dies O(M log N). Sie können diese Zeit optimieren, indem Sie die Kennzeichnung „frozen“ nutzen und alle Mutationen zusammen ausführen. Diese Optimierung wird durch Builder ermöglicht.

Die meisten unveränderlichen Sammlungen einschließlich „ImmutableList<T>“ definieren als „Builder“ bezeichnete Typen, die die gleichen zugrunde liegenden Datenstrukturen verwenden und die gleichen APIs bereitstellen. Der Unterschied besteht darin, dass ein Builder nicht die Kennzeichnung „frozen“ nach jedem Vorgang festlegt. Er hält alle neuen erstellten Knoten in einem veränderlichen Zustand, damit Sie viele Vorgänge effizienter ausführen können. Der Buildertyp für die unveränderliche Liste ist „ImmutableList<T>.Builder“.

Zum Erstellen einer Builderinstanz benötigen Sie eine unveränderliche Sammlungsinstanz. Sie können mit einer leeren Sammlung beginnen und die statische Methode „ImmutableList.CreateBuilder<T>“ verwenden oder die ToBuilder-Instanzmethode für eine angegebene unveränderliche Sammlung nutzen. Im letztgenannten Fall bleiben alle vorhandene Knoten wie versprochen unveränderlich. Nur die neuen Knoten sind veränderlich. Nachdem alle Vorgänge ausgeführt wurden, können Sie die ToImmutable-Instanzmethode aufrufen, um alle Knoten zu sperren und die Sammlung effektiv in einen unveränderlichen Zustand zu versetzen. „ImmutableList<T>“ stellt mehrere Instanzmethoden zur Verfügung (z. B. „AddRange“ und „RemoveRange“), die einen Verweis auf „IEnumerable<T>“ annehmen und intern einen Builder zum Ausführen des Vorgangs für die angegebenen Elemente verwenden.

Einige Vorgänge profitieren nicht von Buildern und sind von Natur aus teuer. Die Reverse-Instanzmethode muss alle Knoten im Baum kopieren, die keine Blätter sind, um die Reihenfolge der Elemente umzukehren. Die Sort-Instanzmethode wird durch Kopieren aller Elemente in ein Array, Sortieren des Arrays und anschließendes Erstellen der unveränderlichen Liste aus dem sortierten Array implementiert.

Die veränderliche „List<T>“ verwendet intern ein Array. Für das Einfügen von Elementen in die Mitte oder Entfernen aus der Mitte eines Arrays ist das Erstellen eines neuen Arrays und Kopieren aller anderen Elemente erforderlich. Außerdem kann das Zuordnen extrem großer Arrays in einem fragmentierten Adressraum nicht möglich sein. Die veränderliche „LinkedList<T>“ löst diese beiden Probleme. „ImmutableList<T>“ bietet die Vorteile beider Elemente, verringert aber die Effizienz anderer Vorgänge. „ImmutableList<T>“ ist die unveränderliche Sammlung, die „List<T>“ und „LinkedList<T>“ entspricht. Beachten Sie, dass „StringBuilder“ im Wesentlichen „List<Char>“ entspricht.

Unveränderliche Arrays

Der Typ „The ImmutableArray<T>“ implementiert ebenso wie „ImmutableList<T>“ eine unveränderliche Liste. Dies geschieht jedoch auf andere Weise. „ImmutableArray<T>“ ist nur ein dünner Wrapper um ein Array vom Typ „T[ ]“. Er ist „dünn“, weil es sich um einen Werttyp handelt, der ein einzelnes Feld vom Verweistyp enthält. Das Array selbst wird über den verwalteten Heap zugeordnet. Zum Ausführen von mutierenden Vorgängen wird eine Kopie des gesamten Arrays erstellt, und der Vorgang wird für diese ausgeführt. Unter diesem Blickwinkel ist „ImmutableArray<T>“ eine Generalisierung von „String“, weil es Zeichenfolgen von Elementen eines beliebigen Typs (nicht nur „Char“) darstellen kann.

Alle mutierenden Vorgänge dauern O(N) mithilfe von „Immutable­Array<T>“, mit „ImmutableList<T>“ hingegen O(log N). „ImmutableArray<T>“ ist jedoch in drei Aspekten überlegen. Erstens: Der Zugriff auf ein Element dauert O(1), wenn sein Index mithilfe von „ImmutableArray<T>“ angegeben wird, mit „ImmutableList<T>“ jedoch O(log N). Zweitens: Beide Implementierungen bieten zwar eine Iteration in linearer Zeit, „ImmutableArray<T>“ ist jedoch cachefreundlich, weil alle Elemente nacheinander gespeichert werden. Das Iterieren durch ein „ImmutableArray<T>“ kann um ein Vielfaches schneller sein als das Iterieren durch eine „ImmutableList<T>“. Drittens: „Immutable­Array<T>“ belegt weniger Arbeitsspeicher, weil keine Zeiger verwendet werden. Im Allgemeinen werden Sie Messungen ausführen müssen, um zu ermitteln, welche Option unter bestimmten Umständen verwendet werden sollte. Beide Typen implementieren die IImmutableList<T>-Schnittstelle. Sie können diese Schnittstelle in Ihrem Code verwenden, um auf einfache Weise zwischen den Typen zu wechseln.

Wie immer können Sie die Leistung steigern und den Druck durch Garbage Collection (GC) verringern, indem Sie Massenvorgänge und einen Pool für die Builder-Objekte verwenden. Sie können die XxxRange-Methoden für Massenvorgänge oder „ImmutableArray<T>.Builder“ verwenden, der ähnlich wie „List<T>“ implementiert ist.

Beachten Sie Folgendes: Da der Standardentwurf von LINQ-Operatoren mit IEnumerable<T>-Verweisen arbeitet, ist für das Anwenden auf den Werttyp „ImmutableArray<T>“ Boxing erforderlich. Das NuGet-Paket für unveränderliche Sammlungen enthält eine Implementierung einiger LINQ-Operatoren, die speziell für „ImmutableArray<T>“ gedacht sind, um Boxing zu vermeiden. Sie finden dieses in „System.Linq.ImmutableArrayExtensions“.

Unveränderliche Wörterbücher

Der Typ „ImmutableDictionary<TKey, TValue>“ verwendet einen ausgeglichenen Binärbaum zum Darstellen des Wörterbuchs. Jeder Knoten im Baum enthält einen „ImmutableList<SchlüsselWertPaar<TKey, TValue>>“ (der ebenfalls ein ausgeglichener Binärbaum ist), der alle Elemente aufweist, deren Hashwert identisch ist. Der veränderliche „Dictionary<TKey, TValue>“ verwendet hingegen ein Array aus Schlüssel-Wert-Paaren mit offener Adressierung für die Konfliktauflösung. Insgesamt ist „ImmutableDictionary<TKey, TValue>“ um ein Vielfaches langsamer und belegt wesentlich mehr Arbeitsspeicher als „Dictionary<TKey, TValue>“. Das Verwenden des Wörterbuchbuilders verbessert die Situation nur unwesentlich, weil die zugrunde liegende Struktur noch immer ein aus Bäumen bestehender Baum ist. Sie sollten definitiv die Leistung messen, wenn „ImmutableDictionary<TKey, TValue>“ verwendet wird, um zu ermitteln, ob sie akzeptabel ist. Wenn dies nicht der Fall ist, müssen Sie ggf. ein eigenes unveränderliches Wörterbuch schreiben.

Leistung und Arbeitsspeichernutzung unveränderlicher Sammlungen

Auch wenn die Verwendung einer unveränderlichen Sammlung im Prinzip ideal ist, führt sie ggf. nicht zu einer akzeptablen Leistung. Aus diesem Grund ist es wichtig zu verstehen, wie eine solche Sammlung implementiert wird und wie sie sich auf die Leistung auswirkt.

Vergleichen wir also die Leistung der unveränderlichen Liste mit der Leistung des veränderlichen Gegenstücks. Sie finden die Zeitkomplexität allgemeiner Vorgänge für unveränderliche Sammlungen unter bit.ly/2ko07HS. Das alles ist nicht wirklich aussagekräftig. Es ist besser, ein Beispiel in der Praxis zu untersuchen. Ich habe drei Programme geschrieben, die einfach 10 Millionen 8-Byte-Integerwerte an eine veränderliche Liste, eine unveränderliche Liste bzw. einen unveränderlichen Listenbuilder anfügen oder dieser/diesem voranstellen. In Abbildung 3 werden die Ergebnisse gezeigt. (Die angezeigten Werte sind ungefähre Werte. Die Zeitangabe erfolgt in Sekunden. Der Arbeitsspeicher wird in MB angegeben. JIT-Optimierungen sind aktiviert. Der Standardkonstruktor wird zum Erstellen der veränderlichen Liste verwendet.)

Abbildung 3: Zeitdauer und verwendeter Arbeitsspeicher für veränderliche Listen, unveränderliche Listen und unveränderliche Arrays

Das Anfügen an eine veränderliche Liste ist effektiv, weil die Basis ein Array ist. Das Array verdoppelt seine Größe zeitweise. Danach ist das Hinzufügen eines Elements ein schneller Vorgang. Andererseits ist das Hinzufügen eines Elements zu einer unveränderlichen Liste weitaus ineffektiver, weil die Basis ein Baum ist. Selbst wenn der Builder verwendet wird, ist der Vorgang ungefähr 40 Mal langsamer. Das ist ein großer Unterschied. Dieser Vergleich ist jedoch nicht ganz fair. Ein fairer Vergleich wäre die Gegenüberstellung der unveränderlichen Liste und einer veränderlichen Liste, die Threadsynchronisierung verwendet, um ähnliche Momentaufnahmesemantik bereitzustellen. Dennoch sind unveränderliche Sammlungen in Singlethreadszenarien viel weniger attraktiv. Auch wenn die Zeitkomplexität nur O(log N) ist, ist der Faktor „verborgene Konstante“ recht groß. Ich werde gleich erläutern, warum.

Für die Voranstellung sieht die Sache ganz anders aus. „List<T>“ würde viele Stunden bis zum Abschluss benötigen, weil 10 Millionen kurzlebige Arrays mit zunehmender Größe zugeordnet und kopiert werden müssten. Die unveränderliche Liste und ihr Builder weisen mehr oder weniger die gleiche Leistung auf.

Abbildung 4 zeigt einen Teil des Diagramms zur verwalteten Speicherbelegung, das mit den Diagnosetools von Visual Studio 2015 beim Anfügen von Elementen an eine unveränderliche Liste erstellt wurde. Markierungen über dem Diagramm geben aufgezeichnete GCs der Generierungen an. Das Diagramm zeigt, dass GCs häufig auftreten (ungefähr alle paar Dutzend Millisekunden). Ich habe PerfView zum Ermitteln der Gesamtzeit verwendet, die für diese kleinen GCs erforderlich war. Ohne Verwendung des Builders beträgt die GC-Dauer ungefähr 4 Sekunden. Dies ist die Differenz zwischen dem direkten Verwenden der unveränderlichen Liste und dem Einsatz des Builders. Zum Ermitteln, ob diese Differenz tatsächlich durch GCs verursacht wird oder nur zufällig auftritt, habe ich ebenfalls PerfView für das Programm verwendet, das den Builder nutzt. Es hat sich herausgestellt, dass dies tatsächlich der Fall ist. Die Erklärung ist einfach, wenn Sie sich die Funktionsweise beider Methoden ansehen. Die unveränderliche Liste erstellt zahlreiche kurzlebige Objekte sowie Objekte mit mittlerer Lebensdauer, während der Builder die Zeiger vorhandener Objekte mutiert. Durch das direkte Verwenden der unveränderlichen Liste wurden mehr als 100 GCs ausgelöst, während das Verwenden des Builders und der veränderlichen Liste weniger als 10 GCs ausgelöst hat.

Abbildung 4: Die GC wird wesentlich häufiger ausgeführt, wenn Elemente an die unveränderliche Liste angefügt werden

Der Builder ist erheblich langsamer als die veränderliche Liste. Dafür gibt es vier Gründe, die miteinander in Beziehung stehen. Erstens: Es wird eine verknüpfte Struktur verwendet, bei der zahlreiche Cachefehler auftreten. Zweitens: Nach dem Anfügen von jeweils zwei Elementen ist der Baum nicht mehr ausglichen und muss gedreht werden, damit der Ausgleich wiederhergestellt wird. Drittens: Für das Anfügen eines Elements müssen (log N) Knoten traversiert werden. Viertens: Bei jedem Hinzufügen eines Elements wird eine separate Speicherbelegung für den Hostknoten ausgelöst.

Dies bedeutet nicht, dass die GC Teil des Problems ist. Im Gegenteil: Durch die automatische Speicherverwaltung wird es sogar einfacher, unveränderliche Sammlungen zu schreiben und zu verwenden. Sie bereinigt automatisch alle unveränderlichen Objekte, die gar nicht verwendet werden.

Vergleichen wir auch den unveränderlichen Stapel mit dem veränderlichen Stapel. Anhand solcher Vergleiche können Sie die Kosten von Objektzuordnungen und den zugehörigen Cachefehlern (die nur einen kleinen Teil der gesamten Cachefehler darstellen, die ggf. später auftreten) quantifizieren, die sich aus der Verwendung verknüpfter Datenstrukturen ergeben. Der unveränderliche Stapel wirkt sich auf die GC positiv aus, weil nur Objekte zugeordnet werden, die Bestandteil des sich ergebenden Stapels sein werden. Er ist so effizient, dass er nicht einmal einen Builder aufweist. Das Übertragen von 10 Millionen 8-Byte-Integerwerten auf einen veränderlichen Stapel mithilfe von Push dauert ungefähr 0,17 Sekunden. Der gleiche Vorgang für einen unveränderlichen Stapel nimmt ungefähr 1 Sekunde in Anspruch. Das ist eine Verlangsamung um ungefähr den Faktor 6 und gar nicht schlecht. Das Iterieren durch einen großen unveränderlichen Stapel oder eine verknüpfte Struktur kann im Vergleich zum Iterieren durch eine entsprechende veränderliche Sammlung um ein Vielfaches langsamer sein. Dies liegt hauptsächlich an Cache- und Seitenfehlern (und wird auf NUMA-Knoten für NUMA-Architekturen aufgrund der Freigabe übertragen).

Vor diese Hintergrund tritt für die auf einem Array basierenden veränderlichen Sammlungen eine Verschwendung des Schlupfspeichers auf. Wenn Sie die meisten Elemente aus einer großen Sammlung entfernen, wird das zugrunde liegende Array nicht kleiner und belegt weiterhin unnötigerweise Arbeitsspeicher. Verknüpfte unveränderliche Sammlungen verwalten immer ein Objekt pro Element. Dies ist jedoch kaum ein Vorteil für verknüpfte Sammlungen, wenn es um typische Verwendungsfälle geht.

Einsatzmöglichkeiten unveränderlicher Sammlungen

Der grundlegende Vorteil von Unveränderlichkeit besteht darin, dass es erheblich einfacher wird, die Funktionsweise von Code zu begründen. Auf diese Weise können Sie schnell richtigen und eleganten Code schreiben. Angenommen, Sie verwenden ein Singlethreadprogramm. In einer bestimmten Codezeile machen Sie sich z. B. Gedanken über den Zustand einer unveränderlichen Sammlung. Diesen können Sie auf einfache Weise herausfinden, indem Sie die Stellen im Code ermitteln, an denen die Sammlung erstellt wurde. Im Allgemeinen kommt nur eine von wenigen solchen Stellen in Betracht. Indem Sie diesen Vorgang fortsetzen, gelangen Sie zu einer veränderlichen Quelle oder einer leeren Sammlung. Es ist unwichtig, ob die unveränderliche Sammlung an Methoden übergeben wurde, weil ihre Struktur mit Sicherheit gespeichert wird. Sie müssen sich daher keine Gedanken machen, was in diesen Methoden geschieht. Wenn die Elemente ebenfalls einen unveränderlichen Typ aufweisen, können Sie den vollständigen Zustand der Sammlung beurteilen. In Multithreadprogrammen ist die Vorgehensweise gleichermaßen einfach. Es wird jedoch schwieriger, wenn freigegebene veränderliche Sammlungen verwendet werden. Auf diesem Grund kann Unveränderlichkeit ein allgemeines Entwurfsprinzip wie in der funktionalen Programmierung sein.

Betrachten Sie nun die folgende Methodensignatur:

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

Diese Methode besitzt einen veränderlichen Stapelparameter. Der Stapel kann daher durch die Methode geändert werden. Dies könnte sogar der Zweck der Methode sein. Wenn der Stapel aber geändert wird, geht der alte Zustand verloren, wenn der Aufrufer keine Kopie davon erstellt hat. Beachten Sie, dass die Methode selbst dann nichts zurückgeben muss, wenn sie den Stapel geändert hat. Ein weiterer Aspekt, den diese Signatur vermittelt: Sie bietet keine Garantien für die Threadsicherheit.

Das ist in Ordnung, wenn Threadsicherheit nicht wichtig ist und die Methode den Stapel ändern soll, weil Sie an diesen Änderungen interessiert sind. Wenn die Funktion der Methode darin besteht, den Stapel nur zu lesen oder zu untersuchen (oder ihn zu ändern, die Änderungen für den Aufrufer zu keinem Zeitpunkt wichtig sind), eignet sich die folgende Signatur ggf. besser:

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

Dabei gibt es zwei Probleme. Erstens: „ReadOnlyCollection<T>“ erfordert, dass eine „List<T>“ generiert wird. Der Aufrufer muss daher den Stapel in eine Liste kopieren. Wenn der Parameter als der Schnittstellentyp „IReadOnly­Collection<T>“ festgelegt wird, wird dieses Problem vermieden, weil „Stack<T>“ ihn implementiert. Die Methode könnte ihn dann aber genau so einfach zurück in „Stack<T>“ konvertieren. Zweitens: Wenn die Methode normalerweise Änderungen am Stapel vornimmt, muss sie ihn zuerst in eine veränderliche Sammlung kopieren. Diese Signatur bietet ebenfalls keine Garantien für Threadsicherheit. Sie ist nur geeignet, wenn die ursprüngliche veränderliche Sammlung „List<T>“ ist und die Methode sie nicht ändert.

In Szenarien, in denen potenziell mehrere Threads auf die Sammlung zugreifen, kann sich die folgende Signatur besser eignen:

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

Der gleichzeitige Stapel ist veränderlich. Alle Threads sehen daher alle Änderungen. Dies ist nur sinnvoll, wenn mindestens eine der folgenden zwei Bedingungen vorliegt: Es wird von der Methode erwartet, dass sie potenziell von anderen Threads vorgenommene Änderungen berücksichtigt, sobald diese erfolgen, oder andere Threads möchten die von der Methode vorgenommenen Änderungen sehen, sobald diese erfolgen. Beachten Sie, dass jeder beliebige Thread jede spezifische Änderung separat sehen kann. Wenn einige Threads nur einen Batch von Änderungen oder keine der Änderungen sehen sollen, müssen diese andernfalls eine globale Sperre abrufen und eine private Kopie des Stapels erstellen. Diese beiden Situationen werden als Momentaufnahmesemantik bezeichnet.

Beachten Sie, dass in verschiedenen Szenarien unterschiedliche Sammlungstypen verwendet werden müssen. Außerdem wäre eine gute Dokumentation wünschenswert, in der die Funktionsweise und Verwendung der Methode erläutert wird. Unveränderliche Sammlungen vereinfachen dies alles. Die folgenden beiden Signaturen eignen sich für die meisten Szenarien:

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

Erkennen Sie, wie elegant diese APIs sind? Die erste Signatur wird verwendet, wenn durch die Methode vorgenommene Änderungen kein Problem darstellen. Andernfalls kann die zweite Signatur verwendet werden. Es sind nur zwei Fälle denkbar, in denen unveränderliche Sammlungen nicht geeignet sind: Durchsatz (die Rate, mit der Elemente verarbeitet werden) und Producer-Consumer-Semantik. Wie bereits weiter oben gezeigt wurde, weisen die unveränderlichen Sammlungen für allgemeine Zwecke einen schlechten Durchsatz auf. Dies gilt insbesondere für Singlethreadszenarien. In der Producer-Consumer-Semantik sind gleichzeitige veränderliche Sammlungen eleganter und führen zu einer besseren Leistung. Der Unterschied zwischen Producer-Consumer-Semantik und Momentaufnahmesemantik besteht darin, wie sich die lesenden oder verbrauchenden Agents verhalten. In der erstgenannten Semantik werden Elemente verbraucht (dauerhaft entfernt), in der letztgenannten hingegen verarbeitet und nur durch die schreibenden oder generierenden Agents entfernt. Ich würde die Momentaufnahmesemantik als eine Changer-Processor-Semantik bezeichnen, weil sie ändernde Agents und verarbeitende Agents verwendet. Verarbeitende Agents können Änderungen vornehmen, solange diese Änderungen in einer separaten Kopie vorliegen, die zusammen mit anderen Kopien erforderlich ist. Wenn diese Änderungen global vorgenommen werden müssten, käme der Bereich von Producer-Consumer-Semantik zum tragen.

Praktische Schnittstellen und APIs

Es sind zahlreiche ToXxx-Erweiterungsmethoden verfügbar, die veränderliche Sammlungen oder sammlungsbezogene Schnittstellen in unveränderliche Sammlungen konvertieren. Diese Methoden kopieren die veränderliche Sammlung, anstatt diese wiederzuverwenden, um die Unveränderlichkeit beizubehalten. Viele unveränderliche Sammlungen bieten praktische Methoden (z. B. zum Sortieren und Suchen), die den Methoden veränderlicher Sammlungen ähnlich sind. Diese unterstützen Sie beim Mischen von Code, der beide Sammlungsarten verwendet.

Damit unveränderliche Sammlungen in vorhandenen Codebasen besser eingesetzt werden können, implementieren einige von ihnen geeignete allgemeine Schnittstellen wie z. B. „IEnumerable<T>“, „IList<T>“ und „ICollection<T>“. Einige der deklarierten Methoden (z. B. „IList<T>.Insert“ dienen zum Mutieren der Sammlung. Diese werden durch Auslösen einer „NotSupported­Exception“ implementiert. Unveränderliche Sammlungen implementieren außerdem die entsprechenden unveränderlichen Schnittstellen, die im NuGet-Paket definiert sind.

Der Typ „System.Collections.Immutable.ImmutableInterlocked“ stellt mehrere Methoden bereit, die ineinandergreifende Austauschmechanismen zum ordnungsgemäßen Aktualisieren von Elementen in unveränderlichen Sammlungen oder von Verweisen auf unveränderliche Sammlungen bereitstellen. Die folgende Methode nimmt z. B. einen Verweis auf ein Element an und aktualisiert dieses gemäß dem angegebenen Transformator:

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

Die Auswirkungen solcher Vorgänge können von allen Threads beobachtet werden, und es wird garantiert, dass das gleiche Element immer von allen Threads beobachtet wird.

Zusammenfassung

In diesem Artikel wurden die Vorteile unveränderlicher Sammlungen vorgestellt, und der Entwurf und die Implementierung unveränderlicher Stapel, Listen, Arrays und Wörterbücher wurden ausführlich behandelt. Im Lieferumfang des NuGet-Pakets sind zahlreiche weitere unveränderliche Sammlungen enthalten. Für beinahe jede veränderliche Sammlung ist eine entsprechende unveränderliche Sammlung vorhanden, die Sie in diesem Paket finden. Ich hoffe, dass Sie diese Typen effektiv in Ihrem Code einsetzen können. Wenn Ihnen das Unveränderlichkeitsmuster gefällt und Sie gerne eigene unveränderliche Typen schreiben möchten, können Sie ein von Andrew Arnott erstelltes, auf Roslyn basierendes Tool verwenden, mit dem das Schreiben unveränderlicher Typen genau so einfach wie das Schreiben veränderlicher Typen ist. Weitere Informationen zu diese Tool finden Sie unter bit.ly/2ko2s5O.

Hadi Brais ist Doktorand am Indian Institute of Technology Delhi. Er erforscht Compileroptimierungen für die Speichersysteme der nächsten Generation. Einen Großteil seiner Zeit verbringt er mit dem Schreiben von Code in C/C++/C# und dem Analysieren von Laufzeiten, Compilerframeworks und Computerarchitekturen. Er bloggt auf hadibrais.wordpress.com. Kontaktieren Sie ihn unter hadi.b@live.com..

Unser Dank gilt den folgenden technischen Experten für die Durchsicht dieses Artikels: Andrew Arnott und Immo Landwerth