Java vs. C++



  • Ablaufsteuerungen? Was soll den der Käse?

    Im Gegensatz zu C kennt C++ so einige Sprachelemente, die sich zur Kompilierzeit auflösen lassen und womit enorm viel Laufzeit gespart werden kann. Templates, constexpr... machts möglich.

    So ist der C++ STL Quicksort sehr viel schneller als der der C Standard Bibliothek. Beides generische Varianten. Der Unterschied ist, dass der C++ Kompiler den Vergleich zweier Elemente einfach inlinen kann und sich pro Vergleich einen Funktionsaufruf spart.

    http://www.geeksforgeeks.org/c-qsort-vs-c-sort/

    STL’s sort ran faster than C’s qsort, because C++’s templates generate optimized code for a particular data type and a particular comparison function.

    STL’s sort runs 20% to 50% faster than the hand-coded quicksort and 250% to 1000% faster than the C qsort library function.

    Ein anderes Beispiel ist das Durchsuchen von Lookup Tabellen oder Berechnungen die zur Kompilierzeit ausgeführt werden können, wenn die Eingangsdaten zur Kompilierzeit bekannt sind.

    constexpr int factorial(int n)
    {
        return n <= 1? 1 : (n * factorial(n - 1));
    }
    

    Das hier rechnet dir der Kompiler zur Kompilierzeit aus, wenn n bekannt ist. Oder eben zur Laufzeit, wenn nicht. Kein extra code.

    Und das hier ist nur die Spitze des Eisbergs. C++ ist wesentlich mächtiger als C und trotzdem genauso performant.



  • QSort schrieb:

    http://www.geeksforgeeks.org/c-qsort-vs-c-sort/

    STL’s sort ran faster than C’s qsort, because C++’s templates generate optimized code for a particular data type and a particular comparison function.

    STL’s sort runs 20% to 50% faster than the hand-coded quicksort and 250% to 1000% faster than the C qsort library function.

    Irgendwelche ein Idiot in Internet postet Sache die mir gefallen.

    Theoretisch gibst es kein Unterschied zu Optimierung von einfachen C-Funktionen oder C++ Template Funktion.

    Praktisch liegt es an dem Implementierung(Compiler) und/oder am der Person, die die Implementierung benutzt.

    Code aus URL (angepasst):
    - include eingefügt
    - N 100000

    Visual Studio 2015
    Einstellung Standard

    C:\Users\zeus\Desktop\Project1\Debug>Project1.exe
    Time taken by C qsort() - 0.052
    Time taken by C++ sort() - 0.175
    
    C:\Users\zeus\Desktop\Project1\Release>Project1.exe
    Time taken by C qsort() - 0.015
    Time taken by C++ sort() - 0.006
    

    Ops C war einmal schneller 😮 🤡



  • Naja, im Debug-Mode zu vergleichen ist ja auch völliger Käse - ist als ob du 2 Autos vergleichst, welche mit angezogener Handbremse fahren 😉



  • also ich hab mir das jetzt eben mal kurz angesehen. wenn ich das richtig verstanden habe, werden da zwei verschiedene sortierverfahren (namentlich quicksort und introsort) gegenüber gestellt. 🙄

    außerdem hab ich mir hier mal sagen lassen, dass es nicht gut ist, wenn ich c-funktionen durch den c++-compiler schicke.



  • Zeus schrieb:

    Irgendwelche ein Idiot in Internet postet Sache die mir gefallen.

    Theoretisch gibst es kein Unterschied zu Optimierung von einfachen C-Funktionen oder C++ Template Funktion.

    Für generischen Code eben schon.

    Zeus schrieb:

    C:\Users\zeus\Desktop\Project1\Debug>Project1.exe
    Time taken by C qsort() - 0.052
    Time taken by C++ sort() - 0.175
    
    C:\Users\zeus\Desktop\Project1\Release>Project1.exe
    Time taken by C qsort() - 0.015
    Time taken by C++ sort() - 0.006
    

    Ops C war einmal schneller 😮 🤡

    Dazu wurde ja alles gesagt.

    HansKlaus schrieb:

    also ich hab mir das jetzt eben mal kurz angesehen. wenn ich das richtig verstanden habe, werden da zwei verschiedene sortierverfahren (namentlich quicksort und introsort) gegenüber gestellt. 🙄

    Nunja introsort ist quicksort, aber da hast du recht. Trotzdem kann die C++ den Vergleich inlinen, C nicht.

    Das Einzige was C++ nicht kann aber C, sind restricted pointer. Hab ich aber noch nirgendwo gesehen. C++ hat dafür aber move semantics, (const) references und was mir gerade noch so nicht einfällt. Damit kann man sicher auch Laufzeit sparen.



  • C:\Users\zeus\Desktop\Project2\Win64\Release>Project1.exe
    Time taken by C++ sort() - 0.016
    Time taken by C qsort() - 0.031
    
    C:\Users\zeus\Desktop\Project2\Win64\Release>Project1.exe
    Time taken by C qsort() - 0.016
    

    Ohne weitere Worte



  • Echt toll, dass du die Zeit der C++ Version weglässt. Absicht?

    Du weißt schon, dass bei jedem Programmdurchlauf andere Werte vorliegen und du deshalb Äpfel mit Birnen vergleichst?

    $ g++ qsort.cpp -O2 -o qsort
    $ ./qsort 
    Time taken by C qsort() - 0.167546
    Time taken by C++ sort() - 0.063008
    


  • Ich vergleiche nix, genau du vergleichst Äpfel mit Birnen 😃

    Propo sind die Test die ich hier poste nur ein Teil was ich wirklichh poste... es ist nur idotisch von solche Microbrench überhaupt eine Aussage zu treffen.

    Oder erkläre mir wieso die C Version auf einmal doppelt/dreimal so schnell wird, wenn man die C++ Version weglässt.

    Unter der Prämisse das die Programme unter N mal beobachtet wurden.



  • Zeus schrieb:

    Ich vergleiche nix, genau du vergleichst Äpfel mit Birnen 😃

    Tipp: Wenn du ernst genommen werden willst, lasse andere nicht rätselraten.

    Propo sind die Test die ich hier poste nur ein Teil was ich wirklichh poste... es ist nur idotisch von solche Microbrench überhaupt eine Aussage zu treffen.

    Oder erkläre mir wieso die C Version auf einmal doppelt/dreimal so schnell wird, wenn man die C++ Version weglässt.

    Unter der Prämisse das die Programme unter N mal beobachtet wurden.

    Sicher dass du den richtigen Code gelöscht hast? Das Verhalten kann ich nicht nachvollziehen, bei mir bleiben die Laufzeiten stabil und die C Version langsamer (Visual Studio 2015 Release und ebenso mit GCC). Auch seltsam, bei dir dass die C Version auch noch exakt so lang braucht wie C++.

    C:\Users\X\Documents\Visual Studio 2015\Projects\QSort\Release>QSort.exe
    Time taken by C qsort() - 0.193
    Time taken by C++ sort() - 0.096
    
    C:\Users\X\Documents\Visual Studio 2015\Projects\QSort\Release>QSort.exe
    Time taken by C qsort() - 0.195
    
    C:\Users\X\Documents\Visual Studio 2015\Projects\QSort\Release>QSort
    Time taken by C++ sort() - 0.094
    

    C Version

    // C++ program to demonstrate performance of
    // C qsort and C++ sort() algorithm
    #include <algorithm>
    #include <cstdlib>
    #include <iostream>
    #include <ctime>
    
    using namespace std;
    
    // Number of elements to be sorted
    #define N 1000000
    
    // A comparator function used by qsort
    int compare(const void * a, const void * b)
    {
    	return (*(int*)a - *(int*)b);
    }
    
    // Driver program to test above functions
    int main()
    {
    	int arr[N], dupArr[N];
    
    	// seed for random input
    	srand(time(NULL));
    
    	// to measure time taken by qsort and sort
    	clock_t begin, end;
    	double time_spent;
    
    	// generate random input
    	for (int i = 0; i < N; i++)
    		dupArr[i] = arr[i] = rand() % 100000;
    
    	begin = clock();
    	qsort(arr, N, sizeof(int), compare);
    	end = clock();
    
    	// calculate time taken by C qsort function
    	time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    
    	cout << "Time taken by C qsort() - "
    		<< time_spent << endl;
    
    	return 0;
    }
    

    Warum die C Version ohne den unteren C++ Code plötzlich schneller sein soll, ist sowieso absolut unlogisch. Also keine Ahnung was du da kompiliert hast...



  • Sorry, wer diesen Artikel postet, ist nicht ernst zu nehmen!

    Code:

    #include <algorithm> 
    #include <cstdlib> 
    #include <iostream> 
    #include <ctime>
    
    using namespace std;
    
    // Number of elements to be sorted
    #define N 100000
    
    // A comparator function used by qsort
    int compare(const void * a, const void * b)
    {
    	return (*(int*)a - *(int*)b);
    }
    
    // Driver program to test above functions
    int main()
    {
    	int arr[N], dupArr[N];
    
    	// seed for random input
    	srand(time(NULL));
    
    	// to measure time taken by qsort and sort
    	clock_t begin, end;
    	double time_spent;
    
    	// generate random input
    	for (int i = 0; i < N; i++)
    		dupArr[i] = arr[i] = rand() % 100000;
    
    	begin = clock();
    	qsort(arr, N, sizeof(int), compare);
    	end = clock();
    
    	// calculate time taken by C qsort function
    	time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    
    	cout << "Time taken by C qsort() - "
    		<< time_spent << endl;
    
    	time_spent = 0.0;
    
    	begin = clock();
    	sort(dupArr, dupArr + N);
    	end = clock();
    
    	// calculate time taken by C++ sort
    	time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    
    	cout << "Time taken by C++ sort() - "
    		<< time_spent << endl;
    
    	return 0;
    }
    

    Projectsettings:
    Dynamic
    - General/Whole Program Optimiziation = Use Link Time Code Generation
    - C/C++/Optimization/Optimization = Maximize Speed (/O2)
    - C/C++/Optimization/Inline Function Expansion = Default
    - C/C++/Code Generation/Runtime Library = Multi-threaded DLL (/MD)
    - Linker/Optimization/Link TIme Code Generation = Use Link Time Code Generation (/LTCG)

    Static
    - General/Whole Program Optimiziation = Use Link Time Code Generation
    - C/C++/Optimization = Maximize Speed (/O2)
    - C/C++/Optimization/Inline Function Expansion = Any Suitable (/Ob2)
    - C/C++/Code Generation/Runtime Library = Multi-threaded (/MT)
    - Linker/Optimization/Link TIme Code Generation = Use Link Time Code Generation (/LTCG)

    ⚠ Inline Function Expansion für Dynamic wurde so gewählt, dass es zu sehen ist, dass Compare aufgerufen wird - ein Nachteil war nicht festzustellen!

    Runtime Output

    C:\Users\patri_000\Desktop\Project1\x64\Release>Project1_static.exe
    Time taken by C qsort() - 0.012
    Time taken by C++ sort() - 0.007
    
    C:\Users\patri_000\Desktop\Project1\x64\Release>Project1_dynamic.exe
    Time taken by C qsort() - 0.013
    Time taken by C++ sort() - 0.006
    

    Profiler Result - Call Tree
    Dynamic
    1. Project1.exe (100%)
    1.1. main (81.82%)
    1.1.1. [external code] (59.09%)
    1.1.1.1. compare (18.18%)
    1.1.2. std::_Sort (22.73%)

    Static
    1. Project1.exe (100%)
    1.1. main (84.21%)
    1.1.1. qsort (47.37%)
    1.1.2. std::_Sort (21.05%)
    1.1.3. std::op < (5.26%)
    1.1.4. rand (5.26%)

    Conclusion:
    - Ohne den Assemblercode zu untersuchen ist eine korrekte Aussage schwer zu treffen.
    - der CallTree zeigt, dass die Inline der Compare-Funktion ein Speedup von ≈ 12% -+x beträgt
    - die C++ Variante braucht aber knapp die Hälfte der Zeit zum Sortieren
    => die Sortierverfahren waren sowieso nicht vergleichbar um ein Inline-Speedup zu zeigen:

    https://de.wikipedia.org/wiki/Introsort schrieb:

    Introsort ist ein Sortieralgorithmus. Der Begriff ist eine Kurzform für „introspektives Sortieren“. Der Algorithmus ist eine Variation von Quicksort, welche in entarteten Fällen auf ein anderes Sortierverfahren mit Worst-Case-Laufzeit {\displaystyle {\mathcal {O}}(n\log n)} {\mathcal {O}}(n\log n) (zum Beispiel Heapsort) zurückfällt. Dazu wird zu Beginn jedes Rekursionsschrittes anhand einer Bewertungsfunktion entschieden, ob ein anderer Algorithmus für die Sortierung der Teilliste verwendet werden soll (zum Beispiel bei Erreichen einer bestimmten Rekursionstiefe).



  • QSort schrieb:

    Trotzdem kann die C++ den Vergleich inlinen, C nicht.

    ähm unter C kannst du den vergleich auch inlinen, indem du ihn einfach inline hinschreibst. also

    int main()
    {
    //inhalt von funktion 1
    
    //inhalt von funktion 2
    
    //...
    
    //inhalt von funktion n
    }
    

    ist durchaus zulässig und in zeiten von festplattenspeicher im bereich von terabyte und hauptspeicher im bereich von mehreren gigabyte sehr wohl vertretbar.

    wenn du dazu noch globale variablen verwendest, sparst du dir sogar noch das ständige push und pop bei den funktionsaufrufen. allerdings kann ich dir aus eigener erfahrung sagen, dass du da bei größeren programmen wahnsinnig bei wirst, sodass das mit vorsicht zu genießen ist.



  • HansKlaus schrieb:

    ist durchaus zulässig und in zeiten von festplattenspeicher im bereich von terabyte und hauptspeicher im bereich von mehreren gigabyte sehr wohl vertretbar.

    Und zerfickt dir den I-Cache.
    Push und Pop auf gecachte Lines ist nicht so ultimativ teuer wie das ständige Nachladen von Instruktionen, weil alles inlined wurde und ständig Cache-Lines rausgeworfen werden, die eigentlich noch gebraucht werden. Wenn du 10.000-mal hintereinander eine Funktion aufrufst, hast du nur Push und Pop, und das braucht nicht mal teuer sein, und der Code ist bereits im I-Cache und muss nicht vom lahmen Hauptspeicher nachgeladen werden. Wenn du stattdessen die 10.000 Aufrufe inlinest, sind Push und Pop weg, aber der Code ist nicht mehr im I-Cache und muss ständig nachgeladen werden.

    Ein Cache-Hit kostet (L1) unter 10 Cycles; ein Cache-Miss kann locker 200 Cycles kosten, wenn direkt vom Hauptspeicher geladen werden muss.

    HansKlaus schrieb:

    wenn du dazu noch globale variablen verwendest, sparst du dir sogar noch das ständige push und pop bei den funktionsaufrufen.

    Und dann hast du noch das Problem eventueller TLB-Misses.
    Du arbeitest gerade mit einem großen Datenset, aber alles passt noch gerade so in den Cache. Dann greifst du auf deine globale Variable zu, die in einer komplett anderen Page liegt. Der TLB kennt die nicht. Also muss er einen Page-Walk machen. Der ist wahrscheinlich auch direkt ungecacht. Da wünschst du dir die 200-Cycle-Latenz noch, da geht es eher in den 2000 - 4000er Bereich. Abgesehen davon evicted es dir noch dein Datenset. Deswegen willst du Daten in der Regel lokal halten.

    Dadurch, dass Sachen gecacht werden, gelten Annahmen, die Anfänger treffen, einfach nicht. Einen Wert wieder und wieder zu berechnen kann schneller sein, als ihn im ungecachten Hauptspeicher zu halten. Meistens will man sich damit auch nicht rumschlagen. Dafür hat man Optimizer in Compilern, die anhand von Heuristiken entscheiden, ob bestimmte Funktionsaufrufe geinlined werden (können). Die sind manchmal nicht die Besten, nein. Aber Pi mal Daumen besser, als was viele Programmierer manuell hingekommen täten.


Anmelden zum Antworten