Matrixmultiplikation in Java so schnell wie in C und C++?



  • Ich habe gerade eine Hochschul-Hausarbeit gelesen, was stimmt damit nicht?
    http://www.hochschule-bochum.de/fileadmin/media/campus_VH/AGMathematikAngInformatik/HausarbeitMatrizenmultiplikationNoth.pdf

    Das Ergbnis 5000x5000 Matrix ohne Threads
    C 119,12
    C++ 118,98
    Java 125,84

    und mit 4 Threads
    C 32,49
    C++ 34,86
    Java 32,35



  • Hier sind mal drei Codeteile für die Version ohne Threads.

    int main(int argc, const char* argv[]){
        int dim = atoi(argv[1]), i, j, k;
        clock_t prganfang, prgende;
        double temp, laufzeit;
    
        double *A = (double*)calloc(dim*dim, sizeof(double));
        double *B = (double*)calloc(dim*dim, sizeof(double));
        double *BTransp = (double*)calloc(dim*dim, sizeof(double));
        double *C = (double*)calloc(dim*dim, sizeof(double));
    
        prganfang = clock();
    
        for(i = 0; i < dim; i++)
            for(j = 0; j < dim; j++)
                BTransp[i*dim+j]=B[j*dim+i];
    
        for (i = 0; i < dim; i++)
            for (j = 0; j < dim; j++){
                temp = 0;
                for (k = 0; k < dim; k++)
                      temp += A[i*dim+k]*BTransp[j*dim+k];
                C[i*dim+j] = temp;
            }
    
        prgende = clock();
    
        laufzeit = (prgende – prganfang)/(double)CLOCKS_PER_SEC;
        printf("%.2f Sekunden\n", laufzeit);
    
        free(A);
        free(B);
        free(BTransp);
        free(C);
    
    return 0;
    }
    
    int main(int argc, const char* argv[]) {
        int dim = atoi(argv[1]);
        clock_t prganfang, prgende;
        double temp, laufzeit;
    
        vector <double> A (dim*dim);
        vector <double> B (dim*dim);
        vector <double> BTransp (dim*dim);
        vector <double> C (dim*dim);
    
        prganfang = clock();
    
        for(int i = 0; i < dim; i++)
            for(int j = 0; j < dim; j++)
                BTransp[i*dim+j]=B[j*dim+i];
    
        for (int i = 0; i < dim; i++)
            for (int j = 0; j < dim; j++){
                temp = 0;
                for (int k = 0; k < dim; k++)
                    temp += A[i*dim+k]*BTransp[j*dim+k];
                C[i*dim+j] = temp;
            }
    
        prgende = clock();
    
        laufzeit = (prgende – prganfang)/CLOCKS_PER_SEC;
        cout << laufzeit << " Sekunden" << endl;
        return 0;
    }
    
    public static void main(String args[]){
        int dim = Integer.parseInt(args[0]);
    
        double A[] = new double[dim*dim];
        double B[] = new double[dim*dim];
        double BTransp[] = new double[dim*dim];
        double C[] = new double[dim*dim];
        double temp;
        double prganfang;
        double prgende;
        double laufzeit;
    
        prganfang = System.currentTimeMillis(); 
    
        for(int i=0;i<dim;i++)
            for(int j=0;j<dim;j++)
                BTransp[i*dim+j]=B[j*dim+i];
    
        for (int i=0;i<dim;i++)
            for (int j=0;j<dim;j++){
                temp = 0;
                for (int k=0;k<dim;k++)
                    temp += A[i*dim+k]*BTransp[j*dim+k];
                C[i*dim+j] = temp;
            }
    
        prgende = System.currentTimeMillis();
    
        laufzeit = (prgende-prganfang)/1000; 
        System.out.printf("%.2f Sekunden\n", laufzeit);
    }
    


  • Kann gut sein. Aber wie siehts aus mit Compiler-Flags?



  • hab in etwa dieselbe CPU (100MHz weniger), mal mit VS2013 getestet:

    //doubles
    67.63 Sekunden
    66.00 Sekunden
    
    //float
    34.85 Sekunden
    34.00 Sekunden
    

    ist relativ cache unfreundlich, 5k*5k*8 -> ~190MB und die geht er 5000mal durch -> 931GB, bei mir also 14GB/s (theoretisch 25.6GB/s oder so, praktisch schafft man 20GB/s), sein memory macht vielleicht 7GB/s (notebook?).



  • Wie kommst Du darauf, dass da etwas falsch sein sollte? Die Java-JVM optimiert sehr gut. Java ist in vielen Fällen sehr schnell. In einigen sogar schneller, als C++-Code. Der Java-JIT-Compiler kann zur Laufzeit für den aktuell verwendeten Prozessor optimieren und nimmt sogar das Laufzeitverhalten des Programms hinzu. Das erste lässt sich bei C++ über Compilerflags steuern. Das 2. ist mit einem nomalen C++-Compiler fast nicht machbar. Es gibt feedback-Optimierung bei einigen Compilern. Der Einsatz ist aber sehr aufwändig.

    Ich halte dennoch C++ für die bessere Wahl für performancekritische Anwendungen. Also eigentlich halte ich C++ praktisch immer für die bessere Wahl.

    Ein so einfacher Benchmark sagt wenig über die Realität aus.

    C++ bietet von der Sprache her viele Möglichkeiten, die in Java nur sehr schwer zu realisieren sind. Vieles muss man in Java umständlicher lösen als in C++.



  • Im gezeigten Code wird nichts mehr berechnet, sondern nur noch auf den RAM gewartet. Dann stört es nicht so arg, dass in Java zusätzlich Prozessorzeit verbraten wird.

    Das ändert sich natürlich, wenn der Code weiter auf Caching optimiert wird, das geht in Java nicht, aber in C/C++ schon: http://lwn.net/Articles/255364/



  • Und was von den vielen C++ Möglichkeiten ist in dem alltäglichen Programmiereralltag wirklich praxisrelevant? In C++ kannst auch ganz schnell viel Mist schreiben, wenn du nicht wirklich jahrelange Erfahrung hast.

    Ist halt immer eine Kosten-/Nutzenfrage. Lohnt es sich wirklich, in das Lernen von C++ so viel Zeit zu invenstieren, für die paar Anwendungsfälle in denen ich wirklich C++ anstellen von Java brauche? Als Firma würde ich mir sogar überlegen, ob ich nicht viel schneller Programmierer für Java finde als für C++ und ob nicht die Gefahr viel kleiner ist, in Java ist unsicheren Code zu schreiben und so weiter und so fort.

    Ich programmiere in beiden Sprachen und in Java bin ich locker dreimal so schnell mit meinen Sachen fertig. Mit einer guten Java-IDE wie IntelliJ an der Hand, wo sehr viel Code automatisch generiert werden kann, ist das Programmieren eine wahre Freude.

    Wenn ich wirklich das letzte bisschen Optimierung brauche, ist C++ sicher der beste Weg, aber was ich mit Java machen kann, mache ich auch in Java. Das geht einfach viel schneller und entspannter.



  • Hier geht es ja nur um eine Berechnung von grossen Arrays und die kann java mindestens so gut optimieren wie jeder C++-Compiler.
    Das was Java langsam macht sind Garbage-Collector, obligatorische Heapallocations (und damit viele indirektionen), default ueberschreibbare Funktionen und so den schwer wegzuoptimierenden overhead haben und starker einsatz von type erasure a.A. bei den generics und das alles tritt hier nicht auf.

    CppOkAber schrieb:

    Ich programmiere in beiden Sprachen und in Java bin ich locker dreimal so schnell mit meinen Sachen fertig. Mit einer guten Java-IDE wie IntelliJ an der Hand, wo sehr viel Code automatisch generiert werden kann, ist das Programmieren eine wahre Freude.

    Bei mir ist es anders herum, wobei ich in Java noch anfaenger bin und deswegen nicht alle Details kenne. In C++ kann ich beim schreiben neuer Algorithmen auf so grundlegende Dinge wie std::find_if und std::partition zurueckgreifen und dadurch den Algorithmus sehr gut strukturieren, ohne beim schreiben die rohen schleifen zu haben und kann dabei gleich out-of-bound errors vermeiden, waehrend mir in Java andauernd die Exceptions um die Ohren flogen.



  • Ja ok, ich komme halt einfach nicht so gut in C++ rein wie ich es in Java gekommen bin. Java konnte ich nach einem Monat lernen schon recht gut. C++ habe ich immer wieder nach ein paar Wochen aufgegeben und dann irgendwann weiter gemacht. Bei mir ist das auch so, dass mich mehr die Algorithmen interessieren als die Sprache an sich oder ob das nun optimal schnell auf meiner CPU läuft. Ich komme einfach bei Java gut vorran und bei C++ hänge ich immer wieder an Sachen die mich dann doch zu den Grundlagen zurückführen und das Arbeiten mit Libs auf unterschiedlichen Plattformen hat mich auch schon in den Wahnsinn getrieben. Die harte Arbeit mit C++ wird sicherlich auch belohnt, aber ich bin es irgendwie schon wieder leit ständig irgenwo was über die Sprache lesen zum müssen und wenn ich Code posten dann gibt es sich Sachen die ich wieder falsch gemacht haben und die mir hinterher um die Ohren fliegen können.

    Da geht mir der Spaß am Programmieren verloren. Ich weiß, dass der GC nicht berechenbar ist und so weiter, aber solange er mir nicht im Weg steht und dabei mache ich auch Echtzeit-Grafikram , solange habe ich keine Sorgen damit. JA und RAII ist auch ganz wunderbar, aber ehrlich? Ich habe es nie in Java vermisst. Auch mit wenig Ressourcen wie unter Android hat mich Java nicht wirklich ausgebremst, gut da habe ich noch nicht so viel gemacht. Aber langsam ist anderes in meinen Augen.

    Was sind denn das für Programme wo ein ständig der GC stört und man ohne RAII nicht auskommt?



  • CppOkAber schrieb:

    Und was von den vielen C++ Möglichkeiten ist in dem alltäglichen Programmiereralltag wirklich praxisrelevant? In C++ kannst auch ganz schnell viel Mist schreiben, wenn du nicht wirklich jahrelange Erfahrung hast. ...flame flame...

    Ich glaube es ist besser nicht darauf einzugehen. Ich möchte keinen Flamewar los brechen. Solche findet man im Internet mehr als genug.

    Ich bevorzuge C++. Dennoch habe ich Java sogar verteidigt. Und dabei sollten wir das belassen. Ich denke alles andere bringt niemanden etwas.



  • cachy schrieb:

    Das ändert sich natürlich, wenn der Code weiter auf Caching optimiert wird, das geht in Java nicht, aber in C/C++ schon: http://lwn.net/Articles/255364/

    Aeusserst interessanter Artikel.

    Allerdings sieht es fuer mich so aus, als ob die meisten der dort genannten Optimierungen unabhaengig von der Programmiersprache sind und somit selbstverstaendlich auch in Javaprogrammen angewandt werden koennen. Ich meine, letztendlich laeuft dort vieles darauf hinaus, dass man moeglichst lokal im Speicher arbeiten sollte und moeglichst wenig Speicher benoetigen sollte. Darueber hat man praktisch in jeder Programmiersprache eine ganz erhebliche Kontrolle.



  • Matrix-Multiplikation geht übrigens mit weniger als O(n^3) Multiplikationen, Stichwort Strassen-Algorithmus.



  • Der ist aber nur für sehr große Matrizen schneller und numerisch weniger stabil, also in der Praxis kaum relevant.


Anmelden zum Antworten