Die Lieblings-Collection

Irgendwann ist es in jedem Projekt so weit: Irgendwann ­arbeiten Sie in absolut jedem .NET-Projekt mit Mengen. Mengen werden sehr häufig mit einer List<T> verwaltet, der generischen Allround-Menge, mit der wir jeden beliebigen Datentyp im Speicher ablegen können.

Aber wissen Sie eigentlich, wie eine List<T> arbeitet, und vor allem, was die Probleme einer Liste sein können? Sie haben keine Ahnung, oder doch so ein bisschen? Keine Angst, wir erklären es ausführlich.

Für den Anfang ziehen wir die Dokumentation des Datentyps zurate [1]. Auf der Suche nach Erkenntnis ist in der Regel auch ein Blick in den Originalquellcode von Microsoft auf GitHub immer sinnvoll. Doch im Fall des Datentyps List<T> verläuft diese Unternehmung im Nichts: Zwar sind im Runtime-Repository viele Klassen aus dem Namespace System.Collection.Generic zu finden, doch ausgerechnet List<T> ist dort nicht dabei [2].

Microsoft verwendet einen kleinen Trick. Gewisse Klassen, die aus Sicht des .NET-Teams von fundamentalem Wert sind, befinden sich in der sogenannten System.Private.CoreLib.

Das ist eine Bibliothek beziehungsweise ein Repository, in dem die Implementierung sehr wichtiger Klassen liegt. Diese werden beim Kompilierungsprozess von der jeweiligen Runtime (Aktuell nur noch Mono und .NET) direkt eingebunden und stellen somit eine Basisimplementierung für verschiedene Runtimes dar. Dort findet man auch die Implementierung der List<T> [3].

Eine List<T> mag eine kleine Klasse sein, wenn man die Anzahl der Methoden betrachtet, doch die Klasse selbst hat stolze 1100 Lines of Code und ist damit schon etwas mächtiger, als man meinen könnte. Beim Durchsehen des Quellcodes entdeckt man einige Aufrufe der Klasse Array, und es wird sehr viel mit einer Array-Referenz (intern
_items genannt) gearbeitet.

Hier steckt auch das wichtige Know-how. .NET ist nicht in der Lage, Arrays einfach zu vergrößern oder zu verkleinern.

Stellen Sie sich dazu vor, dass das Array, das im Speicher liegt, umgeben von anderen Speicherbereichen ist. Ein einfaches Größer- oder Kleinermachen ist somit ein recht kompliziertes Unterfangen.

Gerade unter diesem Gesichtspunkt hilft uns List<T> gewaltig. Wir können beliebige Einträge hinzufügen, aber auch wieder entfernen, ohne uns irgendwelche Gedanken darüber machen zu müssen, wie denn nun welcher Eintrag an seinen Platz kommt.

Dieses Array kann jeder sehr einfach aufdecken. Mit dem Beispielcode in Bild 1 und mithilfe des Debuggers von Visual Studio lässt sich das Array sichtbar machen.

Visual Studio zeigt in der Rohdatenansicht das Innere der Klasse. Das bedeutet, dass auch private Felder oder statische Inhalte sichtbar werden. Unter anderem sieht man hier auch das eingangs erwähnte Array _items. Der Beispielcode in Bild 1 hat dabei zwei Einträge hinzugefügt.

Dem aufmerksamen Leser oder der Leserin wird aber bereits aufgefallen sein, dass dieses Array nicht eine Länge von zwei, sondern tatsächlich von vier hat. Dies ist auch in den Eigenschaften der Liste noch einmal deutlich zu sehen: Der Count beträgt zwei, wohingegen die Capacity vier aufweist. Fügen wir der Liste nun fünf Elemente hinzu, sieht man, dass Count zwar wie erwartet auf fünf steigt, die Capacity dann aber auf einmal acht beträgt (Bild 2).

Die Capacity steigt somit nicht linear an. Zeit, tiefer in den Code abzutauchen.

Im Quellcode auf GitHub ist die Methode Add schnell auffindbar. Siehe dazu [4] und Bild 3. Diese Methode ist sogar recht überschaubar und offenbart uns die interne Logik von unserer beliebten List<T>.

Es gibt ein privates Feld _version, welches bei jeder Operation inkrementiert wird. In den nächsten Zeilen wird überprüft, ob die _size kleiner ist als die aktuelle Länge des in­ternen Arrays _items. Sollte sie (noch) kleiner sein, so wird die _size erhöht und der Eintrag wird an die neue Stelle im Array eingehängt.

Sollte jedoch der Grenzfall eintreten, dass _size größer oder gleich der aktuellen Länge ist, so wird die Methode Add­WithResize aufgerufen. Diese Methode ruft dabei über einen kleinen Umweg die Methode Grow auf (Bild 4).

Und hier versteckt sich auch schon die Erklärung des Verhaltens. Die aktuelle Länge des Arrays wird einfach immer verdoppelt. Das bedeutet, wir haben 4, 8, 16, 32, 64, 128 und so weiter als mögliche Arraygrößen.

Die neu berechnete Größe wird einfach der Property Capacity zugewiesen, und in dieser Property passiert anschließend die eigentliche Action für die Aktion „vergrößern“ (Bild 5).

Diese Methode prüft, ob die neue Capacity ausreichend, also nicht kleiner der aktuellen _size ist, und kümmert sich anschließend um die Vergrößerung des internen Arrays. Dabei wird innerhalb des Setters von Capacity ein neues Array instanziert, die alten Werte werden in das neue Array übertragen und anschließend die Referenz auf das alte Array ersetzt – Schwupps haben wir mehr Platz. Aber Achtung: Das alte Array wird dem Garbage Collector überlassen.

Daraus lässt sich nun direkt eine wichtige Erkenntnis ableiten: Fügt man zu einer Liste sehr schnell sehr viel hinzu, entsteht dabei durchaus erwähnenswerter Müll (Bild 6).

Mit einem kleinen Beispielprogramm, welches in einer Schleife 10 Millionen Zahlen in die Liste wirft, erkennt man gerade mit Visual Studio, dass der Garbage Collector ordentlich zu arbeiten hat. Die gelben Dreiecke, die in Bild 6 eher aussehen wie ein Balken, sind tatsächlich die Iterationen des Garbage Collectors. Dies ist aufgrund unserer Vorgehens­weise und des internen Codes durchaus sinnvoll. Die Frage, die wir uns stellen müssen, ist, ob wir das optimieren können. Und ja, das ist durchaus möglich.

Die List<T> hat einen überladenen Konstruktor, dem wir ­eine initiale Capacity mitgeben können. Dadurch wird das interne Array _items automatisch mit dieser Größe instanziert. Das bedeutet, dass es zwischen Hinzufügeaktionen nicht mehr notwendig ist, dass die Implementierung von List<T> ein neues Array anlegt. Das Resultat sind zwar immer noch viele Garbage-Collection-Iterationen, doch wesentlich weniger, und auch die Laufzeit hat sich natürlich deutlich verringert (Bild 7).

Bleibt nun noch die letzte Frage zu klären: Wenn Aufrufe von Add für eine Vergrößerung und ein Umkopieren sorgen, wie sieht es dann bei Remove, RemoveRange oder Clear aus. Führen diese Methoden zu einer Verkleinerung? Wenn man sich nun erneut den Code der Implementierung ansieht, wird man feststellen: Fehlanzeige!

Dies hat natürlich Gründe: Woher soll die Runtime einen geeigneten Zeitpunkt entdecken, an dem eine Verkleinerung Sinn ergibt? Es könnte ja sein, dass in der nächsten Methode die Liste wieder benötigt wird. Und außerdem müssen wir nicht alle Tage eine Liste mit mehreren Tausend oder gar Millionen Einträgen anlegen.

Doch eine Methode hat sich als Aufräumaktion herausgestellt. Die Me­thode TrimExcess (Bild 8), welche sogar pub­lic ist und somit von außen zugreifbar, prüft, ob es möglich ist, die Capa­city zu verkleinern.

Dabei wird mit einer Schwelle (Threshold) gearbeitet, und wenn diese unterschritten wird, so wird mit der genauen, aktuellen _size (entspricht Count der Einträge) die Capacity minimiert und somit Speicher wieder freigegeben. Das bedeutet, dass unser Beispiel in der letzten Variante am schonendsten ist (Bild 9).

Nachdem in dieser Variante die Liste recycelt wird, wird das Array nur ein einziges Mal allokiert. Die Clear()-Methode verändert zwar die Größe des Arrays nicht, macht es aber wieder benutzbar. Dies zeigt Visual Studio deutlich in den besten Zeiten und auch, ohne eine einzige Garbage Collection angestoßen zu haben.

Nur selten fügen wir in Listen so viele Elemente ein. Trotzdem ist der Vergleich dieser drei Beispiele beeindruckend: Wie viel Garbage-Collection-Aktivität und wie viel Laufzeitverlän­gerung durch eine Grundoperation verursacht werden können.

Das heißt im Umkehrschluss, dass man unter den Gesichtspunkten der Performance und des Speicherbedarfs auch bei der Verwendung einer Liste der Klasse List<T> ein Auge auf den Code haben sollte.