Der Compiler ist schuld – oder auch nicht

 59 total views,  2 views today

Ein Compiler hat die Aufgabe eine höhere Programmiersprache in Maschinensprache zu übersetzen. Bei Großrechnern haben kompilierte Programme schon in den Sechzigern die Maschinensprache sukzessive verdrängt. Im PC Bereich war wegen der anfangs langsamen Prozessoren und dem geringen Speicher Assembler noch in den ersten Jahren wichtig, aber heute sicher nicht mehr.

Machen wir einen geschichtlichen Rückblick. Früher hat man auch evaluiert, wie effizient Compiler sind. Die Ergebnisse sind natürlich stark vom Quelltext abhängig. Die NASA hat für die Flugsoftware der Shuttle evaluiert wie schnell HAL als höhere Programmiersprache verglichen mit Assembler war. Und das Ergebnis war damals: 10-20% langsamer. Das Betriebssystem, das zeitkritisch war, wurde daraufhin in Assembler geschrieben, die „Anwendungen“ dann in HAL. Ein ähnliches Ergebnis gab es bei Tests der ersten Versionen von Turbo Pascal. Das ist erfreulich, denn das Programmieren ist doch erheblich leichter in einer Hochsprache.

Ich glaube in den letzten Jahren habe ich kaum noch was davon gelesen das jemand in Assembler programmiert, selbst wenn man nur Inline Code verwendet, also Assembler in eine höhere Programmiersprache einbettet. Die ct‘ hat als SSE eingeführt wurde das „Apfelmännchen“ also das Fractal mal in diesen Befehlen programmiert um zu sehen wie viel schneller es ist. Ich habe mal im ct Archiv gesucht: das letzte Mal war 2008. Damals war der C-Compiler meist schneller als der eingefügte Assembler.

Also alles in Ordnung? Nicht unbedingt. Es gibt zwei grundlegende Probleme für den Compiler

  • Er hat keinerlei Kenntnis, wie der Prozessor intern arbeitet
  • Das Ausnützen des Befehlssatzes wird immer schwieriger, je mehr Befehle es gibt und desto spezieller sie sind
  • Er muss heute Befehle erzeugen, die ihre Daten von mehreren Quelltextzeilen bekommen, also den Bereich in dem er optimiert vergrößern oder es wird schwieriger den richtigen Befehl auswählen.

Es gibt durchaus Indizien, das hier noch einiges zu verbessern ist. Ich habe schon mal den Test der ct‘ der Matrixmultiplikation erwähnt. Der Benchmark ist nun extrem popelig, denn er besteht aus einer Zeile:

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

Diese 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 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 acht Threads des Core i7- 4750HQ  Prozessors so sind dies 180 GFlops bei 4 Kernen, Hyperthreading sollte weitere 30% erreichen.

Das Ergebnis: Microsofts C-Compiler erreicht 3,2 GFlops, wenn man AVX explizit nutzen will steigert sich das auf 6,5 GFlops – er nutzt aber nur einen Kern. Mit einer Erweiterung die Autoparallisierung nutzt klettert das dann auf 37 GFLOPS. Trotzdem – nur ein Viertel der theoretischen Leistung. Es zeigte sich 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 das 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 bedeutet man kann ein und dasselbe Programm extrem beschleunigen und das, obwohl es sich nur um eine Programmzeile handelt. Es dürfte jedem klar sein, dass es nicht für jedes Problem eine Bibliotheksfunktion gibt, das Ergebnis ist also ernüchternd.

Es gibt noch ein zweites Faktum: das waren gescheiterte Prozessoren. 1989 lancierte Intel den i860 Prozessor, genannt „Cray on a Chip“, weil er die Leistung einer Cray 1 erreichte. Allerdings erzeugten Compiler Programme die nur ein Achtel der theoretischen Pearkperformance erreichten. Das lag nicht nur an den Compilern, der Chip galt als schwer zu programmieren und auch Assembler erreichte nur die Hälfte der Maximalleistung, aber immerhin noch viermal schneller als der Compiler.

Das zweite war das Scheitern des Itanienporzessors. Der hatte eine Philosophie die man VLIW nennt – very Long instruction Word. Dieser Ansatz soll zum einen die Abhängigkeit vom dem Speichersystem reduzieren, dass viel langsamer als der Prozessor ist – man überträgt nicht einen Befehl sondern mehrere, die man zu einem Superwort zusammenfasst. Das Konzept gibt es auch bei Signalverarbeitungsprozessoren und die Cyber Star setzte es auch ein. Das zweite ist das heute alle Prozessoren nicht nur mehrere Kerne haben, sondern jeder Kern auch mehrere Recheneinheiten. Während die Kerne aber nach außen hin sichtbar sind, sind es die Funktionseinheiten nicht. Die Prozessoren versuchen mit einigen Tricks diese Einheiten alle auszulasten sogar indem sie die Befehlsreihenfolge verändern. Der Itanium wollte diese aufwendige Logik einsparen und delegierte die Aufgabe an den Compiler. Einige Bits im Superwort enthielten die Informationen welche Befehle parallel ablaufen konnten und welche nicht. So richtig gelang dies nicht, denn die Performance war immer nur mittelmäßig. Folgerichtig stellte Intel auch diese Entwicklung ein.

Die Chancen, dass ein Compiler optimalen Code erzeugt sind um so besser, je weniger Befehle ein Prozessor hat. Untersuchungen von Kompiliertem Code bei den damals üblichen CISC Prozessoren ergab, dass vom gesamten Befehlssatz nur ein Bruchteil sehr häufig benutzt wurde, manche Befehle niemals. Das war damals der Startschuss für RISC – ein kleinerer Befehlssatz sollte schneller ausgeführt werden. Heute arbeiten die x86 und x64 Prozessoren intern auch mit RISC, sie machen einen Zwischenschritt und übersetzen den CISC Code in RISC. das zeigt schon die Problematik. Trotzdem führte Intel mit MMX, SSE 1-4 und AVX 1+2 immer neue Befehle ein, das mit wurde der Befehlssatz noch komplizierter und die Wahrscheinlichkeit, das der Compiler die beste Lösung findet schwindet, zumal er ja nur eine Vorschrift anwendet.

Was ist die Lösung? Nun OpenMP zeigt eine Lösung auf. Bei OpenMP, das bei Microsofts und Intels Compiler die Performance deutlich erhöhte, gibt der Programmierer an was parelellisierbar ist. Offenbar sind diese immer noch schlauer als die Compiler. Das zeigte auch der Code denn mein Compiler erzeugte. Dort wurde ich an eine Optimierung der Core 2 Architektur erinnert. Es handelt sich um den Befehl „Speichere Daten an Adresse X“ gefolgt wenige Befehle später von „Lade Daten von Adresse X“. Für einen Programmierer erscheint diese Sequenz dämlich, denn erst speichere ich einen Wert dann hole ich ihn, stattdessen kann ich ihn gleich in einem Register halten, das ist viel schneller. Obwohl nur vier der acht FPU Register genutzt wurden, fand sich genau diese Kombination im Code in dieser Zeile. Bei der Core 2 Mikroarchitektur hat man diese das Umsortieren der Befehle aufhaltende Kombination erkannt und sie blockiert nicht mehr das Umsortieren.

Das zeigt: Compiler sind heute noch strunz doof. Der Compiler hätte eigentlich so viel wie möglich in den Registern halten müssen denn der Speicherzugriff ist auch noch langsam. Was folgt daraus? Meine persönliche Ansicht nach sollte man das ursprüngliche Ziel von RISC beibehalten. Anstatt das Innenleben der CPU umzumodeln, damit sie das beste aus dem Code herauskitzeln, indem sie spekulative Sprünge vorhersagen, Register umbenennen, Befehle umsortieren oder Zugriffsmuster auf den Speicher vorhersagen sollte man wenige Befehle sehr schnell ausführen und das geht zum einen mit RISC zum andern mit Eingehen auf den Compiler. Beispielsweise übergeben die meisten Compiler Parameter an Funktionen über den Stack – nicht nur fehlerträchtig, sondern auch langsam.

Stattdessen sollte man für jede Routine eigene Register für die Parameterübergabe zur Verfügung stellen, die man als Fenster aus einem größeren Registerfile auswählt. Dieses Konzept des Registerfiles kennen einige RISC Architekturen. Anders als beim Cache kann der Compiler so viel besser kontrollieren wo die Daten gespeichert werden. Das gilt auch für das Laden von Routinen. Der Compiler weriß wie groß ein Unterprogramm ist und könnte es vorrausschauend in den Cache laden lassen. Auch das Konzept des VLIW ist nicht so dumm. Zumindest wäre es möglich in einem Statusbyte oder einigen Bits pro Befehl anzugeben welche Einheit man nutzt. Gleiche Werte erlauben es dem Prozessor zu erkennen: okay diese Befehle hängen voneinander ab. Man kann mit einem Befehl eine Einheit für eine Befehlssequenz reservieren und wieder freigeben.

Das sind nur einige Ideen, aber je mehr ich über Mikroarchitekturen schreibe, derzeit bin ich bei Nehalem, also der drittletzten Architektur die 2008n erschien, desto mehr wird mir klar, dass man eine ganze Menge Aufwand betreibt um im Prozessor die Performance zu steigern, ohne das der Anwender das heute groß mit dem Compiler beeinflussen könnte. Dabei kennt der den Quelltext er kennt Zugriffsmuster und er weiß wo Routinen sind die häufig gebraucht werden und welche wo langsam sind, bzw., welche als nächstes dran kommen (die man schon mal vom Speicher in den Cache geladen werden können). Man sollte also die Zusammenarbeit intensivieren anstatt neue CISD Befehle zu kreieren.

Es gäbe sogar eine noch weitergehende Möglichkeit: die des Profilings. Das gibt es heute als Tools für Entwicklungsstudios, aber es wurde auch bei PC’s eingesetzt die auf dem Alpha Prozessor basierten und für x86 geschriebene Programme als Emulation ausführten: Ein Programm wird zuerst einfach in Maschinensprache übersetzt und vom Anwender normal benutzt. Dabei führt ein mitgeliefertes Modul Buch wie oft welche Routine ausgeführt wird, auf welche Variablen zugegriffen wird etc. Das kann man ausbauen und auch zeitliche Zusammenhänge erkennen (eine Routine wird kurzzeitig sejr oft aufgerufen, dann wieder längere Zeit gar nicht). In einem zweiten Schritt wird das Programm neu übersetzt wobei die Informationen genutzt werden es zu optimieren. Ohne spezielle SIMD Befehle z.B. Variablen in Registern dauerhaft zu halten oder zumindest im Cache, Routinen vorbeugend laden wenn man weiß das sie oft nach anderen aufgerufen werden. Man kann es aber auch nutzen um CISC Befehle wie obigen FMA zu nehmen indem man beim lauf das Zugriffsmuster und die Operationen in einem Array erkennt.

3 thoughts on “Der Compiler ist schuld – oder auch nicht

  1. Nett, auf meinem Kommentar von Vorgestern gleich mit einem kompletten Beitrag zu antworten. 🙂 – Übrigens: OpenMP war das Stichwort, das mir dabei nicht einfiel. Und da die Compiler wohl wirklich so blöd sind, wäre es wohl mal an der Zeit, irgendwelche zeitkritische Software zu untersuchen. Vieleicht stellt sich dabei ja heraus, dass die kritischen Teile doch nicht soo viel in Hochsprachen geschrieben sind.
    Was das Profiling angeht, das im letzten Absatz beschrieben ist: Da erinnere ich mich an eine Demo an der FH, wo genau das auch praktiziert wurde. Ich weis nur nicht mehr, ob auf einer Maschiene mit Alpha-Prozessor oder einer von Silicon Graphics. Ist aber auch egal. Jedenfalls hatten die für ihre Workstations einen speziellen x86-Emulator, auf dem dann z.B. auch Windwos 3.x lief. Dazu haben die erzählt, dass die x86-Programme auf deren Rechnern irgendwann schneller liefen, als auf den damals gängigen PCs mit x86-CPU. Ein Kollege meinte dazu, das würde daran liegen, dass die das Profiling soweit trieben, dass der Emulator besonders häufig genutzte Teile in den nativen Code der CPU umgesetzt habe, auf der der Emulator lief. – Eine interessante Methode, finde ich.

  2. Kleiner Tip: Bei Linux bekommt man den Quellcode mit, da kann Jeder selbst nachsehen, ob Teile in Assembler enthalten sind.

    Es gab ein russisches PTS-DOS, das komplett in Assembler geschrieben war. Schneller und kleiner als das Original, nur leider zu spät. Es kam etwa zur gleichen Zeit mit Windows 95, und das war der endgültige Todesstoß für DOS.

    Zumindest bei (Action-)Spielen werden immer noch zeitkritische Teile in Assembler geschrieben, um die Hardware-Anforderungen in Grenzen zu halten. Wenn ein Spiel nur auf besonders teurer Hardware läuft, wird man das Spiel nicht richtig los. Zu DOS-Zeiten war es deshalb auch üblich, daß Spiele die Grafikkarte direkt angesprochen haben statt über Treiber. Auch eine Methode um schneller zu werden.

  3. Naja bei Linux ist gar nicht mal so viel in Assembler gaschrieben, ich hab mir das in Teilen mal angesehen. Es kommt vermutlich auch darauf an was man macht ob es etwas bringt Teile in Assembler zu schreiben. Klar bei Matrixmultiplikationen oder Ähnlichem mag das etwas bringen aber bei einfachen Programmen bringt das nichtmal so viel und gerade Kernel sind in ihren Datenstrukturen und Algorithmen meistens doch relativ einfach. Für moderne Grafikkarten gibt es auch C-Erweiterungen um die Grafikkarte direkt anzusprechen also ist auch hier nicht unbedingt Assembler notwendig. Es bringt auch in C oder anderen Programmiersprachen trotzdem gewisse Vorteile die Architektur seines Rechners zu kennen um gewisse Probleme zu vermeiden.

    Befehlsumordnen kommt auch auf RISC-Architekturen zum Einsatz da man auch dort mehrere Funktionseinheiten hat (Superskalarität), zum anderen verwenden auch RISC-Prozessoren (und meines Wissens schon bevor das auf x86 aufkam) Pipelining und dort ist es manchmal von Vorteil Befehle umzuordnen um z.B. die Pipeline immer gefüllt zu halten oder um die Auswirkungen eines Pipelineflushs zu verringern oder diesen ganz zu vermeiden (diese treten bei Sprüngen auf). Da bei einem Pipelineflush im Extremfall alle Befehle in der Pipeline gelöscht werden müssen und dadurch einige Taktzyklen verloren gehen (hier sei mal auf eines der großen Probleme des P4 nämlich seine extrem lange Pipeline von mehr als 20 Stufen verwiesen), werden hier solche Sachen wie Sprungvorhersagen (funktioniert gerade bei Schleifen recht gut) oder eben die Ausführung beider Verzweigungen bis dann eben feststeht welcher Sprung genommen wird (man verliert nur die Hälfte der Zyklen), verwendet.
    Der Vorteil von RISC ist zum einen der beschränkte Befehlssatz und das die Befehle immer die gleiche Länge haben was das Dekodieren der Befehle einfach macht und damit zusammenhängend auch das die Befehle möglichst immer gleich lang brauchen. Zum zweiten sind sie Load-Store-Architekturen, d.h. der Zugriff auf den Speicher erfolgt mit speziellen Instruktionen, alle anderen Instruktionen arbeiten auf dem Registersatz. Ein weiterer Vorteil ist eben und das folgt in gewisser Weise aus dieser Load-Store-Architektur, dass eben dieser Registersatz recht groß ist.

    Was weiterhin gerade bei x86 etwas nachteilig ist, ist das Fehlen eines getagten TLBs, dadurch muss bei jedem Adressraumwechsel der TLB geflusht werden was eben doch wieder viele Speicherzugriffe nach sich zieht und ausserdem verhindert das man den TLB größer machen kann (weil es nichts bringen würde) und so verhindert das man z.B. Microkernelbetriebssysteme sinnvoll einsetzen kann (viele Adressraumwechsel, L4 z.B. verwendet echt ein paar üble Hacks um dennoch halbwegs schnell zu laufen). Bei x64 scheint da allmählich ein Umdenken einzusetzen um diese VMs besser zu unterstützen aber das hat echt lange gedauert.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.