Viele Programmierer verwenden viel Zeit, um ihren Programmcode schneller zu machen, insbesondere Männer. Ihnen scheint, es verhält sich mit einem schnellen Programm wie mit einem schnellem 6-Zylinder.
Gab man früher mit der PS-Zahl und dem Hubraum seines Auto an, so definiert sich der junge männliche Programmierer darüber, wie leistungsstark sein Prozessor und wie schnell seine Programme sind.
Analog dazu wird getunt: war es früher der Spoiler, eine tiefergelegte Chassis und aufgebohrte Zylinder, ist es heute die Übertaktung des Prozessors und das Feintuning von Funktionen.
Die meisten, die diesem Geschwindigkeitswahn verfallen (der Autor gehörte früher selbst dazu), merken nicht einmal, wie wenig sinnvoll eine solche Optimierung ist: wird eine Schleife nicht wenigstens einige Tausende Male durchlaufen, lohnen sich die Optimierungen oft nicht. Zudem wird oft am falschen Ende gesucht: die Geschwindigkeit einer Routine wird weniger von ihren kleinen Details bestimmt (z.B. eine Schleifenvariable x in einem Register zu halten statt auf dem Stack), als vielmehr von ihrem Grobdesign, also vom zugrundeliegenden Algorithmus.
Eine Sortieraufgabe soll dies weiter illustrieren.
Gegeben sei ein junger hoffnungsvoller Programmierer und eine Versicherungsfirma, die ihm die Aufgabe stellt, ein Programm zu entwickeln, welches ihre 1 Mio. völlig unsortierter Kunden sortiert soll.
Unser Programmierer ist so genial, daß er es nicht nötig hat, von anderen abzuschreiben. Er setzt sich einfach hin, denkt eine Weile nach und schickt kaugummikauend seinen ersten Kandidaten ins Rennen: einen Wald- und Wiesenalgorithmus namens Blase:
void sort01(titem a[], size_t len)
{
int i, j;
titem h;
for (j=1; j<len; j++)
for (i=0; i<len-1; i++)
if (a[i] > a[i+1]) {
h = a[i];
a[i] = a[i+1];
a[i+1] = h;
}
}Nehmen wir noch schnell an, der Durchlauf der inneren Schleife benötige 1 ms, und n bezeichne die Anzahl der Datensätze.
Und … Start!
Uups! Durch die Koppelung der inneren Schleife an die äußere wird die innere 1 Mio. x 1 Mio. mal durchlaufen, so daß die ganze Funktion mindestens
1012 ms = 1.000.000.000 s bzw. 16.666.667 m bzw. 277.778 h bzw. 11.574 d bzw. 31,7 a
benötigt. Seine Komplexität beträgt somit
Θ(n) = n2.
Fehlschlag! Unser nun schon leicht deprimiert wirkender Programmierer fängt an, wild herumzudoktern: Fein-Tuning ist angesagt! Die Variablen i und j legt er in ein Register (macht aber ein guter C-Compiler sowieso automatisch):
register int i, j;Und nicht genug, nach einigen Stunden Grübelns (was sind schon einige Stunden, wenn er zum Testen schon 31 Jahre warten mußte) erkennt er auch, daß die innere Schleife nicht jedesmal bis zum bitteren Ende durchlaufen werden muß:
for (j=len-2; j>=0; j--)
for (i=0; i<=j; i++)Und … Start!
Exakt nur noch 50% Zeit wird benötigt. Bravo! Aber geht es noch ein bißchen schneller?
Ist doch gut, wird mancher hier empört einwenden: statt 31 benötigter Jahre nur noch 15 ;-)
Aber unser Programmierer ist beim Austesten seines Sortieralgorithmus nun schon 31 + 15 = 46 Jahre älter geworden. Noch so einen Fehlschlag kann er sich nicht wirklich leisten, sonst ist die Rente eher da als die Lösung.
Was er nun braucht, ist ein wirklich schneller Algorithmus … Er bequemt sich also in die Bibliothek, um nach Literatur zu diesem Thema zu suchen. Eigentlich hat er so etwas ja nicht nötig, es ist ja auch vielmehr, um einen Überblick zu bekommen, wie es die anderen noch schlechter machen …
Tatsächlich findet er einen vielversprechenden Kandidaten mit dem Beinamen „Der Schnelle“. Den schickt er als seinen letzten Trumpf ins Rennen, um die schwierige Aufgabe zu stemmen:
void sort02(titem a[], int l, int r)
{
int i, j;
titem v, h;
if (r <= l)
return;
i = l - 1; j = r; v = a[r];
do {
do i++; while (a[i] < v);
do j--; while (a[j] > v);
h = a[i]; a[i] = a[j]; a[j] = h;
} while (i < j);
a[j] = a[i]; a[i] = v; a[r] = h;
sort02(a,l,i-1);
sort02(a,i+1,r);
}Und … Start!
Bingo! Man sah es dem Typen vorher nicht an, was in ihm steckte: Knapp vier Stunden hat er nur gebraucht!
Seine Komplexität beträgt
Θ(n) = n ln(n) mit ln(n) ≈ 13,82 und somit
Θ(n) ≈ 13,82 x 106 entsprechend 13,82 Mio. ms bzw. 13.820 s bzw. 230 m bzw. 3,84 h.
Unser Programmierer ist begeistert: stolz präsentiert er der Firma die Lösung. Die aber hat ihn schon lange gekündigt, was er aber in der Zwischenzeit nicht mitbekam, da er ja 46 Jahre testen mußte …
Wer vom Fein-Tuning noch nicht abgeschreckt wurde :-), sollte weiterlesen. Wer lieber am Grobdesign basteln möchte, findet Anregungen in den Einführungen zu Suchverfahren und Sortierverfahren.
Optimieren kann man entweder die Geschwindigkeit oder die Codegröße. Grundlegende Optimierungen verbessern sowohl Geschwindigkeit als auch Kompaktheit. Kommt es aber auf jedes bißchen an Optimierung an, verhält sich die Optimierung der Geschwindigkeit gegenläufig zu der der Kompaktheit. Mit anderen Worten, jedes Mehr an Geschwindigkeit wird mit einem Verlust an Kompaktheit erkauft und umgekehrt. Viele der nachfolgenden Beispiele verbessern sowohl Geschwindigkeit als auch Kompaktheit: die Einteilung in eine der beiden Rubriken ist mitunter etwas willkürlich!
Vieles kann man gut lösen, vieles besser. Betrachten wir das Beispiel eines Algorithmus in C, der den Zinseszins nach n Jahren berechnen soll:
for (jahr=1; jahr<=n; jahr++)
saldo = saldo + zins*saldo;Der schnellere Algorithmus ist hier:
double zinsfaktor = 1 + zins;
for (jahr=0; jahr<n; jahr++)
saldo *= zinsfaktor;Unter Berücksichtigung des Umstandes, daß Vergleiche auf 0 von vielen Prozessoren schneller abgearbeitet werden, kann man noch weiter optimieren:
double zinsfaktor = 1 + zins;
for (jahr=n; jahr>0; jahr--)
saldo *= zinsfaktor;Oder für sehr große n folgende Funktion verwenden, wenn es auf jährliche Rundung nicht ankommt:
saldo *= pow(1+zins,n);Optimierung ist gut und schön. Letzten Endes bezahlt macht sich die ganze Mühe aber nur, wenn obige Schleife wirklich oft im Programm durchlaufen wird!
Optimierung mit dem Ziel geringen Speicherplatzes. Gerade C-Entwickler neigen oft zu sehr kompaktem Code, was nicht gerade die Verständlichkeit für Anfänger erhöht.
Im Allgemeinen sollte man einen gesunden Kompromiß zwischen Lesbarkeit und Kompaktheit eingehen. Ein kompakter Quellcode zieht nicht immer kompakten oder schnellen Binärcode nach sich: viele Konglomerate nimmt der Compiler ohnehin wieder auseinander. Aber nach der Philosophie von C hat der Entwickler viele Freiheiten (und damit viel Verantwortung):
Ein C-Programmierer muß genau wissen, was er tut.
Variablen und Funktionen, die nie referenziert werden, verschlingen unnötig Platz und sollten daher wieder aus dem Code entfernt werden („toter Code“). Viele moderne Compiler (z.B. Borland C und Borland Pascal) entfernen sie allerdings automatisch („intelligentes Linken“) bzw. können entsprechende Hinweise auf toten Code ausgeben.
Eine String-Kopierroutine, hier besonders umständlich implementiert und in dieser Struktur in vielen Programmiersprachen anzutreffen, folgt:
void strcpy(char *d, const char *s)
{
int i;
i = 0;
while (s[i] != '\0') {
d[i] = s[i];
i = i + 1;
}
d[i] = 0;
}Dies kann man in C wie folgt „reduzieren“:
void strcpy(char *d, const char *s)
{
while (*d++ = *s++);
}Denjenigen, die nachfolgende Routine als zu kryptisch empfinden, sei gesagt, daß hier noch nicht das Ende der Fahnenstange erreicht ist, und empfohlen, die Entwicklungsgeschichte von C zu lesen. Ebf. empfehlenswert zu lesen ist Duffs Device.
Der folgende Code
c=getchar();
while (c != EOF) {
putchar(c);
c = getchar();
}kann in C/C++/Java (nicht jedoch in Pascal, Zuweisung ist dort kein Ausdruck), vereinfacht werden zu:
while ((c=getchar()) != EOF)
putchar(c);Ausweg in Pascal durch eine Dummy-Schleife:
repeat
read(c);
if c = eof
break;
write(c)
until false;Der Code
/* Passwort mit max. maxlen Zeichen Länge einlesen */
i = 0;
do {
c = getch();
s[i] = c;
i = i + 1;
} while (i<maxlen && c!='\r');
if (s[i-1] != '\r')
s[i] = 0;
else
s[i-1] = 0;kann vereinfacht werden zu:
i = 0;
while(i<maxlen && (c=getch())!='\r')
s[i++] = c;
s[i] = 0;Je mehr Variablen lokal statt global deklariert sind, desto mehr Platz ist im Datensegment frei und um so weniger unbeabsichtigte Seiteneffekte sind möglich.
Optimierung auf Geschwindigkeit. Hinweis: Viele der nachfolgenden Optimierungen werden heutzutage von den Compilern selbsttätig vorgenommen. Darauf verlassen sollte man sich allerdings nicht. Entsprechend der Fachliteratur habe ich ihre englischen Namen belassen: die deutsche Umschreibung ist zu langwierig.
Das sog. Kurzschlußverfahren spart Zeit bei der Auswertung Boolescher Ausdrücke.
Kurzschlußauswertung boolescher Ausdrücke einschalten mit lokalem Compilerschalter $B-.
Führen immer Kurzschlußverfahren aus (Anspruch, schnelle Sprache zu sein), was zu anderen Problemen führt, wenn Seiteneffekte nicht mehr ausgeführt werden:
if (a || b++)Ist a schon wahr, wird b++ nicht mehr ausgeführt; also Vorsicht!
Erlaubt wie Borland Pascal die Auswahl: &&, || mit und &, | ohne Kurzschluß.
Die Verwendung von konstanten Variablenparametern (Call per reference, Call per variable) anstelle von Wertparametern (Call by value) bei großen Datenstrukturen erhöht die Effizienz der Übergabe und erniedrigt die Stackbelastung. Aus
struct tAutomobil {
char typ[30];
int farbe;
unsigned ps;
};
typedef struct tAutomobil tAuto;
void printAuto(tAuto a)
{
printf("Typ: %s, Farbe: %d, PS: %u\n", a.typ, a.farbe, a.ps);
}wird so
void printAuto(const tAuto *a)
{
printf("Typ: %s, Farbe: %d, PS: %u\n", a->typ, a->farbe, a->ps);
}Vorausberechnung konst. Ausdrücke. Im folgenden Code
a = x;
b = 0;
c = a / x;
d = x * c;
e = x + b;gilt b = 0 und c = 1. Die letzten drei Zeilen können daher optimiert werden zu
c = 1;
d = x;
e = x;und in C, C++ und Java infolge der Möglichkeit der Mehrfachzuweisung sogar zu
c = 1;
d = e = x;Vorausberechnung konst. Unterausdrücke. Der folgende Code
x = (a + b + abs(a - b) / 2;
y = (a + b - abs(a - b) / 2;kann optimiert werden zu
u = a + b;
v = abs(a - b);
x = (u + v) / 2;
y = (u - v) / 2;Reduktion der Operatorstärke. Der nachfolgend aufgeführte Code eq = a; x = e4q
x = exp(4*log(a));kann vereinfacht werden zu x = e4q = (eq)4 = a4
x = a * a; x = x * x;Gleichermaßen können durch Schiebebefehle aufwendige Multiplikationen und Divisionen mit Potenzen von 2 vermieden werden. Aus
x = a * 4; y = a / 8;wird somit
x = a << 2; y = a >> 3;Wie schon erwähnt, erledigen dies viele Compiler automatisch: Falls ein Faktor einer Multiplikation eine Konstante mit dem Wert einer Zweierpotenz darstellt, setzen sie automatisch einen Schiebebefehl ein.
Nutzung bereits bekannter Werte aus Variablen. Der Code
x = a + b; help = a; y = help + b;kann reduziert werden zu
help = a + b; x = help; y = help;oder in C/C++/Java sogar zu
x = y = a + b;Entfernung vorausberechenbaren Codes aus Schleifen. Aus
for (i=1; i<=100; i++)
a[i] = x * y;wird
z = x * y;
for (i=1; i<=100; i++)
a[i] = z;Reduktion der Operatorstärke in Schleifen. Aus
for (i=1; i<=100; i++)
a[i] = i * 4;wird
for (i=1,t=0; i<=100; i++)
a[i] = t += 4;Ebenfalls können Vergleiche oft durch Nutzung von Sentinels bzw. Guards vereinfacht werden. So wird aus
i = 0;
while (s[i]!=c && i<strlen(s))
do_sth_with(s[i]);einfach
l = strlen(s);
s[l] = c; /* Append guard c to string */
i = 0;
while (s[i] != c)
do_sth_with(s[i]);
s[l] = 0; /* Restore 0 */Schleifenzusammenführung. Aus
for (i=1; i<=100; i++)
a[i] = 3 * x;
for (i=1; i<=100; i++)
b[i] = a[i] + 2 * y;wird
for (i=1; i<=100; i++) {
a[i] = 3 * x;
b[i] = a[i] + 2 * y;
}Last and least: Umsetzen zeitkritischen Codes in Assembler kann um Faktor 2..50 (oder noch mehr) beschleunigen. Eine 1ms-Schleife 100.000 mal zu durchlaufen kostet über anderthalb Minuten!
Am besten über das Schema nach Horner.
Am besten über das Schema nach Légendre.
Siehe bei den Suchverfahren.
Siehe bei den Sortierverfahren.
S. weiterführende Literatur, insbesondere: