Geschwindigkeitstest: Java, dann VB und dann C++

Atlan

Ich habe nun array als Zeiger durch array als normales Array ersetzt und die Laufzeit ist auf 9,5 Sekunden im Standalone Release gesunken.
Wenn ich vector benutze, wird die Laufzeit wieder auf 13 Sekunden angehoben.
Damit bin ich nun auf VB Niveau.

Ja ich bin C++ noch nicht gewohnt.

Was ich bisher meine verstanden zu haben: Finger weg von Zeigern, außer du willst optimieren oder sie lassen sich auf keinen Fall vermeiden. Wenn etwas dynamisch sein soll, benutz vector, weil das sich um alles kümmert.

SeppJ

Atlan schrieb:

Ich habe nun array als Zeiger durch array als normales Array ersetzt und die Laufzeit ist auf 9,5 Sekunden im Standalone Release gesunken.
Wenn ich vector benutze, wird die Laufzeit wieder auf 13 Sekunden angehoben.

Das ist so ziemlich der Beweis, dass du da irgendwelche Debugfeatures aktiviert hast.

Was ich bisher meine verstanden zu haben: Finger weg von Zeigern, außer du willst optimieren oder sie lassen sich auf keinen Fall vermeiden. Wenn etwas dynamisch sein soll, benutz vector, weil das sich um alles kümmert.

Vector ist ein verkappter Zeiger (beziehungsweise drei). Zeiger sind kein magisches Mittel, um Code schneller zu machen. Zeiger, wo keine Zeiger nötig sind, sind ein gutes Mittel, um Code langsamer zu machen. Das ist mitunter einer der Gründe, warum guter Javacode normalerweise nicht mit gutem C++ mithalten kann, eben weil man dort für jede Kleinigkeit Zeiger aufgebrummt bekommt.
Zeiger haben immer Kosten. Es gibt bloß ein paar Fälle, in denen diese Kosten kleiner sein können, als die Alternativkosten. Das ist aber keine Magie, sondern kleines Einmaleins der Programmierkunde, wie man Argumente an Funktionen übergeben kann. Meistens sind die Alternativkosten jedoch 0 und es wäre schädlich. Zeiger zu benutzen.

Du solltest nicht den Fehler machen, zu denken, Zeiger wären nur die Dinger mit den Sternchen. In C++ und Java werden dir die Dinger mit den Sternchen fast nie begegnen. Die Zeiger arbeiten in diesen Sprachen versteckt im Hintergrund. Wie gesagt, stecken hinter vector ein paar versteckte Zeiger. In Java steckt hinter jedem nicht-primitiven Objekt ein Zeiger.

Atlan

Ich kann noch mal nach diesen Debugfeatures suchen.

Das es einen Unterschied in der Laufzeit bei Zeigern gibt, wusste ich nicht.

Dann haben wir den Code nun auf 9,5 Sekunden runter bekommen.
Das sind aber immer noch 5 mehr, als Java gebraucht hat, nun ist das aber ungefähr VB Niveau. Das kann ich mir sogar vorstellen, da die beiden Sprachen sehr ähnlichen Maschinencode erstellen könnten, weil das Programm sehr einfach ist und deshalb die Vorzüge von C++ nicht zur Geltung kommen könnten.
Nur das Java so schnell ist, gibt mir noch Rätsel auf. Die Optimizer in Java scheinen sehr gut zu sein.

Dann kann ich noch einmal ein komplizierteres Programm in Java und in C++ schreiben und diesmal C++ ausnutzen, vielleicht sogar die API.

Vielen Dank für diese Erklärung.

dot

Atlan schrieb:

Nur das Java so schnell ist, gibt mir noch Rätsel auf. Die Optimizer in Java scheinen sehr gut zu sein.

Ist kein großes Rätsel, du hast halt ein sehr merkwürdiges Beispiel gewählt, C++ Code geschrieben als wäre es Java mit ein paar Segfaults drübergestreut, davon vermutlich noch einen Debug Build gebenchmarked (wenn der Optimizer richtig an wäre, würde ich mit deinem Code eine Zeit von praktisch 0 erwarten) und vermutlich bei der Zeitmessung ein paar Dinge nicht bedacht. Rein prinzipiell kannst du mal davon ausgehen, dass, wenn du einen Benchmark hast, in dem Java signifikant schneller ist als C++, was mit dem Benchmark nicht stimmen kann...

Wieso summierst du kleine Deltas auf, anstatt die Zeit über alle Durchläufe zu messen? Wie hoch ist die Resolution des in Java verwendeten Timers? Wieso in jedem Durchlauf die ganze Initialisierung wiederholen und I/O betreiben? Wie kompilierst du den C++ Code (Compiler, Flags)?

Wenn du alles richtig machst, sollte hier bestenfalls wohl kein signifikanter Unterschied zwischen den Sprachen rauskommen...

tntnet

Ihr redet doch alle nur um den heissen Brei rum. Er hat alle seine Testprogramme inzwischen hier veröffentlicht. Da braucht man nicht mehr zu vermuten, dass er möglicherweise dieses oder jenes gemacht hat.

Seine Frage ist berechtigt. Sein C++ Code ist tatsächlich nicht wirklich gut. Das wissen wir und das weiss auch er.

Ich habe seine Programme mal ausprobiert und konnte das nachvollziehen. Die Programme testen genau diesen Algorithmus und wenn das aussen rum nicht gut ist, ist der Benchmark dennoch valide.

Ich kann den auch nachvollziehen und komme zum gleichen Ergebnis. Ich arbeite unter Fedora und habe das C++-Programm (mit kleinen Änderungen) mit -O3 übersetzt. Das Java-Programm ist tatsächlich mehr als doppelt so schnell.

Und jetzt könnten wir doch mal zum Thema kommen. Warum ist das so?

Java war früher langsam. Der Optimierer von Java ist wirklich sehr gut. Offensichtlich kann er diesen Algorithmus besser optimieren, als gcc. Java optimiert zur Laufzeit und hat daher mehr Informationen zur Verfügung, als der Optimierer von C++. Er verwendet zum Optimieren sowohl die aktuell verwendete CPU als auch das Laufzeitverhalten des Programms. Daher vermute ich, dass ihm diese Informationen verhelfen, diesen Algorithmus wirklich schneller zu machen, als das der gcc schafft.

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

camper

Hier wird also die Sortiergeschwindigkeit auf einem sortierten Array gemessen. Wen interessiert die? (Mal abgesehen davon, dass damit nat. wesentlich Teile des Algorithmus nie ausgeführt und also auch nicht gemessen werden)

camper schrieb:

Hier wird also die Sortiergeschwindigkeit auf einem sortierten Array gemessen. Wen interessiert die? (Mal abgesehen davon, dass damit nat. wesentlich Teile des Algorithmus nie ausgeführt und also auch nicht gemessen werden)

Das Array ist zwar Anfangs sortiert, allerdings genau falsch herum. Der Algorithmus wird also tatsächlich ausgeführt.

scrontch

camper schrieb:

Hier wird also die Sortiergeschwindigkeit auf einem sortierten Array gemessen. Wen interessiert die?

Uns interessiert die weil sie auf Java kleiner ist!! Das allein macht sie schonmal interessant.

@tntnet: +1 für ersten konstruktiven Beitrag.

Mein Gott Leute, der Threadersteller hat sich an die Regeln gehalten, hat sich neutral verhalten, hat sich sehr kooperativ gezeigt.
Warum muss er seit über 4 Seiten gegen Fanboys kämpfen?

Selbst wenn Java *nur* bei der Sortiergeschwindigkeit auf einem (invers) sortierten Array schneller als C++ ist wär das für mich schonmal interessant und erstaunlich. Also warum gehen wir der Sache nicht auf den Grund?

Oder glaubt ihr da waren VW-Techniker am Werk und javac erkennt Bubble-Sort als Testfall?

asc

Atlan schrieb:

@Nathan
Ich wollte ja gerade keine Wrapper oder API benutzen, weil ich die Sprache und nicht die API oder die Programmierer der API testen wollte.

Hast du den Test etwa in Java mit händischen Mitteln gemacht? Vielleicht solltest du mal für alle 3 Fälle den Code liefern. Davon abgesehen das die Bibliotheken häufig weit besser optimiert sind als ein Standardbenutzer es tut.

Artchi

Ich arbeite seit 15 Jahre mit Java, und wir haben auch rechtgroße Desktop-Anwendungen.
Die gesamte Java-Welt hat sich geändert, ja weiterentwickelt. In manchen Dingen ist java richtig flott geworden, in machen immer noch elend langsam. Das ist die Realität. Wenn dieser eine Test C++ schlägt, kann man damit leben. Aber es gibt noch so viele andere Java-Szenarien, die ich hier habe, wo ich denke "Mein Gott, wird das heute noch was?".

Der JVM-Hotspot hat zur Laufzeit Informationen, die er on-the-fly für sich nutzen kann um noch was zu optimieren. Das hat man mit statischen C++ Code nicht.

Aber die C++-Welt hat natürlich auch nicht geschlafen. Es gibt von heutigen C++ Compilern die Profilgesteuerte Optimierungen (PGO). Ich selber habe damit noch keine praktische Erfahrung. Aber im Prinzip ist es das, was der JVM-Hotsport macht: Lautzeitinformationen gewinnen um den Code zu optimieren.

Atlan

@dot
Mittlerweile entspricht mein Code mehr C++ Code, als portiertem Java Code.
Gebenchmarkt habe ich im Release Build als Standalone.
Warum summiere ich kleine Deltas auf: Ich wollte einzig und allein den Algorithmus benchmarken und keine Methodenaufrufe oder for-Schleifen, die nicht zum BubbleSort gehören.
Warum die ganze Initialisierung betreiben: Würde ich das nicht tun, hätte ich beim zweiten Mal ein fertig sortiertes Array und der Test wäre Schrott.
I/O betreibe ich nur außerhalb des Sortierens und das war auch mehr für Debuggingzwecke, damit ich testen kann, dass wirklich etwas getan wird. Da I/O nur außerhalb des Durchlaufs ist, habe ich es drin gelassen.
Input wird auch nur ein mal betrieben.
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).

@tntnet
Danke, für diesen konstruktiven Beitrag.:)
Also meinst du, dass die Java Optimizer tatsächlich für ungefähr die doppelte Geschwindigkeit reichen?

@Gast3
Ich habe C++ mit dem Buch "C++ lernen und professionell anwenden" gelernt, komme aber von Java, weshalb viele Algorithmen nicht neu sind (nur die Syntax und die Mittel).
Java habe ich aus der Schule und dem Internet.

@sebi707
Danke.

@scrontch
Vielen Dank.

@asc
Ja. Der Code in Java ist mit händischen Mitteln ohne API, auch wenn man in Java an der API nicht so ganz vorbei kommt, da sogar Arrays von Object erben.
Der Code steht auf Seite 1 und 2. Der Javacode wurde bisher nicht verändert.
Das mit der Optimierung kann ich mir sehr gut vorstellen.

Marthog

scrontch schrieb:

Oder glaubt ihr da waren VW-Techniker am Werk und javac erkennt Bubble-Sort als Testfall?

So aehnlich. Dieser und viele Benchmarks verwenden integer oder character zum testen und die sind bei java nunmal primitives und damit mehr C als idiomatisches Java. Von manchen fans wird dann gerne abgeleitet, dass der garbage collector geschwindigkeitsmaessig ja ueberhaupt nichts ausmache, aber wenn man dann richtige Objekte einsetzt, sieht das dann ganz anders aus.

Ich hatte langeweile und in der Uni das ganze mal mit verschiedenen Compilern auf verschiedenen CPUs ausgeführt (auf beiden Systemen läuft RHEL 6):

Intel i7-3770:
Java: 2,8s
GCC 4.9.2: 6,4s
Clang 3.6.2: 3,7s
ICC 15.0.0: 3,2s

Intel Xeon E5-2620 v2:
Java: 10,2s
GCC 4.9.2: 9,6s
Clang 3.6.2: 5,6s
ICC 15.0.0: 7,1s

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.

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.