Optimierung: Tricks, Fallstricke und Mythen

[Defnull]

Wusstet ihr, das seit Python 2.5 String Concatenations so schnell sind, das der sonst immer gern zitierte join() Trick kaum noch etwas bringt und sogar schaden kann?

Code: Alles auswählen

>>> min(timeit.repeat('"".join(str(x) for x in xrange(10000))', number=1000))
5.4210538864135742
>>> min(timeit.repeat('out = ""\nfor x in xrange(10000):\n  out += str(x)', number=1000))
5.1908931732177734

Für mich war das neu. Zwei Links kann ich auf jeden Fall empfehlen:

http://wiki.python.org/moin/PythonSpeed/PerformanceTips
http://www.python.org/doc/essays/list2str.html

Daraus lernt man nämlich auch, das Name lookups ziemlich teuer sind, besonders wenn sie nicht auf den lokalen Namensraum, sondern auf globale Variablen oder Objekt-Namensräume zielen. Folgendes hat mich ziemlich überrascht:

Code: Alles auswählen

>>> min(timeit.repeat('a=[]\nfor x in xrange(10000):\n  a.append(x)', number=1000))
1.5238909721374512
>>> min(timeit.repeat('a=[]\nap=a.append\nfor x in xrange(10000):\n  ap(x)', number=1000))
0.82951712608337402

Gibt es sonst noch hartnäckige Optimierungs-Mythen oder vielleicht auch Tricks, die wirklich was bringen? In diesem Thread könnten wir sie ja mal sammeln.

[jens]

Ich wäre da vorsichtig. Was ist wenn eine neue Python Version sich wieder anders verhält? Wichtiger ist gut lesbaren Code statt optimierten.

[numerix]

Gibt es sonst noch hartnäckige Optimierungs-Mythen oder vielleicht auch Tricks, die wirklich was bringen? In diesem Thread könnten wir sie ja mal sammeln.

Ich glaube nicht, dass dabei so wirklich viel herauskommt. Gerade was die Zeichenkettenkonkatenation angeht, gibt es dazu bereits mindestens einen längeren Thread hier im Forum (ca. Herbst 2009), der verschiedene Aspekte beleuchtet und wo unter dem Strich herauskommt, dass viel von der konkreten Python-Implementation abhängt.

Ich habe in den letzten Monaten die ein oder andere Aufgabe bei SPOJ mittels Python gelöst und da kommt man bei einigen Aufgaben um reichlich Performance-Optimierung nicht umhin, um innerhalb des gegenbenen Zeitlimits mit einer Python-Lösung durchzukommen. Dabei musste ich z.B. feststellen, dass es z.B. bei join() und "+" davon abhängt, wie lang die schon existierende Zeichenkette ist, an die angehängt wird, wie lang die Zeichenketten sind, die angehängt werden und wie oft angehängt wird.
Manches hängt auch davon ab, ob psyco verwendet wird oder nicht, denn nicht alles, was ohne psyco die performantere Lösung ist, gilt auch für psyco.
Gelegentlich wird hier im Forum zum Thema "Tupel und Listen" darauf verwiesen, dass Tupel aufgrund ihres immutablen Charakters effizienter (implementierbar?) sind. Was die Performance angeht, so habe ich die Erfahrung gemacht, dass in aller Regel die Verwendung von Listen performanter ist.

Was die lookups angeht. In vielen Fällen ist die Verwendung von lokalen Variablen performanter als die von globalen. Insbesondere bei größeren Datenstrukturen gilt das aber nicht unbedingt (so jedenfalls meine Erfahrung). Speziell bei der Verwendung von Arrays (ja, ich meine Arrays!) kann es performanter sein, nur ein globales Array zu erzeugen (die Erzeugung großer Arrays ist nämlich erheblich teurer als die von Listen) und es ggf. innerhalb einer Funktion nur neu zu initialisieren statt es immer wieder neu (lokal) zu erzeugen.

Ja, natürlich weiß ich, dass es numpy & co gibt, aber bei SPOJ hilft das z.B. nicht ...

[Defnull]

Was die lookups angeht. In vielen Fällen ist die Verwendung von lokalen Variablen performanter als die von globalen. Insbesondere bei größeren Datenstrukturen gilt das aber nicht unbedingt (so jedenfalls meine Erfahrung). Speziell bei der Verwendung von Arrays (ja, ich meine Arrays!) kann es performanter sein, nur ein globales Array zu erzeugen (die Erzeugung großer Arrays ist nämlich erheblich teurer als die von Listen) und es ggf. innerhalb einer Funktion nur neu zu initialisieren statt es immer wieder neu (lokal) zu erzeugen.

Du hast weitgehend recht, hier aber nicht, denke ich. Klar, das Erzeugen von Objekten ist teuer. Es macht durchaus Sinn, eine teure Datenstruktur wieder zu verwenden statt sie neu zu erzeugen. Was aber gemeint ist, ist folgendes:

Dot-Lookups (wie in "a.append()") sind teuer. Es kann Sinn machen, die Methode an eine lokale Variable zu binden, um aus drei Lookups (a, a.__dict__, a.__dict__['append']) einen zu machen. Wie in meinem zweiten Code-Beispiel oben.

Globale Lookups sind teuer, besonders bei vollen lokalen oder globalen Namensräumen. Die Variable muss nämlich erst lokal, dann in alle Namensräumen die zum Definitionszeitpunkt des Funktionsblockes aktiv waren und schließlich im globalen Namensraum gesucht werden. Bei CPython kommt noch hinzu, das ein Lookup nach einem fehlenden Key in der Regel langsamer ist als die Suche nach einem Existierenden. Ein "global" Statement kann daher, selbst wenn man nur lesend auf die Variable zu greift, bei exzessiv genutzten variablen oder Funktionen, durchaus sinnvoll sein. Das erhebt die Variable nämlich schon zur Compile-Zeit in den lokalen Namensraum und beschleunigt damit die Lookups.

Ich rede also nicht vom erzeugen separater lokaler Versionen der Variablen, sondern vom referenzieren globaler oder Objektgebundener Variablen im lokalen Namensraum, um Lookup-Zeit zu sparen.

Beide Tipps verringern allerdings die Les- und Wartbarkeit und sind nur für sehr Performance-kritische Situationen gedacht.

[Leonidas]

Tupel aufgrund ihres immutablen Charakters effizienter (implementierbar?) sind.

... speichereffizienter ...

[Defnull]

Tupel aufgrund ihres immutablen Charakters effizienter (implementierbar?) sind.

... speichereffizienter ...

Nicht nur.

Code: Alles auswählen

>>> min(timeit.repeat('[1,2,3,4,5][-1]', number=1000000))
0.19115710258483887
>>> min(timeit.repeat('(1,2,3,4,5)[-1]', number=1000000))
0.025287866592407227

>>> min(timeit.repeat('[1,2,3,4,5].append(6)', number=1000000))
0.35457897186279297
>>> min(timeit.repeat('(1,2,3,4,5)+(6,)', number=1000000))
0.12063097953796387

Ich finde das schon beachtlich.

[numerix]

Ich finde das schon beachtlich.

Siehst du, genau das meinte ich damit, dass da nicht viel bei herauskommt. Nimmst du nämlich stattdessen z.B. eine lange Liste bzw. Tupel (sagen wir mit 10^7 ints) und rufst (sagen wir ebenfalls 10^7 mal) jeweils das letzte Element ab, dann ist - jedenfalls auf meinem Rechner - die Liste um ca. 15% schneller als das Tupel, die Zeit für die Erzeugung der Datenstruktur ist praktisch gleich.

Edit: Und wenn du psyco dazu nimmst, dann ist der Lookup in der Liste sogar um den Faktor 6 schneller als der im Tupel (Python 2.5). Nimmt man ein echtes Array, dann ist es nochmal ca. doppelt so schnell - dafür dauert die Erzeugung aber unsäglich lang.

[sma]

Optimierungen sind ein Weg, den man nicht gehen will. Nehmen wir eine Schleife, die von 1 bis 10.000 zählt (der komplette Quelltext kommt unten). Lasse ich sie 1000x laufen, sind das 0.2sek. Nun addiere ich 10000x ein "x" zu einem String. Macht 0.9sek, also 0.7 abzüglich der Schleife. Nun füge ich einen Leerstring 10.000x zu einem Array hinzu. Macht 1.3sek. Addiere ich nun meine "x" zu dem String und füge diesen String immer zu dem Array hinzu, komme ich auf 1.3+0.7=2sek, richtig? Falsch, es dauert jetzt über 50sek, denn der String hat jetzt mehr als eine Referenz und Python kann seinen kleinen Trick nicht mehr ausführen, da 10.000x ein immer größer werdender String kopiert werden muss. Auf einmal ist "+=" wieder so langsam wie es auch vorher war.

Code: Alles auswählen

import timeit

s = """
def x():
    s = ""
    t = []
    for i in xrange(10000):
        s += "x"
        t.append(s)
    return s, t
x()"""
print timeit.repeat(s, number=1000)

Stefan

[numerix]

Optimierungen sind ein Weg, den man nicht gehen will.

Also so würde ich das nicht sagen wollen. Will man z.B. bei SPOJ (mit Gewalt) ein bestimmtes Problem mit Python lösen (und das will ich manchmal), dann geht es oft nicht ohne Optimierungen.

Der Rest deines Posts ist allerdings ein weiterer Beleg für das, was ich schon im ersten Post gesagt habe.

[BlackJack]

Defnull: Ich bin mir nicht so ganz sicher was Du mit der lookup-Reihenfolge bei globalen Namen meinst, denn *lokal* müssen die zumindest bei CPython gar nicht erst nachgeschlagen werden, weil der Compiler schon weiss, dass so ein Namen nicht lokal ist. Und er weiss auch schon *wo* dynamisch nachgeschaut werden muss, also bleibt genau ein dynamischer lookup für den Zugriff übrig. Wo wirklich durchprobiert wird, sind Attribute in der Klassenhierarchie. Auch das könnte eine Implementierung cachen, und das Laufzeitverhalten ändern. Das sind also alles relativ unsichere Sachen, die wie schon gesagt von der Implementierung abhängen können.

[DasIch]

In diesem Zusammenhang ist vielleicht promise(auch im cheeseshop) interessant. Durch Dekoratoren kann man damit eine Reihe von Dingen "versprechen", woraufhin der bytecode optimiert werden kann.

[bords0]

Ein "global" Statement kann daher, selbst wenn man nur lesend auf die Variable zu greift, bei exzessiv genutzten variablen oder Funktionen, durchaus sinnvoll sein. Das erhebt die Variable nämlich schon zur Compile-Zeit in den lokalen Namensraum und beschleunigt damit die Lookups.

Ist das aus der Kategorie Mythos?
Hast du ein Beispiel? Mit dis.dis erkenne ich mit und ohne global LOAD_GLOBAL.

Code: Alles auswählen

>>> def f():
...     global a
...     return a
... 
>>> def g():
...     return a
... 
>>> import dis
>>> dis.dis(f)
  3           0 LOAD_GLOBAL              0 (a) 
              3 RETURN_VALUE         
>>> dis.dis(g)
  2           0 LOAD_GLOBAL              0 (a) 
              3 RETURN_VALUE         

[cofi]

@Defnull: Afair betrifft String Concatenation nur CPython. Gerade jetzt wo die Alternativen eigentlich durchstarten wuerde ich mich darauf nicht mehr verlassen und mich an PEP-8 halten, das empfiehlt nicht auf eine (Interpreter-)Plattform hin zu optimieren.

[jens]

promise ... , woraufhin der bytecode optimiert werden kann.

...ja und wird es auch optimiert? Oder braucht man dazu etwas externes???

[DasIch]

Es wird durchaus optimiert.

[snafu]

Ich hoffe ja mal, dass (C)Python bald von selbst solche Optimierungen erkennt, wenn die Sprache jetzt doch eh für einige Zeit ruhen soll. Denn idiomatisches Programmieren (Nutzen von Comprehensions usw) ist das Eine. Es sollte aber IMHO nicht so weit gehen, dass man irgendwelche Funktionsaufrufe cachen muss (`a = l.append`). Bei einer Sprache wie Python ist das vermutlich nicht so einfach, aber man wird wohl über kurz oder lang nicht drum rum kommen. Projekte wie dieses `promise`, `psyco` oder alternative Implementierungen vom Python machen es ja vor.

[DasIch]

Das Problem bei solchen Optimierungen ist, dass sie es schwerer machen CPython zu maintainen. Sobald eine Optimierung einen gewissen Grad an Komplexität übersteigt, interessiert sich keiner mehr für die Benchmarks.

[Dauerbaustelle]

Sobald eine Optimierung einen gewissen Grad an Komplexität übersteigt, interessiert sich keiner mehr für die Benchmarks.

Wie meinen?

[cofi]

...ja und wird es auch optimiert? Oder braucht man dazu etwas externes???

Falls du noch mehr Infos willst:
http://panela.blog-city.com/the_promise ... thon_1.htm
http://pypi.python.org/pypi/promise

(Hab mich damit allerdings noch nicht beschaeftigt, steht aber auf der ToDo-Liste )