Geschwindigkeitstest: Java, dann VB und dann C++

Atlan: Mit welchen Arraygrößen testest du überhaupt? Bedenke außerdem, dass du mit einem invers sortierten Array einen extremen Sonderfall testest, weil der Test, ob zwei Elemente getauscht werden sollen, immer anschlägt. Sowas kann der Java-Optimierer (in meiner Vorstellung) zur Laufzeit erkennen und den Code entsprechend umsortieren, sodass der tatsächlich ausgeführte Codepfad linear im Speicher liegt.

volkard

Atlan schrieb:

Wie kompiliere ich: Visual Studio 2015
General: x64, Windows 10 als Zielplattform, Version der Zielplattform: 10.0.10240.0, Plattform Toolset ist v140, es wird in eine Applikation (.exe) kompiliert, Multi-Byte Character Set, No Common Language Runtime Setup

C/C++: Maximize Speed (/O2), Inline Function Expansion steht auf "Any Suitable (/Ob2), Enable Instrinct Functions: Yes (/Oi), Favor fast Code (/Ot), Omit Frame Pointers: Yes(/Oy), Enable Fiber-Safe Optimizations: Yes(/GT), Whole Program Optimization: Yes (/GL).

Das sieht für mich prächtig aus.

Unter Linux verwende ich immer -march=native
Kannste mal schauen, ob
/favor:INTEL64
noch was bringt?

Entsprechend @sebi707, haste -march=native an?

volkard schrieb:

Entsprechend @sebi707, haste -march=native an?

Jop.

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.