16. Okt 2017
Lesedauer 9 Min.
Generics in C#
Von Daten unabhängigen Code schreiben
Richtig benutzte Generics gewährleisten Typsicherheit bei hoher Performance.
Motivation für diesen Beitrag zu Generics in C# war die Beobachtung, dass Entwickler häufig gegen Best Practices verstoßen und nicht selten offene Fragen existieren. Fakt ist, dass sich die Generics in C#.NET fundamental von anderen Konzepten – etwa von Java und C++ – unterscheiden. Dieser Artikel betrachtet die Generics gemäß dem C#-ECMA-Standard, während sich die Aussagen über Implementationen auf das .NET Framework beziehen.Das Ziel von generischen Programmen ist es, Algorithmen unabhängig von den später verwendeten Datentypen zu formulieren. Das folgende Beispiel soll zur Verwendung von Generics motivieren: Zahlen sollen in einer Liste gespeichert werden. Dabei sollen Zahlen, die kleiner sind als die größte bereits in der Liste vorhandene Zahl, nicht gespeichert werden. Geben Sie also die Zahlen [1, 4, 2, 7, 5] ein, so soll das Ergebnis [1, 4, 7] lauten: Als erste Zahl wird die 1 hinzugefügt. Anschließend kommt die 4 dazu und ist damit das größte Objekt. Da die danach eingegebene 2 kleiner ist als die 4, wird sie nicht berücksichtigt. Die 7 ist wieder größer als die 4 und wird folglich gespeichert. Eine Implementierung könnte für ganze Zahlen so aussehen wie in Listing 1 gezeigt.
Listing 1: Incrementing Collection für int
<span class="hljs-keyword">internal</span> <span class="hljs-keyword">class</span> <span class="hljs-title">IncrementingCollection</span> { <br/> <span class="hljs-keyword">private</span> <span class="hljs-keyword">readonly</span> List&lt;<span class="hljs-keyword">int</span>&gt; _storageList = <br/> <span class="hljs-keyword">new</span> List&lt;<span class="hljs-keyword">int</span>&gt;(); <br/> <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span>[] <span class="hljs-title">GetData</span>(<span class="hljs-params"></span>) </span>{ <br/> <span class="hljs-comment">// kopiert die Daten, schützt vor Änderungen</span><br/><span class="hljs-comment"> return _storageList.ToArray(); </span><br/><span class="hljs-comment"> } </span><br/><span class="hljs-comment"> public void AddItem(int itemToAdd) { </span><br/><span class="hljs-comment"> if (_storageList.Count == 0 || </span><br/><span class="hljs-comment"> itemToAdd &gt; _storageList.Last()) </span><br/><span class="hljs-comment"> { </span><br/><span class="hljs-comment"> _storageList.Add(itemToAdd); </span><br/><span class="hljs-comment"> } </span><br/><span class="hljs-comment"> } </span><br/><span class="hljs-comment">} </span>
Der Code erzeugt das gewünschte Ergebnis. Die Wiederverwendbarkeit ist allerdings nicht optimal. Wenn beispielsweise eine neue Anforderung gestellt wird und der Algorithmus auch mit reellen Zahlen umgehen soll, dann taugt die Collection dafür nicht. Eine Möglichkeit, sie anzupassen, besteht darin, die Klasse zu kopieren und int durch float zu ersetzen. Dies ist aber nicht wirklich praktikabel, da man mit jedem neuen Datentyp die IncrementingCollection kopieren muss. Anstatt die Klasse zu kopieren, kann man auf die nachfolgende Technik zurückgreifen. Es fällt auf, dass die einzige Bedingung, die der Datentyp erfüllen muss, die Vergleichbarkeit ist. Diese muss mit IComparable gegeben sein, und die IncrementingCollection2 kann wiederverwendet werden, siehe Listing 2. Benutzt werden kann die Klasse nun wie folgt:
Listing 2: IncrementingCollection2 mit IComparable
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-type">IncrementingCollection2</span> { </span><br/><span class="hljs-class"> private readonly <span class="hljs-type">List</span>&lt;<span class="hljs-type">IComparable</span>&gt; _storageList = </span><br/><span class="hljs-class"> new <span class="hljs-type">List</span>&lt;<span class="hljs-type">IComparable</span>&gt;(); </span><br/><span class="hljs-class"> public <span class="hljs-type">IComparable</span>[] <span class="hljs-type">GetData</span>() { </span><br/><span class="hljs-class"> // kopiert die <span class="hljs-type">Daten</span>, schützt vor Änderungen</span><br/><span class="hljs-class"> return _storageList.<span class="hljs-type">ToArray</span>(); </span><br/><span class="hljs-class"> } </span><br/><span class="hljs-class"> public void <span class="hljs-type">AddItem</span>(<span class="hljs-type">IComparable</span> <span class="hljs-title">itemToAdd</span>) { </span><br/><span class="hljs-class"> if (<span class="hljs-title">itemToAdd</span> == <span class="hljs-title">null</span>) </span><br/><span class="hljs-class"> throw new <span class="hljs-type">ArgumentNullException</span>(</span><br/><span class="hljs-class"> <span class="hljs-title">nameof</span>(<span class="hljs-title">itemToAdd</span>)); </span><br/><span class="hljs-class"> if (<span class="hljs-title">_storageList</span>.<span class="hljs-type">Count</span> == 0 || </span><br/><span class="hljs-class"> <span class="hljs-title">itemToAdd</span>.<span class="hljs-type">CompareTo</span>(<span class="hljs-title">_storageList</span>.<span class="hljs-type">Last</span>()) &gt; 0) </span><br/><span class="hljs-class"> { </span><br/><span class="hljs-class"> _storageList.<span class="hljs-type">Add</span>(<span class="hljs-title">itemToAdd</span>); </span><br/><span class="hljs-class"> } </span><br/><span class="hljs-class"> } </span><br/><span class="hljs-class">} </span>
var collectionWithFloats =
new IncrementingCollection2();
collectionWithFloats.AddItem(2.5f);
collectionWithFloats.AddItem(4.5f);
collectionWithFloats.AddItem(3.5f);
// Cast in den genutzten Datentyp
float[] dataFloats =
collectionWithFloats.GetData().Cast<float>().ToArray();
Hier ist unschön, dass durch die Nutzung der IncrementingCollection2 der Aufrufer der Methode GetData die Information verliert, welcher Datentyp in der Collection gespeichert worden ist. Da es in diesem einfachen Fall ersichtlich ist, um welchen Datentyp es sich bei dem Rückgabewert handelt, kann dieser mit LINQ konvertiert werden. Der Nachteil des Overheads ist offensichtlich. Beim Casten muss man zudem extrem aufpassen, dass keine Laufzeitfehler entstehen, denn der Compiler lässt den statischen Typecast nicht nur mit float, sondern mit jedem beliebigen Datentyp zu. Was macht der Compiler, wenn wir Äpfel mit Birnen vergleichen?
Listing 3: Kritischer Vergleich
var collectionWithFloats = <br/> new IncrementingCollection2(); <br/>collectionWithFloats.AddItem(2); <br/>collectionWithFloats.AddItem(4f);
Der Compiler bemängelt nichts, denn sowohl 2 als auch 4f sind IComparable. Während man noch argumentieren kann, dass 2 und 4f vergleichbar sein könnten, ergibt es spätestens dann keinen Sinn mehr, wenn man eine Klasse class Apfel : IComparable und eine zweite Klasse class Birne : IComparable hat und deren Instanzen nacheinander in dieselbe Collection gibt. Tatsächlich wird zur Laufzeit auch bei Vergleichen von int mit float eine System.ArgumentException geworfen. Der Code in Listing 3 wird das Programm also abstürzen lassen, obwohl es ohne Probleme kompiliert. Ein weiteres Problem ist, dass dabei int-Werte in IComparable geboxt werden. Häufiges und unnötiges Boxing kann Performance-Probleme zur Folge haben.
Generics in C 2.0
Der C#-ECMA-Standard (ECMA-334:2006) [1] beziehungsweise (ISO/IEC 23270:2006) hat 2006 in Version 2.0 Generics als Antwort auf das obige Problem eingeführt. Eine ähnliche Motivation kann in der neuesten Version dem Kapitel 8.16.1 „Why Generics“ entnommen werden. Ziel ist es, dem Programmierer mehr Sicherheit zu geben und gleichzeitig unnötiges Boxing zu verhindern. Wissenschaftliche Ausarbeitungen über Generics gibt es unter anderem von Microsoft Research [2]. Macht man von Generics etwas mehr Gebrauch, kann man die Collection wie in Listing 4 implementieren:Listing 4: Collection mit Generic
internal class IncrementingCollection&lt;T&gt; <br/> where T : IComparable&lt;T&gt; <br/>{ <br/> private readonly List&lt;T&gt; _storageList = <br/> new List&lt;T&gt;(); <br/> public void AddItem(T itemToAdd) { <br/> if (itemToAdd == null) <br/> throw new ArgumentNullException(<br/> nameof(itemToAdd)); <br/> if (_storageList.Count == 0) <br/> { <br/> _storageList.Add(itemToAdd); <br/> return; <br/> } <br/> if (itemToAdd.CompareTo(<br/> _storageList.Last()) &gt; 0) <br/> _storageList.Add(itemToAdd); <br/> } <br/>}
Durch den Klassenparameter T kann man die Collection so implementieren, als sei T eine beliebige, aber feste Klasse. Durch where T:IComparable<T> wird signalisiert, dass die Klasse nur mit solchen Typen instanzierbar ist, die IComparable<T> erfüllen. Ein Vergleich von Äpfeln und Birnen wird zudem unterbunden, wie Bild 1 zeigt. Zudem verliert man bei GetData nicht die Information, um welchen Datentyp es sich handelt. In diesem Fall ist es ein Array<T>, also Array<int>.
IComparable versus IComparable
Eine Frage, die man sich stellen kann, ist, ob man die Anforderung des Datentyps im Algorithmus mit IComparable oder IComparable<T> formulieren sollte. Angenommen, die verwendeten Klassen erfüllen beide Interfaces. Dies ist unter anderem dann nicht der Fall, wenn man ein nicht ordentlich implementiertes oder sehr altes API benutzt. Best Practice ist es, als Datentyp beide Interfaces zu implementieren, um mit alten Algorithmen kompatibel zu sein (Listing 5). Wenn man aber annehmen kann, dass alle Datentypen, die den Algorithmus aufrufen, sowohl IComparable als auch IComparable<T> sind, welches Interface sollte dann mit der where-Klausel im Algorithmus verlangt werden? Fehler aufgrund von nicht zueinander passenden Typen können mit beiden Interfaces verhindert werden. Fehler wie in Listing 3, bei dem man Äpfel mit Birnen vergleicht, geben keinen Hinweis auf die Lösung. Prüfungen wie in Bild 1 haben mit der Comparable-Spezifizierung nichts zu tun.
Listing 5: Comparable<T> versus Comparable
public int CompareGeneric&lt;T&gt;(T a, T b) <br/> where T : IComparable&lt;T&gt; <br/>{ <br/> return a.CompareTo(b); <br/>} <br/>public int Compare&lt;T&gt;(T a, T b) <br/> where T : IComparable <br/>{ <br/> return a.CompareTo(b); <br/>}
Die Antwort lautet IComparable<T>! Die Begründung findet sich direkt im Interface: int CompareTo(object obj); Wie man sieht, ist dies ein vergleichbarer Ansatz wie in Listing 2. Da IComparable während des Kompilierens keine Information darüber besitzt, welcher Datentyp verglichen wird, ist der Parameter der CompareTo-Methode vom Typ object. Implementiert eine Klasse nun die CompareTo-Methode, muss diese erst einmal das obj in seinen Typ zurückwandeln (casten), um anschließend einen Vergleich durchführen zu können. Bei Wertetypen (value types) müssen die Daten dabei noch völlig umsonst geboxt werden!
Beide Methoden kann man nur mit Parametern mit identischen Typen aufrufen, und beide Methoden verlangen vergleichbare Datentypen. Bild 2 zeigt den generierten IL-Code beider Varianten. In der Abbildung sieht man links den generierten IL-Code der nicht generischen CompareTo-Methode und auf der rechten Seite den IL-Code der generischen CompareTo-Methode. Auffällig ist, dass die generische Methode keinen Boxbefehl hat und eine kleinere Code size aufweist, was zu einem Benchmark motiviert. Der Benchmark
in Listing 6 (siehe auch [3]) wurde durchgeführt, um die Beobachtung zu untermauern. Bild 3 zeigt die Ergebnisse.Es ist nicht verwunderlich, dass die Ergebnisse für die Object-Methode schlechter sind, als die der Generic-Methode. Verwunderlich ist jedoch die krasse Relation. Die Object-Methode hat in diesem Data-Crunching-Beispiel deutliche Performance-Probleme.
in Listing 6 (siehe auch [3]) wurde durchgeführt, um die Beobachtung zu untermauern. Bild 3 zeigt die Ergebnisse.Es ist nicht verwunderlich, dass die Ergebnisse für die Object-Methode schlechter sind, als die der Generic-Methode. Verwunderlich ist jedoch die krasse Relation. Die Object-Methode hat in diesem Data-Crunching-Beispiel deutliche Performance-Probleme.
Wie funktionieren Generics?
Generics bringen Performance-Vorteile und dem Programmierer mehr Sicherheit beim Entwickeln. Genauer gesagt ist es nicht möglich, einen Laufzeitfehler zu erzeugen, wenn man auf statische Typenkonvertierungen verzichtet. Wird eine Collection wie in Listing 4 verwendet oder wie die obere Methode in Listing 6, dann kann bereits zur Kompilierzeit ermittelt werden, ob die Typen zueinander passen. Nun wird gezeigt, wie der Compiler beziehungsweise die Laufzeitumgebung mit generischen Typen umgeht.Listing 6: Benchmark
[ClrJob] <br/>public class GenericVsObject { <br/> private const int N = 10000; <br/> private readonly int[] _data; <br/> public GenericVsObject() { var random = <br/> new Random(42); <br/> _data = new int[N].Select(<br/> p =&gt; random.Next()).ToArray(); } <br/> <br/> [Benchmark] public int Object() { <br/> return _data.Aggregate(_data[0], Compare); } <br/> [Benchmark] public int Generic() { <br/> return _data.Aggregate(_data[0], <br/> CompareGeneric); } <br/> private int Compare&lt;T&gt;(T a, T b) <br/> where T : IComparable { <br/> return a.CompareTo(b); } <br/> private int CompareGeneric&lt;T&gt;(T a, T b) <br/> where T : IComparable&lt;T&gt; { <br/> return a.CompareTo(b); } <br/>} <br/>public class Program { <br/> public static void Main(string[] args) { <br/> BenchmarkRunner.Run&lt;GenericVsObject&gt;(); <br/> } <br/>}
Am Anfang des Artikels wurde der Ansatz vorgeschlagen, für jeden benutzten Typ die Klasse naiv zu kopieren und die Typparameter mit den konkreten Typen jeweils zu ersetzen. Dies ist vergleichbar mit dem Ansatz, der in C++ mittels Templates umgesetzt ist [4]. Beim Kompilieren wird ermittelt, mit welchen Typen die generische Klasse benutzt wird. Dann wird die Klasse vom C++-Compiler intern kopiert und jeweils separat kompiliert. Dieser Ansatz sorgt für große Binaries und gegebenenfalls lange Kompilierungszeiten. Das Problem mit den großen Binaries findet man auch unter der Bezeichnung Code-Explosion [5]. Da C#-Klassen in der CLR mittels Just-in-Time-Verfahren erst dann kompiliert werden, wenn sie gebraucht werden, bleibt dem Entwickler die lange Kompilierzeit erspart und die Binaries bleiben schlank. Zudem bietet C# Code-Sharing innerhalb einer App-Domain, was dafür sorgt, dass beispielsweise eine List<int> nicht für jede Binary eigenen x86-Code erzeugt. Nachfolgend wird das Generieren von Generics in der CLR betrachtet.Für Referenztypen (zum Beispiel Klassen und Strings) bietet es sich an, die generische Klasse intern einfach als Klasse mit Typparameter object zu kompilieren und diese Klasse als Basis für alle anderen Referenztypen zu teilen. Der Compiler hat bereits geprüft, dass der Code nur von zusammenpassenden Typen genutzt wird. Der Binary ist es aber egal, ob ein Typparameter von der Klasse ClassA oder ClassB ist. Intern haben alle Klassen Referenzen derselben Größe – 32 Bit bei 32-Bit-Plattformen und 64 Bit bei 64-Bit-Plattformen [6]. Dies ist vergleichbar mit Listing 2 mit object anstelle IComparable. Man kann sich also vorstellen, dass eine List<ClassA> intern nichts anderes ist als eine List<object>. Dementsprechend ist der generierte x86-Code von List<ClassA> exakt der gleiche wie von List<ClassB>. Wie bereits angedeutet, wird die Typsicherheit schon beim Kompilieren überprüft. Entscheidend ist hier, dass es zu keiner Code-Explosion mehr kommt. Der generierte Code von List<ClassA> ist im Grunde derselbe wie List<List<ClassA>>, da sowohl List<ClassA> als auch ClassA Referenztypen sind. Listing 7 zeigt, wie man eine Code-Explosion provozieren kann.
Listing 7: Code-Explosion
static void GenerateType&lt;T&gt;(int counter) { <br/> if (counter == 1000) { <br/> Console.WriteLine("1000 classes generated"); <br/> return; <br/> } <br/> GenerateType&lt;List&lt;T&gt;&gt;(++counter); <br/>}
Anders verhält sich der JIT-Compiler bei Wertetypen wie int, float oder struct. Hier liegen keine Zeiger im Speicher, bei denen man so tun kann, als seien sie object, sondern die Werte an sich. Tatsächlich könnte man, wie in Listing 5 angedeutet, die Wertetypen boxen. Dies führt aber unter anderem zu Performance-Nachteilen, wie in Bild 3 zu sehen ist. Hier hat man sich dafür entschieden, für jeden Wertetyp eigenen x86-Code zu generieren. Es liegt also für List<int> und List<float> jeweils eigener x86-Code vor. Vorteilhaft ist die Performance, Nachteile kann die Verwendung von Generics mit structs haben. Eine Code-Explosion ist an dieser Stelle nicht ausgeschlossen. Es kann sein, dass man für structs desselben Layouts und insbesondere derselben Größe den Code teilen kann, dies konnte aber in Recherchen nicht belegt werden.
Interessant ist noch die Frage, wie sich der JIT-Compiler verhält, wenn man in einer Klasse oder in einer Methode sowohl Werte- als auch Referenztypen verwendet. Auch in diesem Fall wird so viel Code wie möglich geteilt. Ein Dictionary<string, int> ist also gleichzusetzen mit einem Dictionary<object, int> und somit auch mit einem Dictionary<ClassA, int>. Ein Dictionary<object, float> hingegen erzeugt separaten Code.
Fazit
In diesem Artikel wurden verschiedene Ansätze zum generischen Programmieren besprochen. Zunächst wurde der Ansatz aufgezeigt, die Klassen zu kopieren. Dies ist vergleichbar mit Templates in C++. Im darauffolgenden Ansatz wurde in Listing 2 durch Abstrahieren nur noch eine einzige Implementierung benötigt. Dies führt aber zu Performance-Problemen und die Typsicherheit ist nicht mehr gewährleistet, da man auf statische Typkonvertierung angewiesen ist. Einige Interfaces existieren sowohl in generischer als auch in nicht generischer Form. Hier ist es aufgrund unnötigen Boxings empfehlenswert, die generische Version zu verwenden – sofern erlaubt. Die Generics ab C# 2.0 ermöglichen für den Entwickler Typsicherheit und sorgen für hohe Performance. Eine Anwendung sieht man in Listing 4. Abschließend wurde das Code-Sharing-Konzept betrachtet, laut dem der JIT-Compiler so viel x86-Code wie möglich teilt und für jeden Wertetyp separaten Code erzeugt.Fussnoten
- C# Language Specification, ECMA International, http://www.dotnetpro.de/SL1711Generics1
- Dachuan Yu, Andrew Kennedy, Don Syme, Formalization of Generics for the .NET Common Language Runtime, in POPL ’04, http://www.dotnetpro.de/SL1711Generics2
- BenchmarkDotNet.Diagnostics.Windows, http://www.dotnetpro.de/SL1711Generics3
- Standard C++ Foundation, isocpp, 2017, http://www.dotnetpro.de/SL1711Generics4
- Cédric Bastoul, Code Generation in the Polyhedral Model Is Easier Than You Think, http://www.dotnetpro.de/SL1711Generics5
- Jeffrey Richter, CLR Via C#, Fourth Edition, Microsoft Press, 2012, ISBN 978-0-73566745-7,
