Geschwindigkeitstest: Java, dann VB und dann C++

volkard

sebi707 schrieb:

volkard schrieb:

Entsprechend @sebi707, haste -march=native an?

Jop.

Hab's befürchtet. Meiner Erfahrung nach tut sich kaum da kaum was: Sobald man x64 hat, bringt's sauwenig, noch auf den eigenen Prozessor zu optimieren. Also liegts nicht an dieser Erlaubnis des Jitters.

Atlan

@sebi707
Mein Wissen über Assembler ist leider zu beschränkt, als das ich da reingucken könnte und etwas verstehen würde.

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

@volkard
Ich habe /favour:INTEL64 hinzugefügt, jedoch gab es keinen messbaren Unterschied vorher und nachher.

tntnet

Gast3 schrieb:

kannst du mal "deine" C++, Java Quellen hier einstellen?

Das sind fast genau die, die hier schon standen. Java habe ich gar nicht angefasst und hier mein C++-code:

#include <iostream>
#include <ctime>
#include <vector>
using namespace std;

class Main
{
public:
    Main(int, int);
private:
    void initArray(int elems);
    long sortList(int);
    std::vector<int> array;
};

Main::Main(int times, int elems)
{
    std::vector<long> timesEach(times);
    long calcAid = 0;
    cout << "Total times speedtest will run: " << times << endl;
    for (int i = 0; i < times; i++) {
        cout << "Time " << i << " out of " << times << endl;
        cout << "Initializing List" << endl;
        initArray(elems);
        cout << "Finished initializing. List has " << elems << " elements" << endl;
        cout << "Starting sorting" << endl;
        timesEach[i] = sortList(elems);
        cout << "Time: " << timesEach[i] << endl;
    }

    for (int i = 0; i < times; i++) {
        long ms = timesEach[i];
        calcAid += ms;
    }

    //double result = (double)((double)calcAid / (double)times) / CLOCKS_PER_SEC;
    double result = (double)((double)calcAid / (double)times);

    cout << "Average time taken for sorting process in Microseconds: " << result << endl;
}

long Main::sortList(int elems) {
    int observedElems = elems; //noch zu behandelnde Objekte
    bool swapped;   //wurde schon gewechselt? Muss nicht initialisiert werden, da in do-while Schleife erledigt
    int aid;    //Hilfsvariable zum Tauschen der Werte

    time_t StartingTime, EndingTime, ElapsedMicroseconds; //Zeit
    StartingTime=clock();                                 //      starten

    do {//do-while-Schleife: Wird mindestens ein mal ausgeführt, aber nur so oft wiederholt, wie die Bedingung stimmt
        swapped = false;    //wahrheitsgemäß. Es wurde noch nicht getauscht
        for (int i = 1; i < observedElems; i++) {   //for-Schleife durchäuft Array von 1 bis observedElems - 1
            if (array[i - 1] < array[i]) {  //wenn der Wert an der Stelle i - 1 größer ist, als an Stelle i
                aid = array[i - 1]; //der Wert von array an Ort i - 1 wird in aid geschrieben
                array[i - 1] = array[i]; //der Wert an Stelle i wird an Stelle i - 1 geschrieben
                array[i] = aid; //der Wert von aid wird an Stelle i geschrieben
                swapped = true; //wahrheitsgemäß. Es wurde getauscht
            }
        }
        observedElems--;    //das gerade eingefügte Element muss nicht mehr überprüft werden; observedElems um einen decrementieren
    } while (swapped);//Bediungung der do-while-Schleife

    EndingTime=clock();                                       //Zeitmessung
    ElapsedMicroseconds = (EndingTime-StartingTime)/(double(CLOCKS_PER_SEC)/1000);
    return (long) ElapsedMicroseconds;                                     //verarbeiten
}

void Main::initArray(int elems) {
    array.resize(elems);

    for (int i = elems - 1; i >= 0; i--) {
        this->array[i] = i;
    }
}

int main(int count, char** args) {
    Main main(5,100000);
}

Also ich konnte die Finger nicht von den Pointern lassen . Ansonsten ist es wirklich nicht mein Stil. Wenn man den Code mit dem Java-Code vergleicht, kann man erkennen, dass die gemessene Schleifen exakt gleich sind. Was drum herum ist, interessiert eigentlich nicht. Ich habe noch ein wenig weiter geforscht. Ich habe jetzt noch den clang hinzugefügt. Das Ergebnis ist:

gcc: 8,1s
java: 3,6s
clang: 4.0s!!!

In diesem Fall scheint also der gcc speziell weniger gut zu optimieren. Der erwähte switch -march=native bewirkt gar nichts. Gcc ist übrigens Version 5.1.1, clang Version 3.7.0 und das Java meldet sich als openjdk version 1.8.0_65. Alles auf Fedora 23 auf einem inzwischen recht alten Intel i5 mit 2,67 GHz.

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.