Autor: Andr\u00e9 Schmitz, Green Hills Software<\/p>\n
Compiler-Optimierung ist ein alter Hut und bekannt, seidem es Compiler gibt. Trotzdem kommen jedes Jahr neue Versionen von Compilern auf den Markt, die nochmal z.B. 5% kleineren oder 10% schnelleren Code generieren. Wie kann das sein? Sind die bisherigen Compiler etwa schlecht, oder verwendet der Compiler-Hersteller Tricks, die nicht standardkonform sind? Compiler-Optimierung ist von Natur her eine komplexe Angelegenheit, und der Erfolg der Optimierung h\u00e4ngt sehr stark von dem zu optimierenden Sourcecode ab. Dieser Beitrag beleuchtet grunds\u00e4tzliche Konzepte von optimierenden Compilern f\u00fcr C und C++, zeigt Beispiele sowohl von altbekannten als auch von sehr aktuellen Optimierungen auf und hinterfragt den Sinn dieser Optimierungen. Au\u00dferdem werden Fallstricke aufgezeigt beim Versuch, Code manuell zu optimieren.<\/strong><\/p>\n Gerade in Embedded-Softwareprojekten besteht das Ziel, m\u00f6glichst schnellen oder kleinen Code zu generieren. Je schneller Code ausgef\u00fchrt wird, desto schneller kann man auf Events regieren, was die Reaktionszeit und die Verwend\u00adbarkeit verbessert. Je schneller eine Aufgabe erledigt ist, desto eher kann man in den Stromspar-Modus wechseln, was zur Energieeinsparung und bei batteriegetriebenen Ger\u00e4ten zur Verl\u00e4ngerung der Batterielaufzeit genutzt werden kann. Kleinerer Code erlaubt es, mehr Funktionalit\u00e4t in dem gleichen Speicher eines Ger\u00e4tes unter zu bringen.<\/p>\n Manchmal versuchen Softwareentwickler, bereits optimierten Sourcecode zu schreiben. Das kann von Vorteil sein, in manchen F\u00e4llen kann es aber auch die Qualit\u00e4t des Programms verschlechtern, weil der Optimierer des Compilers diesen manuell optimierten Code dann nicht mehr so gut optimieren kann, was unterm Strich schlechtere Optimierung bedeuten kann (siehe unten).<\/p>\n Grunds\u00e4tzlich kann man bei Compiler-Optimierungen unterscheiden zwischen der targetabh\u00e4ngigen Optimierung, bei der man auf Instruktionsebene arbeitet, und der targetunabh\u00e4ngigen Optimierung, bei der auf Sourcecode-Ebene optimiert wird. Dabei gibt es wiederum Optimierungen, die sowohl die Gr\u00f6\u00dfe als auch die Geschwindigkeit des Programms verbessern, also das Programm sowohl kleiner als auch schneller machen. Es gibt aber auch gegens\u00e4tzliche operierende Ma\u00dfnahmen, d.h. einige Optimierungen verkleinern den Code auf Kosten der Geschwindigkeit oder umgekehrt. Schauen wir uns nachfolgend mal einige Beispiele an.<\/p>\n Typische und altbekannte Source-Level-Optimierungen sind zum Beispiel „Loop Unrolling“ oder „Function Inlining“. Beide haben das Ziel, auf Kosten der Codegr\u00f6\u00dfe die Geschwindigkeit des Programms zu erh\u00f6hen. Eine weitere g\u00e4ngige Optimierung ist die „Common Subexpression Elimination“ (CSE), bei der mehrere redundante Berech\u00adnungen, die in jedem Programmpfad auftreten, durch eine Berechnung ersetzt wird (siehe Beispiel in Bild 1,\u00a0PDF<\/a>).<\/p>\n Ein neuerer Algorithmus, der aggressiver ist als CSE, ist „Partial Redundancy Elimi\u00adnation“ (PRE). Bei diesem reicht es, wenn die Berechnung nur in einem Pfad redundant ist, und er kommt auch mit Schleifen zurecht. CSE und PRE helfen auch bei vielen redundanten Speicher Berechnungen. So kann zum Beispiel<\/p>\n \u00a0\u00a0\u00a0\u00a0 arr[i] + arr[i+3]<\/p>\n durch<\/p>\n \u00a0\u00a0\u00a0\u00a0 ptr = arr + i; ptr[0] + ptr[3];<\/p>\n ersetzt werden, was die eine oder andere Instruktion spart. Weitere altbekannte Optimierungen w\u00e4ren zum Beispiel „Dead Code Elimination“ (DCE), wo der Compiler versucht, Codekompo\u00adnen\u00adten zu l\u00f6schen, die f\u00fcr das Ergebnis einer Funktion keine Relevanz haben, oder auch „Constant Propagation“.<\/p>\n Bei der „Busy Code Motion“ (BCM) wird die Gr\u00f6\u00dfe des Programms reduziert, indem der Compiler versucht, \u00e4hnliche Instruktionen in mehreren Bl\u00f6cken in nur einem Block zu reduzieren. (siehe Bild 2,\u00a0PDF<\/a>). Diese Idee wird in der Linker-Optimierung, die im n\u00e4chsten Kapitel beschrieben wird, noch weitergetrieben. Bei der targetabh\u00e4ngigen „Instruction Scheduling“ Optimierung wird das Wissen \u00fcber das Scheduling von Instruktionen in der CPU-Pipeline verwendet. W\u00e4hrend eine Instruktion in der Pipeline ausgef\u00fchrt wird, beginnt schon die Ausf\u00fchrung der n\u00e4chsten Instruktion. Und wenn die n\u00e4chste Instruktion auf das Ergebnis der vorherigen warten muss, kommt es zu Pipeline „Stalls“. Der Compiler sortiert im Rahmen der M\u00f6glichkeiten die Instruktionen so, dass es so selten wie m\u00f6glich zu Pipeline Stalls kommt.<\/p>\n Ein weiterer Bereich der Optimierung befasst sich mit der Vektorisierung, wobei man in der Regel zwischen manueller und automatischer Vektorisierung unterschiedet. Gerade in diesem Bereich passiert in den letzten Jahren sehr viel, nicht zuletzt, weil viele moderne CPUs neuerdings entsprechende SIMD-Instruktionen (Single Instruction Multiple Data) mitbringen, die eine Vektorisierung erlauben, wie z.B. Power Architecture AltiVec, ARM NEON oder Intel SSE. Manuelle Vektorisierung kann zu sehr guten Verbesserungen der Performance f\u00fchren, erfordert aber, dass der Entwickler hier selbst entscheidet, was man wie parallelisieren kann und was daf\u00fcr zu tun ist. Er muss neue Datentypen und Compiler Intrinsics lernen und anwenden und sich zudem Gedanken \u00fcber Alignment und Aliasing machen.<\/p>\n Automatische Vektorisierung hat das gleiche Ziel und verspricht auf den ersten Blick, den Entwickler zu entlasten, ist aber meist nicht so einfach zu verwenden, wie man sich das als Entwickler w\u00fcnscht. \u00c4hnlich wie bei automatischer Parallelisierung von Programmen im Allgemeinen muss eine saubere Alias-Analyse durchgef\u00fchrt werden, und das ist sehr schwierig in den Sprachen C und C++. Daher sollte der Entwickler auch bei der automatischen Vektorisierung dem Compiler mithilfe von Pragmas oder anderen Schl\u00fcsselworten klar machen, wo es sicher ist zu Vektorisieren.<\/p>\n Weitere Bereiche f\u00fcr Optimierung betreffen gerade in j\u00fcngster Zeit zum Beispiel den Bereich der Register-Allokierung, oder im Fall von C++ das L\u00f6schen nicht verwendeter virtueller Funktionen oder der Umgang mit C++ Exceptions. Au\u00dferdem werden mehr und mehr spezielle CPU-Instruktionen direkt vom Compiler oder mithilfe von Intrinsics unterst\u00fctzt. Intermodulare Optimierung hat ein sehr gro\u00dfes Potential, erfordert aber, dass der Compiler zweimal \u00fcber jede Quelldatei geht. Beim ersten Mal wird zun\u00e4chst die Struktur des Modules erkannt und gemerkt, und im zweiten Durchlauf wird jedes Modul unter Zuhilfenahme der Strukturinformationen von allen anderen Modulen tats\u00e4chlich \u00fcbersetzt und optimiert.<\/p>\n In manchen Projekten ist die Geschwindigkeit das wichtigste und die Codegr\u00f6\u00dfe egal, in anderen F\u00e4llen ist die Codegr\u00f6\u00dfe das wichtigste, ganz egal, wie langsam dadurch der Code wird. Aber meistens will man irgendwie einen Mittelweg, und man w\u00e4hlt dann eine Optimierungseinstellung, die einen Kompromiss aus Geschwindigkeit und Gr\u00f6\u00dfe darstellt. Dieser Mittelweg ist aber nicht unbedingt der beste Weg, denn meist verbringt das Programm recht viel CPU-Zeit in nur sehr wenig Code, und ein gro\u00dfer Teil des Codes wird nur wenig ausgef\u00fchrt. Wie optimiert man so etwas dann am besten? Die optimale L\u00f6sung daf\u00fcr ist die Profiler-basierte Optimierung, bei der die tats\u00e4chliche Optimierung durch die Ergebnisse des Profilings zur Laufzeit parametrisiert wird.<\/p>\n Profiling erkennt, welche Teile des Programms wie oft aufgerufen werden und wie viel Zeit man dort verbringt. Damit erkennt man die Bereiche, in denen sehr viel Zeit verbracht wird und bei denen Geschwindigkeitsoptimierung daher sehr viel bringt, und solche Bereiche in denen man nur wenig Rechenzeit verbringt und bei denen es daher sinnvoll sein kann, auf Gr\u00f6\u00dfe zu optimieren, da hier der eventuelle Trade-Off bzgl. Geschwindigkeit vernachl\u00e4ssigbar ist. In Bild 3 (s.\u00a0PDF<\/a>) sieht man zum Beispiel, dass die meiste CPU-Zeit in nur zwei Funktionen verbracht wird (minSpanningTreePrims und minSpanningTreeKruskals). Diese beiden Funktionen kann man also extrem auf Geschwindigkeit optimieren, auch wenn diese dadurch deutlich gr\u00f6\u00dfer werden. Alle anderen k\u00f6nnten vermutlich eher mit einer Optimierung auf Gr\u00f6\u00dfe leben. Funktionen, die sehr h\u00e4ufig aufgerufen werden, auch wenn sie nur wenig Zeit kosten, w\u00e4ren vermutlich gute Kandidaten f\u00fcr Inlining.<\/p>\n Letztlich kann der Entwickler mithilfe des Profiling-Ergebnisses die Hotspots seines \u00a0Programmes erkennen und die Optimierungs-Optionen in der Build-Umgebung entsprechend anpassen.<\/p>\n Die wenigstens Entwickler wissen, dass auch der Linker optimieren kann. Warum macht das Sinn? Der Linker muss alle Module anfassen und sieht als letzter im Build-Prozess, welche Funktionen und Daten tats\u00e4chlich verwendet werden. Er kann also am Ende alle nicht verwendeten Funktionen und Daten einfach beim Linken weglassen. Nat\u00fcrlich ist etwas Vorsicht geboten bei der Verwendung von zur Laufzeit festgelegten Funktionszeigern, aber da kann man dem Linker entsprechende Hinweise geben, was er auf keinen Fall entfernen darf. Au\u00dferdem kann der Linker im gesamten Programm sehen, ob ggf. bestimmte Instruktionssequenzen an verschiedenen Stellen vorkommen, die man ggf. durch eine Subroutine ersetzen kann. Diesen Ansatz kann man auch als „Outlining“ (Gegenteil von Inlining) bezeichnen.<\/p>\n Nun gibt es nat\u00fcrlich auch Dinge, die man vermeiden sollte, damit der Compiler m\u00f6glichst gut optimieren kann. Manche Entwickler denken sich, was der Compiler will, kann ich besser, oder wollen einfach nur bestimmte Aspekte eines Programms effizient in Assembler implementieren. Grunds\u00e4tzlich kann handgeschriebener Assembler-Code nat\u00fcrlich deutlich besser sein als das, was ein Compiler aus einer Hochsprache wie C oder C++ an Instruktionen generiert. Kritisch wird es aber dann, wenn der Entwickler Inline-Assembler verwendet, also mitten im C-Code einzelne Instruktionen von Hand einf\u00fcgt. Diese Inline-Assemblerinstruktionen gelten n\u00e4mlich automatisch als Optimierungs-Barriere f\u00fcr den Compiler. Die ganzen oben erw\u00e4hnten Tricks wie CSE, BCM, DCE, etc. d\u00fcrfen \u00fcber die Grenze der eingef\u00fcgten Assembler\u00adinstruktion hinweg nicht angewendet werden. Der Versuch einer manuellen Opti\u00admierung kann also ganz b\u00f6se nach hinten losgehen.<\/p>\n Weitere Probleme k\u00f6nnen auch durch die falsche Annahme dar\u00fcber entstehen, wie ein Compiler Daten im Speicher ablegt und wie Datenzugriffe optimiert werden d\u00fcrfen. Compiler und Linker d\u00fcrfen Variablen im Speicher beliebig umsortieren, solange sie nicht als Elemente einer Struktur oder Attribute eines Klasse deklariert sind. Lokale Variablen kann der Compiler auf den Stack oder in Register legen, und Zugriffe auf Variablen k\u00f6nnten im besten Fall auch komplett wegoptimiert werden (siehe DCE weiter oben). Will man das Entfernen der Zugriffe verhindern, so bietet sich die Verwendung des „volatile“ Type Qualifiers an, denn dieser sagt dem Compiler, dass die zugrundeliegende Variable auch au\u00dferhalb der Kontrolle des compilierten Codes ge\u00e4ndert werden kann.<\/p>\n Wie man sieht, gibt es sehr viele verschiedene Optimierungen, die sehr unter\u00adschiedliche Ziele haben und auf sehr unterschiedlichen Sourcecodes oder Instruktions\u00adsequenzen operieren. Von den Optimierungen sind also abh\u00e4ngig vom zugrunde\u00adliegenden Code und von der zugrunde liegenden Hardwarearchitektur sehr unterschiedliche Ergebnisse zu erwarten.<\/p>\n [1] https:\/\/compileroptimizations.com\/index.html<\/a><\/strong><\/p>\n Andre Schmitz erhielt sein Diplom in Physik 1997 an der Universit\u00e4t Bonn. Anschlie\u00dfend entwickelt er bei der FhG Steuerungs- und Simulations-Software f\u00fcr Autonome Roboter. Von 2000 bis 2005 entwickelte Herr Schmitz Embedded Software f\u00fcr UMTS Kommunikationssysteme. Seit 2005 ist Herr Schmitz bei Green Hills Software f\u00fcr die technische Unterst\u00fctzung von Kunden und die Durchf\u00fchrung von Schulungen zust\u00e4ndig. Herr Schmitz ist seitdem regelm\u00e4\u00dfig Referent bei diversen Fachkonferenzen.<\/p>\n Beitrag als PDF downloaden<\/strong><\/a><\/p>\n Wollen Sie sich auf den aktuellen Stand der Technik bringen?<\/strong><\/p>\n Dann informieren Sie sich\u00a0hier<\/strong>\u00a0<\/a>zu Schulungen\/ Seminaren\/ Trainings\/ Workshops und individuellen Coachings von MircoConsult zum Thema Implementierung \/Embedded- und Echtzeit-Softwareentwicklung.<\/p>\n Training & Coaching zu den weiteren Themen unseren Portfolios finden Sie\u00a0hier<\/a>.<\/strong><\/p>\n Wertvolles Fachwissen zum Thema Implementierung\/\u00a0Embedded- und Echtzeit-Softwareentwicklung steht\u00a0hier\u00a0<\/strong><\/a>f\u00fcr Sie zum kostenfreien Download bereit.<\/p>\nWarum Optimierung?<\/h2>\n
Beispiele von Compiler-Optimierungen<\/h2>\n
Linker-Optimierung<\/h2>\n
Typische Fallstricke<\/h2>\n
Zusammenfassung<\/h2>\n
Referenzen<\/h2>\n
Autor<\/h2>\n
\nImplementierung – unsere Trainings & Coachings<\/h2>\n
\nImplementierung – Fachwissen<\/h2>\n