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

40

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?

fredoverflow
quelle
7
Ich bin verwirrt, warum Sie vorschlagen, dass C ++ in einer Funktion, die C ++ nicht einmal unterstützt, schneller ist als andere Sprachen.
17
@eco: C ++ ist schneller beim Array-Zugriff, da es keine Co-Varianten-Arrays unterstützt. Fred möchte wissen, ob es "modernen OO-Sprachen" möglich ist, den Overhead von Co-Varianten-Arrays zu umgehen, um näher an C ++ - Geschwindigkeiten heranzukommen.
Mooing Duck
13
"Code, der kompiliert, aber zur Laufzeit Ausnahmen auslöst, ist eine schlechte Nachricht"
4
@Jesse Und Millionen von Menschen schreiben zuverlässigen, hoch skalierbaren Code in dynamischen Sprachen. Imo: Wenn Sie keine Testfälle für Ihren Code schreiben, ist es mir egal, ob es Compilerfehler gibt oder nicht, ich werde ihm sowieso nicht vertrauen.
Voo
7
@Jesse Und wann sonst würden Sie Ausnahmen erwarten, aber zur Laufzeit? Das Problem ist nicht Code, der zur Laufzeit Ausnahmen auslöst - es gibt viele Fälle, in denen dies sinnvoll ist -, sondern Code, der garantiert falsch ist und vom Compiler nicht statisch abgefangen wird, sondern stattdessen eine Ausnahme bei auslöst Laufzeit.
Jonathan M Davis

Antworten:

33

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.

Jonathan M Davis
quelle
Erscheint nicht - d-programming-language.org/arrays.html sagt : „Ein statisches Array T[dim]kann implizit auf eine der folgenden Optionen umgewandelt werden: ... U[]... Ein dynamisches Array T[]implizit auf eine der folgenden Optionen umgerechnet werden können U[]. .. wo Uist eine Basisklasse von T. "
Ben Voigt
2
@BenVoigt Dann müssen die Online-Dokumente aktualisiert werden. Leider sind sie nicht immer zu 100% auf dem neuesten Stand. Die Konvertierung funktioniert mit const U[], da Sie dann den Elementen des Arrays nicht den falschen Typ zuweisen können, aber T[]definitiv nicht konvertieren, U[]solange U[]es veränderlich ist. Das Zulassen von kovarianten Arrays wie zuvor war ein schwerwiegender Konstruktionsfehler, der jetzt behoben wurde.
Jonathan M Davis
@JonathanMDavis: Covariante Arrays sind schwierig, funktionieren aber gut für das spezielle Szenario von Code, der nur in Array- Elemente schreibt, die aus demselben Array gelesen wurden . Wie würde D erlauben, eine Methode zu schreiben, die Arrays beliebigen Typs sortieren könnte?
Supercat
@supercat Wenn Sie eine Funktion schreiben möchten, die beliebige Typen sortiert, dann templatisieren Sie sie. zB dlang.org/phobos/std_algorithm.html#sort
Jonathan M Davis
21

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

Lasse Espeholt
quelle
2
Scala verhindert auch dieses Konstrukt: val a = Array("st"); val b: Array[Any] = aist illegal. (Arrays in Scala sind jedoch ... aufgrund der verwendeten zugrunde liegenden JVM eine besondere Magie.)
17.
13

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.

Voo
quelle
10

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 ++.

Peter Alexander
quelle
Laut d-programming-language.org/arrays.html "Ein statisches Array T [dim] kann implizit in eines der folgenden konvertiert werden: ... U [] ... Ein dynamisches Array T [] kann implizit konvertiert werden zu einem der folgenden Werte: U [] ... wobei U eine Basisklasse von T ist. "
Ben Voigt
1
@BenVoigt: Veraltete Dokumente.
BCS
1
@BenVoigt: Ich habe eine Pull-Anfrage erstellt, um die Dokumentation zu aktualisieren. Hoffentlich wird dies bald behoben. Vielen Dank für den Hinweis.
Peter Alexander
5

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.

Peter Lawrey
quelle
2

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.

Mason Wheeler
quelle
1

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.

user40989
quelle
1

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.

Pillsy
quelle