Geschwindigkeitstest: Java, dann VB und dann C++

Mechanics

sebi707 schrieb:

Irgendwie scheint Java auf dem i7 ein glückliches Händchen zu haben was Optimierungen angeht. Auf dem Xeon sieht es allerdings sehr schlecht aus. Ich habe mal kurz ins Disassembly geschaut und es scheint als ob Clang und ICC loop unrolling für die do-while-Schleife gemacht haben. GCC konnte ich auf die schnelle nicht dazu überreden.

Das ist schon interessant. Mich würd echt noch interessieren, welchen Code Hotspot hier erzeugen kann. Selbst wenn man weiß, dass man auf einem i7 läuft, wie würde man das implementieren? Kann man sich den von Hotspot erzeugten Code ausgeben lassen?

Techel

Jetzt lohnt es sich vlt noch das mit der standardfunktion zu vergleichen.

Mechanics schrieb:

Kann man sich den von Hotspot erzeugten Code ausgeben lassen?

Hab ich mich auch schon gefragt. Soll wohl mit der Option " -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly " gehen. Allerdings fehlt mir dafür die hsdis-amd64.so Library. Wenn ich zuviel Langeweile habe versuche ich die mal zu besorgen oder selbst zu compilieren.

roflo schrieb:

Jetzt lohnt es sich vlt noch das mit der standardfunktion zu vergleichen.

Welche Standardfunktion? Das std::sort schneller ist als Bullesort sollte klar sein. Oder meinst du Java Standardlibrary gegen C++ Standardlibrary?

hustbaer

Atlan schrieb:

@m.e.
Anscheinend kann er es tatsächlich. Ich habe das Array mit Zufallszahlen zwischen -1 und 100.000 befüllt und Java hat 15 Sekunden gebraucht. Allerdings hat C++ mit derselben Modifikation knapp unter 18 Sekunden gebraucht.

Das kannst du daraus nicht schliessen.
Die Ausführung wird schonmal deswegen langsamer weil die Branch-Prediction der CPU nicht mehr helfen kann. Was auch der Grund ist warum der C++ Code langsamer wird.

Was du probieren müsstest:
Erst ein paar Durchläufe mit zufälligen Zahlen machen und danach nochmal ein paar Durchläufe mit vorsortierten Zahlen.

Also z.B. vergleichen:

10 Durchläufe random
t=schellste von(10 Durchläufe sortiert)

vs.

10 Durchläufe sortiert
t=schellste von(10 Durchläufe sortiert)

SeppJ

Hat mal jemand profile guided optimization beim GCC und/oder ICC ausprobiert? Das ist meiner Erfahrung nach sowieso eine der stärksten Compileroptimierungen und diese Form der Optimierung ist vermutlich auch das, was Java hier den kleinen Vorteil gegenüber dem ICC und Clang gibt.

SeppJ schrieb:

Hat mal jemand profile guided optimization beim GCC und/oder ICC ausprobiert? Das ist meiner Erfahrung nach sowieso eine der stärksten Compileroptimierungen und diese Form der Optimierung ist vermutlich auch das, was Java hier den kleinen Vorteil gegenüber dem ICC und Clang gibt.

Ich habs getestet aber vorher noch nie benutzt und vielleicht was falsch gemacht. Jedenfalls ist es dadurch nur noch langsamer als nur mit -O3 geworden.

Mechanics

sebi707 schrieb:

Hab ich mich auch schon gefragt. Soll wohl mit der Option " -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly " gehen. Allerdings fehlt mir dafür die hsdis-amd64.so Library. Wenn ich zuviel Langeweile habe versuche ich die mal zu besorgen oder selbst zu compilieren.

Müsste man das nicht schon mit perf sehen?

Atlan

@hustbaer
Ich tat, wie mir geheißen:

| rand() | sorted
--------------+-------
C++  |17301843|9165127
-----+--------+-------
Java |17963707|4136285

Im Zufallsversuch war Java tatsächlich etwas langsamer (und zwar ganze 661864 Mikrosekunden). Im Vorsortierten ist Java C++ allerdings davongelaufen.

Caligulaminus

Atlan schrieb:

(und zwar ganze 661864 Mikrosekunden)

Wieviele Elemente sortierst Du??

Atlan

Ich habe 100.000 Elemente sortiert.

tntnet

Also das hat mir doch keine Ruhe gelassen. Ich habe ein wenig weiter getestet. Und ich habe was raus bekommen.

Ein wesentlicher Unterschied ist, dass ein int in C++ auf einer 64-Bit-Plattform 64 Bit groß ist. In Java dagegen ist er immer 32 Bit. Verwende ich im C++-Programm short, also auch eine 32 Bit Ganzzahl, dann sieht die Sache schon anders aus. Die gcc-Variante liegt jetzt bei 5,2 Sekunden und mit clang Übersetzt ist das C++-Programm wie die Java-Variante bei 3,6 Sekunden. clang optimiert also genauso gut, wie Java. Der Optimierer von gcc arbeitet in dem Fall aber nicht so gut.

Ach ja - und ich habe da 2 Bugs im Programm gefunden, die sich aber gegenseitig aufheben.

Erst mal wird das Array gar nicht absteigend gefüllt sondern eben bereits aufsteigend sortiert. Es wird immer "array[i] = i" gesetzt. Da ist es egal, ob i von unten nach oben oder umgekehrt zählt.

Der Sortieralgorithmus sortiert allerdings nicht aufsteigend, sondern absteigend. Daher ist ein sortiertes Array wieder der Worst-case. Daher ist es für die Messung eigentlich egal.

Und ein interessantes Phänomen ist mir aufgefallen. Wenn ich in der Java-Methode sortList das observedElems als long deklariere, benötigt das Programm mehr als doppelt so lang. Plötzlich ist die Sortierdauer bei 9,5 Sekunden .

tntnet schrieb:

Ein wesentlicher Unterschied ist, dass ein int in C++ auf einer 64-Bit-Plattform 64 Bit groß ist.

Irgendwie nicht. Außer du benutzt irgendwas sehr merkwürdiges (https://en.wikipedia.org/wiki/64-bit_computing#64-bit_data_models).

hustbaer

tntnet schrieb:

Ein wesentlicher Unterschied ist, dass ein int in C++ auf einer 64-Bit-Plattform 64 Bit groß ist. In Java dagegen ist er immer 32 Bit.

???
Auf welchen 64 Bit Plattformen soll das so sein?
Verwechelst du gerade long und int ?

https://en.wikipedia.org/wiki/64-bit_computing#64-bit_data_models

Nene, int ist auf gängigen x86/amd64 Compilern immer 32 Bit. MSVC, GCC, Clang etc. sind sich da hübsch einig. "Strittig" ist bloss wie lange long zu sein hat.

tntnet schrieb:

Verwende ich im C++-Programm short, also auch eine 32 Bit Ganzzahl, dann sieht die Sache schon anders aus

OK, jetzt willst du uns verarschen.
KEIN mir bekannter Compiler macht short = 32 Bit. Entweder short = 16 Bit oder short = 64, aber niemals 32. (Ja, erlaubt wäre es, aber es macht halt keiner.)

EDIT: Argh, zu langsam /EDIT

EDIT2: Wenn du 32 Bit willst, dann schreib einfach int32_t . Dann muss keiner irgendwo nachgucken und wir wissen trotzdem alle dass es sicher genau 32 Bit sind.

Hab noch den an dieser Stelle obligatorischen Hinweis auf die Fixed width integer types vergessen.

hustbaer

Atlan schrieb:

@hustbaer
Ich tat, wie mir geheißen:
| rand() | sorted
--------------+-------
C++  |17301843|9165127
-----+--------+-------
Java |17963707|4136285
Im Zufallsversuch war Java tatsächlich etwas langsamer (und zwar ganze 661864 Mikrosekunden). Im Vorsortierten ist Java C++ allerdings davongelaufen.

Cool, danke fürs Ausprobieren.

D.h. der Optimizer von Java nutzt tatsächlich Statistiken über den Control-Flow durch eine Funktion um möglichst guten Code zu erzeugen.

Jetzt fehlt nur noch ein Test mit Profile-Guided-Optimization wo C++ dann auch im "sortiert" Test gleich schnell ist, dann können alle wieder beruhigt schlafen (oder auch nicht, hihi).

dot

tntnet schrieb:

Ein wesentlicher Unterschied ist, dass ein int in C++ auf einer 64-Bit-Plattform 64 Bit groß ist.

Nö, int ist auf allen gängigen 64-Bit PC Plattformen 32 Bit. Es liegt wohl ziemlich sicher wirklich daran, dass die Java VM während der Ausführung den massiven Hotspot in der Loop aufgrund der exakt verkehrten Sortierung entdeckt und adaptiv Code für genau diesen Spezialfall generiert, sodass alle späteren Aufrufe wesentlich schneller sind. Um diese Hypothese zu testen, müsste man wohl einfach mal nur die erste Ausführung der Sortierung timen und zum Schluss noch einmal ein zufällig sortiertes Array durchlassen und das auch extra timen. Die Vorhersage wäre, dass die erste(n) Aufrufe wesentlich länger dauern als der Rest und der finale Aufruf auf dem unsortierten Array auch wieder länger...oder einfach mal nicht nur Mittelwert, sondern auch Standardabweichung ausrechnen, so wie man das eigentlich sowieso immer tun sollte...oder einen Boxplot machen...

Offenbar hat der Threadersteller sich hier unabsichtlich wirklich eines dieser seltenen Beispiele konstruiert, wo ein JIT tatsächlich was von Signifikanz zustande bringt, das ihm erlaubt, AOT davonzulaufen. Praktische Relevanz hat das Beispiel natürlich absolut keine und im unsorted Fall sieht man, wie erwartet, keinen Unterschied zwischen den Sprachen; interessant ist es allemal.

PGO ist natürlich ein Weg, über den man den C++ Compiler dazu veranlassen kann, ebenfalls so zu optimieren wie der Java JIT es hier tut, dann hat man ein C++ Programm, das im sorted Fall gleich schnell sein wird wie Java und im unsorted Fall dann schlechter...

Atlan

tntnet hat in der Hinsicht recht, dass es schneller wird. Bei mir fällt die Zeit auf 7,3 Sekunden von 9,3, wenn ich short in C++ benutze.
Wenn ich in Java aber auf long ändere, ändert sich nichts.
Das mit der Sortierung habe ich bemerkt aber es hat mich nicht gestört, da, wie du gesagt hast, die Bugs sich gegenseitig aufgeben. Trotzdem danke fürs Draufansprechen.

@dot
Ich habe es einmal ausprobiert und wie du gesagt hast, die einzelnen Durchläufe der do-while-Schleife ohne den Rücksprung ("von Klammer zu Klammer") gemessen und dabei dies herausbekommen (alle Werte in Nanosekunden):

Es stimmt, dass die Ausführungszeit am Anfang rapide abnimmt und dann ungefähr gleich bleibt. Rechnet man den kleinsten Wert dort hoch, so sind es ca. 11,6 Sekunden, allerdings ist diese Rechnung wertlos, da die Zahl der überprüften Elemente mit jedem Durchlauf der do-While-Schleife verringert wird.
Die Standardabweichung beträgt 141.9973347754622 Nanosekunden.

dot

Atlan schrieb:

Es stimmt, dass die Ausführungszeit am Anfang rapide abnimmt und dann ungefähr gleich bleibt. Rechnet man den kleinsten Wert dort hoch, so sind es ca. 11,6 Sekunden, allerdings ist diese Rechnung wertlos, da die Zahl der überprüften Elemente mit jedem Durchlauf der do-While-Schleife verringert wird.

Wieso das denn? Wird das Array nicht nach jedem Mal neu initialisiert? Wie verhält das Ganze sich mit unsortierten Werten?

tntnet

sebi707 schrieb:

tntnet schrieb:

Ein wesentlicher Unterschied ist, dass ein int in C++ auf einer 64-Bit-Plattform 64 Bit groß ist.

Irgendwie nicht. Außer du benutzt irgendwas sehr merkwürdiges (https://en.wikipedia.org/wiki/64-bit_computing#64-bit_data_models).

Oh man. Man sollte so spät nicht mehr im Forum schreiben. Eigentlich hätte ich es wissen müssen. Ihr habt ja so recht. Int ist immer 32 Bit.

Atlan

@dot
Mit Durchlauf meinte ich hier ein mal "von Klammer zu Klammer" und nicht bis zum Verlassen des Blocks.
Unsortierte Werte versuche ich nachher nochmal.