Kleinere Programme durch kleinere Datenstrukturen
Es ist mittlerweile bekannt, dass Speicherzugriffe für moderne CPUs sehr teuer sind und dass es sich deshalb lohnt, häufig genutzte Datenstrukturen möglichst kompakt auszulegen, so dass die CPU-Caches gut ausgenutzt werden können.
Weniger bekannt ist, dass sich das auch bei selten genutzten, “kalten” Datenstrukturen lohnen kann. Allerdings nicht für die Verarbeitungsgeschwindigkeit, sondern für die Größe des Kompilats.
Heißer Code, kalter Code
In den meisten Programmen wird der Großteil der Rechenleistung von relativ wenig Code verbraucht – von den innersten Schleifen und den Flaschenhälsen. Dieser Code ist “heiß”, da er ständig benutzt wird.
Der restliche Code liegt weitgehend brach und wird nur wenige Male pro Sekunde angesprungen (aus CPU-Sicht so gut wie nie).
Die passende Optimierung
Alle Compiler-Hersteller empfehlen Profile-Guided Optimization. Dabei wird das Programm in zwei Schritten optimiert:
Zuerst erzeugt der Compiler ein Programm für Profiling. Dieses wird gestartet und führt eine Reihe Use Cases aus, die der Entwickler bereitstellt – im Falle eines Web Browsers etwa das Laden von Seiten, das Betrachten von Videos, das Öffnen und Schließen von Tabs. Dabei werden die Profiling-Daten aufgezeichnet.
Durch diese Daten erhält der Compiler Informationen darüber, welcher Code heiß ist, und welcher kalt. Damit kompiliert er das zweite, finale Programm.
Die wichtigste Optimierung ist dann: Der heiße Code wird auf Geschwindigkeit optimiert; der kalte Code auf Größe. Das maximiert die Ausnutzung des Befehls-Caches in der CPU. Selten durchlaufene Schleifen “verpesten” den Cache nicht mehr, indem sie zu unrecht abgerollt werden und Berge an Befehlen produzieren, die die CPU am Ende doch nicht ausführt. Häufig durchlaufenen Schleifen steht mehr Cache zur Verfügung, so dass sie stärker abgerollt und schneller ausgeführt werden können.
Wie stark das Verhältnis von heißem zu kaltem Code ist, zeigt
dieser Artikel des Visual C++ Team Blogs:
As a general rule of thumb for a medium or large component, there should be <5 % methods compiled for speed.
Große Anwendungen (die Klasse Microsoft Exchange, Firefox, Microsoft Word) werden also zu über 95 % auf Größe optimiert.
(Ich persönlich nutze keine Profile-Guided Optimization, sondern optimiere alles auf Größe. Meine Bottlenecks lassen sich nur selten durch Optimierung auf Geschwindigkeit lösen.)
Wie die CPU auf Datenstrukturen zugreift
Wird auf ein Member einer Klasse oder Datenstruktur zugegriffen, muss zuerst dessen Adresse berechnet werden. In den allermeisten Fällen ergibt sie sich aus der Adresse der umgebenden Datenstruktur (bei Klassen bekannt als
this):
struct Foo {
int a;
int b;
};
void overwrite_b(Foo & foo) {
foo.b = 123;
}
Die Funktion kompiliert zu
MOV DWORD PTR [eax+4], 123
Dabei ist
MOV der
MOVE-Befehl, der aber eher
Copy hätte heißen sollen. Er kopiert einen Wert aus einem Register in ein Register, oder aus dem Speicher in ein Register, oder umgekehrt.
MOV ist auf x86 der mit Abstand häufigste Befehl. Während RISC-Prozessoren mit hunderten adressierbaren Registern kommen, hat x86 nur acht (32-Bit) oder 16 (64-Bit). Bei so wenig Registern muss man viel hin- und herschieben.
DWORD PTR bedeutet, dass wir hier auf Speicher zugreifen, und zwar auf ein 4-Byte großes Stück (denn so groß ist das
int, das wir setzen wollen).
[eax+4] bedeutet, dass an eine Speicherposition geschrieben werden soll, die vier Bytes über dem Wert im
eax-Register liegt. Das
eax-Register ist jenes, in dem unser Parameter
foo gelandet ist.
123 ist der Wert, der geschrieben werden soll.
Insgesamt bedeutet die Zeile also:
Schreibe den Wert 123 an die Speicheradresse, die im eax-Register steckt, plus vier Bytes.
Ein Klassensystem
Diese Adressierung kennt drei subtile Unterschiede. Ändern wir das Beispiel zu:
struct Foo {
int first;
int second;
char longString[256];
int last;
};
void init(Foo & foo) {
foo.first = 1;
foo.second = 2;
foo.longString[0] = 0;
foo.last = 123;
}
Nun bekommen wir:
MOV DWORD PTR [eax], 1
MOV DWORD PTR [eax+4], 2
MOV BYTE PTR [eax+8], 0
MOV DWORD PTR [eax+264], 123
Dem Anschein nach hat sich hier nichts geändert. Die Datenstruktur wird noch immer durch
eax adressiert, und die einzelnen Attribute beginnen bei Offsets von 0, 4, 8, und 264 Bytes.
Die Situation änder sich schlagartig, wenn wir nicht die Bedeutung der Befehle anzeigen, sondern die tatsächlichen Bytes der Assembler-Befehle:
C7 00 01 00 00 00 MOV DWORD PTR [eax],1
C7 40 04 02 00 00 00 MOV DWORD PTR [eax+4], 2
C6 40 08 00 MOV BYTE PTR [eax+8], 0
C7 80 08 01 00 00 7B 00 00 00 MOV DWORD PTR [eax+264], 123
Die Einfärbung bedeutet:
- Rot ist der eigentliche Befehl;
- Grün ist der Versatz in der Adresse;
- Blau ist der Wert, der geschrieben werden soll.
Wie ihr seht, verbraucht alles Platz: Möchte man ein
int schreiben, muss man diesen vier-Byte-Wert auch tatsächlich in den Befehl schreiben. Ein einzelnes Byte zu schreiben ist schon drei Bytes kürzer.
Interessanter ist hier aber der Versatz! Man erkennt, dass dem Compiler drei Arten der Adressierung zur Verfügung stehen:
- Ohne Versatz. Diese Variante funktioniert nur mit dem ersten Member, denn dessen Adresse gleicht jener der Datenstruktur. Diese Variante ist die kürzeste.
- Mit kleinem Versatz (bis 127 Bytes*). Diese Variante ist ein Byte länger.
- Mit großem Versatz (bis 2³¹-1 Bytes). Diese Variante ist volle drei Bytes länger als die Variante mit kleinem Versatz!
Versteckte Kosten großer Datenstrukturen
Drei Bytes sind nicht viel, aber
MOV-Befehle machen nunmal einen Großteil aller Executables aus. Wir haben gesehen, dass Executables zu über 95 % auf Größe optimiert werden. Ist eine Datenstruktur größer als 128 Bytes, sind dem Compiler aber die Hände gebunden, und er muss zur Adressierung die langen Varianten des
MOV-Befehls einsetzen.
Für heiße Datenstrukturen empfehle ich weiterhin:
- Haltet sie klein (achtet auf Alignment)!
- Gruppiert Attribute nach Zugriffsmustern!
Für kalte Datenstrukturen kommen nun aber diese Empfehlungen hinzu:
- Haltet Datenstrukturen kleiner als 128 Bytes. Teilt sie gegebenenfalls auf. (Weckt Erinnerungen an Style Guides, oder?)
- Sortiert die Attribute, so dass das am häufigsten genutzte Attribut vorn liegt (also ohne Versatz adressiert werden kann).
Ich habe das auf eine meiner kalten Gottklassen (*hust* GUI *hust*) angewendet und 0,5 % kleineres Kompilat bekommen. Tausende Bytes weg, durch Umsortierung der Attribute einer einzigen Klasse!
* Die 127 Bytes rühren daher, dass die CPU den Versatz signed interpretiert. Man kann also zwischen -128 und +127 Bytes angeben. Ein cleverer Compiler könnte den this-Zeiger um 127 Bytes versetzt speichern, und so alle 256 Bytes über ein kurzes MOV adressierbar machen. So einem Compiler bin ich aber bisher nie begegnet – wer auch immer den Debugger pflegen muss, würde sich darüber die Haare raufen!