Java vs. C++

Th69

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.

Zeus

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

Zeus

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

Zeus

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.

dachschaden

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.