Let’s Code: StructLayout
Und weiter geht’s mit der kleinen Serie. Analog zu Let’s Play Serien, in denen Personen spontan drauf los spielen und sich dabei aufnehmen, code ich einfach einige Zeilen C#, mit offenem Ziel.
Im vergangenen Beitrag habe ich gezeigt wie man mit yield return ein IEnumerable<T> als eine Art Stream erzeugen kann. Bevor ich aber die Vorteile davon aufzeige, muss noch das IShortTuple Interface implementiert werden. Als zusätzliche Einschränkung wählen wir noch, dass diese Implementierung sich in einem Dictionary gut verhalten soll. Das heißt wir wollen möglichst wenige Kollisionen der Hashwerte. Falls es doch zu Kollisionen kommt muss die Equals-Methode herhalten. Gleichheit definieren wir als Wertgleichheit der beiden Properties.
interface IShortTuple { ushort A { get; set; } ushort B { get; set; } }
Nun gibt es im .NET Framework bereits ein Tupel, jedoch verhält es sich eher grottig in Dictionaries (warum sich Tuple<…> so und nicht anders verhält erklärt Microsoft mit dem Einsatzzweck). Jedenfalls scheint das .NET Tuple die Hashcodes der einzelnen Elemente zu nehmen und mit folgender Funktion zu verwursteln (die Macht der Reflection möge mit uns sein)
// Yepp, this is why you should not use tuples of numeric values as dictionary keys internal static int CombineHashCodes(int h1, int h2) { return (((h1 << 5) + h1) ^ h2); }
Das Taugt für unseren Einsatzzweck natürlich wenig. Also schreiben wir eine eigene Implementierung, welche bei einem so kleinen Interface kaum der Rede wert ist. GetHashCode() gibt einen Integer zurück und da wir nur zwei shorts haben, können wir eindeutige (im Sinne von “ohne Kollisionen”) Hash-Codes für unsere Implementierung berechnen. Hierzu verschieben wir einen der beiden Werte um 16 Bit und “verodern” (sorry für das Wort) die Beiden zu einem Integer.
struct BitShiftTuple : IShortTuple { public ushort A { get; set; } public ushort B { get; set; } public override int GetHashCode() { return A | (B << 16); } }
Mit einer vergleichbaren Implementierung war ich jetzt eine ganze Weile lang zufrieden. Um ehrlich zu sein, war ich gar nicht auf der Suche nach einer besseren Lösung. Beim Stöbern in der MSDN Doku bin ich jedoch auf das StructLayout Attribut gestoßen. Hierdurch kann die Anordnung der Felder in einem Struct explizit angegeben werden, wobei auch Überlappungen möglich sind. Perfekt, so können wir beispielsweise ein Struct definieren, welches Felder für A und B sowie für den Hash hat. Dabei legen wir A und B so in dem Struct aus, dass A den ersten 16 Bit des Structs und B den zweiten 16 Bit entspricht:
[StructLayout(LayoutKind.Explicit)] internal struct LayoutTuple : IShortTuple { [FieldOffset(0)] private int hash; [FieldOffset(0)] private ushort a; [FieldOffset(2)] private ushort b; public override int GetHashCode() { return this.hash; } public ushort A { get { return this.a; } set { this.a = value; } } public ushort B { get { return this.b; } set { this.b = value; } } }
Den Hash müssen wir demnach gar nicht mehr berechnen. Die Frage die sich nun stellt ist ob uns dies tatsächlich einen Performance-Vorteil gibt. Ebenso muss das mit einer Implementierung verglichen werden, die sich vergleichbar verhält, aber ohne das explizite Layout des Structs auskommt. Das Thema für den nächsten Teil ist also ein 1×1 des Profilings, ich freue mich schon :)
Um die obigen Methoden abzurunden sollte noch Equals überschrieben oder besser IEquatable implementiert werden, wobei der Code einfach nur die Hash-Werte vergleichen muss, falls die zu vergleichenden Objekte unser Interface implementieren (Vorsicht: das Interface gibt ansich nicht vor wie GetHashCode implementiert ist. CodeContracts sind als zukünftiges Thema aber bereits vorgemerkt).