C ist keine einfache Sprache

Ihr Computer ist keine schnelle Version von PDP-11

Hallo Habr!

Mein Name ist Anton Dovgal, ich bin ein C (und nicht nur) Entwickler bei Badoo.

Ich stieß auf einen Artikel von David Chiznell, einem Forscher an der Universität Cambridge, in dem er die allgemein akzeptierte Meinung bestreitet, dass C eine einfache Sprache ist, und seine Argumente schienen mir interessant genug.

Angesichts der kürzlich entdeckten Sicherheitslücken sollten sich Meltdown und Spectre die Zeit nehmen, um die Gründe für ihr Auftreten herauszufinden. Diese beiden Sicherheitslücken nutzten die spekulative Ausführung von Anweisungen durch Prozessoren und ermöglichten es einem Angreifer, Ergebnisse über Kanäle von Drittanbietern zu erhalten. Sicherheitslücken in Prozessoren wurden zusammen mit mehreren anderen hinzugefügt, so dass C-Programmierer weiterhin glauben, dass sie in einer einfachen Sprache programmieren, obwohl dies seit Jahrzehnten nicht mehr der Fall ist.

Prozessorhersteller sind damit nicht allein. C / C ++ - Compilerentwickler haben ebenfalls dazu beigetragen.

Was ist eine niedrige Sprache?

Der amerikanische Informatiker und erste Turing-Preisträger Alan Perlis gab folgende Definition:

"Eine Programmiersprache ist auf niedrigem Niveau, wenn die darauf geschriebenen Programme das Unwesentliche beachten müssen."

Obwohl sich diese Definition auf C bezieht, vermittelt sie kein Verständnis dafür, was Menschen in einer niedrigen Sprache sehen wollen. Verschiedene Eigenschaften lassen die Menschen die Sprache als niedrig betrachten. Stellen Sie sich eine Skala von Programmiersprachen mit Assembler an einem Ende und einer Schnittstelle zu einem Enterprise-Computer am anderen Ende vor. Niedrigstufige Sprachen sind näher an Eisen, während höherstufige Sprachen näher an der Denkweise der Menschen sind.

Um „näher an der Hardware“ zu sein, muss die Sprache Abstraktionen bereitstellen, die mit den Abstraktionen der Zielplattform übereinstimmen. Es ist leicht zu beweisen, dass C in PDP-11 eine einfache Sprache war. Die sequentielle Ausführung von Programmen, ein flacher Adressraum, selbst Operatoren vor und nach dem Inkrementieren, fiel perfekt auf die PDP-11-Adressierungsmodi.

Schnelle PDP-11-Emulatoren

Der Hauptgrund für die Schwachstellen von Spectre und Meltdown ist, dass die Entwickler der Prozessoren nicht nur schnelle Prozessoren, sondern auch schnelle Prozessoren mit PDP-11-Schnittstelle hergestellt haben. Dies ist wichtig, da C-Programmierer weiterhin glauben können, dass ihre Sprache der Hardware nahe kommt.

C-Code bietet einen meist sequentiellen abstrakten Automaten (bis C11 ist er vollständig sequentiell, wenn nicht standardmäßige Erweiterungen ausgeschlossen sind). Das Erstellen eines neuen Threads ist ein Aufruf einer Bibliotheksfunktion, eine Operation, die ziemlich teuer ist. Daher verlassen sich Prozessoren, die weiterhin C-Code ausführen möchten, auf Parallelität auf Befehlsebene (ILP). Sie analysieren benachbarte Operationen und führen parallel unabhängige Operationen durch. Dies verkompliziert die Prozessoren erheblich und führt zu einem erhöhten Stromverbrauch, ermöglicht es Programmierern jedoch, hauptsächlich sequentiellen Code zu schreiben. Im Gegensatz dazu erzielen Grafikprozessoren (GPUs) auf andere Weise eine hohe Leistung: Sie erfordern das Schreiben paralleler Programme.

Eine hohe Parallelität auf Befehlsebene ist die direkte Ursache für Spectre und Meltdown. Der moderne Intel-Prozessor führt bis zu 180 Befehle gleichzeitig aus (im Gegensatz zur sequentiellen abstrakten C-Maschine, die erwartet, dass der vorherige Befehl ausgeführt wird, bevor der nächste startet). Eine typische Heuristik des C-Codes zeigt, dass pro sieben Anweisungen durchschnittlich ein Zweig vorhanden ist. Wenn Sie die Anweisungspipeline vollständig halten möchten, müssen Sie die nächsten 25 Zweige erraten. Dies erhöht wiederum die Komplexität: Der Prozessor berechnet zuerst den falsch erratenen Zweig und gibt dann die Ergebnisse der Berechnungen aus, was sich negativ auf den Energieverbrauch auswirkt. Diese geworfenen Daten haben sichtbare indirekte Ergebnisse, die bei den Spectre- und Meltdown-Angriffen verwendet wurden.

Das Umbenennen von Registern verbraucht in modernen Prozessoren viel Energie und Chipfläche. Es kann nicht ausgeschaltet oder sein Energieverbrauch reduziert werden, was es in der dunklen Silizium- Ära unpraktisch macht, wenn die Transistoren niedrig sind, aber die beteiligten Transistoren sind eine wertvolle Ressource. Dieses Gerät fehlt in der GPU, wo die Parallelität durch die Verwendung von Threads erreicht wird, anstatt zu versuchen, anfänglich parallelen Code parallel auszuführen. Wenn die Anweisungen keine Abhängigkeiten aufweisen, die neu erstellt werden müssen, müssen die Register auch nicht umbenannt werden.

Betrachten Sie einen weiteren grundlegenden Teil des C-Designs: den flachen Speicher. Es existiert seit ein paar Jahrzehnten nicht mehr. Ein moderner Prozessor verfügt häufig über drei Caching-Ebenen zwischen Registern und Hauptspeicher, wodurch die Zeit für den Zugriff auf letztere reduziert wird.

Der Cache ist vor dem Programmierer verborgen und daher für C nicht zugänglich. Die effektive Verwendung des Caches ist eine der Möglichkeiten, die Codeausführung auf einem modernen Prozessor zu beschleunigen. Er ist jedoch vollständig vor der abstrakten Maschine verborgen, und Programmierer sind gezwungen, sich auf die Kenntnis der Details der Cache-Implementierung zu verlassen (z. B. diese zwei ausgerichteten 64-Bit-Dateien) Werte können in einer Zeile des Caches angezeigt werden, um effizienten Code zu schreiben.

C-Optimierung

Eine der gemeinsamen Eigenschaften von Low-Level-Sprachen ist die Geschwindigkeit. Insbesondere sollten sie ohne einen komplizierten Compiler leicht in schnellen Code zu übersetzen sein. Das Argument, dass ein ausreichend intelligenter Compiler eine Sprache schnell machen kann, wird von C-Befürwortern häufig ignoriert, wenn sie über andere Sprachen sprechen.

Leider können Sie mit einer einfachen Übersetzung keinen schnellen Code von C erhalten.
Prozessorarchitekten unternehmen heldenhafte Anstrengungen, um Chips zu erstellen, die C-Code schnell ausführen können. Die von Programmierern erwarteten Leistungsniveaus werden jedoch nur mithilfe unglaublich komplexer Optimierungen erreicht, die vom Compiler durchgeführt werden.
Der Clang-Compiler (einschließlich der entsprechenden Teile von LLVM) besteht aus etwa 2 Millionen Codezeilen. Für die Analyse und Transformation des Codes, die zur Beschleunigung von C erforderlich sind, werden ca. 200.000 Codezeilen benötigt (ohne Kommentare und Leerzeilen).

Um beispielsweise eine große Datenmenge in C zu verarbeiten, müssen Sie eine Schleife schreiben, die jedes Element nacheinander verarbeitet. Für die optimale Ausführung dieses Zyklus auf einem modernen Prozessor muss der Compiler bestimmen, dass die Iterationen des Zyklus unabhängig voneinander sind. Das Schlüsselwort "Einschränken" kann in diesem Fall hilfreich sein. Es stellt sicher, dass das Schreiben in einen Zeiger das Lesen von einem anderen Zeiger nicht beeinträchtigt. Diese Informationen in C sind viel eingeschränkter als in einer Sprache wie Fortran, was der Hauptgrund dafür ist, dass C sie nicht aus dem Hochleistungsrechnen herausholen konnte.

Nachdem der Compiler festgestellt hat, dass die Iterationen unabhängig voneinander sind, ist der nächste Schritt ein Versuch, das Ergebnis zu vektorisieren, da der Durchsatz moderner Prozessoren für vektorisierten Code vier- bis achtmal höher ist als für skalaren Code. Eine einfache Sprache für solche Prozessoren hätte ihre eigenen Vektortypen beliebiger Länge. Solche Typen sind in der LLVM-Zwischendarstellung vorhanden, da es immer einfacher ist, große Operationen mit Vektoren in mehrere kleine aufzuteilen, als größere Vektoroperationen zu konstruieren.

Zu diesem Zeitpunkt müssen sich Optimierer mit den C-Speicherregeln auseinandersetzen. C stellt sicher, dass Strukturen mit demselben Präfix austauschbar verwendet werden können, und bietet Zugriff auf versetzte Feldfelder von Strukturen in der Sprache. Dies bedeutet, dass der Compiler die Reihenfolge der Felder in der Struktur nicht ändern oder keine Ausrichtung hinzufügen kann, um die Vektorisierung zu verbessern (z. B. Transformieren einer Struktur von Arrays in ein Array von Strukturen oder umgekehrt). Dies ist normalerweise kein Problem in einfachen Sprachen, in denen es möglich ist, die Position von Feldern in der Struktur zu steuern, aber es erschwert die Aufgabe, C. zu beschleunigen.

C erfordert auch eine Ausrichtung am Ende der Struktur, da sichergestellt wird, dass in Arrays keine Ausrichtung erfolgt. Die Ausrichtung ist ein ziemlich komplexer Teil der C-Spezifikation, der schlecht mit anderen Teilen der Sprache interagiert. Beispielsweise sollten Sie in der Lage sein, zwei Strukturen mit der typenlosen Vergleichsmethode (dh der Funktion memcmp ()) zu vergleichen, sodass auch die Kopie der Struktur ausgerichtet werden muss. In einigen Fällen dauert das Kopieren der Ausrichtung sehr lange.

Berücksichtigen Sie die beiden grundlegenden Optimierungen, die der C-Compiler erzeugt: SROA (skalares Ersetzen von Aggregaten, skalares Ersetzen von Aggregaten) und Schleifenöffnung .

SROA versucht, Strukturen und Arrays mit fester Größe durch separate Variablen zu ersetzen. Auf diese Weise kann der Compiler den Zugriff auf sie unabhängig voneinander verarbeiten und die Operation ignorieren, wenn offensichtlich ist, dass das Ergebnis nicht verwendet wird. In einigen Fällen besteht der indirekte Effekt dieser Optimierung darin, die Ausrichtung zu entfernen.

Die zweite Optimierung, das Öffnen der Schleife, konvertiert die Schleife mit der Bedingung in eine Bedingung mit unterschiedlichen Schleifen in beiden Zweigen. Dies ändert die Ausführungsreihenfolge im Gegensatz zu der Behauptung, dass der Programmierer weiß, was in einer einfachen Sprache ausgeführt wird. Dies führt auch zu ernsthaften Problemen beim Umgang von C mit undefinierten Variablen und undefiniertem Verhalten.

In C hat eine nicht initialisierte Variable einen undefinierten Wert, der bei jedem Aufruf unterschiedlich sein kann. Dies ist wichtig, da Sie damit das verzögerte Recycling von Speicherseiten implementieren können. In FreeBSD teilt die malloc () - Implementierung dem System beispielsweise mit, dass die Seiten nicht mehr verwendet werden, und das System verwendet den ersten Eintrag auf der Seite als Beweis dafür, dass dies nicht der Fall ist. Das Aufrufen des neu zugewiesenen Speichers kann den alten Wert erhalten, dann kann das Betriebssystem die Speicherseite wiederverwenden und sie beim nächsten Schreiben an eine andere Stelle auf der Seite durch eine mit Null gefüllte Seite ersetzen. Der zweite Aufruf an derselben Stelle auf der Seite erhält den Wert Null.

Wenn die Bedingung einen undefinierten Wert verwendet, ist das Ergebnis ebenfalls nicht definiert - alles kann passieren. Stellen Sie sich eine Optimierung zum Öffnen einer Schleife vor, bei der eine Schleife null Mal ausgeführt wird. Im Original ist die gesamte Schleife toter Code. In der offenen Version gibt es jetzt eine Bedingung mit einer Variablen, die möglicherweise nicht initialisiert wird.
Infolgedessen kann toter Code in undefiniertes Verhalten konvertiert werden. Dies ist nur eine von vielen Optimierungen, die sich bei eingehenderer Untersuchung der Semantik von C als unzuverlässig herausstellen.

Am Ende können Sie den C-Code schnell laufen lassen, aber erst, nachdem Sie Tausende von Mannjahren damit verbracht haben, einen ausreichend intelligenten Compiler zu erstellen. Dies ist jedoch nur möglich, wenn bestimmte Regeln der Sprache verletzt werden. Mit Compiler-Erstellern können sich C-Programmierer vorstellen, dass sie Code schreiben, der "der Hardware nahe kommt", aber sie müssen Maschinencode generieren, der sich anders verhält, damit Programmierer weiterhin glauben, dass sie in einer schnellen Sprache schreiben.

C verstehen

Eines der grundlegenden Attribute einer einfachen Sprache ist, dass Programmierer leicht verstehen können, wie eine Maschine mit abstrakter Sprache auf eine physische Maschine übertragen wird. Dies war definitiv bei PDP-11 der Fall, wo C-Ausdrücke in eine oder zwei Anweisungen übersetzt wurden. In ähnlicher Weise legte der Compiler Variablen in Stapelsteckplätze und konvertierte einfache Typen in für PDP-11 verständliche.

Seitdem sind C-Implementierungen viel komplizierter geworden - um die Illusion aufrechtzuerhalten, dass C leicht auf eine Hardwareplattform portiert werden kann und schnell läuft. Im Jahr 2015 ergab eine Umfrage unter C-Programmierern, Compilerautoren und Mitgliedern des Standardisierungsausschusses, dass es Probleme beim Verständnis von C gab. Mit dieser Sprache kann eine Implementierung beispielsweise Strukturen (aber nicht Arrays) ausrichten, um sicherzustellen, dass alle Felder für die Zielplattform korrekt ausgerichtet sind. Wenn Sie diese Struktur mit Nullen füllen und dann für einige Felder einen Wert angeben, werden die Ausrichtungsbits Nullen enthalten? Laut der Umfrage waren sich 36% sicher, und 29% kannten die Antwort nicht. Abhängig vom Compiler und der Optimierungsstufe kann dies zutreffen (oder nicht).

Dies ist ein ziemlich triviales Beispiel, aber viele Programmierer geben entweder die falsche Antwort oder können überhaupt nicht antworten.

Wenn Sie Zeiger hinzufügen, wird die Semantik von C noch verwirrender. Das BCPL-Modell war ziemlich einfach: Alle Bedeutungen sind Wörter. Jedes Wort ist entweder Daten oder eine Adresse im Speicher. Der Speicher ist eine flache Anordnung von Zellen, die nach Adresse indiziert sind.

Modell C ermöglicht die Implementierung für verschiedene Plattformen, einschließlich segmentierter Architekturen, wobei der Zeiger aus Segment-IDs und Offsets sowie virtuellen Maschinen mit einem Garbage Collector bestehen kann. Die C-Spezifikation schränkt zulässige Zeigeroperationen ein, um Probleme mit solchen Systemen zu vermeiden. In der Antwort auf den Fehlerbericht 260 wird der Ursprung des Zeigers erwähnt:

„Implementierungen können dem Ursprung einer Reihe von Bits folgen und diejenigen, die einen undefinierten Wert enthalten, anders behandeln als diejenigen, die einen bestimmten Wert enthalten. "Sie können Zeiger je nach Herkunft unterschiedlich behandeln, auch wenn sie hinsichtlich ihres Bitwerts gleich sind."

Leider fehlt das Wort "Ursprung" in der C11-Spezifikation, sodass die Compiler selbst entscheiden, was es bedeutet. GCC und Clang unterscheiden sich beispielsweise darin, ob der Zeiger, der in die Ganzzahl und zurück konvertiert wurde, seinen Ursprung behält. Compiler können entscheiden, dass zwei Zeiger auf die Ergebnisse von malloc () beim Vergleich immer ein negatives Ergebnis liefern, selbst wenn sie auf dieselbe Adresse verweisen.

Diese Missverständnisse sind nicht rein akademisch. Beispielsweise wurden bereits Schwachstellen beobachtet, die auf das Überlaufen einer vorzeichenbehafteten Ganzzahl (undefiniertes Verhalten in C) oder das Dereferenzieren eines Zeigers vor dem Überprüfen auf NULL zurückzuführen sind , obwohl dem Compiler mitgeteilt wurde, dass der Zeiger nicht NULL sein kann.

Wenn es solche Probleme gibt, ist es schwierig zu erwarten, dass ein Programmierer vollständig versteht, wie ein C-Programm in die entsprechende Architektur übersetzt wird.

Einführung eines Prozessors nicht für C.

Die vorgeschlagenen Patches zum Schutz vor Spectre und Meltdown führen zu erheblichen Leistungseinbußen, wodurch alle Errungenschaften der Mikroarchitektur im letzten Jahrzehnt zunichte gemacht werden. Vielleicht ist es an der Zeit, nicht mehr darüber nachzudenken, wie C-Code schneller gemacht werden kann, sondern über neue Programmiermodelle auf Prozessoren nachzudenken, die auf Geschwindigkeit ausgelegt sind.

Es gibt viele Beispiele für Architekturen, die sich nicht auf traditionellen C-Code konzentriert haben und von denen man sich inspirieren lassen kann. Multithreading-orientierte Prozessoren wie Sun / Oracle UltraSPARC Tx benötigen beispielsweise nicht so viel Cache, um ihre Aktoren zu beschäftigen. Forschungsprozessoren haben dieses Konzept auf eine sehr große Anzahl von Hardware-geplanten Threads erweitert. Die Schlüsselidee ist, dass der Prozessor mit genügend Threads die Threads anhalten kann, die auf Daten warten, und die Aktuatoren mit Anweisungen von anderen Threads füllen kann. Das Problem ist, dass C-Programme normalerweise nur sehr wenige Threads haben.

ARMs SVE (Scalar Vector Extensions, Scalar Vector Extensions) ist eine weitere ähnliche Arbeit von Berkeley, die einen Blick auf die verbesserte Schnittstelle zwischen Programm und Hardware bietet. Regelmäßige Vektorisierungsblöcke implementieren Operationen mit Vektoren fester Größe und erwarten, dass der Compiler den Algorithmus an die angegebene Größe anpasst. Im Gegensatz dazu fordert die SVE-Schnittstelle den Programmierer auf, den Grad der Parallelität unabhängig zu beschreiben, und erwartet, dass die Hardware ihn an die verfügbaren Aktuatoren anpasst. Die Verwendung in C ist schwierig, da der Auto-Vektorisierer die Parallelität basierend auf den Schleifen im Code berechnen muss.

Caches sind groß, aber dies ist nicht der einzige Grund für ihre Komplexität. Das Cache-Kohärenz- Unterstützungsprotokoll ist eine der komplexesten Komponenten eines modernen Prozessors. Die größte Schwierigkeit besteht darin, eine Sprache zu pflegen, in der Daten gemeinsam genutzt und verändert werden können. Als entgegengesetztes Beispiel können wir eine abstrakte Maschine im Erlang-Stil verwenden, bei der jedes Objekt entweder lokal oder unveränderlich ist. Das Cache-Kohärenzprotokoll für ein solches System hätte nur zwei Fälle: veränderbare Daten und gemeinsam genutzte Daten. Der Cache des Programmstroms, der auf einen anderen Prozessor übertragen wurde, muss explizit deaktiviert werden. Dies ist jedoch eine relativ seltene Operation.

Unveränderliche Objekte können Caches noch weiter vereinfachen und einige Vorgänge billiger machen. In einem Maxwell-Projekt von Sun Labs wurde festgestellt, dass Objekte im Cache und kürzlich erstellte Objekte fast immer gleich sind. Wenn Objekte sterben, bevor sie aus dem Cache ausgeschlossen werden, können Sie sie nicht in den Hauptspeicher schreiben und so Energie sparen. Das Maxwell-Projekt schlug einen Garbage Collector vor, der im Cache funktioniert und es Ihnen ermöglicht, Speicher schnell wiederzuverwenden. Mit unveränderlichen Objekten auf dem Heap und dem veränderlichen Stapel wird der Garbage Collector zu einer sehr einfachen Zustandsmaschine, die leicht in die Hardware implementiert werden kann und es Ihnen ermöglicht, einen relativ kleinen Cache effizient zu verwenden.

Ein Prozessor, der ausschließlich auf Geschwindigkeit und nicht auf den Kompromiss zwischen Geschwindigkeit und C-Unterstützung ausgelegt ist, sollte wahrscheinlich eine große Anzahl von Threads unterstützen, große Vektorisierungsblöcke und ein einfacheres Speichermodell aufweisen. Es wird schwierig sein, C-Code auf einem solchen Prozessor auszuführen, daher ist es angesichts des Volumens des alten C-Codes in der Welt unwahrscheinlich, dass es kommerziellen Erfolg hat.

Im Bereich der Softwareentwicklung gibt es einen Mythos, dass parallele Programmierung schwierig ist. Alan Kay wäre sehr überrascht, dies zu hören: Er brachte den Kindern bei, das Schauspielermodell zu verwenden, mit dem sie Programme in mehr als 200 Streams schrieben. Dies ist auch Erlang-Programmierern unbekannt, die häufig Programme mit Tausenden von parallelen Komponenten schreiben. Es ist richtiger zu sagen, dass parallele Programmierung in einer Sprache mit einer abstrakten Maschine wie C schwierig ist. Wenn Sie auf die Dominanz paralleler Hardware achten (von Mehrkernprozessoren bis zu Mehrkern-GPUs), ist dies nur eine andere Möglichkeit zu sagen, dass C für moderne Hardware nicht geeignet ist Bereitstellung.