Welche Codierungstechniken verwenden Sie zur Optimierung von C-Programmen?

Erste Sachen zuerst - nicht optimieren zu früh. Es ist nicht ungewöhnlich, Zeit zu verbringen, die gezielt die Optimierung ein Stück code, nur um herauszufinden, dass es war nicht der Engpass, dass Sie dachte, es war. Oder, um es anders zu sagen ", Bevor Sie es schnell, damit es funktioniert"

Untersuchen, ob es irgendeine option für die Optimierung des Algorithmus vor der Optimierung des Codes. Es wird einfacher sein, zu finden, eine Verbesserung der Leistung durch optimieren eines schlechten Algorithmus, als es ist, optimieren Sie den code, nur dann, um es wegzuwerfen, wenn Sie ändern Sie den Algorithmus trotzdem.

Und arbeiten Sie heraus, warum Sie benötigen, zu optimieren, in den ersten Platz. Was wollen Sie erreichen? Wenn Sie versuchen, sagen wir, zur Verbesserung der Reaktionszeit auf ein Ereignis, wenn es eine Möglichkeit zum ändern der Reihenfolge der Ausführung zu minimieren die Zeit, die kritischen Bereiche. Zum Beispiel, wenn Sie versuchen zur Verbesserung der Reaktion auf den externen interrupt kann man tun, irgendwelche Vorbereitung in der Toten Zeit zwischen den Ereignissen?

Sobald Sie sich entschieden haben, die Sie brauchen, um zu optimieren, den code, der die bit-tun Sie optimieren? Einen profiler verwenden. Konzentrieren Sie Ihre Aufmerksamkeit (zunächst) auf die Bereiche, die am häufigsten verwendet werden.

Also, was können Sie tun, um jene Bereiche?

• minimieren Zustand prüfen. Überprüfen von Bedingungen (zB. Abbruch-Bedingungen for-Schleifen) ist die Zeit, die nicht ausgegeben eigentliche Verarbeitung. Zustand prüfen können minimiert werden, mit Techniken wie loop-unrolling.
• In einigen Fällen die Bedingung kann eine überprüfung auch beseitigt werden durch die Verwendung von Funktionszeigern. Zum Beispiel, wenn Sie die Implementierung einer state-Maschine, die Sie finden können, dass die Umsetzung der Handler für die einzelnen Staaten als kleinen Funktionen (mit einer einheitlichen Prototyp) und speichern Sie die "next state", indem die Funktion der Zeiger des nächsten hf ist effizienter, als mit einem großen switch-Anweisung mit dem handler-code implementiert in den einzelnen case-Anweisungen. YMMV.
• Minimierung der Funktionsaufrufe. Funktion Anrufe in der Regel tragen eine Last von Kontext zu speichern (zB. schreiben von lokalen Variablen, die in Registern auf dem stack speichern der stack-pointer), so dass, wenn Sie nicht haben, um einen Anruf zu tätigen, dies ist die Zeit gespeichert. Eine option (wenn Sie die Optimierung für Geschwindigkeit und nicht der Raum) ist das verwenden von inline-Funktionen.
• Wenn Funktionsaufrufe sind unvermeidlich minimieren die Daten, die an die Funktionen übergeben werden. Zum Beispiel übergabe von Zeigern ist wahrscheinlich effizienter als die übergabe von Strukturen.
• Wenn die Optimierung für die Geschwindigkeit wählen Sie die Datentypen, die die native Größe für Ihre Plattform. Zum Beispiel auf einem 32-bit Prozessor ist es wahrscheinlich effizienter zu manipulieren 32bit-Werte als 8-oder 16-bit-Werte. (Randbemerkung - es lohnt sich zu überprüfen, dass der compiler das macht, was Sie denken, es ist. Ich habe Situationen gehabt, wo ich entdeckt habe, dass mein compiler darauf bestanden, dabei 16-bit arithmetische Operationen auf 8-bit-Werte, die mit allen von und conversions mit Ihnen zu gehen)
• Finden Daten vorberechnet, und entweder berechnen, die während der Initialisierung oder (noch besser) zur compile-Zeit. Zum Beispiel bei der Implementierung einer CRC-entweder können Sie berechnen Sie Ihre CRC-Werte on-the-fly (mit dem Polynom direkt) das ist toll für die Größe (aber schrecklich für die Leistung), oder Sie erstellen eine Tabelle aller Zwischenwerte - das ist eine viel schnellere Implementierung, zum Nachteil der Größe.
• Lokalisieren Ihre Daten. Wenn Sie die Bearbeitung eines blob-Daten oft Ihr Prozessor kann in der Lage sein, die Dinge zu beschleunigen, indem Sie speichern Sie alle im cache. Und dein compiler kann in der Lage sein, kürzere Anweisungen, die geeignet sind, die zu mehr lokalisierten Daten (zB. Anweisungen, verwenden Sie 8 bit-offsets statt 32 bit)
• In die gleiche Richtung, zu lokalisieren Ihre Funktionen. Aus den gleichen Gründen.
• Arbeiten aus den Annahmen, die Sie machen können über die Operationen, die Sie durchführen und Wege finden, Sie auszubeuten. Z. B. auf einem 8-bit-Plattform, wenn die einzige operation, die auf Sie sind auf 32-bit-Wert ist erhöht, können Sie feststellen, dass Sie tun können, besser als der compiler inlining (oder erstellen Sie ein makro), die speziell für diesen Zweck eher, als mit einem normalen arithmetischen operation.
• Vermeiden Sie teure Anweisungen - division ist ein gutes Beispiel.
• Die "register" - Schlüsselwort kann dein Freund sein (obwohl hoffentlich dein compiler hat eine ziemlich gute Vorstellung über den register usage). Wenn du gehst zu verwenden, "registrieren" es ist wahrscheinlich, dass Sie haben zu erklären, dass die lokalen Variablen, die Sie wollen, "registrieren"ed zuerst.
• Im Einklang mit Ihren Datentypen. Wenn Sie dabei sind arithmetische Operationen auf eine Mischung von Datentypen (zB. shorts und ints, doubles und floats), dann ist der compiler hinzufügen implizite Typ-Konvertierungen für jede Abweichung. Dies ist verschwendet cpu-Zyklen, die möglicherweise nicht erforderlich.

Meisten der oben aufgeführten Optionen können verwendet werden, als Teil der normalen Praxis ohne Nachwirkungen. Aber wenn Sie wirklich versuchen, zu Fristen die beste Leistung:
- Untersuchen Sie, wo Sie können (sicher) deaktivieren der Fehlerüberprüfung. Es ist nicht empfohlen, aber es sparen Sie einiges an Platz und Zyklen.
- Hand-Handwerk Teile des Codes in assembler. Das bedeutet natürlich, dass Ihr code ist nicht mehr tragbar, aber wo ist das nicht ein Problem, das Sie finden können Einsparungen hier. Seien Sie sich aber bewusst, dass es möglicherweise Zeit verloren, die das verschieben von Daten in und aus dem Register, die Sie zur Verfügung haben (ie. zu befriedigen, registrieren Sie Nutzung von Ihr compiler). Auch bewusst sein, dass Ihr compiler sollte machen einen ziemlich guten job auf seine eigene. (natürlich gibt es Ausnahmen)

InformationsquelleAutor der Antwort Andrew Edgecombe

Meine Lieblings-Technik ist die Verwendung einer guten profiler. Ohne ein gutes Profil, sagen Ihnen, wo der Engpass liegt, keine tricks und Techniken gehen, um Ihnen zu helfen.

InformationsquelleAutor der Antwort 1800 INFORMATION

Für low-level-Optimierung:

1. START_TIMER/STOP_TIMER Makros von ffmpeg (clock-Pegel Genauigkeit für die Messung von code).
2. Oprofile, natürlich, für die Profilerstellung.
3. Enorme Mengen von hand-codiert Montage (nur ein wc -l auf x264 /common/x86-Verzeichnis, und dann denken Sie daran, die meisten der code Vorlagen).
4. Sorgfältige Codierung im Allgemeinen; kürzere code ist in der Regel besser.
5. Smart low-level-algorithmen, wie zum Beispiel die 64-bit bitstream Schriftsteller, den ich schrieb, verwendet nur ein einziges wenn und kein anderes.
6. Explizite write-combining.
7. Unter Berücksichtigung wichtiger seltsam Aspekte der Prozessoren, wie Intel cacheline split Problem.
8. Suche nach Fällen, in denen kann man verlustfrei oder fast verlustfrei machen ein frühes Ende, wo der Anfang-Kündigung prüfen kostet viel weniger als die Geschwindigkeit, erhält man von ihm.
9. Tatsächlich inline-assembly für Aufgaben, die weit mehr geeignet, um die x86-SIMD-Einheit, wie median-Berechnung (benötigt compile-time check für MMX-support).

InformationsquelleAutor der Antwort Dark Shikari

Vermeiden Sie die Verwendung des heap. Verwenden obstacks oder pool-Zuweisung für identisch große Objekte. Setzen Sie kleine Dinge mit kurzer Lebensdauer auf den Stapel. alloca noch existiert.

InformationsquelleAutor der Antwort Nils Pipenbrinck

Als meine-Anwendungen in der Regel brauchen nicht viel CPU-Zeit, die durch design, konzentriere ich mich auf die Größe meiner Binärdateien auf der Festplatte und im Arbeitsspeicher. Was ich mache, meist ist auf der Suche nach statisch dimensionierte arrays und ersetzt Sie mit dynamisch zugewiesenen Speicher, wo es sich lohnt, den Mehraufwand der freien ' Ing den Speicher später. Zu reduzieren die Größe der binären, Suche ich für große arrays initialisiert werden zur compile-Zeit, und setzen Sie die initializiation zur Laufzeit.

char buf[1024] = { 0, };
/* becomes: */
char buf[1024];
memset(buf, 0, sizeof(buf));

Dadurch entfernen Sie die 1024 null-bytes aus den Binärdateien .DATA-Abschnitt und stattdessen erstellen Sie den Puffer auf dem stack zur Laufzeit und füllen Sie es mit Nullen.

EDIT: achja, und ich mag, um cache-Sachen. Es ist nicht C-spezifisch, aber je nachdem, was Sie sind, Zwischenspeichern, kann es geben Ihnen einen großen Schub in der Leistung.

PS: Bitte lassen Sie uns wissen Sie, wenn Ihre Liste fertig ist, ich bin sehr neugierig. 😉

InformationsquelleAutor der Antwort jkramer

Etwas anderes, was nicht erwähnt wurde:

• Kennen Ihre Anforderungen: nicht optimiert für Situationen, die kaum oder nie passieren, konzentrieren sich auf die meisten bang für die buck

InformationsquelleAutor der Antwort Sklivvz

Schwer zu fassen ...

• Datenstrukturen:

  • Teilung einer Datenstruktur, die je nach Fall der Nutzung ist extrem wichtig. Es ist üblich, um zu sehen, eine Struktur, die enthält Daten, auf die zugegriffen wird, basierend auf einer flow control. Diese situation kann zu senken signifikant die cache-Nutzung.
  • Zu berücksichtigen cache-line-Größe und prefetch-Regeln.
  • Auf die Reihenfolge der Mitglieder der Struktur zu erhalten, die einen sequenziellen Zugriff, um Sie aus deinem code

• Algorithmen:

  • Nehmen Sie sich Zeit, um über Ihr problem zu denken und zu finden, den richtigen Algorithmus.
  • Wissen, die Grenzen der Algorithmus, den Sie wählen (von einer radix-sort-quick-sort für 10 Elemente, die sortiert werden vielleicht nicht die beste Wahl).

• Low-Pegel:

  • Wie für die neuesten Prozessoren ist es nicht empfehlenswert, zu entrollen einer Schleife, hat einen kleinen Körper. Der Prozessor bietet einen eigenen Mechanismus zur Erkennung und Kurzschluss gesamten Abschnitt der pipeline.
  • Vertrauen der HW-prefetcher. Natürlich, wenn Sie Ihre Daten-Strukturen sind gut gestaltet 😉
  • Kümmern uns um Ihre L2-cache-Zeile findet.
  • Zu reduzieren versuchen, so viel wie möglich der lokalen Arbeit Ihre Anwendung, da die Prozessoren sich auf kleinere caches pro-Kerne (C2D genossen ein 3 MB pro core max, wo iCore7 wird eine max 256 KB pro Kern + 8MB shared für alle Kerne für einen quad-core-sterben.).

Das wichtigste von allen: Messen Sie früh, Messen oft und nie macht Annahmen, die Basis Ihres Denkens und Optimierungen auf Daten abgerufen, die von einem profiler (bitte verwenden Sie PTU).

Ein weiterer Hinweis, performance ist der Schlüssel für den Erfolg einer Anwendung und sollte berücksichtigt werden, die zur design-Zeit, und Sie sollten klare performance-Ziele.

Dies ist bei weitem nicht erschöpfend, sondern soll eine interessante Basis.

InformationsquelleAutor der Antwort Fabien Hure

Sammeln profile der code-Ausführung erhalten Sie 50% von dem Weg dorthin. Die anderen 50% befasst sich mit der Analyse dieser Berichte.

Weiter, wenn Sie GCC oder VisualC++ verwenden, können Sie "profile guided optimization", wo der compiler nehmen info aus früheren Ausführungen und verlegen Anweisungen, um die CPU glücklicher.

InformationsquelleAutor der Antwort Frank Krueger

Auf den meisten embedded-system i gearbeitet, es wurde kein profiling-tools, so ist es schön zu sagen, verwendet profiler aber nicht sehr praktisch.

Erste Regel in der speed-Optimierung ist - finden Sie Ihre kritischen Pfad.

In der Regel finden Sie, dass dieser Pfad nicht so lang und nicht so Komplex. Es ist schwer zu sagen, in generischer Art und Weise, wie Sie diese optimieren, es hängt davon ab, was machst du und was steht in Ihrer macht, das zu tun. Zum Beispiel, Sie wollen in der Regel vermeiden, memcpy, die auf den kritischen Pfad, also immer müssen Sie die Verwendung von DMA oder optimieren, aber was ist, wenn man hw nicht DMA ? überprüfen Sie, ob memcpy Umsetzung ist die beste, wenn nicht das schreiben.

Verwenden Sie keine dynamische Zuordnung an alle in der embedded-aber wenn Sie aus irgendeinem Grund tun Sie es nicht im kritischen Pfad.

Organisieren Sie Ihre thread-Prioritäten richtig, was richtig ist echte Frage, und es ist klar spezifisches system.

Wir verwenden sehr einfache tools zum analysieren der Flasche-Hals, einfaches makro, speichern der Zeit-Stempel und index. Paar (2-3) wird in 90% der Fälle finden, wo Sie Ihre Zeit verbringen.

Und der Letzte ist code-review sehr wichtig. In den meisten Fällen vermeiden wir performance-problem beim code-review sehr effektiven Art und Weise 🙂

InformationsquelleAutor der Antwort Ilya

Manchmal müssen Sie entscheiden, ob Sie mehr Platz oder mehr Geschwindigkeit, die Sie nach sich ziehen wird fast gegenüber Optimierungen. Zum Beispiel, um das meiste aus Ihnen Raum, Sie pack Strukturen z.B. #pragma pack(1) und verwenden Sie bit-Felder in den Strukturen. Für mehr Geschwindigkeit, die Sie packen zu richten, wobei die Prozessoren bevorzugt und vermeiden bitfields.

Ein weiterer trick ist die Auswahl des richtigen re-sizing algorithmen für die wachsende arrays via realloc, oder noch besser schreiben Sie Ihre eigenen heap-manager, basierend auf Ihren speziellen Anwendungsfall. Gehen Sie nicht davon, die eine, die kommt mit dem compiler ist die bestmögliche Lösung für jede Anwendung.

InformationsquelleAutor der Antwort Shane MacLaughlin

Große Listen. Ich will nur hinzufügen, einen Tipp, den ich nicht sah, in die oben genannten Listen, die in einigen Fällen kann Ausbeute große Optimierung für minimalen Kosten.

• bypass linker

  wenn Sie haben eine Anwendung gliedert sich in zwei Dateien, sagen main.c und lib.c, in vielen Fällen können Sie einfach fügen Sie eine \#include "lib.c" in Ihrem Haupt.c, die vollständig bypass linker und ermöglichen viel effizienter die Optimierung für den compiler.

Der gleiche Effekt kann erreicht werden, Optimierung der Abhängigkeiten zwischen den Dateien, aber die Kosten für die änderungen ist in der Regel höher.

InformationsquelleAutor der Antwort kriss

Ich würde empfehlen, die Optimierung der Nutzung effizienter algorithmen, und es nicht wie ein nachträglicher Einfall, aber code es so von Anfang an. Lassen Sie den compiler arbeiten Sie heraus, die details über die kleinen Dinge, die, wie Sie weiß mehr über den Ziel-Prozessor, als Sie tun.

Zum einen, ich selten verwenden, loops zu suchen, die Dinge, die ich hinzufügen von Elementen zu einer hashtable und dann verwenden der hashtable-lookup die Ergebnisse.

Zum Beispiel, Sie haben einen string zu suchen und dann 50 möglichen Werte. Also anstatt das zu tun, 50 strcmps, fügen Sie alle 50 Zeichenketten zu einer hashtable und geben Sie jedem eine eindeutige Nummer ( Sie müssen nur einmal gemacht werden ). Dann Suche die Ziel-string in hashtable und haben einen großen Schaltschrank mit allen 50 Fällen ( oder Funktionen, Zeiger ).

Wenn man sich Dinge, die mit gemeinsamen sets von input ( wie die css-Regeln ), nutze ich schnell code zu verfolgen, die nur möglich solitions und iteriere dachte, diese um eine übereinstimmung zu finden. Einmal habe ich ein Spiel Speichere ich die Ergebnisse in eine Hash-Tabelle ( als cache ) und dann mit dem cache-Ergebnisse, wenn ich den gleichen input später eingestellt.

Meine wichtigsten Werkzeuge für die schneller-code:

hashtable - für die schnelle Suche und für die Zwischenspeicherung der Ergebnisse

qsort - es ist die einzige Art, die ich verwenden

bsp - für das nachschlagen von Dingen, basierend auf Bereich ( map-rendering etc )

InformationsquelleAutor der Antwort KPexEA