Können moderne OO-Sprachen mit der Speicherleistung von C ++ mithalten?

Mir ist gerade aufgefallen, dass jede moderne OO-Programmiersprache, mit der ich zumindest ein wenig vertraut bin (die im Grunde nur Java, C # und D ist), kovariante Arrays zulässt. Das heißt, ein String-Array ist ein Objekt-Array:

Object[] arr = new String[2];   // Java, C# and D allow this

Covariante Arrays sind ein Loch im statischen Typsystem. Sie ermöglichen Typfehler, die zur Kompilierungszeit nicht erkannt werden können. Daher muss jedes Schreiben in ein Array zur Laufzeit überprüft werden:

arr[0] = "hello";        // ok
arr[1] = new Object();   // ArrayStoreException

Dies scheint ein schrecklicher Leistungseinbruch zu sein, wenn ich viele Array-Stores betreibe.

C ++ hat keine kovarianten Arrays, daher ist eine solche Laufzeitprüfung nicht erforderlich, was bedeutet, dass es keine Leistungseinbußen gibt.

Wird eine Analyse durchgeführt, um die Anzahl der erforderlichen Laufzeitprüfungen zu verringern? Zum Beispiel, wenn ich sage:

arr[1] = arr[0];

man könnte argumentieren, dass der Laden unmöglich scheitern kann. Ich bin mir sicher, dass es noch viele andere Optimierungsmöglichkeiten gibt, an die ich nicht gedacht habe.

Führen moderne Compiler solche Optimierungen tatsächlich durch, oder muss ich damit leben, dass beispielsweise ein Quicksort immer unnötige Laufzeitprüfungen durchführt?

Können moderne OO-Sprachen den durch die Unterstützung von Co-Varianten-Arrays verursachten Overhead vermeiden?

D hat keine kovarianten Arrays. Es erlaubte ihnen vor der letzten Veröffentlichung ( dmd 2.057 ), aber dieser Fehler wurde behoben.

Ein Array in D ist praktisch nur eine Struktur mit einem Zeiger und einer Länge:

struct A(T)
{
    T* ptr;
    size_t length;
}

Die Überprüfung von Grenzen erfolgt normalerweise beim Indizieren eines Arrays, wird jedoch beim Kompilieren mit entfernt -release. Im Release-Modus gibt es also keinen wirklichen Leistungsunterschied zwischen Arrays in C / C ++ und denen in D.

Ja, eine entscheidende Optimierung ist:

sealed class Foo
{
}

In C # kann diese Klasse für keinen Typ ein Supertyp sein, daher können Sie die Prüfung für ein Array von Typ vermeiden Foo.

Und zur zweiten Frage: In F # sind Co-Varianten-Arrays nicht zulässig (aber ich denke, die Prüfung bleibt in der CLR, es sei denn, dies wird in Optimierungen zur Laufzeit für unnötig befunden.)

let a = [| "st" |]
let b : System.Object[] = a // Fails

https://stackoverflow.com/questions/7339013/array-covariance-in-f

Ein etwas verwandtes Problem ist die Überprüfung der Array-Grenzen. Dies könnte eine interessante (aber alte) Lektüre über Optimierungen sein, die in der CLR vorgenommen wurden (Kovarianz wird auch an 1 Stelle erwähnt): http://blogs.msdn.com/b/clrcodegeneration/archive/2009/08/13/array-bounds -check-eliminierung-in-the-clr.aspx

Java-Antwort:

Ich nehme an, Sie haben den Code noch nicht verglichen, oder? Im Allgemeinen sind 90% aller dynamischen Casts in Java kostenlos, weil die JIT sie beseitigen kann (Quicksort sollte ein gutes Beispiel dafür sein), und der Rest ist eine ld/cmp/brSequenz, die absolut vorhersehbar ist (wenn nicht, warum zum Teufel wirft Ihr Code?) all diese dynamischen Besetzungsausnahmen?).

Wir laden viel früher als der eigentliche Vergleich, der Zweig wird in 99,9999% aller Fälle korrekt vorhergesagt (zusammengesetzt!), Sodass wir die Pipeline nicht blockieren (vorausgesetzt, wir treffen den Speicher nicht mit dem Ladevorgang, wenn nicht gut, das wird sich bemerkbar machen, aber dann ist die Last sowieso notwendig). Daher betragen die Kosten 1 Taktzyklus, wenn die JIT die Prüfung überhaupt nicht vermeiden kann.

Etwas Aufwand? Klar, aber ich bezweifle, dass du es jemals bemerken wirst.

Um meine Antwort zu unterstützen, lesen Sie bitte diesen Dr. Cliff Click-Blogpost , in dem es um die Leistung von Java vs. C geht.

D erlaubt keine kovarianten Arrays.

void main()
{
    class Foo {}
    Object[] a = new Foo[10];
}  

/* Error: cannot implicitly convert expression (new Foo[](10LU)) of type Foo[]
to Object[] */

Wie Sie sagen, wäre es ein Loch im Typensystem, dies zuzulassen.

Ihnen kann der Fehler verziehen werden, da dieser Fehler erst im letzten DMD behoben wurde, das am 13. Dezember veröffentlicht wurde.

Der Array-Zugriff in D ist genauso schnell wie in C oder C ++.

Vom Test habe ich auf einem billigen Laptop gemacht, der Unterschied zwischen der Verwendung int[]und Integer[]liegt bei ca. 1,0 ns. Der Unterschied ist wahrscheinlich auf die zusätzliche Prüfung des Typs zurückzuführen.

Im Allgemeinen werden Objekte nur für Logik höherer Ebenen verwendet, wenn nicht alle ns zählen. Wenn Sie alle ns speichern müssen, würde ich die Verwendung übergeordneter Konstrukte wie Objects vermeiden. Aufträge alleine sind wahrscheinlich nur ein sehr kleiner Faktor in einem realen Programm. Das Erstellen eines neuen Objekts auf demselben Computer dauert beispielsweise 5 ns.

Aufrufe zu compareTo sind wahrscheinlich viel teurer, insbesondere wenn Sie ein komplexes Objekt wie String verwenden.

Sie haben nach anderen modernen OO-Sprachen gefragt? Nun, Delphi vermeidet dieses Problem vollständig, indem es stringein Primitiv und kein Objekt ist. Ein Array von Zeichenfolgen ist also genau ein Array von Zeichenfolgen und nichts anderes. Alle Operationen auf diesen Zeichenfolgen sind so schnell wie der native Code, ohne dass der Aufwand für die Typprüfung groß ist.

String-Arrays werden jedoch nicht sehr oft verwendet. Delphi-Programmierer bevorzugen die TStringListKlasse. Für einen minimalen Overhead bietet es eine Reihe von String-Group-Methoden, die in so vielen Situationen nützlich sind, dass die Klasse mit einem Schweizer Taschenmesser verglichen wurde. Daher ist es idiomatisch, ein Zeichenfolgenlistenobjekt anstelle eines Zeichenfolgenarrays zu verwenden.

Wie bei anderen Objekten im Allgemeinen besteht das Problem nicht, da Arrays in Delphi wie in C ++ nicht kovariant sind, um die hier beschriebenen Typsystemlöcher zu vermeiden.

oder muss ich damit leben, dass zB ein Quicksort immer O (n log n) unnötige Laufzeitprüfungen durchführt?

Die CPU-Leistung ist nicht monoton, was bedeutet, dass längere Programme schneller als kürzere sein können (dies ist CPU-abhängig und gilt für die gängigen x86- und amd64-Architekturen). Daher ist es möglich, dass ein Programm, das gebundene Prüfungen an Arrays durchführt, tatsächlich schneller als das Programm ist, das aus dem vorherigen Programm abgeleitet wurde, indem diese gebundenen Prüfungen entfernt werden.

Der Grund für dieses Verhalten ist, dass die gebundene Prüfung die Ausrichtung des Codes im Speicher ändert, die Häufigkeit von Cache-Treffern ändert usw.

Also ja, leben Sie mit der Tatsache, dass Quicksort immer O (n log n) falsche Prüfungen durchführt und nach der Profilerstellung optimiert.

Scala ist eine OO-Sprache, die eher invariante als kovariante Arrays aufweist. Es zielt auf die JVM ab, sodass dort kein Leistungsgewinn zu verzeichnen ist. Es vermeidet jedoch ein gemeinsames Fehlverhalten von Java und C #, das die Typensicherheit aus Gründen der Abwärtskompatibilität beeinträchtigt.