© photocase.com

Jeder wünscht sich Programme, mit denen er flink arbeiten kann. Schnelle Software entsteht aber nicht durch flächendeckende, sondern durch wenig Optimierung – an den richtigen Stellen. Dieser Workshop zeigt, wie Sie bei Python-Programmen ins Schwarze treffen.

Die Optimierung von Programmen will in erster Linie Laufzeit sparen. Die Software soll sich zügiger anfühlen, ihre Rechenergebnisse schneller präsentieren und so fort. Doch leider verlängert Optimierung die Entwicklungszeit. Der entstehende Quelltext ist normalerweise komplizierter als vorher, was den Aufwand zum Testen und zur Fehlersuche steigert. Doch das ist noch nicht alles: Durch die gestiegene Komplexität des Code werden auch dessen Wartung und zum Beispiel nachträgliche Erweiterungen schwieriger. Das kostet weitere Entwicklungszeit, was oft übersehen wird, weil sie mitunter erst lange nach der Optimierung fällig sind.

Deshalb ist es falsch, schon beim Schreiben jeder Funktion oder Methode darüber nachzudenken, wie sie am schnellsten arbeiten könnte. Diese Einstellung bringt C. A. R. Hoare – obwohl der Satz häufig Donald Knuth zugeschrieben wird – mit “Premature optimization is the root of all evil” auf den Punkt. Das ist der Fall: Der Programmierer sollte die Laufzeitoptimierung erst angehen, wenn das Programm fehlerfrei läuft.

Wo optimieren?

Ein Programm ist aus Sicht des Entwicklers nie durchweg langsam oder durchweg schnell. Für träges Verhalten ist normalerweise nur ein kleiner Teil des Code verantwortlich, die so genannten Flaschenhälse (Bottlenecks). Bevor Sie anfangen, auf Verdacht Codeteile zu beschleunigen, sollten Sie messen, wo es genau klemmt. Im ersten Schritt ist festzustellen, ob die Software beim Ausführen einer bestimmten Funktion durch die CPU oder das EA-Subsystem behindert wird. So ist es sinnlos, einen Algorithmus auf ein Hundertstel seiner ursprünglichen Rechenzeit zu bringen, wenn tatsächlich die Festplatten oder das Netzwerk die Software bremsen.

Um zu ermitteln, ob der langsame Prozessor, die Festplatte oder andere Hardware die Schuldigen sind, helfen Ihnen grafische Werkzeuge wie Xosview [1] oder Gkrellm [2]. Daneben gibt es Tools wie Dstat [3], die beispielsweise den Datentransfer von und zu einer bestimmten Partition in Zahlen wiederspiegeln. Um plausibel zu messen, dürfen allerdings möglichst keine anderen Prozesse laufen, die den Rechner auslasten. Alternativ liefern »top« oder »ps« einzelne Leistungsdaten von Prozessen.

Die Abbildungen 1 bis 3 zeigen Screenshots von Gkrellm und Dstat für einen durch die CPU und einen durch Datentransfer begrenzten Prozess. Der zweite Fall ist schwieriger zu erkennen als die CPU-Begrenzung, da es keine Hardware-unabhängige Obergrenze gibt. Ermitteln Sie entsprechende Grenzwerte am besten durch Hardware-Spezifikationen oder Benchmarks. Bedenken Sie, dass Datentransfer sich nicht nur wie hier auf ein CD-ROM-Laufwerk beziehen kann, sondern auch auf Netzwerk-Schnittstellen, Tape-Wechsel-Roboter in Backup-Systemen und so weiter.

Wird die Software durch eine vollständige CPU-Auslastung gehemmt, müssen Sie die bremsenden Stellen im Code weiter eingrenzen. Dabei hilft das Python-Modul »cProfile« (bis Python 2.4 »profile«), dessen Ergebnisse das Modul »pstats« auswertet.

Abbildung 1: Links zeigt Gkrellm die hundertprozentige Prozessorauslastung für einen von der CPU-begrenzten Prozess. Rechts stellt das Programm den Datendurchsatz beim Kopieren einer CD-ROM dar.

Abbildung 2: Ausgabe von »dstat« für einen CPU-begrenzten Prozess. Die Summe der beiden ersten Spalten liegt bei 100 Prozent.

Abbildung 3: Dstat-Report für einen durch Datentransfer begrenzten Prozess (Kopieren einer CD-ROM). Wichtig sind die Werte der Spalte »disk/total/read«.

Profiling-Beispiel: Emerge

Als praktisches Beispiel für den Einsatz des Python-Profilers soll eine Suche in der Paket-Datenbank von Gentoo Linux dienen. Das entsprechende Tool »emerge« ist in Python geschrieben. Eine Suche mit »emerge –search python« läuft auf dem Rechner des Autors in einer akzeptablen Zeit von knapp 10 Sekunden. Eine Optimierung wäre also höchstens für langsamere Rechner sinnvoll, aber zunächst soll es hier ja nur um die Analyse gehen.

Die Ablaufstatistik mit Pythons C-Profile-Modul zu erzeugen ist etwas umständlich, da dessen Kommandozeilenschnittstelle nicht vorsieht, dem aufgerufenen Programm Parameter mitzugeben. Daher verwendet der Workshop den interaktiven Interpreter (Listing 1). Nach dem Importieren der Python-Module und der Vorbereitung der Parameter startet »cProfile.run()« den Testlauf. Das Modul »pstats« gibt dann die Laufzeitstatistik tabellarisch aus (Listing 2).

01 >>> import cProfile
01 >>> import sys
01 >>> sys.argv.append("--search")
01 >>> sys.argv.append("python")
01 >>> f = open("/usr/bin/emerge")
01 >>> ef = f.read()
01 >>> f.close()
01 >>> cProfile.run(ef, "emerge.stats")
01 Searching...
01 [ Results for search key : python ]
01 [ Applications found : 48 ]
01 ...

01 >>> import pstats
01 >>> s = pstats.Stats("emerge.stats")
01 >>> s.sort_stats('time')
01 <pstats.Stats instance at 0xb7d80eac>
01 >>> s.print_stats(10)
01 Sun Oct  1 23:12:36 2006    emerge.stats
01 
01          602508 function calls (586701 primitive calls) in 9.052 CPU seconds
01 
01    Ordered by: internal time
01    List reduced from 609 to 10 due to restriction <10>
01 
01    ncalls  tottime  percall  cumtime  percall filename:lineno(function)
01      1240    1.022    0.001    1.022    0.001 {method 'readlines' of 'file' objects}
01     11387    0.849    0.000    0.849    0.000 {method 'flush' of 'file' objects}
01      1096    0.579    0.001    1.513    0.001 /usr/lib/portage/pym/portage.py:200(cacheddir)
01 14550/160    0.421    0.000    1.173    0.007 /home/schwa/python2.5/lib/python2.5/copy.py:144(deepcopy)
01     76352    0.359    0.000    0.359    0.000 {method 'append' of 'list' objects}
01         1    0.335    0.335    2.513    2.513 <string>:468(output)
01 66288/66173    0.316    0.000    0.317    0.000 {len}
01     11383    0.256    0.000    1.225    0.000 <string>:94(update_twirl)
01     36953    0.224    0.000    0.224    0.000 {method 'split' of 'str' objects}
01         1    0.213    0.213    3.629    3.629 <string>:408(execute)

Ein besonderer Flaschenhals fällt zwar nicht auf, dennoch sind ein paar Stellen zu erkennen, an denen eine Optimierung ansetzen könnte. So verbringt Emerge immerhin 1,2 von 9 Sekunden damit, die Fortschrittsanzeige (Methode »update_twirl«) zu aktualisieren (zu sehen in der Spalte »cumtime«, kumulative Zeit, in der achten Tabellenzeile). Allerdings gibt es bereits eine Emerge-Option, die diese Ausgabe abschaltet.

Etwa 1,2 Sekunden fallen für tiefe Kopien an (Spalte »cumtime« in der vierten Tabellenzeile). Tiefe Kopien werden von Programmierern manchmal einfach sicherheitshalber gemacht. Hier gibt es Einsparpotenzial, falls die tiefe Kopie nicht wirklich nötig ist.

Möglicherweise ließe sich der Code nach einer Umstrukturierung noch besser beschleunigen, da dann deutlicher zu erkennen wäre, wann welcher Code abläuft und welche algorithmischen Vereinfachungen möglich sind. Schließlich ist die Änderung von Algorithmen oft die wirksamste Laufzeitoptimierung.

Wie optimieren?

Prinzipiell gibt es zwei Wege, CPU-begrenzten Code zu beschleunigen: Dinge schneller oder seltener tun. Manchmal gelingt auch beides zugleich, wenn Sie zum Beispiel eine selbst gestrickte Datenverwaltung mit linear strukturierten Dateien durch ein Datenbanksystem wie SQLite [4] ersetzen.

Wie erwähnt spielen bei der Optimierung zwei Kriterien zusammen: Wie schnell lässt sich der Code machen und wie viel Entwicklerzeit ist dafür nötig? Natürlich ist es erstrebenswert, mit einem Minimum an Aufwand eine maximale oder besser gesagt ausreichende Geschwindigkeitssteigerung zu erreichen. Dabei ist auch die Wartbarkeit des entstehenden Quelltextes zu berücksichtigen.

Bevor Sie mit der Geschwindigkeitsmessung, dem Profiling, auch nur beginnen, muss der Code so weit wie möglich fehlerfrei sein. Ist das nicht der Fall, besteht die Gefahr, Code zu optimieren, der nur aufgrund eines Programmfehlers zu langsam läuft. Für die ursprüngliche Fehlerreduktion wie auch zur Kontrolle der Code-Änderungen während der Optimierung sind automatisierte Tests hilfreich, zum Beispiel mit den Python-Modulen »doctest« und/oder »unittest«. Damit lässt sich leichter feststellen, ob die Optimierung vielleicht Programmfehler eingeführt hat.

Profiling

Als Nächstes sollten Sie zum Profiling übergehen, um die wichtigsten zu beschleunigenden Stelle im Code zu finden. Das sind üblicherweise jene mit der höchsten Gesamtlaufzeit, also Stellen, bei denen das Produkt der einzelnen Ausführungszeit und der Ausführungshäufigkeit sehr groß ist. Es ist normalerweise sinnvoller, eine Funktion zu optimieren, die 10 000-mal abläuft und dafür jeweils eine Sekunde benötigt, als eine Funktion, die fünfmal jeweils 10 Sekunden läuft.

Dabei sollten Sie aber berücksichtigen, wie stark ein Anwender des Programms die Ausführung als Bremse empfindet. Es könnte nämlich auch sein, dass die erste Situation das Programm lediglich etwas zäher erscheinen lässt, die zweite Situation den Anwender aber zu 10 Sekunden Untätigkeit verdammt.

Das Ersetzen eines Algorithmus durch einen effizienteren beschleunigt ein Programm am nachhaltigsten. Während bei den meisten Optimierungstechniken das optimierte Codestück maximal 10 Prozent schneller wird, sind durch den Austausch von Algorithmen mitunter mehrere 100 Prozent möglich.

Algorithmen beurteilen

Die O-Notation beschreibt formal, welche Algorithmen schneller als andere sind. Dabei steht O für die Ordnung des Algorithmus. Ausdrücke wie O(n) oder O(n ln n) stehen für die Komplexität von Algorithmen. Der Ausdruck in Klammern beschreibt, wie sich die Laufzeit ändert, wenn die vom Algorithmus zu verarbeitende Datenmenge ansteigt, etwa die Anzahl der Werte in einer Liste oder die Länge einer Zeichenkette.

Zum Beispiel läuft ein O(n)-Algorithmus doppelt so lange, wenn sich die Datenmenge verdoppelt, ein O(n2)-Algorithmus bei jeder Verdopplung der Datenmenge dagegen viermal so lange. Offenbar ist es erstrebenswert, dass der eingeklammerte Ausdruck mit wachsendem n möglichst wenig wächst. Tabelle 1 zeigt die Laufzeiten mehrer Python-Algorithmen. Von oben nach unten verschlechtert sich das Laufzeitverhältnis.

Bei mehrfach verschachtelten Schleifen oder bei bestimmten kombinatorischen Problemen nehmen die Laufzeiten auch noch ein größeres Verhältnis als ein quadratisches an. Dann können selbst kleine Werte von n extrem lange Laufzeiten bewirken. Wenn die entsprechende Stelle ein Engpass ist, sollten Sie bei großem n auf Algorithmen mit mehr als quadratischer Ordnung verzichten.

Verwenden Sie einen Algorithmus mit kleineren Datenmengen, ist der schlechtere möglicherweise der schnellere. Bei manchen Algorithmen nimmt zwar die Laufzeit bei wachsendem n nur langsam zu, sie erfordern aber vielleicht einen länger dauernden Vorbereitungsschritt. Dann kann ein langsamer Algorithmus, der aber gleich zur Sache kommt, letztlich schneller sein.

Der Vergleich von Algorithmen anhand ihrer Ordnung ist zwar prinzipiell nützlich. In ihrer reinen Form treten sie in freier Wildbahn aber eher selten auf, jedenfalls für alle Größenordnungen von Datenmengen. Zum Beispiel ändert ein Sortieralgorithmus, der sich für bis zu 100 000 zu sortierende Werte gemäß O(n ln n) verhält, sein Laufzeitverhalten erheblich, wenn die zu sortierende Liste nicht mehr in den Hauptspeicher passt und das Betriebssystem mit der Auslagerung von Speicherinhalten auf die Festplatte beginnt. Solche Effekte zeigen sich ebenfalls, sobald die Speicherverwaltung der unter dem Interpreter liegenden C-Standard-Bibliothek die Laufzeit merklich mitbestimmt.

Schnittmenge optimiert

Ein weiteres Beispiel soll die Unterschiede bei der Verwendung verschiedener Algorithmen illustrieren. Jede der dabei betrachteten Python-Funktionen ermittelt die Schnittmenge zweier Listen – also jene Listenelemente, die in beiden Listen vorkommen – und gibt sie als neue Liste zurück.

Der erste verwendete Algorithmus weist quadratisches Zeitverhalten auf, wenn beide Listen n Elemente enthalten (Listing 3). Die äußere Schleife iteriert über alle Elemente der ersten Liste und zeigt ein lineares Zeitverhalten. Innerhalb der Schleife steht jedoch eine weitere, die im Beispiel implizit in »wert in liste2« steckt: Da die Liste »liste2« linear durchsucht wird, ergibt sich nochmals lineares Verhalten. Die Verschachtelung der expliziten Schleife außen und der impliziten Schleife innen führt insgesamt zu einem O(n2)-Algorithmus.

01 def schnittmenge1(liste1, liste2):
02     """Ermittle Schnittmenge mit O(n^2)-Algorith- mus."""
03     ergebnis = {}
04     for wert in liste1:
05         if wert in liste2:
06             ergebnis[wert] = True
07     return ergebnis.keys()

Die Ermittlung der Schlüssel in der »return«-Anweisung ist linearer Natur, tritt gegenüber dem vorherigen quadratischen Verhalten für große n aber in den Hintergrund. Versuchen Sie generell, geschachtelte Schleifen zu vermeiden. Diese zeigen selbst im besten Fall quadratisches Zeitverhalten. Für kleine Datenmengen lohnt sich eine Optimierung aber vermutlich nicht.

Der Algorithmus in Listing 4 zeigt eine veränderte Version des vorherigen, jetzt mit linearem Zeitverhalten. Dieser Code sieht dem vorherigen zwar sehr ähnlich, jedoch erzeugt er bereits vor dem Eintritt in die äußere Schleife aus der zweiten Liste ein Dictionary und verwendet es in der Schleife. Da aber »wert in dict2« konstantes Zeitverhalten aufweist, ist die äußere Schleife unterm Strich zeitlich linear.

01 def schnittmenge2(liste1, liste2):
02     """Ermittle Schnittmenge mit O(n)-Algorithmus."""
03     ergebnis = {}
04     dict2 = dict((wert, True) for wert in liste2)
05     for wert in liste1:
06         if wert in dict2:
07             ergebnis[wert] = True
08     return ergebnis.keys()

Auch der letzte Algorithmus führt zu linearem Zeitverhalten (Listing 5). Die Umwandlung der ersten Liste in eine Menge ist linear, ebenso die Bildung der Schnittmenge mit der »intersection«-Methode und die Konvertierung der Ergebnismenge in eine Liste. Zwar sind diese Operationen von der Schreibweise her ineinander verschachtelt, sie laufen jedoch nacheinander ab. Die drei linearen Schritte hintereinander ergeben insgesamt wieder einen O(n)-Algorithmus.

01 def schnittmenge3(liste1, liste2):
02     """Ermittle Schnittmenge mit O(n)-Algorithmus."""
03     return list(set(liste1).intersection(liste2))

Bessere Algorithmen

Aus den obigen Beispielen lassen sich bereits einige allgemeine Regeln ableiten, die Sie bei der Optimierung beherzigen sollten. So sollten Sie Operationen, deren Ergebnisse sich während der Schleifendurchläufe nicht ändern, aus der Schleife herausziehen, sodass diese Operationen nicht bei jeder Schleifeniteration ablaufen.

Teilen Sie die Daten, mit denen Sie arbeiten, geschickt auf. Ein bekanntes Beispiel ist die binäre Suche, die zwar nur auf vorsortierte Daten anwendbar ist, dann aber in O(ln n) zum Ziel kommt statt in O(n). Sind die Datenmengen klein, bleiben Sie lieber bei einer trivialen linearen Suche.

Cachen Sie Werte, statt sie immer neu zu laden oder zu berechnen. Aber Vorsicht: Insbesondere in Systemen, die mit mehreren Threads oder mit Transaktionen arbeiten, sollten Sie sich die Folgen gut überlegen und mögliche Inkonsistenzen der Daten bedenken. Denken Sie auch daran, die Größe des Cache zu begrenzen, damit das System nicht seine Speicherbereiche auf die Platte auslagert und damit jeden Geschwindigkeitsgewinn zunichte macht. Die Situationen, die auch Caching sinnvoll erscheinen lassen, sind oft gerade jene, in denen die Verwendung eines Datenbankservers das Programm beschleunigt.

Wenn Sie ein Objekt auf einer Festplatte speichern oder es über ein Netzwerk verschicken, können Sie den Vorgang beschleunigen, indem Sie nur den tatsächlich geänderten Teil der Daten übertragen. Nachteilig ist dabei, dass diese Optimierung die Abstraktion einer Klasse oder sonstigen Code beeinträchtigen kann. Versuchen Sie daher die Schnittstelle abstrakt zu halten, auch wenn Sie intern optimieren.

Bei der zeilenweisen Verarbeitung von Textdateien gelten folgende Regeln: Sind die zu verarbeitenden Dateien kurz, ist es meist einfacher und schneller, sie komplett einzulesen und alle Daten zu verarbeiten. Sind die Dateien aber lang – Logdateien sind ein typisches Beispiel -, sollten Sie jeweils eine Zeile lesen und diese gleich bearbeiten. Andernfalls könnten die eingelesenen Daten den verfügbaren Arbeitsspeicher sprengen; ständiges Swappen würde den Rechner in die Knie zwingen.

Eng verwandt mit der Wahl von Algorithmen ist die Auswahl der richtigen Datenstrukturen. Mit ihnen ändern sich implizit die Algorithmen für den Datenzugriff. Wie oben gezeigt, finden Sie einen bestimmten Schlüssel in einem Dictionary wesentlich schneller als einen Wert in einer Liste, für den Sie linear suchen müssten.

Die Architektur eines Softwaresystems hat ebenfalls großen Einfluss auf die Laufzeit. Man kann sie als den Algorithmus ansehen, nach dem das Gesamtsystem arbeitet. Im Gegensatz zu anderen Optimierungen sollten Sie sich über die Architektur schon zu Beginn der Entwicklung ein paar Gedanken machen.

Python-Tricks

Bei Python-spezifischen Optimierungen sollten Sie beachten, dass sich manche je nach Python-Version verschieden auswirken. In Extremfällen wird ein Codestück durch eine neue Python-Version sogar langsamer, aber das ist wohl die Ausnahme. Der einfachste Weg zur Optimierung von Python-Skripten ist es, die Option »-O« des Interpreters zu verwenden, um den erzeugten Python-Bytecode von ihm optimieren zu lassen.

Im Skript sollten Sie auf »from modul import *« verzichten. Der Python-Interpreter kann sonst einige interne Optimierungen nicht mehr durchführen. Dieses Idiom verschlechtert auch die Wartung, sodass Sie mit dem Verzicht zwei Fliegen mit einer Klappe schlagen.

Sparen Sie Lookup-Operationen in mehreren Namensräumen, indem Sie Objekte im lokalen Namensraum binden. Zum Beispiel können Sie nach der Zeile »opj = os.path.join« die »join«-Funktion schneller als »opj« erreichen. Offensichtlich macht diese Optimierung den Code schlechter lesbar.

Setzen Sie nicht »exec« und »eval« ein. Python ist sehr flexibel, daher ist eine Codevariante, die ohne »exec« und »eval« auskommt, meist sogar die verständlichere Version. Insbesondere Code, der kurz laufende Funktionen in Schleifen ausführt, lässt sich oft durch das Inlinen des Funktionsrumpfes beschleunigen. Das erhöht aber im Allgemeinen die Redundanz und macht die Software schwieriger zu warten.

Wollen Sie viele Zeichenketten hintereinander hängen, sammeln Sie sie in einer Liste und verknüpfen die Listenelemente hinterher mit »””.join(liste)«. Das geht viel schneller als die Verkettung mit »+«. Das »key«-Argument in »list.sort« führt zu schnellerem Code als das »cmp«-Argument. Im ersten Fall wird die Vergleichsfunktion für jeden Listenwert nur einmal berechnet, im zweiten Fall für jeden Vergleich zweier Werte.

Sie können Dictionaries oder Mengen (Sets) verwenden, um Werte zu ermitteln, die in zwei Wertemengen oder nur in einer von zwei Wertemengen auftreten. Manchmal sind List Comprehensions oder Generator Comprehensions schneller als »for«-Schleifen.

Manchmal ist es das Beste, eine Operation in hochoptimiertem C ausführen zu lassen, aber trotzdem Pythons Vorzüge beizubehalten. Dazu schreiben Sie Ihren Code oder Teile davon so um, dass er möglichst viele von Pythons eingebauten Funktionen (zum Beispiel »range« statt einer entsprechenden Schleife) oder Datentypen (Listen, Tupel, Dictionaries, Mengen) nutzt.

Verwenden Sie in C geschriebene Bibliotheken für zeitkritischen Code. Zum Beispiel können Sie XML mit der Libxml2-Bibliothek [5] parsen. Zum Kapseln vorhandener C-Bibliotheken bieten sich SWIG [6] und Ctypes [7] an. Letzteres ist seit Python 2.5 sogar Bestandteil der Standard-Distribution.

Pyinline [8] und Weave [9] erlauben es, C-Fragmente in Python-Code zu integrieren. Einen etwas anderen Weg geht Pyrex [10], eine Sprache, die Python sehr ähnlich ist und die sowohl vorhandene C-Bibliotheken kapseln als auch eigene (letztlich in C konvertierte) Erweiterungen erzeugen kann. Am flexibelsten, aber auch am kompliziertesten ist das Python/C-API. Als Alternative dazu, gleich in C zu programmieren, bietet sich Psyco [11] an, ein Just-in-Time-Compiler für Python, der aber leider nur für 32-Bit-x86-Systeme verfügbar ist.

Trau, schau wem

Auch in interpretierten Sprachen wie Python lassen sich flotte Programme schreiben. Wichtig ist dabei, nicht drauflos zu optimieren, sondern erst zu testen, ob die Software für die geplante Anwendung bereits schnell genug ist. Wenn nicht, bestimmen Sie die Engpässe des Code mit geeigneten Werkzeugen und optimieren Sie gezielt.

Den größten Geschwindigkeitsgewinn erzielen Sie mit der Änderung von Algorithmen und Datenstrukturen. Python-spezifische Optimierungen können ebenfalls helfen. Nutzen Sie besonders die Gelegenheiten, implizit C-Code in Form von Python-Code zu verwenden, zum Beispiel durch Pythons Datenstrukturen oder externe C-Bibliotheken. Und denken Sie daran: Behalten Sie bei allen Optimierungen die Wartbarkeit der Software im Auge. (ofr)