--->also available in English.

Optimierte Programme mit und ohne Assembler schreiben

Im ersten Teil des Textes geht es um Optimierungen für alle Sprachen, die weiteren Abschnitte beziehten sich speziell auf Assembler.
Codeoptimerung ist als ganzheitliche Sache sehen, von der Konzeption bis zum endgültigen Code. Wer die angesprochenen Punkte im ersten Teil beachtet hat man schon den wichtigsten Teil der Optimierung geschafft. Optimierungen mit Assembler sind nur die letzte, aber meist nicht entscheidende Stufe (in speziellen Fällen sind aber durchaus auch dort Verbesserungen bis hin zur doppelten Geschwindigkeit oder mehr möglich).

Inhalt:

Universelle Tips für mehr Geschwindigkeit

Die wichtigste Aussage kommt zuerst: Der Code kann nie schneller sein als der ihm zugrundeliegende Algorithmus. Es ist sinnlos, eine Schleife, die 500 mal durchläuft um den Faktor 3 schneller zu machen wenn dasselbe Problem durch zwei Schleifen mit zusammen 5 Durchläufen gelöst werden kann.
(Tip: In mathematischen Nachschlagewerken finden sich oft hierfür nützliche Formeln).

Viele für die Geschwindigkeit entscheidende Punkte hängen nicht nur von der Prozessorgeschwindigkeit ab, sondern vom gesamten Rechneraufbau. Dazu gehört die Geschwindigkeit und Größe des Caches, dessen Organisation, die Zugriffszeiten der Festplatte und des Hauptspeichers (Sequentielle Zugriffe sind im allgemeinen schneller als wahllos verteilte Zugriffe) und die Geschwindigkeit des Grafikspeichers (Schreibzugriffe auf den Grafikspeicher sind oft schneller als auf den Hauptspeicher, dagegen ist der Lesezugriff wesentlich langsamer).
Man sollte ebenfalls abschätzen können, was die verschiedenen Betriebsystemfunktionen intern alles erledigen und wie lange sie zur Ausführung brauchen.

Es empfiehlt sich, den Speicher komplett in Blöcken zu bearbeiten, die in den 1st oder 2nd Level Cache passen bevor man den nächsten in Angriff nimmt. Wahllos verteilte Zugriffe sind zu vermeiden.
Ebenso sollte man vermeiden, parallel Speicheradressen zu bearbeiten, die in den unteren Bits identisch sind, sonst aber weit auseinander liegen, da sich sonst die einzelnen Cacheeinträge gegenseitig überschreiben.
Aus dem Grafikspeicher sollte nur gelesen werden, wenn es anders nicht geht. Wenn man häufig Informationen vom Betriebsystem benötigt, kann es sinnvoll sein, diese intern zwischenzuspeichern, um zeitfressende Funktionsaufrufe zu verringern. Lesezugriffe von der Festplatte oder gar von CD-ROM sollten soweit möglich vermieden werden, und die Zugriffe sollten möglichst große Datenblöcke am Stück laden.

Abfragefunktionen (meist "polling" genannt) können oft durch Ereignisfunktionen ("event handler") ersetzt werden (es lohnt sich, die Maus- und Tastaturinterrupts bzw. - Nachrichten abfangen; dieses Verfahren ist aber weniger sinnvoll, um die aktuelle Uhrzeit abzufragen - ein gelegentlicher Aufruf von "TimeGetTime" ist schneller als ein permanent aktiver "Timer Callback").
Wenn es eine Möglichkeit gibt, dem Betriebssystem oder der CPU mitzuteilen, welche Daten in Kürze benötigt werden sollte man diese nutzen ("Prefetch" genannt).
Permanente Änderungen der belegten Speichermenge sollten ebenfalls vemieden werden, da ansonsten das Betriebssystem einiges zu tun hat, besonders wenn sowieso schon auf die Festplatte ausgelagert wird.

Hardwarebeschleunigte Funktionen sind nicht immer schneller: Falls die entsprechende Hardware fehlt, sind sie deutlich langsamer, und die verringerte Rechenlast kann durch eine stark erhöhte Last auf den Datenbussen wieder zunichte gemacht werden. Asynchrone Hardwarefunktionen (etwa via Busmaster-DMA) sind etwas schwieriger zu handhaben, bringen aber oft Vorteile.

Im Code selbst kann man auch einiges optimieren:
Schleifen und Sprünge sollte man vermeiden, wenn eine in etwa gleich komplexe Lösung ohne Sprünge und/oder Schleifen möglich ist. Falsch vorhergesagte Sprünge können den Prozessor für einige Zeit aufhalten. Dies gilt auch für Funktionsaufrufe, besonders bei externen Funktionen.

Veränderungen am Datentyp, insbesondere von Gleitkommazahlen (float, double) zu Ganzzahlen (int, char) und zurück verschwenden ebenfalls Taktzyklen (in manchen Fällen kann man dies aber verhindern, indem man den Variablentyp ignoriert, was sich überwigend in Assembler anbietet).

Bei Mathematischen Funktionen gilt: Exponential/Wurzel- und Logarithmusfunktionen benötigen relativ lange, ebenso Sinus/Cosinus und Tangens. Divisionen sind auch nicht gerade schnell. Multiplikationen sind schneller, aber immer noch nicht optimal. Wo möglich, sollten Multiplikationen, Divisionen und Potenzen durch Shift (shl / shr in Pascal und Assembler, >> / << in C und ähnlichen) ersetzt werden. Am schnellsten und unproblematischsten sind Additionen und Subtraktionen. Mit Hilfe der Booleschen Operatoren AND, OR, XOR, NOT kann man Bereichsüberprüfungen und andere Entscheidungsfälle kreativer und effizienter lösen.

Typische Optimierungen mit Assembler (überwiegend für x86-CPUs)

Prozessorregister sollten so oft wie möglich anstelle von Speichervariablen verwendet werden. Man sollte so viele Variablen wie möglich in den sieben Registern unterbringen: (E)AX, (E)BX, (E)CX, (E)DX, (E)SI, (E)DI, (E)BP. Dasselbe gilt für die FPU- und MMX-Register. Der Stackzeiger selbst ist fast immer zur Zwischenspeicherung ungeeignet, da er von Funktionsaufrufen, Interrupts, Ausnahmefehlern, PUSH und POP benötigt wird. Die 32-Bit Register ab dem 386 kann man auch unter DOS verwenden, allerdings bleibt die Beschränkung des Speicherzugriffes auf 64k ab der Segmentadresse.

Eine beliebte Optimierung besteht darin, die Register nur teilweise zu verändern, indem man nur auf einen 8 oder 16 Bit großen Teil von ihnen zugreift.
Beispiel: Man greift auf ein quadratisches Array der Form 256*256 zu. Nun kann man die Zeilenadresse in AH und die Spaltenadresse in AL speichern. Auf diese Weise hat man den Offset innerhalb des Arrays erhalten, ohne ihn zu berechnen. Und da sowohl die Zeilen als auch die Spaltenadresse genau in ein 8-Bit-Register paßt besteht auch keine Gefahr mehr, daß auf Speicher außerhalb des Arrays zugegriffen wird. Somit kann man sich zusätzlich die Bereichsüberprüfung sparen.

Bei Speicherzugriffen kann man mehrere Register zur Adressberechnung kombinieren. Besonders im 32-Bit-Modus sind Konstruktionen wie MOV EAX,[EDI+4*EBP+15] erlaubt, mit denen sich die Adresse berechnen läßt ohne den Wert der betroffenen Register verändern zu müssen.

In ein 32-Bit-Register wie EAX passen bis zu 3 Zählvariablen: Eine in AH, eine in AL und die dritte wird in den oberen 16 Bit von EAX gespeichert. Die 8-Bit-Variablen werden wie gewohnt zur Zählung benützt, auf die oberen 16 Bit greift man zu, indem man immer mit 65536 oder einem Vielfachen davon zählt. In allen 3 Fällen gibt ein Überlauf, d.h Carry gesetzt, das Ende der jeweiligen Schleife an.

Eine weitere beliebte Optimierung befaßt sich mit den Statusflags. Jeder bedingte Sprung (ausgenommen JCX/JNCX) wird von ihnen kontrolliert. Die Flags werden zwar nicht nur von CMP und TEST verändert, aber nicht jede Instruktion verändert Flags, oder zumindest nicht alle Flags. Aus der ersten Aussage folgt, daß viele Anweisungen schon dieselbe Auswirkung wie auf die Flags wie ein CMP oder TEST haben, so daß man sich dort die CMP bzw. TEST-Instruktion sparen kann. Dies bietet sich besonders bei ADD,SUB,AND,OR,XOR,NOT,INC und DEC an. Die zweite Aussage erlaubt es, zwischen dem Setzen eines Flags und dem dazugehörigen bedingten Sprung auch Instruktionen vorkommen können. Es ist beispielsweise möglich, zwischen CMP und Jxx einige MOVs einzubauen.
Manchmal geht es auch ganz ohne Sprung: Instruktionen wie SETxx, ADC, SBB sowie (ab Pentium II) CMOVxx ermöglichen es, bedingte Anweisungen ohne Sprünge zu verwenden.

Als Paradebeispiel hierfür bietet sich der Linienalgorithmus nach Bresenham an. Man berechne zuerst den Wert, um den ein Pixel höher bzw. niedriger liegt als sein Vorgänger. Dieser Wert ist meist eine Kommazahl zwischen 0 und 1. Diesen multipliziert man mit 2 hoch Größe des Register (256 bei einem 8-Bit-Register) und speichert diesen als Ganzzahl. Für jeden Schritt addiert man nun diesen Wert auf eine zweite Variable. Jedesmal wenn ein Carry erfolgt ist der Pixel um eins gestiegen bzw. gesunken. Dies wird berücksichtigt, indem man das Carryflag in jedem Schritt mittels ADC reg,0 bzw. SBB reg,0 auf die momentane Höhe addiert.

Nicht unerwähnt bleiben soll die Fähigkeit moderner Prozessoren, mehrere Befehle gleichzeitig abzuarbeiten, wenn sie voneinander unabhängig sind (das bedeutet, daß die eine Instruktion nicht auf das Ergebnis der anderen zugreift). Man kann zwei oder drei Ganzzahloperationen, eine FPU oder zwei MMX-Anweisungen gleichzeitig laufen lassen. Einige Prozessoren können auch mehrere Gleitkommazahlen parallel bearbeiten - mehr dazu am Ende der Seite.

Eines sollte nie vergessen werden: Alle Daten müssen ausgerichtet ("aligned") sein, sonst ist jede weitere Optimierung sinnlos. Das heißt WORDs müssen an einer durch 2 teilbaren Addresse liegen, DWORDs an einer durch 4 teilbaren, QWORDS an einer durch 8 teilbaren. Ausgerichtete Addressen sind immer ein Vielfaches der Zweierpotenz, die der Datengröße am nächsten liegt. Bei einer 12 Byte großen Struktur wären dies also 16 Byte.

Optimierung auf minimale Größe

Größenoptimierung ist ein komplett anderes Thema. So gut wie alles aus dem Bereich der Geschwindigkeitsoptimierung ist hier hinfällig.
Ausgerichtete Daten verschwenden oft Platz, den man mit nicht ausgerichteten Daten füllen kann. Code, der wiederholt verwendet wird kann durch Schleifen und Funktionsaufrufe ersetzt werden.

Konstanten im Code benötigen relativ viel Platz (nur Konstanten zwischen -128 und 127 sind ein Byte klein). Da sie nicht nur in Berechnungen und Vergleichen, sondern bei fast jedem Speicherzugriff vorkommen, ist es sinnvoller, lokale Variablen auf dem Stack zu speichern anstelle als statische Variablen. Bei Konstanten ist 8 oder 16 Bit Code kürzer als 32 Bit Code, so daß man bei 32 Bit möglichst viele Konstanten durch den Inhalt von Registern ersetzen sollte.

Beim Linken der Dateien gilt: DOS *.COM-Dateien sind das kleinste Dateiformat; das Verwenden statischer Bibliotheken sollte vermieden werden, insbesondere wenn sie unbenützten Code beinhalten.

Optimierungen mit gegensätzlichem Effekt

Wie man sieht sind Codegröße und Geschwindigkeit zwei völlig verschiedene Gebiete.
Es gibt aber auch "Optimierungen", die im Endeffekt die Geschwindigkeit unbeabsichtigterweise verringern. Früher war selbstmodifizierender Code beliebt, um Programme schneller zu machen. Allerdings sind heutzutage Änderungen in geladenem Programmcode das schlimmste was CPUs mit getrenntem Cache für Code und Daten sowie langen Befehlswarteschlangen ("Prefetch Queues") passieren kann. Dies wird durch die Schutzmechanismen im Protected Mode weiter verstärkt. Wenn der Code verändert wird, muß der Zustand der CPU und des Caches weitgehend neu aufgebaut werden, was hunderte von Takten benötigen kann. Im Cyrix 5x86 gibt es sogar ein Bit, mit dem die Unterstützung von selbstmodifizierendem Code zugunsten der Geschwindigkeit des Prozessors abgeschaltet werden kann. Es ist zudem denkbar, daß die Unterstützung von selbstmodifizierendem Code in einiger Zeit völlig abgeschafft wird, entweder im Prozessor oder im Betriebssystem.

Unter DOS war es beliebt, die Segmentregister neu zu laden, um damit Speicherzugriffe zu vereinfachen oder um sie als zusätzliche Register zu verwenden. Im Protected Mode (dazu gehört auch der V86-Modus vieler DOS-Boxen) werden die Segmentregister jedoch als Selectorregister behandelt. Dies bedeutet, daß man jedesmal einen Zeiger in eine Deskriptortabelle ladet, wodurch ein nicht unerheblicher Aufwand beim Neuladen des adressierten Deskriptors entsteht.

Es ist auch möglich, mehrere Gleitkommaoperationen gleichzeitig laufen zu lassen. Jede Anweisung benötigt zwar mehrere Takte, aber da sie parallel laufen ist die mittlere Dauer geringer. Dazu müssen sie aber unabhängig sein, was oft den FXCH-Befehl erfordert, um die Register neu zu sortieren (FXCH benennt nur die Register intern um, benötigt aber dazu keine Ausführungszeit). Dies wurde mit dem Pentium eingeführt. Viele andere Prozessoren unterstützen aber nur eine Operation zu einer bestimmten Zeit und benennen die Register nicht um, so daß sie durch das FXCH langsamer werden.

Mail an den Autor: webmeister@deinmeister.de

Hauptseite Programmieren Win32Asm Downloads Software Hardware Cartoons+Co Texte Sitemap