Will man bei einem Programm Optimierungen (Laufzeit) vornehmen, muss man wissen wo die meiste Rechenzeit verbraucht wird, um dann effektiv dort zu optimieren wo es etwas bringt. Dieses “messen” der Laufzeiten wird als profiling bezeichnet. Die entsprechenden Tools heissen Profiler.
Die GNU-Toolchain liefert auch einen solchen Profiler mit: gprof. Dieses Dokument zeigt wie ein Programm mit Hilfe dieses Tools einem profiling unterzogen werden kann.
Das compilieren und linken eines Programmes geschieht im Wesentlichen gleich wie normal. Der kleine Unterschied liegt in einem Parameter.
Beispiel 1:
Erzeugt ein ausführbares Programm myprog mit Allem was es braucht ein profiling durchzuführen.
Beispiel 2:
Hier wird das ausführbare Programm myprog in zwei Schritten erzeugt. Es ist auch möglich gewohnte Parameter anzugeben, wie in diesem Beispiel die Optimierung -O2.
Ist das Programm mit der Option -pg compiliert und gelinkt, so kann das profiling beginnen. Zunächst wird das Programm ganz normal ausgeführt:
Beim Beenden des Programms wird eine Datei gmon.out geschrieben, welche alle Informationen des Programmablaufs und die entsprechenden Zeiten enthält. Diese Datei kann nun ausgewertet werden:
Die Datei myprog.out enthält nun alle möglichen Informationen über den Programmablauf in lesbarer Form. Für weitere Optionen und Möglichkeiten von gprof ist die Dokumentation und die manpage zu konsultieren.
Ein konkretes Beispiel ist unten aufgeführt. Dort wird auch auf den Inhalt des generierten Reports eingegangen.
Ausgehend von einer Version 1 des Bubble-Sort-Algorithmus’ werden hier zwei Varianten vorgestellt und miteinander verglichen:
version1.c:
void bubble_sort_1(int * data, int size)
{
int i;
for (i = 0; i < size-1; i++) {
int j;
for (j = size-1; j > i; j--) {
if (data[j] < data[j-1]) swap(data, j-1, j);
}
}
}version2.c:
void bubble_sort_2(int * data, int size)
{
int i;
for (i = 0; i < size-1; ++i) {
int j;
for (j = size-1; j > i; --j) {
if (data[j] < data[j-1]) swap(data, j-1, j);
}
}
}version3.c :
void bubble_sort_3(int * data, int size)
{
int i = 0, j;
--size;
for (; i < size; ++i) {
for (j = size; j > i; --j) {
if (data[j] < data[j-1]) swap(data, j-1, j);
}
}
}Alle drei Funktionen erhalten den gleichen Array von int, bestehend aus 50’000 nicht sortierten Werten, zum sortieren. Die Prozedur wurde wie folgt durchgeführt:
Funktion swap und den Rest des Programms sind ausser Acht, da sie für jede Version die gleiche ist. Durchgeführt mit gcc X.XX.X auf einem PentiumIII, 500MHz. Die absoluten Werte sind hier nicht von Bedeutung, es geht um den Vergleich des Codes und der jeweiligen Laufzeit relativ zueinander.
Resultate (ohne Optimierung):
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
9.33 95.25 20.25 1 20.25 236.00 bubble_sort_1
8.60 113.93 18.68 1 18.68 234.43 bubble_sort_2
8.03 131.37 17.44 1 17.44 233.19 bubble_sort_3Resultate (mit Optimierung -O2):
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
7.79 72.57 9.85 1 9.85 170.36 bubble_sort_1
6.60 80.92 8.35 1 8.35 168.86 bubble_sort_2
6.50 89.14 8.22 1 8.22 168.73 bubble_sort_3Die Werte der Laufzeiten künnen geringfügige Abweichungen enthalten. In der manpage steht mehr darüber.
Wie zu erwarten ist in beiden Fällen die Version 3 die schnellste. Dies kommt daher, dass weniger berechnet werden muss (size-1 wurde durch vorgängiges --size ersettzt.
Die wahrscheinlich interessanteste Erkenntnis erhält man wenn man Version 1 und Version 2 betrachtet (mit und ohne Optimierung). Der einzige Unterschied im Code sind die Postfix-Operatoren (Version 1) ersetzt durch Prefix-Operatoren (Version 2). Der Gewinn alleine durch verändern des Operators is sehr gross.
Die Unterschiede zwischen Version 2 und Version 3 sind nicht mehr so gross. Die Gründe wurden oben schon erwähnt.
Dieses Kapitel zeigt verschiedene Sortieralgorithmen die gegeneinander antreten. Wiederum werden zwei verschiedene Optimierungen (keine, -O2) verglichen. Der Source Code: prog1.c.
Als Resultat werden nur die Sortieralgorithmen aufgeführt. Alle andern Funktionen wie swap, etc. werden nicht in Betracht gezogen, da sie nicht von Interesse und für alle Algorithmen gleich sind.
Resultat (ohne Optimierung):
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
9.06 94.17 19.54 1 19.54 208.58 bubble_sort_1
8.31 112.08 17.91 1 17.91 206.95 bubble_sort_2
8.00 129.33 17.25 1 17.25 206.29 bubble_sort_3
6.75 143.89 14.56 1 14.56 203.60 insertion_sort_3
6.47 157.85 13.96 1 13.96 203.00 insertion_sort_2
6.19 171.19 13.34 1 13.34 202.38 insertion_sort_1
6.06 184.25 13.06 1 13.06 202.10 shake_sort_2
6.01 197.20 12.95 1 12.95 201.99 shake_sort_1
4.30 206.47 9.27 1 9.27 9.29 selection_sort_2
4.20 215.53 9.06 1 9.06 9.08 selection_sort_1
0.01 215.56 0.03 1 0.03 0.09 quick_sort_2
0.00 215.59 0.01 1 0.01 0.01 quick_sort_3
0.00 215.60 0.00 1 0.00 0.06 quick_sort_1Resultat (mit Optimierung -O2):
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
7.10 71.51 9.02 1 9.02 155.26 bubble_sort_3
6.77 80.11 8.60 1 8.60 154.84 bubble_sort_1
6.68 88.60 8.49 1 8.49 154.73 bubble_sort_2
5.94 96.15 7.55 1 7.55 153.79 shake_sort_2
5.51 103.16 7.01 1 7.01 153.25 shake_sort_1
4.64 109.06 5.90 1 5.90 152.14 insertion_sort_1
4.48 114.75 5.69 1 5.69 151.93 insertion_sort_2
4.44 120.39 5.64 1 5.64 151.88 insertion_sort_3
2.63 123.73 3.34 1 3.34 3.35 selection_sort_1
2.62 127.06 3.33 1 3.33 3.34 selection_sort_2
0.02 127.08 0.02 1 0.02 0.06 quick_sort_2
0.01 127.09 0.01 1 0.01 0.05 quick_sort_1
0.01 127.10 0.01 1 0.01 0.01 quick_sort_3Die Werte der Laufzeiten künnen geringfügige Abweichungen enthalten. In der manpage steht mehr darüber.
Wie zu erwarten war ist QuickSort der schnellste Algorithmus mit einer Komplexität von . BubbleSort macht mit das Schlusslicht.