Welche Programmiertechniken verwenden Sie zur Optimierung von C-Programmen? [closed]

Vor einigen Jahren war ich in einem Gremium, das Kandidaten für eine relativ hochrangige Stelle als Embedded-C-Programmierer interviewte.

Eine der Standardfragen, die ich gestellt habe, betraf Optimierungstechniken. Ich war ziemlich überrascht, dass einige der Kandidaten keine Antworten hatten.

Also, um eine Liste für die Nachwelt zusammenzustellen – welche Techniken und Konstrukte verwenden Sie normalerweise, wenn Sie C-Programme optimieren?

Antworten zur Optimierung für Geschwindigkeit und Größe werden beide akzeptiert.

Das Wichtigste zuerst – optimieren Sie nicht zu früh. Es ist nicht ungewöhnlich, Zeit damit zu verbringen, einen Codeabschnitt sorgfältig zu optimieren, nur um festzustellen, dass dies nicht der Engpass war, von dem Sie dachten, dass er sein würde. Oder anders ausgedrückt: „Bevor du es schnell machst, lass es funktionieren“

Untersuchen Sie, ob es eine Option zum Optimieren des Algorithmus gibt, bevor Sie den Code optimieren. Es ist einfacher, eine Leistungsverbesserung durch die Optimierung eines schlechten Algorithmus zu finden, als den Code zu optimieren, nur um ihn dann wegzuwerfen, wenn Sie den Algorithmus trotzdem ändern.

Und finden Sie heraus, warum Sie überhaupt optimieren müssen. Was versuchst du zu erreichen? Wenn Sie beispielsweise versuchen, die Reaktionszeit auf ein Ereignis zu verbessern, prüfen Sie, ob es eine Möglichkeit gibt, die Ausführungsreihenfolge zu ändern, um die zeitkritischen Bereiche zu minimieren. Wenn Sie beispielsweise versuchen, die Reaktion auf einen externen Interrupt zu verbessern, können Sie sich in der Totzeit zwischen Ereignissen vorbereiten?

Wenn Sie entschieden haben, dass Sie den Code optimieren müssen, welchen Teil optimieren Sie? Verwenden Sie einen Profiler. Richten Sie Ihre Aufmerksamkeit (zunächst) auf die Bereiche, die am häufigsten verwendet werden.

Was können Sie also gegen diese Bereiche tun?

• Zustandsprüfung minimieren. Das Prüfen von Bedingungen (z. B. das Beenden von Bedingungen für Schleifen) ist Zeit, die nicht für die eigentliche Verarbeitung aufgewendet wird. Die Zustandsprüfung kann mit Techniken wie Loop-Unrolling minimiert werden.
• Unter Umständen kann die Bedingungsprüfung auch durch die Verwendung von Funktionszeigern eliminiert werden. Wenn Sie beispielsweise einen Zustandsautomaten implementieren, stellen Sie möglicherweise fest, dass es effizienter ist, die Handler für einzelne Zustände als kleine Funktionen (mit einem einheitlichen Prototyp) zu implementieren und den “nächsten Zustand” durch Speichern des Funktionszeigers des nächsten Handlers zu speichern, als eine große switch-Anweisung mit dem in den einzelnen case-Anweisungen implementierten Handler-Code. YMMV.
• Funktionsaufrufe minimieren. Funktionsaufrufe sind normalerweise mit einer Belastung des Kontextspeicherns verbunden (z. B. Schreiben lokaler Variablen, die in Registern enthalten sind, auf den Stapel, Speichern des Stapelzeigers). Wenn Sie also keinen Aufruf durchführen müssen, sparen Sie Zeit. Eine Option (wenn Sie auf Geschwindigkeit und nicht auf Speicherplatz optimieren) besteht darin, Inline-Funktionen zu verwenden.
• Wenn Funktionsaufrufe unvermeidlich sind, minimieren Sie die Daten, die an die Funktionen übergeben werden. Beispielsweise ist das Übergeben von Zeigern wahrscheinlich effizienter als das Übergeben von Strukturen.
• Wählen Sie bei der Geschwindigkeitsoptimierung Datentypen, die der nativen Größe Ihrer Plattform entsprechen. Beispielsweise ist es auf einem 32-Bit-Prozessor wahrscheinlich effizienter, 32-Bit-Werte als 8- oder 16-Bit-Werte zu manipulieren. (Nebenbemerkung – es lohnt sich zu überprüfen, ob der Compiler das tut, was Sie denken. Ich hatte Situationen, in denen ich festgestellt habe, dass mein Compiler darauf bestand, 16-Bit-Arithmetik mit 8-Bit-Werten mit allen Konvertierungen nach und von durchzuführen mit ihnen gehen)
• Finden Sie Daten, die vorberechnet werden können, und berechnen Sie sie entweder während der Initialisierung oder (noch besser) zur Kompilierzeit. Wenn Sie beispielsweise einen CRC implementieren, können Sie Ihre CRC-Werte entweder im laufenden Betrieb berechnen (unter direkter Verwendung des Polynoms), was großartig für die Größe (aber schrecklich für die Leistung) ist, oder Sie können eine Tabelle mit allen Zwischenwerten erstellen – was a ist viel schnellere Implementierung, zu Lasten der Größe.
• Lokalisieren Sie Ihre Daten. Wenn Sie einen Datenklumpen manipulieren, kann Ihr Prozessor die Dinge möglicherweise beschleunigen, indem er alles im Cache speichert. Und Ihr Compiler kann möglicherweise kürzere Anweisungen verwenden, die für lokalisiertere Daten geeignet sind (z. B. Anweisungen, die 8-Bit-Offsets anstelle von 32 Bit verwenden).
• Lokalisieren Sie in gleicher Weise Ihre Funktionen. Aus denselben Gründen.
• Erarbeiten Sie die Annahmen, die Sie über die von Ihnen durchgeführten Operationen treffen können, und finden Sie Wege, diese auszunutzen. Wenn beispielsweise auf einer 8-Bit-Plattform die einzige Operation, die Sie auf einem 32-Bit-Wert ausführen, ein Inkrement ist, stellen Sie möglicherweise fest, dass Sie es besser machen können als der Compiler, indem Sie speziell für diesen Zweck Inlining (oder Erstellen eines Makros) vornehmen. anstatt eine normale arithmetische Operation zu verwenden.
• Vermeiden Sie teure Anleitungen – Teilung ist ein Paradebeispiel.
• Das Schlüsselwort “register” kann Ihr Freund sein (obwohl Ihr Compiler hoffentlich eine ziemlich gute Vorstellung von Ihrer Verwendung von Registern hat). Wenn Sie “register” verwenden, müssen Sie wahrscheinlich zuerst die lokalen Variablen deklarieren, die Sie “registrieren” möchten.
• Seien Sie konsistent mit Ihren Datentypen. Wenn Sie Arithmetik mit einer Mischung von Datentypen durchführen (z. B. shorts und ints, doubles und floats), fügt der Compiler für jede Nichtübereinstimmung implizite Typkonvertierungen hinzu. Dies sind verschwendete CPU-Zyklen, die möglicherweise nicht erforderlich sind.

Die meisten der oben aufgeführten Optionen können im Rahmen der normalen Praxis ohne negative Auswirkungen verwendet werden. Wenn Sie jedoch wirklich versuchen, die beste Leistung herauszuholen: – Untersuchen Sie, wo Sie die Fehlerprüfung (sicher) deaktivieren können. Es wird nicht empfohlen, aber es spart Ihnen etwas Platz und Zyklen. – Stellen Sie Teile Ihres Codes in Assembler von Hand her. Das bedeutet natürlich, dass Ihr Code nicht mehr portabel ist, aber wo das kein Problem ist, können Sie hier Einsparungen finden. Beachten Sie jedoch, dass beim Verschieben von Daten in und aus den Registern, die Ihnen zur Verfügung stehen, möglicherweise Zeit verloren geht (z. B. um die Registernutzung Ihres Compilers zu befriedigen). Seien Sie sich auch bewusst, dass Ihr Compiler alleine ziemlich gute Arbeit leisten sollte. (Natürlich gibt es Ausnahmen)

Wie alle anderen gesagt haben: profil, profil profil.

Was die eigentlichen Techniken betrifft, so wurde eine meiner Meinung nach noch nicht erwähnt:

Heiße und kalte Datentrennung: Das Bleiben im Cache der CPU ist unglaublich wichtig. Eine Möglichkeit, dies zu erreichen, besteht darin, Ihre Datenstrukturen in Abschnitte mit häufigem Zugriff (“heiß”) und selten aufgerufene Abschnitte (“kalt”) aufzuteilen.

Ein Beispiel: Angenommen, Sie haben eine Struktur für einen Kunden, die in etwa so aussieht:

struct Customer
{
    int ID;
    int AccountNumber;
    char Name[128];
    char Address[256];
};

Customer customers[1000];

Nehmen wir nun an, dass Sie häufig auf die ID und die Kontonummer zugreifen möchten, aber nicht so sehr auf den Namen und die Adresse. Was Sie tun würden, ist, es in zwei Teile aufzuteilen:

struct CustomerAccount
{
    int ID;
    int AccountNumber;
    CustomerData *pData;
};

struct CustomerData
{
    char Name[128];
    char Address[256];
};

CustomerAccount customers[1000];

Auf diese Weise ist jeder Eintrag nur 12 Byte groß, wenn Sie Ihr Array “Kunden” durchlaufen, und Sie können viel mehr Einträge in den Cache einfügen. Dies kann ein großer Gewinn sein, wenn Sie es auf Situationen wie die innere Schleife einer Rendering-Engine anwenden können.

Meine Lieblingstechnik ist die Verwendung eines guten Profilers. Ohne ein gutes Profil, das Ihnen sagt, wo der Engpass liegt, werden Ihnen keine Tricks und Techniken helfen.

Die häufigsten Techniken, denen ich begegnet bin, sind:

• Schleife abrollen
• Loop-Optimierung für besseren Cache-Prefetch (dh N Operationen in M ​​Zyklen statt NxM Einzeloperationen)
• Datenabgleich
• Inline-Funktionen
• handgefertigte Asm-Schnipsel

Was allgemeine Empfehlungen betrifft, so sind die meisten bereits erklingen:

• Wählen Sie bessere Algos
• Profiler verwenden
• Optimieren Sie nicht, wenn es keine Leistungssteigerung von 20-30 % bringt

Für Low-Level-Optimierung:

1. START_TIMER/STOP_TIMER-Makros von ffmpeg (Genauigkeit auf Taktniveau zur Messung von beliebigem Code).
2. Oprofile natürlich für die Profilerstellung.
3. Enorme Mengen an handcodierter Assemblierung (führen Sie einfach ein wc -l im /common/x86-Verzeichnis von x264 aus und denken Sie dann daran, dass der größte Teil des Codes auf Vorlagen basiert).
4. Sorgfältige Codierung im Allgemeinen; kürzerer Code ist normalerweise besser.
5. Intelligente Low-Level-Algorithmen, wie der 64-Bit-Bitstream-Writer, den ich geschrieben habe und der nur ein einziges if und kein anderes verwendet.
6. Explizite Schreibkombination.
7. Unter Berücksichtigung wichtiger seltsamer Aspekte von Prozessoren, wie z Intels Cacheline-Split-Problem.
8. Fälle finden, wo man verlustfrei oder nahezu verlustfrei vorzeitig kündigen kann, wo die Frühkündigungsprüfung viel weniger kostet als die Geschwindigkeit, die man daraus gewinnt.
9. Tatsächlich eingebettete Assemblierung für Aufgaben, die für die x86-SIMD-Einheit weitaus besser geeignet sind, wie z. B. Medianberechnungen (erfordert Kompilierzeitprüfung für MMX-Unterstützung).

• Verwenden Sie in erster Linie einen besseren/schnelleren Algorithmus. Es hat keinen Sinn, Code zu optimieren, der von Natur aus langsam ist.
• Wenn Sie auf Geschwindigkeit optimieren, tauschen Sie Speicher gegen Geschwindigkeit ein: Nachschlagetabellen mit vorberechneten Werten, Binärbäume, schreiben Sie schnellere benutzerdefinierte Implementierungen von Systemaufrufen …
• Wenn Sie Geschwindigkeit gegen Speicher eintauschen: Verwenden Sie In-Memory-Komprimierung

Vermeiden Sie die Verwendung des Haufens. Verwenden Sie obstacks oder pool-allocator für Objekte gleicher Größe. Legen Sie kleine Dinge mit kurzer Lebensdauer auf den Stapel. Alloca existiert noch.