Compiler, Interpreter und ihre Schwächen

Zeit, dass ich mich mal wieder einem Computerthema widme. Das heutige Thema war als ich mit der Computerei anfing – Anfang der Achtziger Jahre – „in“, ist heute aber kein Thema mehr. Es geht darum, wie ein ausführbares Programm erzeugt wird. Da heute zwar viel mehr Leute einen Computer oder ein Gerät das einen Computer beinhaltet wie ein Smartphone oder Tablett nutzen, aber nicht mehr wie früher Programmieren (müssen) zuerst mal eine Erklärung.

Prozessoren interpretieren das Bitmuster, dass sie aus dem Speicher holen als Befehle. Jeder Befehl hat einen eigenen Code. Diese unterste Ebene nennt man Maschinensprache, in ihr würde man ein Programm als eine Folge von Zahlen schreiben. Wer als ich anfing „patchte“ man so Programme, gab tatsächlich so auch Befehle ein, meist als Hexadezimalzahl. So kann man aber keine größeren Programme schreiben. Daher liefert jeder Prozessorhersteller für einen neuen Prozessor zumindest ein Programm: den Assembler. In ihr hat jeder Befehl ein meist kryptische Kürzel, aber das ist immerhin besser zu merken als eine Zahl. Daneben berechnet der Assembler Adressen und er erlaubt das Arbeiten mit Konstanten und Variablen.

Ein Assembler ist aber auf einen Prozessor beschränkt und jeder Prozessor hat einen anderen Befehlssatz. Für die Lösung eines Problems muss man sich zuerst in die Architektur des Prozessors einarbeiten und bei einem anderen Prozessor fängt man von vorne an.

In den Fünfziger Jahren entstanden die ersten Hochsprachen in denen die Befehle viel abstrakter und dem Erfahrungswert von Menschen z.B. wie man mathematischen Gleichungen formuliert oder Abläufe organisiert, angepasst wurden. Die beiden ersten waren FORTRAN für mathematische Probleme und COBOL für kaufmännische Probleme. Doch damit der Prozessor diese Sprache verstand, braucht man ein Programm das diese Befehle in die Befehle des Prozessors übersetzte. Die ersten Sprachen verwandten alle Compiler. So wird ein Programm bezeichnet, dass das Hochsprachenprogramm direkt in den Binärcode des Prozessors übersetzt. Man erhält ein ausführbares Programm, dass ohne den ursprünglichen Quelltext auf jedem Computer mit diesem System (Prozessor, aber auch Betriebssystem) ausführbar ist.

Das hat Vorteile für den Softwareentwickler, der so den Quelltext behält und damit auch sein geistiges Eigentum. Es hat auch Vorteile für den Kunden, denn das ausführbare Programm entspricht dem in Maschinensprache. Er muss es nicht erst in Maschinensprache übersetzen. Allerdings braucht man zum Entwickeln einige Programme – einen Editor, eine einfache Textverarbeitung um den Quelltext zu schreiben, den Compiler und für die Fehlersuche einen Debugger. In der praktischen Arbeit musste man dauernd zwischen diesen drei Programmen wechseln, bis Turbo Pascal 1983 alle drei Programme erstmalig zusammenfasste und eine IDE schuf (IDE = Integrated Development Enviroment).

Es gab schon immer das Bestreben vor allem für das Erlernen der Programmierung dies einfacher zu machen. Für BASIC, (Beginners All Symbolic Instruction Code) eine Lehrsprache die Studenten an FORTRAN heranführen sollte, wurde das Konzept des Interpreters verwendet. Bei einem Interpreter führt der Computer jeden Befehl sofort aus und gibt das Ergebnis aus. Programme werden in BASIC dadurch entwickelt, dass man jede Zeile nummeriert. So führt der Interpreter sei nicht sofort aus, dann muss man das Programm mit „Run“ starten. Ein Interpreter macht dann im Prinzip das gleiche wie ein Compiler. Er holt sich jede Programmzeile und übersetzt sie in Maschinencode. Er macht das aber nie mit dem ganzen Programm, sondern immer nur dem teil den er gerade ausführen muss, das ist eine Anweisung, Das ist aber aus zwei Gründen langsamer. Zum einen braucht die Übersetzung Zeit. Bei meinem längsten Turbo Pascal Programm das ich auf einem 8-Bit Rechner schrieb, dauerte das Übersetzen einige Minuten. Ich habe mir dann jedes mal einen Kaffee geholt. Gut diese Zeit verteilt sich beim Interpreter auf Tausende Programmzeilen, sodass jede einzelne Zeile schnell übersetzt ist. Der zweite Punkt ist wichtiger. In Programmen wird immer ein Großteil des Codes wiederholt, man spricht von einer Schleife. Wäre dem nicht so, niemand müsste ein Programm schreiben, sondern könnte auch alles von Hand berechnen. Bei einem (klassischen) Interpreter wird aber bei jeder Wiederholung neu übersetzt, was das Programm sehr verlangsamen kann.

Trotzdem wurde praktisch jeder Heimcomputer in den Achtziger Jahren mit einem BASIC-Interpreter ausgeliefert. Aus einem einfachen Grund – ohne Diskettenlaufwerk konnte man nicht die für einen Compiler benötigten drei Programme Editor, Compiler, Assembler im Speicher halten. Auch ist im Speicher bei einem Compiler neben dem Quelltext das gesamte Programm, man benötigt also mehr Speicher. Daneben war BASIC eine so einfache Programmiersprache, das der Interpreter in einigen Kilobyte Speicher unterbringbar war. Der BASIC Interpreter war zugleich Betriebssystem. Es gab auch andere interpretierte Programmiersprachen, viele für den Einsatz in Lehre wie LOGO oder Comal, andere wegen der einfacheren Möglichkeit Fehler zu finden, wie bei Lisp, der allerersten interpretierten Sprache. Als ich zu Programmieren anfing, hatten Interpreter keinen guten Ruf. Das lag zum einen daran, das alle von größeren Systemen bekannten Hochsprachen compiliert waren, wie Pascal, C, Cobol. Algol oder FORTRAN. Die bekannteste interpretierte Sprache war aber BASIC das wegen des eingeschränkten Sprachstandards und der Fehleranfälligkeit keinen guten Ruf hatte. Vor allem aber waren die Rechner damals langsam und da wollte man nicht auch noch viel Rechenzeit für das dauernde Übersetzen opfern.

BASIC starb mit den Heimcomputern aus. Wert in den Neunzigern entwickelte, tat dies mit Compilern. Meist in C oder Pascal. Mit Java kam ein neuer Interpretertyp auf. Java ist eine objektorientierte Sprache, die sich in der Syntax an C anlehnt. Also durchaus nicht so was „einfaches“ wie BASIC. Java sollte aber auf jeder Plattform laufen. Dazu wählte man den (auch nicht neuen) Weg eines Zwischencodes. Der Java-Compiler erstellt aus Java-Quellcode einen plattformunabhängigen Bytecode. Der von einer Java-Virtual Maschine auf dem Rechner dann interpretiert wird. Der Bytecode ist aber plattformunabhängig, kann wie ein Maschinenspracheprogramm weitergegeben werden. Um die Nachteile des Interpreters bezüglich Geschwindigkeit zu kompensieren, gibt es auch Just-In-Time Compiler, die beim Starten des Bytecodes ein Maschinenspracheprogramm erzeugen. Das ist aber nicht Standard. Dieses Konzept verwandten auch andere Programmiersprachen wie die Konkurrenzsprache zu Java, C# von Microsoft. Es ist zumindest deutlich schneller als Java, das ich als langsam in Erinnerung habe, vor allem bis ein Programm überhaupt startet.

Seitdem sind etliche neue Sprachen erschienen, die meisten interpretiert. Entweder weil es nicht anders möglich ist, wie dies z.B. bei PHP und Javascript, wo der Quellcode in einer HTML Seite steckt oder weil so die Plattformunabhängigkeit gewährleistet wird. Die besteht bei der Dominanz der IA-64 Architektur heute nicht mehr in der Unterstützung vieler anderer Prozessoren als vielmehr darin das heute niemand mehr Programme mit Textausgaben schreibt. Jede grafische Oberfläche hat aber andere Routinen für die Ausgabe und jeweils ein anderes Design. Damit ein Programm trotzdem plattformunabhängig ist, muss es praktisch zur Laufzeit die richtigen Routinen aufrufen.

Heute sehr populär ist Python. Python ist einfach zu erlernen und leistungsfähig und es ist interpretiert. Bei der Geschwindigkeit heutiger Rechner spielt der Nachteil der Geschwindigkeit eines Interpreters selten eine Rolle. Wenn dies der Fall ist, dann nutzt man mit Python eben C-Bibliotheken, die in Maschinencode codiert wird, z.B. wenn es um künstliche Intelligenz (KI) geht.

Was aber immer bleibt ist, wie gut der Compiler selbst ist, egal ob er ein nativer Compiler ist oder in einem Interpreter versteckt ist. Das Problem ist nicht neu. Das erste Mal das man versuchte die Geschwindigkeit von erzeugtem Code von Interpretern/Compilern zu messen ist, meiner Ansicht nach das „Sieve“ Benchmark von Byte (9/1981). Er ermittelt die Primzahlen zwischen 2 und 8191 und wurde in dem Heft in verschiedensten Programmiersprachen veröffentlicht, darunter etlichen von denen ich bis heute nie gehört habe. Es gibt auch eine Liste der Resultate verschiedener Interpreter und Compiler. Hier sieht man auch das die Programmiersprache nicht unbesiegt über die Geschwindigkeit entscheidet. Das zweitschnellste Ergebnis hatte ein C-Compiler. Ein anderer C-Compiler lieferte auf demselben Rechner aber auch das langsamste Ergebnis: 337-mal langsamer!

Die Ergebnisse bestätigten aber, dass Compiler in der Regel schneller sind als Interpreter, den auf den letzten Plätzen tummeln sich etliche BASIC-Interpreter, 34 bis 300-mal langsamer als der Spitzenreiter während das compilierte Microsoft Basic nur um den Faktor 1,32 langsamer war. Die Geschwindigkeit liegt auch an der Implemtierung des Interpreters/Compilers.

Das grundlegende Problem ist das ein Compiler die möglichst beste Lösung suchen soll. Dabei gibt es oft einen Konflikt: Soll der Code schneller oder kompakter sein. Das schließt sich oft aus. Kompakter Code packt möglichst viel in Unterroutinen, die aufgerufen werden. Doch das Aufrufen kostet Zeit. Wiederholt man den Code, so wird das Programm zwangsläufig länger. Das grundlegende Problem ist aber das der Code maschinell nach Regeln erstellt wird. Eine Untersuchung von Compilern erzeugtem Code ergab, dass 80 Prozent des Codes nur 20 Prozent der verfügbaren Instruktionen verwenden – und die restlichen 20 Prozent die restlichen 80 Prozent der Instruktionen. Das ist ein typisches Beispiel für die 80/20 Regel oder Paretoprinzip. Das führte in den Achtzigern dazu, das man neue Prozessoren nach dem RISC Prinzip entwarf – sie sollten nur diese 20 Prozent der Befehle einsetzen, die aber schneller ausführen. Eine der damals entstandenen Architekturen, die ARM-Architektur steckt heute in jedem Smartphone.

Ich bin auf die Problematik gekommen, weil ich derzeit eine kleine Reihe über Prozessoren schreibe die Intel herausbrachte und sich zu Flops entwickelten. Ich habe schon über den iAPX 432 und i860 geschrieben. Beim i860 war es so, dass dessen Spitzenperformance nur zu einem Bruchteil mit Compilern erreicht wurden, weil diese nicht das Leerlaufen der Caches vorhersagen können – die Caches waren beim i860 nur 4/8 KByte groß. Heute sind sie aus gutem Grund einige Megabytes groß. Ein ähnliches Schicksal hat der nächste Fehlschlag der Itanium, bei dem der Compiler die Befehle so gruppieren sollte, das er schnell ausgeführt werden kann. Auch das klappte nicht.

Das grundlegende Problem ist, dass auch nach Jahrzehnten Compilerentwicklung diese relativ „dumm“ sind. Sie ersetzen eben einen Hochspracheinbefehl 1:1 durch eine Maschiensprachensequenz und sehen nicht die Umgebung in der diese Befehlsfolge sich befindet.

Vor einigen Jahren hat die ct’ in der Ausgabe 12/2014 unter dem Titel „Matrix reloaded“ mal einen Test veröffentlicht. Sie haben eine einfache Matrizenmultiplikation geschrieben, nur wenige Zeilen Code, der entscheidende Teil geht sogar in eine Zeile:

c[i][j] += a[i][k] * b[k][j];

Diese Zeile wird in drei Schleifen (i,J,k) für Spalten und Zeilen der beiden Matrizen durchlaufen. Nun gibt es einen Befehl, der genau diese Zeile durchführt: FMA – fused Add Multiply. Dieser Befehl kann bei AVX256 sogar vier doppelt genaue und acht einfach genaue Zahlen in einem Takt addieren und multiplizieren. Das bedeutet pro Takt sollte er acht bzw. 16 Fließkommaoperationen durchführen, multipliziert man dies mit dem Takt und den vier Kernen des Prozessors Core i7- 4750HQ Prozessors (4 Kerne, maximal 3,2 GHz, Hyperthreading) so sind dies 102,4 GFlops, Hyperthreading sollte weitere 30% erreichen also 133,12 Gflops.

Das Ergebnis: Microsofts C-Compiler erreicht 3,2 GFlops, wenn man AVX explizit nutzt und das dem Compiler mitteilt, steigert sich das auf 6,5 GFlops – er nutzt aber nur einen Kern. Mit einer Erweiterung für den Compiler, die alle Kerne nutzt, klettert das dann auf 37 GFLOPS. Trotzdem – nur ein Viertel der theoretischen Leistung. Es zeigte sich im Test auch, dass die Ergebnisse extrem sensitiv waren wie der Code aufgebaut war. Führte man die Initialisierung von C in einer vorgezogenen Schleife durch, so war die Geschwindigkeit in der Rechenschleife eine andere, als wenn dies in der Rechenschleife direkt erfolgte.

Intel als Prozessorhersteller sollte bessere Compiler liefern und sie sind auch besser. Sie kommen 5-8 GFlops bei einem Kern, auf 20 GFLOPS mit AVX Unterstützung und Nutzung aller Kerne, nimmt man die Erweiterung OpenMP hinzu, kommt man auf 37 GFLOPS – ein vielfaches der Basisleistung. Doch programmiert man die Matrieznmultiplikation nicht selbst, sondern nutzt eine Bibliotheksfunktion, von der man annehmen kann, dass sie optimal programmiert ist, wahrscheinlich in Assembler, so erreicht man 140 GFLOPs.

Das zeigt das Dilemma auf. Eigentlich ist die Zeile ein Idealfall für den erwähnten Fused Multiply Add. Der Befehl macht zuerst mit zwei Operanden eine Multiplikation und addiert dann das Ergebnis zu einem dritten Operanden, der so aufsummiert wird. Genau das steht aber in der Zeile. (Die Parallelität von 2 Operationen pro Takt erhält man dadurch, dass der Prozessor pro Kern mehrere Rechenwerke hat, und je eines für die Multiplikation eines Paares und ein anderes für die Addition des vorherigen Paares (letzter Schleifendurchlauf). Da die Datenstruktur ein Array ist, sollte der Compiler als erste Maßnahme das Array in n Teiloperationen zerlegen, die er auf die n logischen Kerne verteilt. Als zweite Maßnahme müsste er je vier Rechnungen, z.B. mit Index i bis i+3 in einer FMA Operation zusammenfassen.

Nur das tut er nicht, und hilfreich ist auch nicht, dass es eine Bibliothekfunktion vom Compilerhersteller gibt, die in Assembler die Spitzenperformance herausholt, denn diese Bibliothek ist eben für gerade diesen Fall nutzbar, sobald man einen eigenen Fall hat bei dem z.B. noch jeweils eine Konstante addiert werden muss, ist sie nicht mehr nutzbar.

Das ist keine Ausnahme. Der (beim Schreiben des Blogs) aktuell schnellste Rechner weltweit, der Fugako Supercomputer leistet im LINPACK-Benchmark auf 152.064 Nodes eine gemessene Performance von 415,53 PFLOPS (theoretisches Maximum: 537 Pflops). Der LINPACK ist im Prinzip eine Matrizenmultiplikation wie auch im ct-Test. Nur ist das nicht repräsentativ für echte Anwendungen. Im HPCG – High Performance Conjugate Gradient Benchmark, der reale naturwissenschaftlich-technische Anwendungen simuliert, sind es bei 138.240 Nodes ein Bestwert von 13.366 Pflops. Also 2.732 Gflops pro Node beim Linpack, 96 Gflops pro Node beim HPCG – das sind gerade mal 3,5 Prozent der theoretischen Spitzenleistung!

Gibt es einen Ausweg aus dem Dilemma? Da man in Jahrzehnten den Compiler anscheinend kaum verbessern konnte, wäre der logische Weg den Prozessor anzupassen. Versuche einen Prozessor zu erzeugen die direkt Hochsprachenkonstrukte ausführen, anstatt viel einfacheren befehlen scheiterten. Der zweite Weg ist es, auf Spezialbefehle wie eben FMA zu verzichten und die einfachen Befehle schneller auszuführen. Dieser Ansatz RISC konnte aber auch nicht die IA64 Architektur vom Thron verdrängen. Für beide Architekturansätze gibt es die physikalisch bedingte, gleiche maximale Taktfrequenz die man vor etwa seit 20 Jahren erreicht hat. (Schon damals erreichte man 3,8 GHz, heute geht es mit maximal 5 GHz nicht wesentlich schneller). Dann ist aber die CISC Architektur, die IA64 hat immer schneller als RISC. Zudem kommen ja auch bei RISC mit jeder Generation neue Befehle hinzu und so wird RISC immer mehr zu CISC. Gerade der Itanium ist ein Beispiel wie eine neue Prozessorarchitektur nicht die Erwartungen erfüllt, die man an sie hatte.