Optimierung in Hochsprachen, Teil 1

So ganz ehrlich ging es beim Wettrennen zwischen dem Hasen und dem Igel bekanntlich nicht zu. Auch Hochsprachen-Programmierer machen ihrer Software mit allen Tricks der Optimierung Beine. Solche Programme können dann - ein neutraler Schiedsrichter darf anwesend sein - durchaus mit Assembler konkurrieren.

Früher oder später gelangt jeder Programmierer einmal an einen Punkt, an dem er sich den schnelleren Ablauf einer Funktion wünscht. Nur weil ein schnellerer Algorithmus nicht zur Hand ist (der wäre ja gleich verwendet worden), ist ein Hinabsteigen in die Tiefen des Prozessors via Assembler noch lange nicht der schnellste oder gar beste Weg. Allein die Tatsache, daß eine in Assembler geschriebene Funktion drei- bis sechsmal länger ist als die gleiche Funktion einer Hochsprache, wirft ein Licht auf die zu erwartende Komplexität, die der Entwickler zu bewältigen hat. Der fehlende Überblick behindert dabei die Suche nach Optimierungswegen. Der gewünschte Effekt der Assembler-Programmierung verkehrt sich ins Gegenteil.

Schwarzmalerei? Egal wie die Antwort lautet: fest steht, daß sich bereits auf Hochsprachen-Ebene einiges in puncto Tempo machen läßt. Doch dafür muß man bereits bei der Programmentwicklung ansetzen. Modularer Aufbau und gute Lesbarkeit erleichtern die Optimierung eines Programms in zweierlei Hinsicht. Erstens erkennt man schneller, an welchen Stellen Optimierungen einzusetzen sind. Tritt bei einem zunächst lauffähigen Programm dann doch ein Fehler auf, stehen die Chancen gut, ihn an der zuletzt geänderten Stelle zu finden. Im Klartext heißt das: Während der Programmentwicklung noch nichts optimieren, was der Lesbarkeit des Programmes schadet. Erst das fertige Produkt modulieren wir in Richtung Geschwindigkeit. Schließlich erkennt man erst beim Ablauf die noch »lahmen« Routinen.

Die Aufteilung von Aufgabenbereichen in Unterfunktionen sorgt, abgesehen von der besseren Lesbarkeit, für ein kompakteres Programm - auch eine Art der Optimierung. Der freigewordene Platz steht für Verbesserungen im Laufzeitverhalten zur Verfügung. Soviel zum allgemeinen Aspekt der Programm-Optimierung. Es sei noch angemerkt, daß manche Compiler den einen oder anderen »Trick« bereits beherrschen. Hier sind keine Verbesserungen mehr zu erwarten. Geben die Compiler-Handbücher keine genaueren Hinweise über deren Verfahren zur Code-Optimierung, hilft nur probieren.

Minimierung der Abfragen

Die meisten heutigen Compiler beherrschen für die Überprüfung einer Bedingung die Bool‘sche Kurzschlußauswertung (»short-cut boolean evaluation«). Das bedeutet, daß sie die Auswertung einer Abfrage abbrechen, wenn sich am Ergebnis - aufgrund der Bool‘schen Gesetze - nichts mehr ändert:

if (Bedingung1 && Bedingung2)
	MachIrgendwas

Die Ausführung von »Machirgendwas« hängt von zwei Bedingungen ab, die beide erfüllt sein müssen. Da Bedingungen auch komplexere Ausdrücke sein dürfen, ist es wünschenswert, diese auch nur nötigenfalls zu berechnen. Ist Bedingung1 nicht mehr erfüllt, überspringt das Programm automatisch die Berechnung von Bedingung2.

Mit diesem Wissen läßt sich nun die Anzahl der Abfragen zur Laufzeit reduzieren, indem man die unwahrscheinlichere Bedingung voranstellt. Bei Oder-Verknüpfungen stellt man dementsprechend die am ehesten erfüllbare Bedingung voran, da ab diesem Zeitpunkt die Verknüpfung schon »wahr« ist.

Von diesem allgemeinen Fall lassen sich jetzt viele Spezialfälle ableiten. Zuerst benötigen wir zwei Bedingungen. Hier zum Beispiel das Abfragen verschiedener Bits einer Variablen durch eine bitweise Und-Verknüpfung:

if (variable & konstante1)
	MachIrgendwas
if (variable & konstante2)
	MachIrgendwasAnderes

In Fällen, wo beide Bedingungen sehr selten erfüllt sind, erspart man dem Programm viel zeitfressende Abfragerei während der Laufzeit, indem man den Quelltext mit zusätzlichen Abfragekonstruktionen betrachtet:

if (variable & (konstante1 | konstante2)
	if (variable & konstante1)
		MachIrgendwas
	if (variable & konstante2)
		MachIrgendwasAnderes
		

Wichtig ist dabei, daß der Compiler den Ausdruck »(konstante1 | konstante2)« schon im voraus berechnet. Sollte das nicht der Fall sein, muß man selbst Hand anlegen, und gleich das Ergebnis des Ausdrucks im Quelltext verwenden. Es gilt also, zuerst durch ein kleines Programm herauszufinden, ob der Compiler solche Fähigkeiten besitzt. Ist die beschriebene Lösung immer noch zu langsam, geht‘s natürlich noch schneller (und aufwendiger):

if (variable & (konstante1 | konstante2))
	if (variable & konstante1)
		MachIrgendwas
	if (variable & konstante2)
		MachIrgendwasAnderes
	else
		MachIrgendwasAnderes

Ideal ist das Ergebnis wiederum, wenn die Erfüllung von »(variable & konstante2)« wahrscheinlicher ist. Aber nicht an jeder Stelle des Programms sind solche Konstruktionen zu empfehlen. Wir möchten dazu noch einmal auf die Grundüberlegungen der Einleitung verwiesen.

Minimierung der Abfragekomplexität

Aus einer Liste von Dreiecken ist jenes mit der größten Fläche gesucht.
Es gilt: F = g * h/2 (g = Grundfläche, h = Höhe)
Eine Abfrage sieht wie folgt aus:

if (g1 * h1/2 > g2 * h2/2) 	/* dann ist das erste Dreieck größer */

Allerdings interessiert in dieser Abfrage gar nicht der absolute Wert der Fläche, sondern lediglich, welcher der beiden Ausdrücke größer ist. Nachstehende vereinfachte Version liefert deshalb das gleiche Ergebnis (algebraische Äquivalenzen ausnutzen!):

if (g1 * h1 > g2 * h2)	/* dann ist das erste Dreieck größer */

Besondere Aufmerksamkeit ist den sich oft wiederholenden Programmteilen zu widmen, will heißen: allem, was sich innerhalb von Schleifen befindet. Da Schleifen ein Programm am meisten beschäftigen, läßt sich hier auch am meisten Zeit einsparen. Dazu kommt der Multiplikator-Effekt: Mehrfaches Aufrufen einer optimierten Routine spart mehrfach Zeit ein. Erster Schritt ist natürlich das Voranstellen der nicht direkt in den Schleifen benötigten Ausdrücke. Häufig ist aber schwer zu erkennen, was genau innerhalb der Schleifen überflüssig ist:

for i = 1 to 10
	a = a + b * c
end

Die Schleife berechnet »b * c« bei jedem Durchgang von neuem, obwohl der Wert dafür konstant bleibt. Also ist es ratsam, eine temporäre Variable einzuführen, die vor Schleifenbeginn das Ergebnis von »b * c« aufnimmt.

Temp = b * c
for i = 1 to 10
	a = a + temp
end

Obiges Beispiel würde wohl niemand in der dargestellten Form anwenden. In der Praxis zeigt sich auch, daß eine typische Schleife immer dann zum Einsatz kommt, wenn irgendwelche Felder zu bearbeiten sind. Der Schleifenzähler dient dabei als Index für ein Element aus dem Feld. Die nächste Routine ist ein typischer Vertreter dieser Klasse, und zeigt besonders schön, wieviel aus einer so »alltäglichen« Routine bei genauerer Untersuchung herauszuholen ist.

for i = 1 to 10
	a[i] = a[i] * x^i +a[i-1]^2
end

Zuerst fällt auf, daß das Ergebnis gleich beim nächsten Durchlauf wieder einzusetzen ist. Speicherzugriffe lassen sich also reduzieren, indem wir für das Zwischenergebnis eine temporäre Variable verwenden:

Temp = a[0]
for i = 1 to 10
	temp = a[i] * x^i + temp^2
	a[i] = temp
end

Da der Rechenaufwand beim Potenzieren wesentlich größer ist als bei einer Multiplikation (bei Fließkommazahlen wie bei Integern), erreicht die nächste Optimierungsstufe den größten Zeitgewinn. Dies gilt auch beim Einsatz von Coprozessoren:

Temp = a[0]
for i = 1 to 10
	temp = a[i] * x + temp * temp
	a[i] = temp
	x = x * x
end

Nebenbei enthält diese Routine keine Typkonvertierung, da »i«, für das Potenzieren mit »x«, nicht mehr in eine Fließkommazahl zu wandeln ist.

Keep on roll

Eine weitere Methode ist das sogenannte Ausrollen von Schleifen. Bei sehr kleinen Feldern rollt man intuitiv die Schleife gleich ganz aus, und erspart sich so den Schleifenzähler:

a[1] = b
a[2] = 2 * b

Anstelle von:

for i = 1 to 2
	a[i] = b * i
end

Doch erscheint ein Ausrollen einer mehrere hundertmal durchlaufenen Schleife recht fragwürdig. Trotzdem erreicht man durch das zwei- oder dreifache Ausrollen höhere Durchlaufzeiten:

for i = 1 to 5
	a[i] = b * i
	i = i + 1
	a[i] = b * i
end

Wie man sieht, ist der Geschwindigkeitsgewinn bei jedem weiteren Ausrollen geringer, da die Abfrage des Schleifenendes im Verhältnis zur Abarbeitungszeit des Schleifeninhaltes immer weniger ins Gewicht fällt. Abbruchbedingungen für Schleifen lassen sich auch auf ganz anderen Gebieten reduzieren. Zum Beispiel bei der Suche eines bestimmten Elements in einem Feld. Üblicherweise überprüft man bei jedem Durchlauf das Erreichen des Feld-Endes und des gesuchten Elements.

Was aber, wenn sich das gesuchte Element mit Sicherheit im Feld befindet?

Die Schleife bricht hier doch immer auf Grund eines gefundenen Elements ab, und nicht weil das Feld komplett ausgelesen wurde. Eine Überprüfung des Schleifenendes ist also überflüssig. Ein Feld sollte also immer so angelegt sein, daß sich das gesuchte Element garantiert in diesem befindet. Wenn nicht, ergänzt man das Feld um einen weiteren Eintrag, der dem gesuchten Element entspricht. Einen solchen Eintrag nennt man auch »Sentinel«, zu deutsch »Wächter«. Jetzt ist nämlich nur noch eine Feldende-Abfrage notwendig. Erst wenn ein Element gefunden ist, überprüft man, ob es das letzte (Sentinel) war. Wenn ja, dann enthält das Feld keinen Eintrag der gesuchten Art, da sich lediglich unser eingesetzter »Wachposten« im Feld befindet.

* Langsam *
for i = 0 to 10
	if (a[i] == 007)
		gefunden
end
* Schnell *
i = 0
a[11] = 007
while (a[i] != 007)
	i = i + 1
end
if (i < 11)
	gefunden
	

Auch diese Version ist noch lange nicht die schnellste. Ändern sich die Einträge des Feldes selten, und benötigen Sie sehr oft ein Element aus diesem, empfiehlt es sich, das Feld sortiert zu verwalten. Mit Hilfe des »Binary search«-Algorithmus aus [1] braucht man nicht einmal mehr jedes Element zu prüfen. Da der »Binary Search«-Algorithmus genauso wie der »Quicksort«-Algorithmus in den meisten Hochsprachen zur Verfügung steht, sei hier auf die Handbücher der verschiedenen Compiler verwiesen. Übrigens ist die Anwendung dieser Funktionen im Gegensatz zur vielseits bekundeten Ansicht recht leicht, so daß sich ein Blick ins Handbuch auf jeden Fall lohnt.

Um nicht bei jedem Optimierungsschritt erwähnen zu müssen, daß der Compiler diesen eventuell automatisch vornimmt, beschäftigen wir uns im zweiten Teil dieses Artikels in der nächsten TOS-Ausgabe mit Optimierungen an einem konkreten Beispiel in Turbo C, beziehungsweise dessen Nachfolger Pure C.(ah)

Literaturhinweise
[1] Brian Kerninghan, Dennis Ritchie, The C Programming Language, Prentice-Hall 1978
[2] Robert Sedgewick, Algorithms, Addison-Wesley 1988
[3] Jun Bentley, (More) Programming Pearls, Addison-Wesley 1982 / 1988

Jürgen Lietzow

---

---