Ist dies eine gute Passform für eine Klasse oder Struktur (Geschwindigkeit ist wichtiger als Speicher)?

Question

Normalerweise würde ich nie in Frage stellen müssen, ob ein bestimmtes Szenario besser für eine Struktur oder Klasse geeignet ist, und ehrlich gesagt habe ich diese Frage nicht gestellt, bevor ich mich in diesem Fall für die Klasse entschieden habe. Jetzt, da ich optimiere, werden die Dinge ein wenig verwirrend.

Ich schreibe eine Anwendung zur Zahlenverarbeitung, die mit extrem großen Zahlen mit Millionen von Basis-10-Ziffern umgeht. Die Zahlen sind (x, y)-Koordinaten im 2D-Raum. Der Hauptalgorithmus ist ziemlich sequenziell und hat zu keinem Zeitpunkt mehr als 200 Instanzen der Klasse Cell (unten aufgeführt) im Speicher. Jede Instanz der Klasse belegt etwa 5 MB Speicher, was insgesamt nicht mehr als 1 GB maximalem Speicherbedarf für die Anwendung entspricht. Das fertige Produkt wird auf einem 16-Core-Maschine mit 20 GB RAM ausgeführt und keine anderen Anwendungen beanspruchen Ressourcen.

Hier ist die Klasse:

// Vererbung ist praktisch, aber hier nicht unbedingt erforderlich.
public sealed class Cell: CellBase
{
    // Enthält Zahlen mit Millionen von Ziffern (im Durchschnitt 512 KB).
    public System.Numerics.BigInteger X = 0;
    // Enthält Zahlen mit Millionen von Ziffern (im Durchschnitt 512 KB).
    public System.Numerics.BigInteger Y = 0;

    public double XLogD = 0D;
    // Die Größe des Arrays entspricht ungefähr Base2Log(this.X).
    public byte [] XBytes = null;

    public double YLogD = 0D;
    // Die Größe des Arrays entspricht ungefähr Base2Log(this.Y).
    public byte [] YBytes = null;

    // Unmengen anderer Eigenschaften für wissenschaftliche Berechnungen zu X und Y.
    // ANMERKUNG: 90% der anderen Felder und Eigenschaften sind Strukturen (ähnlich wie BigInteger).

    public Cell (System.Numerics.BigInteger x, System.Numerics.BigInteger y)
    {
        this.X = x;
        this.XLogD = System.Numerics.BigInteger.Log(x, 2);
        this.XBytes = x.ToByteArray();

        this.Y = y;
        this.YLogD = System.Numerics.BigInteger.Log(y, 2);
        this.YBytes = y.ToByteArray();
    }
}

Ich habe mich für die Verwendung einer Klasse anstelle einer Struktur entschieden, einfach weil es sich 'natürlicher' anfühlte. Die Anzahl der Felder, Methoden und der Speicher deuteten instinktiv auf Klassen statt auf Strukturen hin. Ich rechtfertigte das weiter, indem ich darüber nachdachte, wie viel Overhead temporäre Zuweisungsaufrufe verursachen würden, da die zugrunde liegenden Hauptobjekte Instanzen von BigInteger sind, die selbst eine Struktur ist.

Die Frage ist, habe ich klug gewählt, wenn die Geschwindigkeitseffizienz in diesem Fall das Hauptziel ist?

Hier noch ein wenig über den Algorithmus, falls es hilfreich ist. In jeder Iteration:

1. Einmaliges Sortieren aller 200 Instanzen. 20% der Ausführungszeit.
2. Berechnung benachbarter (x, y)-Koordinaten von Interesse. 60% der Ausführungszeit.
3. Parallelisierungs-/Thread-Overhead für Punkt 2 oben. 10% der Ausführungszeit.
4. Verzweigungs-Overhead. 10% der Ausführungszeit.
5. Die kostspieligste Funktion: BigInteger.ToByteArray() (Implementierung).

Answer 1

Dies würde besser als Klasse passen, aus vielen Gründen, einschließlich

• Es stellt logischerweise keinen einzelnen Wert dar
• Es ist größer als 16 Bytes
• Es ist veränderlich

Weitere Details siehe Auswahl zwischen Klassen und Strukturen.

Zusätzlich würde ich auch vorschlagen, dass es besser als Klasse geeignet ist, da:

• Es Verweistypen (Arrays) enthält. Strukturen, die Klassen enthalten, sind selten eine gute Designidee.

Das gilt besonders, angesichts dessen, was du tust. Wenn du eine struct verwenden würdest, würde das Sortieren Kopien der gesamten Struktur erfordern, anstatt nur Kopien der Verweise. Methodenaufrufe (es sei denn, sie werden per ref übergeben) würden ebenfalls einen enormen Overhead verursachen, da du alle Daten kopieren müsstest.

Die Parallelisierung von Elementen in einer Sammlung könnte auch wahrscheinlich einen enormen Overhead verursachen, da die Grenzprüfung in jedem Array der Struktur (d.h. wenn sie in einer List oder ähnlichem gespeichert wird) zu einer schlechten falschen Verwendung führen würde, da der gesamte Zugriff in die Liste den Speicher am Anfang der Liste zugreifen würde.

Ich würde empfehlen, dies als Klasse zu belassen und darüber hinaus versuchen, die Felder in Eigenschaften zu verschieben und die Klasse so unveränderlich wie möglich zu machen. Dies wird dazu beitragen, Ihr Design sauber zu halten und weniger wahrscheinlich problematisch bei der Mehrfachgewindigkeit zu sein.

Answer 2

Basierend auf dem, was Sie geschrieben haben, ist es schwer zu sagen (wir wissen zum Beispiel nicht, wie oft Sie einen Wert vom Typ Cell kopieren), aber ich würde nachdrücklich erwarten, dass hier ein class der richtige Ansatz ist.

Die Anzahl der Methoden in der Klasse spielt keine Rolle, aber wenn sie viele Felder hat, müssen Sie die Auswirkungen berücksichtigen, wenn Sie jedes Mal, wenn Sie einen Wert an eine andere Methode übergeben, all diese Felder kopieren (usw.).

Grundlegend scheint es ursprünglich kein Werttyp zu sein - aber ich verstehe, dass, wenn die Leistung besonders wichtig ist, die philosophischen Aspekte für Sie möglicherweise nicht so interessant sind.

Also ja, ich denke, Sie haben die richtige Entscheidung getroffen, und ich sehe keinen Grund, im Moment etwas anderes zu glauben - aber natürlich, wenn Sie die Entscheidung leicht ändern können und es als struct testen können, wäre das besser als Spekulation. Die Leistung ist bemerkenswert schwer genau vorherzusagen.

Answer 3

Da deine Klasse Arrays enthält, die den Großteil des Speichers verbrauchen, und du nur etwa 200 Zellinstanzen hast, ist der Speicherverbrauch der Klasse selbst kein Problem. Du hattest recht, dass sich eine Klasse natürlicher anfühlt und es tatsächlich die richtige Wahl ist. Meine Vermutung wäre, dass der Vergleich von XByte[] und XYByte[] die Sortierzeit begrenzt. Es kommt alles darauf an, wie groß deine Arrays sind und wie du den Vergleich durchführst.

Answer 4

Lassen Sie uns zunächst die Leistungsfragen ignorieren und uns langsam an sie herantasten.

Structs sind ValueTypes und ValueTypes sind Werttypen. Integer und DateTime sind Werttypen und ein guter Vergleich. Es macht keinen Sinn, darüber zu sprechen, ob eine 1 gleich oder ungleich einer anderen 1 ist, oder ob eine 2010-02-03T12:45:23.321Z gleich oder ungleich einer anderen 2010-02-03T12:45:23.321Z ist. Sie haben in verschiedenen Anwendungen unterschiedliche Bedeutungen, aber dass 1 == 1 und 1 != 2 ist, und dass 2010-02-03T12:45:23.321Z == 2010-02-03T12:45:23.321Z und 2010-02-03T12:45:23.321Z != 2931-03-05T09:21:29.43Z ist in der Natur von Ganzzahlen und Datum/Zeit enthalten und das macht sie zu Werttypen.

Das ist die reinste Art, darüber nachzudenken. Wenn es mit dem oben Genannten übereinstimmt, ist es ein Werttyp, wenn nicht, ist es ein Verweistyp. Nichts anderes spielt dabei eine Rolle.

Erweiterung 1: Wenn ein X ein X haben kann, muss es sich um einen Verweistyp handeln. Ob das logisch aus dem oben Gesagten folgt, ist diskutabel, aber was auch immer Sie zu dieser Frage denken, Sie können keine Struktur haben, die eine Instanz von sich selbst als Mitglied hat (direkt oder indirekt) in der Praxis, also das ist das.

Erweiterung 2: Einige sagen, dass die Schwierigkeiten, die von veränderbaren Strukturen herrühren, von dem oben Gesagten kommen, und manche nicht. Wie auch immer Sie zu dieser Frage stehen, es gibt praktische Schwierigkeiten. Eine veränderbare Struktur kann in einigen Fällen nützlich sein, aber sie verursachen genug Verwirrung, dass sie auf private Fälle als Optimierung beschränkt werden sollten, anstatt auf öffentliche Fälle als Regel.

Hier kommt der Leistungsaspekt...

Werttypen und Verweistypen haben in verschiedenen Fällen unterschiedliche Eigenschaften, die die Geschwindigkeit, den Speicherverbrauch und die Art und Weise beeinflussen, wie der Speicherverbrauch die Garbage Collection in mehreren Hinsichten beeinflusst, wodurch jeder verschiedene Vor- und Nachteile in Bezug auf die Leistung hat. Wie viel Aufmerksamkeit wir diesem Aspekt schenken, hängt davon ab, wie sehr wir uns auf diese Ebene einlassen müssen. Es lohnt sich zu sagen, dass die Unterschiede tendenziell zu einem Gewinn führen, wenn Sie sich an die obige Regel halten, um zwischen Struktur und Klasse zu entscheiden. Wenn wir darüber hinaus über dieses Thema nachdenken, bewegen wir uns zumindest in Richtung Optimierung.

Optimierungsstufe 1.

Wenn eine Werttyp-Instanz mehr als 16 Bytes pro Instanz enthält, sollte sie wahrscheinlich zu einem Verweistyp gemacht werden. Dies wird manchmal sogar als "natürlicher" Unterschied und nicht als Optimierung betrachtet. Streng genommen gibt es nichts im Begriff "Werttyp", das "16 oder weniger Bytes" impliziert, aber es neigt dazu, sich so auszugleichen.

Abgesehen von der simplen "16-Byte"-Regel, je kleiner es ist, desto schneller ist es zu kopieren. Werden Sie also viele Boxen machen müssen? Seit der Einführung von Generics konnten wir viele Fälle vermeiden, in denen wir mit 1.0 und 1.1 boxen mussten, daher ist das nicht mehr so ein großes Thema wie früher, aber wenn Sie es tun, wird es die Leistung beeinträchtigen.

Optimierungsstufe 2.

Die Tatsache, dass Werttypen auf einem Stack platziert werden können, direkt in einem Array platziert werden können (anstatt Referenzen dazu) und direkte Felder einer Struktur oder Klasse sein können (wiederum ohne Referenzen dazu), kann den Zugriff auf sie und ihre Felder schneller machen.

Wenn Sie ein Array von ihnen erstellen und wenn Nullwerte einen nützlichen Ausgangspunkt für Sie darstellen, erhalten Sie diesen unmittelbar, während Sie bei Verweistypen ein Array von Nullen erhalten. Dies kann Strukturen schneller machen.

Bearbeitung: Etwas, das sich aus dem Obigen ergibt, wenn Sie schnell durch Arrays iterieren, dann, zusätzlich zu dem direkten Zugriff, der einen Schub gegenüber dem Folgen des Verweises gibt, laden Sie ein paar Instanzen jedes Mal in den CPU-Cache (64 Bytes auf aktuellen x86-32 oder x86-64/amd, 128 Bytes auf ia-64). Es muss eine ziemlich enge Schleife sein, damit es eine Rolle spielt, aber es gibt Fälle, in denen es wichtig ist.

Praktisch gesagt, die meisten Fälle von "Ich habe mich für eine Struktur anstelle einer Klasse entschieden, um die Leistung zu verbessern" basieren entweder auf dem ersten Punkt oder dem ersten in Kombination mit dem zweiten.

Optimierungsstufe 3.

Wenn einige der Werte, die Sie interessieren, Duplikate voneinander sind und sie groß sind, dann können Sie mit unveränderlichen Instanzen (oder veränderbare Instanzen, die Sie einfach niemals ändern, sobald Sie mit dem, was folgt, beginnen) bewusst unterschiedliche Verweise aliasen, um viel Speicher zu sparen, weil Ihre z. B. 20 duplizierten Objekte von je 2 KiB tatsächlich dasselbe Objekt sind, wodurch in diesem Fall 26 KiB gespart werden. Dies kann auch Vergleiche schneller machen, weil die Fälle, in denen Sie auf Identität Abkürzungen machen können, häufiger sind. Dies kann nur mit Verweistypen erfolgen.

Optimierungsstufe 4.

Strukturen, die Arrays enthalten, könnten jedoch das enthaltene Array aliasen und intern die oben genannte Technik verwenden, was diesen Punkt ausgleicht, obwohl dies etwas komplizierter ist.

Optimierungsstufe X.

Es spielt keine Rolle, wie viel Nachdenken über diese Vor- und Nachteile zu einer bestimmten Antwort führt, wenn tatsächlich das Messen der Ergebnisse zu Unterschieden führt. Da es sowohl Vor- als auch Nachteile gibt, ist es immer möglich, sich zu irren.

Beim Nachdenken über 1 bis 4, zusammen mit den Unterschieden zwischen Wert- und Verweistypen abgesehen von solchen Optimierungsüberlegungen, denke ich, dass Sie sich für eine Klasse entscheiden sollten.

Beim Nachdenken über Stufe X würde es mich nicht überraschen, wenn Ihre tatsächliche Testung mich widerlegen würde. Der beste Teil ist, wenn es mühsam ist, von einer Klasse auf eine Struktur zu wechseln (Sie machen von Aliasierung oder der Möglichkeit eines Nullwertes starken Gebrauch), dann können Sie recht zuversichtlich sein, dass dies ein Verlust ist. Wenn es nicht mühsam ist, können Sie einfach wechseln und messen! Ich würde dringend empfehlen, einen Test zu messen, bei dem Sie tatsächlich etwas ausführen anstelle etwas 10.000 mal zu wiederholen - was spielt es für eine Rolle, wenn Sie eine bestimmte Operation ein paar Sekunden lang 10.000 Mal schneller ausführen können, wenn Sie eine andere Operation in der Realität 20 Mal häufiger durchführen?

Answer 5

Ein Struct kann nur sicher ein Feld vom Array-Typ enthalten, wenn entweder (1) der Zustand des Structs von der Identität des Arrays abhängt und nicht von dessen Inhalt (wie es bei ArraySegment der Fall ist), oder (2) keine Referenz zum Array von irgendetwas gehalten wird, das versuchen könnte, es zu verändern (typischerweise bedeutet dies, dass das Array-Feld privat sein wird und der Struct selbst das Array erstellen und alle Modifikationen durchführen wird, die jemals damit gemacht werden sollen, bevor er eine Referenz im Feld speichert).

Ich befürworte den häufigeren Einsatz von Structs im Vergleich zu anderen hier, aber die Tatsache, dass Ihr Datenspeicher-Ding zwei Felder vom Array-Typ hätte, wäre ein starkes Argument gegen die Verwendung eines Structs.