mario::konrad
programming / C++ / sailing / nerd stuff
Profiling
© 2003 / Mario Konrad
Profiling eines C Programms mit gprof

Einleitung

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.

Compilieren und Linken

Das compilieren und linken eines Programmes geschieht im Wesentlichen gleich wie normal. Der kleine Unterschied liegt in einem Parameter.

Beispiel 1:

$ gcc -o myprog myprog.c -pg

Erzeugt ein ausführbares Programm myprog mit Allem was es braucht ein profiling durchzuführen.

Beispiel 2:

$ gcc -O2 -c myprog.c -o myprog.o -pg
$ gcc -o myprog myprog.o -pg

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.

Profile Erstellen

Ist das Programm mit der Option -pg compiliert und gelinkt, so kann das profiling beginnen. Zunächst wird das Programm ganz normal ausgeführt:

$ ./myprog

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:

$ gprof myprog > myprog.out

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.

Beispiel: Bubble Sort

Ausgehend von einer Version 1 des Bubble-Sort-Algorithmus' werden hier zwei Varianten vorgestellt und miteinander verglichen:

version1.c:

1
2
3
4
5
6
7
8
9
10
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:

1
2
3
4
5
6
7
8
9
10
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 :

1
2
3
4
5
6
7
8
9
10
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:

$ gcc -o prog1 prog1.c -pg
$ ./prog1
$ gprof prog1 / prog1.out

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_3

Resultate (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_3

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

Beispiel: Sortieralgorithmen

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_1

Resultat (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_3

Die 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 O(n*log(n))O(n * log(n)). BubbleSort macht mit O(n2)O(n^2) das Schlusslicht.