Tipps zum Verbessern von zeitkritischem Code
Aktualisiert: November 2007
Das Schreiben von schnellem Code erfordert eine sorgfältige Analyse sämtlicher Aspekte der Anwendung und deren Interaktion mit dem System. In diesem Thema werden Alternativen zu einigen der naheliegenden Codierungstechniken vorgestellt. Dadurch soll sicherstellt werden, dass die zeitkritischen Codebereiche zufriedenstellend ausgeführt werden.
Zur Verbesserung des zeitkritischen Codes sollten Sie sich folgende Punkte überlegen:
Welcher Teil des Programms muss schnell sein?
Welche Größe und Geschwindigkeit soll der Code haben?
Wie hoch dürfen die Kosten für neue Features sein?
Welcher Minimalaufwand ist zur Durchführung der Aufgabe erforderlich?
Leistungsdaten zum Code können Sie mithilfe des Systemmonitors (perfmon.exe) erfassen.
Erfolglose Cachezugriffe und Seitenfehler
Sortieren und Suchen
MFC- und Klassenbibliotheken
Gemeinsam genutzte Bibliotheken
Heaps
Threads
Kleines Workingset
Erfolglose Cachezugriffe und Seitenfehler
Erfolglose Cachezugriffe sowohl im internen als auch im externen Cache sowie Seitenfehler (Suchen nach Programmanweisungen und Daten in einem sekundären Speichermedium) verlangsamen die Programmleistung.
Ein CPU-Cachezugriff beansprucht im Programm 10–20 Taktzyklen. Ein externer Cachezugriff kann 20–40 Taktzyklen beanspruchen. Ein Seitenfehler beansprucht eine Million Taktzyklen (vorausgesetzt, ein Prozessor verarbeitet 500 Millionen Anweisungen pro Sekunde und einen Seitenfehler in 2 Millisekunden). Daher liegt es im Sinne einer optimalen Programmausführung, Code zu schreiben, der die Anzahl der erfolglosen Cachezugriffe und Seitenfehler möglichst gering hält.
Ein Grund für die Langsamkeit von Programmen besteht darin, dass sie häufiger Seitenfehler oder erfolglose Cachezugriffe verursachen. Um dies zu verhindern, ist es wichtig, Datenstrukturen mit weitgehend lokalen Verweisen zu verwenden – also Datenstrukturen, die zusammenhängende Elemente auch zusammenhalten. Eine auf den ersten Blick durchdachte Datenstruktur kann sich als ausgesprochen schlecht erweisen, weil sie nicht nur lokale Verweise enthält, manchmal trifft jedoch genau das Gegenteil zu. Hier zwei Beispiele:
Dynamisch zugeordnete, verknüpfte Listen können die Programmleistung mindern, da bei der Suche nach einem Element oder beim Durchlaufen einer Liste bis zum Ende jeder Sprung außerhalb des Caches landen oder einen Seitenfehler generieren könnte. Eine Listenimplementierung, die auf einfachen Arrays basiert, könnte aufgrund der besseren Cacheverwaltung und der geringeren Anzahl von Seitenfehlern tatsächlich wesentlich schneller sein. Auch unter Berücksichtigung der Tatsache, dass ein Array schwieriger zu erweitern ist, ist dies immer noch die schnellere Lösung.
Hashtabellen, die dynamisch zugeordnete, verknüpfte Listen verwenden, können die Leistung mindern. Bei der Erweiterung können Hashtabellen, die dynamisch zugeordnete, verknüpfte Listen zur Speicherung ihres Inhalts verwenden, eine deutlich schlechtere Leistung zeigen. Letztlich könnte eine einfache lineare Suche in einem Array (je nach den Umständen) schneller sein. Auf Arrays basierende Hashtabellen (so genanntes "geschlossenes Hashing") sind eine häufig übersehene Implementierungsmöglichkeit, die oft eine bessere Leistung bringt.
Sortieren und Suchen
Verglichen mit vielen typischen Operationen ist das Sortieren naturgemäß ein zeitintensiver Vorgang. Am besten lässt sich ein unnötiger Leistungsverlust vermeiden, indem zu kritischen Zeiten auf eine Sortierung verzichtet wird. Folgende Voraussetzungen sollten erfüllt sein:
Verschieben Sie die Sortierung auf einen nicht leistungskritischen Zeitpunkt.
Sortieren Sie die Daten zu einem früheren, nicht leistungskritischen Zeitpunkt.
Sortieren Sie nur diejenigen Daten, die wirklich sortiert werden müssen.
Manchmal lässt sich die Liste bereits in sortierter Reihenfolge erstellen. Wenn Sie Daten in sortierter Reihenfolge eingeben müssen, kann es sein, dass Sie eine komplexere Datenstruktur benötigen, die nicht nur lokale Verweise enthält. Dies kann zu erfolglosen Cachezugriffen und Seitenfehlern führen. Es gibt keinen allgemeingültigen Ansatz für alle Situationen. Probieren Sie verschiedene Vorgehensweisen aus, und vergleichen Sie die Leistungsdaten.
Im Folgenden einige allgemeine Tipps zum Sortieren:
Verwenden Sie einen vordefinierten Sortiervorgang, um die Fehlerquote gering zu halten.
Alle Maßnahmen, durch die Sie die Komplexität im Voraus verringern können, sind lohnenswert. Wenn Vergleichsoperationen durch einen einmaligen Datendurchlauf vereinfacht und Sortierdurchläufe von O(n log n) zu O(n) reduziert werden können, sind Sie ein gutes Stück vorangekommen.
Wägen Sie das Vorhandensein lokaler Verweise für den verwendeten Sortieralgorithmus und den Typ der zu sortierenden Daten gegeneinander ab.
Beim Suchen gibt es weniger Alternativen als beim Sortieren. Wenn die Suche zeitkritisch ist, wird eine binäre Suche oder eine Suche in einer Hashtabelle in den meisten Fällen die richtige Lösung sein. Wie beim Sortieren sollten Sie jedoch das Kriterium lokaler Verweise im Auge behalten. Eine lineare Suche in einem kleinen Array kann schneller sein als eine binäre Suche in einer Datenstruktur mit zahlreichen Zeigern, die Seitenfehler oder erfolglose Cachezugriffe verursachen könnte.
MFC- und Klassenbibliotheken
Durch Microsoft Foundation Classes (MFC) kann das Schreiben von Code außerordentlich erleichtert werden. Beim Schreiben von zeitkritischem Code sollten Sie den Aufwand berücksichtigen, der mit der Verwendung einiger Klassen verbunden ist. Überprüfen Sie den MFC-Code, den der zeitkritische Code verwendet, um festzustellen, ob er Ihren Leistungsanforderungen entspricht. Die folgende Liste enthält MFC-Klassen und Funktionen, die Sie beachten sollten:
CString MFC ruft die C-Laufzeitbibliothek auf, um Speicher für CString dynamisch zuzuordnen. Die Verwendung von CString ist im Allgemeinen genauso effizient wie die Verwendung anderer dynamisch zugeordneter Zeichenfolgen. Wie bei allen anderen dynamisch zugeordneten Zeichenfolgen entsteht auch hier zusätzlicher Aufwand für die dynamische Zuweisung und Freigabe. Oft erfüllt auch ein einfaches char-Array auf dem Stapel denselben Zweck und ist sogar leistungsfähiger. CString sollte nicht zum Speichern einer konstanten Zeichenfolge verwendet werden. Verwenden Sie stattdessen const char *. Jede Operation, die Sie mit einem CString-Objekt durchführen, ist mit Mehraufwand verbunden. Möglicherweise stellt die Verwendung von Zeichenfolgenfunktionen aus der Laufzeitbibliothek eine schnellere Lösung dar.
CArray CArray bietet eine Flexibilität, die ein normales Array nicht vorweisen kann, nicht immer wird diese vom Programm jedoch auch benötigt. Wenn Ihnen die spezifischen Grenzen des Arrays bekannt sind, können Sie stattdessen auch ein globales Array fester Größe verwenden. Wenn Sie CArray verwenden, sollten Sie mit CArray::SetSize die Größe und die Anzahl der Elemente angeben, um die das Array erweitert werden soll, wenn eine Neuzuordnung notwendig wird. Andernfalls kann es vorkommen, dass das Array beim Hinzufügen von Elementen mehrfach neu zugeordnet und kopiert wird. Diese Vorgehensweise ist ineffizient und kann zu einer Fragmentierung des Speichers führen. Sie sollten auch berücksichtigen, dass CArray beim Einfügen eines Elements in ein Array die nachfolgenden Elemente im Speicher verschiebt und dass das Array möglicherweise erweitert werden muss. Dadurch können erfolglose Cachezugriffe und Seitenfehler verursacht werden. Wenn Sie den von MFC verwendeten Code durchsehen, werden Ihnen möglicherweise Abschnitte auffallen, die Sie spezifischer programmieren können, um die Leistung zu optimieren. Da es sich bei CArray um eine Vorlage handelt, können Sie beispielsweise CArray-Spezialisierungen für bestimmte Typen angeben.
CList CList ist eine doppelt verknüpfte Liste; das Einfügen von Elementen ist also am Kopf, am Ende wie auch an einer bekannten Position (POSITION) der Liste schnell möglich. Um ein Element nach dem Wert oder Index zu suchen, ist eine sequenzielle Suche erforderlich. Bei einer langen Liste kann dieser Vorgang jedoch sehr lange dauern. Wenn für den Code keine doppelt verknüpfte Liste erforderlich ist, sollten Sie die Verwendung von CList nochmals überdenken. Durch die Verwendung einer einfach verknüpften Liste sparen Sie die Aktualisierung eines zusätzlichen Zeigers für alle Operationen sowie Speicherkapazität für diesen Zeiger. Der zusätzliche Speicherbedarf ist zwar nicht groß, kann jedoch eine weitere Quelle für erfolglose Cachezugriffe oder Seitenfehler sein.
IsKindOf Diese Funktion kann viele Aufrufe und zahlreiche Speicherzugriffe in verschiedenen Datenbereichen generieren. Dies kann dazu führen, dass nicht nur lokale Verweise vorhanden sind. Diese Funktion eignet sich für ein Debugbuild (z. B. in einem ASSERT-Aufruf), sollte in Releasebuilds jedoch möglichst nicht verwendet werden.
PreTranslateMessage Sie sollten PreTranslateMessage verwenden, wenn eine bestimmte Fensterstruktur verschiedene Tastaturzugriffstasten benötigt, oder wenn Sie eine Meldungsbehandlung in die Meldungsverteilschleife einfügen müssen. PreTranslateMessage ändert MFC-Dispatchmeldungen. Wenn Sie PreTranslateMessage überschreiben, sollte dies nur im erforderlichen Umfang geschehen. Es ist z. B. nicht nötig, CMainFrame::PreTranslateMessage zu überschreiben, wenn Sie lediglich an den Meldungen interessiert sind, die an untergeordnete Strukturen einer bestimmten Ansicht gesendet werden. Überschreiben Sie stattdessen PreTranslateMessage für die Ansichtsklasse.
Sie sollten den normalen Dispatchpfad nicht umgehen, indem Sie PreTranslateMessage für die Behandlung von Meldungen verwenden, die an Fenster gesendet werden. Verwenden Sie zu diesem Zweck Fensterprozeduren und MFC-Meldungszuordnungen.
OnIdle Leerlaufereignisse können gelegentlich unerwartet auftreten, z. B. zwischen den Ereignissen WM_KEYDOWN und WM_KEYUP. Zeitgeber können hier eine effizientere Lösung zum Auslösen des Codes sein. Sie sollten OnIdle nicht wiederholt durch die Erzeugung falscher Meldungen oder durch die ständige Rückgabe von TRUE durch eine OnIdle-Überschreibung aufrufen lassen, da der Thread auf diese Weise niemals zur Ruhe kommt. Auch hier ist ein Zeitgeber oder ein separater Thread besser geeignet.
Gemeinsam genutzte Bibliotheken
Die Wiederverwendung von Code ist wünschenswert. Wenn Sie jedoch fremdprogrammierten Code verwenden, sollten Sie in den Fällen, in denen es auf Leistung ankommt, genau wissen, wie sich dieser Code verhält. Dies können Sie am besten nachvollziehen, indem Sie den Quellcode Schritt für Schritt durchgehen oder Leistungsdaten mit Tools wie PView oder dem Systemmonitor erfassen.
Heaps
Lassen Sie bei der Verwendung mehrerer Heaps Vorsicht walten. Mithilfe zusätzlicher Heaps, die mit HeapCreate und HeapAlloc erstellt wurden, können Sie eine zugehörige Gruppe von Zuordnungen verwalten und dann löschen. Vermeiden Sie eine zu hohe Speicherbelastung. Wenn Sie mehrere Heaps verwenden, achten Sie insbesondere auf die Größe des Speichers, der zu Anfang belegt wird.
Sie können Hilfsfunktionen verwenden, die die Schnittstelle zwischen dem Code und dem Standardheap darstellen, anstatt mehrere Heaps zu verwenden. Hilfsfunktionen vereinfachen benutzerdefinierte Zuordnungsstrategien, durch die die Anwendungsleistung gesteigert werden kann. Wenn Sie z. B. häufig viele kleine Zuordnungen vornehmen, könnten Sie diese Zuordnungen auf einen Teil des Standardheaps begrenzen. Sie könnten einen großen Speicherblock zuordnen und dann mittels einer Hilfsfunktion weitere Zuordnungen von diesem Block aus vornehmen. Wenn Sie so vorgehen, haben Sie keine zusätzlichen Heaps mit ungenutzten Speicherbereichen, da die Zuordnung auf dem Standardheap erfolgt.
Die Verwendung des Standardheaps kann in einigen Fällen jedoch dazu führen, dass nicht nur lokale Verweise vorhanden sind. Sie sollten daher die Auswirkungen von Objektverschiebungen von Heap zu Heap mithilfe von Programmen, wie Prozess-Viewer, Spy++ oder dem Systemmonitor, testen.
Erfassen Sie Heapdaten, sodass Sie eine Übersicht über jede Zuordnung auf dem Heap haben. Verwenden Sie die zur C-Laufzeit ausgeführten Routinen zum Debuggen von Heaps, um den Heap zu überprüfen und den Speicherinhalt auszugeben. Sie könnten die Ausgabe dann in ein Tabellenkalkulationsprogramm, wie Microsoft Excel, einlesen und die Ergebnisse in Pivottabellen anzeigen lassen. Notieren Sie sich die Gesamtanzahl, Größe und Verteilung von Zuordnungen. Vergleichen Sie diese Werte mit der Größe der Workingsets. Achten Sie dabei auch auf die Clusteranordnung ähnlich großer Objekte.
Sie können auch die Leistungsindikatoren verwenden, um die Speichernutzung zu überwachen.
Threads
Für im Hintergrund ausgeführte Tasks kann eine effiziente Leerlaufbehandlung von Ereignissen im Vergleich zur Verwendung von Threads die schnellere Lösung sein. Das Vorhandensein lokaler Verweise lässt sich in einem Singlethreadedprogramm leichter nachvollziehen.
Im Allgemeinen sollten Sie einen Thread nur dann verwenden, wenn eine Betriebssystembenachrichtigung, die Sie abfangen müssen, den Ausgangspunkt für die Hintergrundverarbeitung bildet. Threads sind in solchen Fällen die beste Lösung, da es nicht sinnvoll ist, einen Hauptthread mit dem Warten auf ein Ereignis zu blockieren.
Threads stellen Sie auch vor Kommunikationsprobleme. Die Kommunikation zwischen den Threads muss verwaltet werden, sei es mit einer Liste von Meldungen oder durch die Reservierung und Verwendung von gemeinsam genutztem Speicher. Die Verwaltung der Kommunikationsverbindung erfordert normalerweise eine Synchronisierung, um Probleme mit der Geschwindigkeit und gegenseitigem Sperren zu verhindern. Eine solche Komplexität kann leicht zu Fehlern und Leistungsproblemen führen.
Weitere Informationen finden Sie unter Leerlaufschleifen-Verarbeitung und Multithreading.
Kleines Workingset
Bei kleineren Workingsets sind überwiegend lokale Verweise vorhanden, die weniger Seitenfehler und mehr Cachetreffer implizieren. Das Prozessworkingset ist die genaueste Maßeinheit, die das Betriebssystem direkt anbietet, um festzustellen, ob die Verweise lokal sind oder nicht.
Weitere Informationen zum Festlegen der Ober- und Untergrenze des Workingsets finden Sie unter SetProcessWorkingSetSize.
Weitere Informationen zum Abrufen der Ober- und Untergrenze des Workingsets finden Sie unter GetProcessWorkingSetSize.
Um die Größe des WorkingSets anzeigen zu lassen, verwenden Sie Spy++.