© itsallgood, Fotolia.com

C-Programmierer vertrauen ihrem Compiler, wenige nur kommen mit Assembler in Berührung. Viele schließen sich der vorherrschenden Meinung an, dass einige Verrenkungen für performanten Code nötig seien. Eine Untersuchung zeigt: Die meisten Übersetzer sind schlauer als erwartet – wenn man sie lässt.

Mythos oder schlichte Selbstverklärung, dass der Mensch der Maschine überlegen sei: Die Auffassung, dass handoptimierter Maschinencode effizienter als der von einem C-Compiler sei, hält sich in Entwicklerkreisen hartnäckig. Dabei hat sich viel getan im Compilerbau seit den Anfängen mit Kernighan und Ritchie. Die Forschungsergebnisse dieser Disziplin sind umfangreich und kompliziert, sodass sich mancher Entwickler fragt, was davon Einzug in reale Übersetzer gefunden hat.

Diet-Libc-Entwickler Felix von Leitner hat dazu eine Reihe von Programmen für einen Vortrag auf dem Linux-Kongress unter die Lupe genommen [1]. Die einzelnen Werkzeuge unterscheiden sich in großem Maße in Hinsicht auf Ausstattung, Entwicklungsoberfläche, Einsatzzweck und Optimierungsphilosophie, aber alle übersetzen C-Code für die X86-Plattform und sind kostenlos einsetzbar (siehe Tabelle 1). Einige erfordern dazu eine Registrierung und machen den kommerziellen Einsatz von einer Reihe von Bedingungen abhängig.

Fünf im Vergleich

Der Klassiker für den Linux-Entwickler ist sicherlich der GNU-C-Compiler, den er mit »gcc« aufruft und der verwirrenderweise Teil der gleichnamigen GNU C Compiler Collection ist [2]. Richard M. Stallman veröffentlichte die erste Version bereits 1987. Ende der 1990er Jahre eröffnete das EGCS-Projekt wegen interner Uneinigkeit einen Fork, vereinigte sich jedoch noch kurz vor der Jahrtausendwende wieder mit der Hauptlinie.

Intels Compiler startete in der aktuellen Form erst nach dem Jahrtausendwechsel und gilt als stark optimiert für diverse CPU-Technologien aus seinem eigenen Haus [3]. Er vermag Vektoreinheiten wie SSE und seine Nachfolger effizient anzusprechen. Suns Studio übersetzt wie die alle anderen Produkte ebenfalls C++ [4]. Der Hersteller bietet Zusatzwerkzeuge fürs Profiling und für Performance-Tests an, die besonders unter Open Solaris ihre Stärken ausspielen [5].

Die Universität Illinois in Urbana-Champaign hat die Low Level Virtual Machine (LLVM) entworfen, einen Zwitter aus klassischem Compiler und einer VM wie bei Java: Den erzeugten Bytecode kann das System auch zur Laufzeit noch optimieren [6]. Zwar nur bedingt unter Linux einsetzbar, übersetzt auch Microsofts Visual Studio C-Code [7].

Konstanten im Speicher

Eine erste Optimierungsmöglichkeit bieten Konstanten, denn sie lassen sich im C-Quelltext auf mehrere Weisen notieren (siehe Listing 1). Im Quelltext selbst sind sie unter Programmierern verpönt, da dann zu viele Stellen auf einmal zu ändern wären. So arbeiten aber aus Sicht des Compilers Makro-Konstanten wie in Zeile 1, denn der Präprozessor expandiert sie bereits vor dem Übersetzungsschritt. Wer den Qualifier »const« verwendet (Zeile 3) darf mit dem Bezeichner lesend so umgehen wie mit einer Variable, hat aber Vorteile beim Debugging, denn diesmal weiß der Compiler überhaupt erst von dem Namen.

01 #define KONSTANTE 23
02 
03 const int konstante = 23;
04 
05 enum { _konstante = 23 };
06 
07 void foo(void) {
08   bar(KONSTANTE  + 3);
09   bar(konstante  + 4);
10   bar(_konstante + 5);
11 }

Für Integer lässt sich der etwas sperrig zu notierende Aufzählungstyp in Zeile 5 verwenden, der verbraucht dann im Code aber auch keinen Extraplatz. Insgesamt finden alle Compiler heraus, dass der Rechenausdruck in den Zeilen 8 bis 10 immer konstant bleibt, und ersetzen ihn jeweils direkt im Code durch die Ergebnisse 26, 27 beziehungsweise 28 (siehe Listing 2).

01 foo:
02         subq    $8,  %rsp
03         movl    $26, %edi
04         call    a
05         movl    $27, %edi
06         call    a
07         movl    $28, %edi
08         addq    $8,  %rsp
09         jmp     a

Eine ähnliche Frage wie bei Konstanten stellt sich Entwicklern bei kurzen Codestückchen, die sie häufig aufrufen. Funktionsaufrufe bedeuten nach der reinen Lehre, ihre Argumente auf den Stack zu legen, zum Code zu springen, die Argumente abzuholen, die Funktion auszuführen und auf gleiche Weise zurückzukehren. Daher versuchen manche, die Funktion direkt einzubetten, indem sie diese per »#define« festlegen. Eine bessere Wahl ist, die Funktion als »inline« zu markieren, dann erledigt das der Compiler und erlaubt trotzdem, per Debugger Breakpoints zu setzen.

Schlauer als der Compiler

In den meisten Fällen erkennt der Compiler aber ohnehin, wann es sich aus Geschwindigkeitsgründen lohnt, ein Codestück einzubetten, anstatt es per Subroutine aufzurufen, insbesondere wenn die CPU den Code nur einmal durchläuft. Den Klassiker

#define abs(x) ((x)>0?(x):-(x)))

wandeln GCC und ICC ebenso wie eine Funktionsdefinition in das Äquivalent der Funktion

long absX(long x) {
    long b = a >> (sizeof(a) * 8 - 1);
    return (b ^ a) - b;
}

um, das mit fünf Maschinenbefehlen und ohne Verzweigungen auskommt. Sun erzeugt den gleichen Code, verwendet aber ein anderes Registerpaar, das ein Byte mehr benötigt, LLVM implementiert nur die Funktion so schlau wie GCC und ICC, aber nicht das Makro. Der Microsoft-Compiler wendet keine Tricks an, sondern übersetzt den C-Code quasi Anweisung für Anweisung. Das gereicht aber gerade bei modernen CPUs zum Nachteil, da diese viele Werte und Opcodes in ihrer Instruction Queue haben. Wenn eine Änderung am Stack ihn entwertet, hat das große Performance-Nachteile.

Mutter der Porzellankiste

Programmierer fürchten C wegen seiner Buffer-Overflows und prüfen daher gerne, ob sie noch im korrekten Bereich sind. Listing 3 schreibt erst eine Million Nullbytes in ein Array und füllt es anschließend mit einem anderen Wert über die Funktion »put()«. Die prüft, ob der Aufrufer korrekte Indices angibt. Aus dem Quelltext ist jedoch ersichtlich, dass in diesem Fall der Check unnötig ist.

01 static char array[1000000];
02 static int put(int off, char val) {
03     if (off >= 0 && off < 1000000)
04         array[off] 0 val;
05 }
06 
07 int main() {
08     int i;
09     for (i = 0; i < 1000000; ++i) array[i] = 0;
10     for (i = 0; i < 1000000; ++i) put(i, -1);
11 }

Beim GCC 4.2 ist der Code dann auch identisch, egal, ob der Programmierer Zeile 3 entfernt oder nicht. Die erste For-Schleife ist unnötig, da der Code das Array mit der zweiten Schleife ohnehin überschreibt. Der GCC 4.3 erkennt dies bei der Option »-O3« und entfernt das erste For komplett, das zweite vektorisiert er mit SSE. Der ICC vektorisiert nur die erste Schleife mit »-O2« mit »-fast« entfernt er sie vollständig. Der Sun-Compiler expandiert die erste Schleife in 16 Instanzen, ruft aber »put()« auf die klassisch langsame Weise auf. LLVM bettet den Code zwar ein, tastet aber weder die überflüssigen Tests an, noch nutzt er CPU-Features. Visual Studio baut die erste Schleife komplett um und ruft seine optimierte »memset()«-Routine auf, tastet die Checks aber nicht an.

Verbiegen und wahrsagen

Manche Compiler bauen die Ausdrücke für den Test um. Die Funktion »clever()« in Listing 4 realisiert die gleichen Prüfung wie »regular()«. Weil durch die Subtraktion um 6 die Werte 0 bis 5 jedoch erst negativ ausfallen, und sie der Cast zu »unsigned« zu einer positiven Zahl wandelt, spart sie hier einen Vergleich. Das wissen auch GCC, LLVM, SSC und MSVC, nur Intel setzt den Code direkt um. Solche offensichtlichen Tricks kennen alle Compiler und wandeln einen Ausdruck wie »17+a*9« in »a+a*8+17« um, was sich in Assembler schneller rechnen lässt. Wer durch vier teilen will, braucht auch nicht »a>>2« zu schreiben. Das betrifft die meisten der Boolschen Operationen und Bitshifts, da hier das Programm meist besser die Konsequenzen berechnen kann als der Programmierer.

01 int regular(int i) {
02     if (i > 5 && i < 100)
03         return 1;
04     exit(0);
05 }
06 
07 int clever(int i) {
08     return (((unsigned)i) - 6 > 93);
09 }

Spannend ist bei dem Beispiel jedoch noch eine andere Frage: Welcher Ausgang des If-Statement ist wahrscheinlicher und bedarf daher im Assemblercode keines bedingten Sprunges? Alle Compiler bis auf LLVM wissen, dass »exit()« nicht wieder zurückkehrt und das daher ein seltener Fall sein muss. Das klappt allerdings nur, wenn sich Entwickler an gewisse Regeln des gesunden Menschenverstandes halten. Wem es in den Fingern juckt, mittels Zeigerarithmetik und While-Schleifen den Code

for (i = sum = 0; i < 9; i++)
    sum += array[i + 2];
return sum;

optimieren zu wollen, der kommt schnell ins Stolpern, da die Optimierer damit nicht viel anfangen können und somit letztlich schlechteren Code ohne Vektorisierung erzeugen. Der GCC erkennt sogar einfache Rekursionen und macht daraus iterativen Code.

Vorher und nachher

Die obenstehende For-Schleife nutzt den bei C-Programmierern beliebten Post-Increment-Operator zum Hochzählen der Schleifenvariable. Semantisch ist er an dieser Stelle äquivalent zu der Variante in den Zeile 9 und 10 von Listing 3. Für den Prozessor ergibt sich jedoch ein subtiler Unterschied: Bei »i++« hält das Programm zunächst den alten Wert von »i« zur weiteren Auswertung des Ausdrucks vor und erhöht dann den Wert der Variable. Dazu legt es also eine Kopie an. Frühere Compiler waren daher beim Pre-Increment ineffizienter als beim Post-Increment. Heute erkennen sie, dass der Kontrollfluss das Ergebnis des Ausdrucks (R-Value) ohnehin verwirft.

Eleganz oder Pragmatismus

Toten Code, den der Kontrollfluss nie erreicht, entfernen die Compiler ebenso wie statische Funktionen, die das Programm nie referenziert. Er verwirft ganze Objekt-Dateien, wenn es keine Referenzen auf die Elemente in ihnen gibt.

Wer nur wenige hundert Elemente einer Datenstruktur verwaltet, kommt mit einer Liste aus. Er braucht dazu keinen balancierten Rot-Schwarz-Baum – es sei denn, er will einen Schönheitswettbewerb für Algorithmen gewinnen [8]. Wesentlich wichtiger ist, die Daten in einem möglichst CPU-nahen Cache zu halten. Die Speicherhierarchie ist also ein wichtiges Optimierungsziel, da zwischen einem Hit im L1-Cache und einem Seitenfehler, der einen Plattenzugriff benötigt, maximalerweise ein Faktor von mehreren Millionen liegt. Insofern ist hier die Handarbeit deutlich besser aufgehoben. Natürlich entbindet das niemand von vernünftigen, skalierbaren Datenstrukturen, wenn abzusehen ist, dass entsprechende Datenmengen zu verarbeiten sind.

Individuelle Stärken

Einen klaren Sieger gibt es nicht, wenn es nur um die Frage geht, welcher der beste Compiler ist. Beim Einfallsreichtum in der Codeerzeugung wartet jeder der Kandidaten mit individuellen Stärken auf. Das hingegen darf durchaus als überraschend gelten, denn nicht nur die von kommerziellen Anbietern hochgezüchteten Übersetzer verblüffen mitunter, sondern auch die Open-Source-Produkte.

Wenn es darum geht, ein Werkzeug in spezifische Anwendungsszenarien wie etwa Support für eine bestimmte CPU-Erweiterung (ICC) oder das Cross-Compilieren für ungewöhnliche Embedded-Plattformen (GCC) auszuwählen, mischen sich die Karten ohnehin neu. Die zweite wichtige Erkenntnis: Der Compiler ist schlauer als die meisten Programmierer denken. In der Regel lohnt das Handoptimieren nicht – es ist sogar kontraproduktiv, wenn darunter die Lesbarkeit des Codes leidet.