Geschwindigkeitstest: Java, dann VB und dann C++

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.

kurze_frage

wie wäre es mit etwas mehr Praxis relevanten vergleichen,
die Ints einfach mal in Klassen stecken und dann damit arbeiten.
weil ints sind in Java keine Klassen und daher in der Regel auch nicht das was die Performance eines Programms ausmacht und der Unterschied in diversen Sprachen sollte beim Int sortieren Null oder fast Null sein.

die Ints einfach mal in Klassen stecken und dann damit arbeiten.

und was soll dann das für die Analyse des Laufzeitunterschieds zwischen C++ und Java bringen?

hustbaer

Gast3 schrieb:

die Ints einfach mal in Klassen stecken und dann damit arbeiten.

und was soll dann das für die Analyse des Laufzeitunterschieds zwischen C++ und Java bringen?

Java wird haushoch verlieren? Weil es keine Value-Types kann?

kurze_frage

hustbaer schrieb:

Gast3 schrieb:

die Ints einfach mal in Klassen stecken und dann damit arbeiten.

und was soll dann das für die Analyse des Laufzeitunterschieds zwischen C++ und Java bringen?

Java wird haushoch verlieren? Weil es keine Value-Types kann?

ob es so wäre oder nicht könnte durch einen Praxis relevanten Test der nicht nur Ints vergleicht sondern sich an der Realität orientiert und mit Objekten arbeitet festgestellt werden.

Das Durchlaufen der Schleife in entgegengesetzter Richtung läuft bei mir deutlich schneller (8.5s zu 5.3s)

do 
	{
		swapped = false;    //wahrheitsgemäß. Es wurde noch nicht getauscht
		for (int i = observedElems-1; i > 0; --i) 
		{  
			if (array[i-1] < array[i])
			{ 
				aid = array[i - 1];
				array[i - 1] = array[i]; 
				array[i] = aid; 
				swapped = true;
			}
		}
		--observedElems;
	} while (swapped);//Bediungung der do-while-Schleife

Vielleicht ist es ja das, was der JIT macht.

asdfasdf schrieb:

Das Durchlaufen der Schleife in entgegengesetzter Richtung läuft bei mir deutlich schneller (8.5s zu 5.3s)
do 
	{
		swapped = false;    //wahrheitsgemäß. Es wurde noch nicht getauscht
		for (int i = observedElems-1; i > 0; --i) 
		{  
			if (array[i-1] < array[i])
			{ 
				aid = array[i - 1];
				array[i - 1] = array[i]; 
				array[i] = aid; 
				swapped = true;
			}
		}
		--observedElems;
	} while (swapped);//Bediungung der do-while-Schleife
Vielleicht ist es ja das, was der JIT macht.

Hast du mal probiert, ob das überhaupt noch sortiert?

javadoof schrieb:

Hast du mal probiert, ob das überhaupt noch sortiert?

Ja und Ja

asdfasdf schrieb:

javadoof schrieb:

Hast du mal probiert, ob das überhaupt noch sortiert?

Ja und Ja

Lustig, bei mir wird die Eingabe 0,1,2 (verkehrt vorsortiert) zu 2,0,1 "sortiert".

Stimmt, war quatsch. Sorry for the inconvenience. Hätte nicht nur einen Lauf kontrollieren sollen