Für Benutzeroberflächen gibt es besondere Ansprüche. Sie müssen blitzschnell reagieren und oft 60 Bilder pro Sekunde mit teilweise Millionen von Pixeln berechnen, um einen hochwertigen Eindruck zu vermitteln. Dies stellt besonders Embedded Systeme auf die Probe. Dieser Artikel basiert auf der Optimierung einer 2D-Anwendung unter Linux, die die Grafikbibliothek SDL verwendet hat. Die Konzepte sind jedoch auch auf andere Systeme oder Grafikbibliotheken übertragbar.

Wo liegt das Problem? – Profiling-Tools

Damit man nicht an falscher Stelle unnötigen Aufwand betreibt, sollte man zunächst natürlich herausfinden, mit welchen Dingen die CPU die meiste Zeit verbringt. Dort lässt sich oft auch die meiste Zeit einsparen. Zum Finden von Problemstellen sind Profiling-Tools sehr nützlich.

Callgrind ist eines davon und Teil des mächtigen Analysetools Valgrind. Leider benötigt Callgrind beim Sammeln der Daten viel Zeit und kann Anwendungen, die sowieso schon zu langsam sind, noch soweit verlangsamen, dass sie nicht mehr nutzbar bzw. testbar sind.
Das Tool gprof ist deutlich schneller, hat aber auch seine Nachteile. Die Zeit in Syscalls (z.B. sleep, read, write, blockierendes Warten auf Nachrichten) rechnet der Profiler nämlich nicht mit und gerade die Operationen können relativ lange dauern.
Callgrind und gprof sind beide mit dem Programm gprof2dot kompatibel, mit dem übersichtlichere Darstellungen der Abhängigkeiten und Rechenzeiten generiert werden können. Das Tool ist für einen schnellen Überblick sehr empfehlenswert.
Gerade hinter Syscalls können sich enorme Zeitverschwendungen verbirgen. Um diese zu finden, bietet sich strace an, besonders mit den Optionen -r -T und zum Filtern der Syscalltypen z.B. -​-trace=read,write.
Programme wie htop können helfen, um zumindest grob erkennen zu können, in welchem Thread das Problem liegen könnte, allerdings führen Befehle wie sleep natürlich nicht zu viel Auslastung, aber zu viel Zeitverlust. Alternativ kann man auch manuell die Zeit bestimmter Funktionsaufrufe messen und sich diese Zeit ausgeben lassen oder man kann verdächtige Funktionsaufrufe auskommentieren. Das ist nicht so elegant, führt aber auch ganz gut zum Ziel.

Was meistens passt muss nicht immer gut sein – Zeichenalgorithmen

Grafikbibliotheken sollten für viele verschiedene Anwendungen brauchbar sein und können deshalb nur schwer auf bestimmte Anwendungsfälle optimiert werden. Je nachdem, was man zeichnen möchte, kann man aber auch deutlich optimiertere Algorithmen zum Zeichnen verwenden. Hier muss eine Abwägung zwischen Performance, Aufwand und Verständlichkeit des Codes getroffen werden.

Linien zwischen zwei beliebigen Punkten werden beispielsweise meist mithilfe des Bresenham-Algorithmus gezeichnet. Teilen sich die Punkte aber eine x- oder y-Koordinate (sind also achsenparallel), dann ist auch ohne komplexen Algorithmus offensichtlich, welche Pixel eingefärbt werden müssen. Er kann also durch eine einfache Schleife über die Pixel ersetzt werden. Die Grafikbibliothek SDL stellt hierfür bereits Funktionen bereit, solange die Linien nur einen Pixel breit sind. Für breitere Linien wird allerdings, unabhängig von der Orientierung der Linie, der Murphy-Algorithmus verwendet (eine Abwandlung des Bresenham-Algorithmus für dicke Linien). Hier kann man viel Rechenzeit einsparen, indem man dicke horizontale und vertikale Linien durch einfache Schleifen über die Pixel bzw. durch Rechtecke ersetzt. Bei vielen Anwendungen ist der Großteil der Linien parallel zu den Achsen, wodurch diese Optimierung anwendbar ist.

Zeit lässt sich auch durch eine eigene Implementierung des Kantenlisten-Algorithmus‘ einsparen, den SDL und andere Bibliotheken zum Zeichnen von ausgefüllten Polygonen verwenden. Wie dieser funktioniert, zeigt die Seite unter dem Punkt „Scan Line Algorithm“ anschaulich. Für ein Polygon der Pixelhöhe h mit n Ecken bzw. Kanten werden dort h*n potentielle Schnittpunkte berechnet, was schnell rechenintensiv werden kann. Zwischen Schnittpunktpaaren wird immer eine horizontale Linie gezeichnet (für die definitiv nicht der Bresenham-Algorithmus verwendet werden sollte).

Polygone wie abgerundete Buttons nutzen in SDL ebenfalls den Kantenlisten-Algorithmus, aber für einen großen Bereich solcher Buttons sind die berechneten Schnittpunkte immer an der gleichen linken und rechten Kante. Das kann man sich zunutze machen: Hat man Schnittpunkte an zwei achsenparallelen Kanten gefunden, dann kann man für viele Polygone nicht nur die Linie zwischen den Schnittpunkten, sondern ein ganzes Rechteck bis zum Ende einer der Kanten zeichnen. Hierzu muss für das Polygon gelten, dass jede horizontale Linie höchstens zwei Schnittpunkte mit dem Polygon haben darf. Das trifft unter anderem auf alle konvexen Polygone zu.

Zeichnen von Polygonen. Mit normalem (links) und optimiertem (rechts) Algorithmus. Der bereits gezeichnete Bereich ist dunkelblau, der durch den optimierten Algorithmus in einem Schritt gezeichnete Bereich hellblau.

Das Bild zusammensetzen

Verwendet man mehrere Zeichenebenen, dann muss man sie für jedes Bild korrekt zusammensetzen bevor man damit das angezeigte Bild aktualisiert. Hier ist es nützlich sich zu merken welche Bereiche sich seit dem letzten Bild geändert haben, falls die verwendete Grafikbibliothek dies nicht schon übernimmt. Gerade bei Benutzeroberflächen, in denen sich nicht allzu viel ändert, kann man viel Rechenleistung sparen, indem man nur die veränderten Bereiche der Ebenen zusammenkopiert und dann auch nur den Bereich des angezeigten Bildes aktualisiert. Ein einfacher Startpunkt ist es, sich ein Rechteck zu definieren, das nach jeder Zeichenoperation immer so erweitert wird, dass es den Bereich aller vorherigen Operationen seit dem letzten Bild umschließt. Erweiterte Methoden kann man unter dem Stichwort „Dirty Rectangles“ finden.

Unter Umständen kann man auch die Anzahl der Ebenen verringern, das Blitting (kopieren der Bilddaten, block image transfer) ist nämlich relativ aufwändig, wenn es nicht hardwarebeschleunigt ist.

Oft ist es jedoch nicht vermeidbar, mehrere Ebenen zu haben. Eventuell stellt sich dann die Frage, ob man in einer unteren Ebene zeichnen sollte, wenn der Inhalt aktuell sowieso von einer höheren Ebene verdeckt wird. Man könnte schließlich auch erst zeichnen, wenn die untere Ebene nicht mehr verdeckt ist und sich so die Zeit für das Zeichnen vorher sparen. Ob sich das lohnt, hängt aber auch davon ab, was gezeichnet wird. Problematisch könnte es sein, wenn man in einem Frame sehr viel nachzeichnen muss. Statt die durchschnittliche Zeit pro Frame zu optimieren, ist die maximale Zeit pro Frame meist sinnvoller. In dem Fall sollte man weiterhin auch auf einer verdeckten Ebene zeichnen.

Einstellungen überprüfen

Hardwarebeschleunigung kann der CPU einiges an Arbeit ersparen. Ein Blick in die verfügbaren Hardwareoperationen lohnt sich, aber es kann natürlich auch gut sein, dass entscheidende Funktionalitäten nicht hardwarebeschleunigt sind.

Die Pixelformate verschiedener Ebenen können unterschiedlich sein. Das führt dazu, dass die Pixeldaten beim zusammensetzen des Gesamtbildes erst in das korrekte Format umgewandelt werden müssen, was zusätzlich Zeit kostet. Meistens ist es also sinnvoll, die Formate einheitlich zu halten.

Einen sehr großen Unterschied macht auch die Wahl der Grafikbibliothek. Wenn Performanceprobleme absehbar sind, sollte man zumindest einige Bibliotheken ausprobieren bevor man weitermacht.

Haben Sie noch einen Profiling- oder Optimierungs-Geheimtipp? Lassen Sie es uns in den Kommentaren wissen!