Python beschleunigen. Was hilft?

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
BlackJack

Freitag 13. März 2009, 21:30

Ansonsten kann man Python-Programme noch beschleunigen indem man schaut ob man bessere Algorithmen verwenden kann. Und immer dran denken zu "profilen", damit man nicht an den falschen Stellen optimiert.

Wenn man Psyco auf ganze Programme loslässt, sollte man auch ein Auge auf den Speicherverbrauch haben, der dadurch ganz schön in die Höhe schiessen kann. Auch hier lohnt es sich den Profiler anzuwerfen und dann nur gezielt bestimmte Funktionen durch Psyco zu jagen.

Zur Zukunft von Psyco: Ich dachte ja auch immer das Projekt wird nicht weiter entwickelt, aber ich habe gerade letzte Woche eine Ankündigung eines Vortrags von Christian Tismer bei der Python Usergroup Berlin mit dem Titel `Psyco v2` gelesen. Vielleicht tut sich da ja doch noch etwas.

Zeit und Ort: 19.03. 19Uhr, newthinkingstore, Tucholskystr. 48, 10117 Berlin
burli
User
Beiträge: 1116
Registriert: Dienstag 9. März 2004, 18:22

Freitag 13. März 2009, 21:39

Ja, das wollte ich vorhin auch schonmal fragen. Wie Profilet man? Gibt es da schon was fertiges? Gibt es einen Profiler der so Infos ausspuckt welche Funktion wie oft aufgerufen wurde, wie lang die durchschnittliche Ausführungszeit der Funktion war usw?
Benutzeravatar
Blade Runner
User
Beiträge: 21
Registriert: Montag 23. Februar 2009, 11:41

Freitag 13. März 2009, 21:42

burli hat geschrieben:Wie Profilet man? Gibt es da schon was fertiges? Gibt es einen Profiler der so Infos ausspuckt welche Funktion wie oft aufgerufen wurde, wie lang die durchschnittliche Ausführungszeit der Funktion war usw?
http://docs.python.org/library/profile.html
[quote="Roy Batty"]All those moments will be lost in time, like tears in rain ... time to die.[/quote]
burli
User
Beiträge: 1116
Registriert: Dienstag 9. März 2004, 18:22

Freitag 13. März 2009, 23:14

ok, danke. Ist recht einfach. Aber mit GUI Programmen (wx, Qt) scheint das nicht zu funktionieren, zumindest nicht so ohne weiteres, kann das sein? Ich habe es nämlich auf diverse Programme losgelassen und es kam nichts dabei raus.
Benutzeravatar
Hyperion
Moderator
Beiträge: 7472
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Freitag 13. März 2009, 23:20

burli hat geschrieben:ok, danke. Ist recht einfach. Aber mit GUI Programmen (wx, Qt) scheint das nicht zu funktionieren, zumindest nicht so ohne weiteres, kann das sein? Ich habe es nämlich auf diverse Programme losgelassen und es kam nichts dabei raus.
Wobei die "stressigen" Algos ja eher unabhängig von der GUI implementiert sein sollten! Und dann stellt das kein Problem mehr dar.
burli
User
Beiträge: 1116
Registriert: Dienstag 9. März 2004, 18:22

Samstag 14. März 2009, 01:08

stimmt auch wieder. ich nehme mal an, man muss den Profiler dann selektiv auf bestimmte Funktionen ansetzen. Na mal sehen
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Samstag 14. März 2009, 11:16

Ich verstehe die Frage mal als "kann man Python prinzipiell beschleunigen". Wie viel Luft nach oben ist da noch, gerade auch im Vergleich zu "schnelleren" dynamischen Sprachen wie z.B. Smalltalk oder JavaScript? Dabei muss natürlich die komplette Semantik von Python erhalten bleiben. Kann man Techniken dieser Sprachen übernehmen?

Kann man mit Python etwa die Geschwindigkeit von Java oder C erreichen?

Dabei geht es mir nicht darum, ob man eine spezielle Operation jetzt schneller hinbekommt sondern ob das typische durchschnittliche Python-Programm so schnell ablaufen kann. Als typisch definiere ich dabei einen Methodenaufruf. Letztlich ist alles ein Methodenaufruf und `3+4` entspricht `(3).__add__(4)`. Die Performance dieser Operation - das haben schon Untersuchungen von Smalltalk in den 80ern gezeigt - bestimmt entscheidend die Gesamtperformance der Programmiersprache.

Optimieren, so hat ein schlauer Mensch mal gesagt, dessen Namen ich nicht kenne, aber ich habe es von Dan Ingalls gehört, ist die Kunst, sich beim Schummeln nicht erwischen zu lassen.

Bevor wir optimieren können, müssen wir erst einmal sehen, was eigentlich bei `a.m(b)` in Python alles passiert.

Es wird die Klasse von `a` bestimmt. CPython speichert für jedes Objekt meines Wissens einen Pointer auf das Objekt, welches die Klasse repräsentiert. Typisch für viele Sprachen ist, dass es verschiedene Objektrepräsentationen gibt und man diese noch unterscheiden muss. Ruby behandelt z.B. fixnums und ein paar anderen Objekte speziell. Dies hat sich eigentlich als vorteilhaft herausgestellt. Keine Ahnung, warum Python das nicht macht.

Hat man die Klasse, muss man nach einer `__getattribute__`-Methode suchen. Falls es diese gibt, werden `a` und `m` nämlich nicht normal gesucht, sondern es wird `__getattribute__` aufgerufen. Falls man nichts findet, wird im `__dict__` von `a` nach einem Wert zu dem Schlüssel `m` gesucht. Gibt das einen `KeyError`, geht es weiter. Ansonsten hat man seinen Wert.

Eine Methode wird gesucht, in dem in dem `__dict__` der Klasse nach dem Namen gesucht wird. Gibt dies einen `KeyError`, wird in den Oberklassen nachgeschaut. Dazu muss die Menge der Oberklassen gemäß eines recht komplexen Algorithmus serialisiert werden und die MRO-Liste entsteht. Diese kann man nun iterieren und in jeder Klasse (es sind doch hoffentlich nur Klassen, jedenfalls sollten sie ein `__dict__` haben, ob Python es wohl ab kann, wenn man da andere Objekte hineinschummelt?) wird das `__dict__` untersucht. Ist man am Ende der Liste angekommen und immer noch nicht fündig, wird ein `AttributeError` geworfen.

In diesem Fall oder falls `__getattribute__` die Exception geworfen hat, wird nach `__getattr__` gesucht. Gibt das auch einen `AttributeError`, wird der erste Fehler geworfen. Falls nein, hat man den Wert.

Dies kann ein Descriptor sein. Hat er eine `__get__`-Methode (und schon wieder findet die komplette Methodensuche statt!), wird diese aufgerufen und jetzt man man endgültig seinen Wert. Ist das eine Funktion, mache sie zu einer Methode. In Python 3 geschieht dies glaube ich nicht mehr explizit sondern dadurch, dass jedes Funktionsobjekt eine passende `__get__`-Methode hat und somit ein Descriptor ist.

Das man neben `__dict__` auch immer noch `__slots__` untersuchen muss, lasse ich mal zur Vereinfachung weg.

In jedem Fall hat man jetzt bereits schon mehrere 100 oder 1000 Maschinenbefehle ausgeführt, nur um `a.m` auszuwerten.

Eine Funktion oder ein Methode, allgemein ein callable aufzurufen, ist der zweite komplexe Prozess. Ich suche nun nach der Methode `__call__` wie oben. Ich schaue mir an, wie viele Parameter mein callable benötigt und wie viele ich habe. Passt dies nicht, ist es ein `TypeError`. Dann ordne ich Positionsparameter zu, in dem ich ein Tupel baue, in das ich `b` (und mögliche weitere Argumente) einfüge. Erwartet das callable mehr Parameter als ich habe und gibt es Standardwerte, hole ich mir diese aus dem Funktionsobjekt und trage sie ebenfalls in das Tupel ein. Wurde mir eine mit `*` gesplicte Liste übergeben, mache ich daraus (indem ich nach `__iter__` und ein paar anderen Dingen suche und das dann Aufrufe) eine aufzählbare Sequenz und füge so viele Argumente wie nötig zu meinem Tupel hinzu. Gibt es noch einen `*`-Parameter, mache ich aus dem Rest ein zweites Tupel und füge dieses dann zu dem ersten Tupel hinzu. Gibt es in der Argumentliste noch Schlüsselwörter, suche ich zu jedem Namen in der Parameterliste die richtige Position heraus und wenn da noch kein Wert steht, trage ihn ein. Andernfalls ist es ein `TypeError`. Habe ich ein mit `**` gesplictes dict, iteriere die items (und noch eine Methodensuche nach `items` und nach `__iter__` und Aufrufe dieser Methoden). Gibt es in der Parameterliste ein `**`, verpacke den Rest in einem neuen `dict` und füge es dem ersten Tupel hinzu.

Ich habe jetzt meine Parameterliste. Nun kann ich meine Funktion aktivieren, in dem ich einen neuen Frame erzeuge, dort eine Referenz auf das globals-`dict` aus der Funktion eintrage, ein neues `dict` für die lokalen Variablen einfüge und aus der Liste der Parameternamen und meinem Tupel dieses `dict` fülle.

In diesem neuen Frame kann ich nun die eigentliche Funktion aufrufen.

Auch dies sind einige 100 wenn nicht 1000 Maschinenbefehle, wenn man wirklich alle Varianten der doch recht komplexeren Aufrufsemantik von Python berücksichtigen will. Dies war der `(b)`-Teil.

Von Closures war jetzt noch gar nicht die Rede.

Am Ende der Funktion muss ich ein Tupel aus den Rückgabewerten bauen, den Frame wieder abbauen und die Kontrolle zurück an den aufrufenden Frame geben. Dieser wird in der Regel das Tupel zuerlegen und die Werte irgendwelchen Variablen zuweisen.

Was passiert im Vergleich dazu bei C++?

Jedes Objekt, auf das ein Pointer zeigt, trägt an dieser Stelle einen Pointer auf eine Sprungtabelle mit Pointern auf die virtuellen Funktion. Ich hole mir diese Tabelle, weiß dann, mit welchem Offset in dieser Tabelle `m` assoziiert ist, hole mir die Funktion, schiebe `b` auf den Stack und rufe die Funktion auf.

Java geht in der Regel noch trickreicher vor. An der Aufrufstelle hat sich der Code durch vorherige Optimierungen des dynamischen just-in-time-Compilers derart verändert, dass dort einfach folgender Code steht: Ist die Klasse von `a`, die die ich glaube, dass es sie ist (ein einfacher Vergleich), dann führe den folgenden Code aus, der aus dem Funktionsobjekt hier hin kopiert wurde. Falls nein, gehe so vor wie bei C++.

Das nennt sich dann Callsite-Inline-Caching und wenn man nur nur auf eine Klasse testet, sondern z.B. auf 4 oder 8, spricht man von Polymorphic oder Megamorphic Inline Caching. Das meiste bringt hierbei das inlinen, sprich, das Kopieren des Codes aus der in der Regel sehr kurzen Funktion bzw. Methode und so das Vermeiden von Sprüngen zu absoluten Adressen. Das killt nämlich die langen Befehlsverarbeitungsprozesse moderner CPUs und führt zu Cache-Fehlern und zwingt die CPU lange pause zu machen, bis neue Daten aus dem Hauptspeicehr (der im Vergleich zur CPU und ihren Caches extrem langsam ist) vorliegen.

Will man Python schneller machen, muss man schummeln, d.h. optimieren, und häufige Sonderfälle erkennen und anders behandeln. Das ist nicht einfach. CPython macht schon das eine oder andere, aber im Vergleich zu JavaScript, welches dank moderner JIT-Compiler, die mit Callsite-Caches und anderen Strategien arbeiten locker überholt hat, ist das echt schwer.

Wenn man erkennen könnte, dass man keine komplexe Funktionsaufrufsemantik braucht oder keine Metamethoden zum Finden von Attributen hat, könnte man etwas reißen. Ideen, wo man eingreifen kann, überlasse ich dem Leser, der bis hier durchgehalten hat.

Meiner Einschätzung nach, hat Ruby aber mehr Potential, von den neuen Entwicklungen bei JavaScript (also v8, TraceMonkey und SquirrelFishExtreme) zu profitieren, da es vom Objektmodell wesentlich einfacher aufgebaut ist.

Eine vielversprechende Idee von v8 und Maglev ist, Attribute nicht naiv in Dictionaries zu halten, sondern als Feld von Exemplarvariablen, in das man mit einem einfachen numerischen Index greift. Dazu rät man einmal nach Ausführen des Konstruktors die Feldstruktur und baut das Feld einfach bei jeder dynamischen Änderung (die eher selten sein sollten) um und kompiliert alle Methode mit neuen Indizes neu. Das spart diese leidigen `dict`-Suchen ein. Eine weitere Idee wäre, Einfachvererbung speziell zu behandeln, da man so die MRO-Liste einsparen kann.

Stefan
Darii
User
Beiträge: 1177
Registriert: Donnerstag 29. November 2007, 17:02

Samstag 14. März 2009, 15:15

Danke für diesen tollen Beitrag sma :)
Antworten