Seite 1 von 2

Python beschleunigen: Pyrex, weave, C++, Cython -- und nun?

Verfasst: Freitag 6. Mai 2011, 21:02
von Tyrax
Hallo Gemeinde,

ich möchte einen Teil meines Codes beschleunigen und weiß nicht, was ich dafür verwenden soll. Zwei threads im Forum und einige weitere Quellen, helfen mir nicht wirklich. Hier mal die Eckdaten:

- In Python läuft mein Code, wenn auch mutmaßlich sehr langsam.
- Ich kann bisher weder C(++) noch FORTRAN.
- Der langsame Teil meines Python-Codes braucht nicht viel mehr als das folgende (sinnlose) Programm:

Code: Alles auswählen

def dummeFunktion(a, b, c, d):
  import random
  check = 0
  while check==0:
    x = random.gauss(a, b)
    y = random.gauss(c, d)
    if x==y:
      check = 1
  return x
Mein Ziel ist wie gesagt, den Code zu beschleunigen, mein Wunsch wäre, dafür nicht erstmal ernsthaft C++ lernen zu müssen.

Wie sollte ich am besten vorgehen und was sollte ich verwenden (zum Beispiel aus der Liste im Titel)?

Danke und beste Grüße, Tyrax

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Freitag 6. Mai 2011, 21:59
von BlackJack
@Tyrax: Welcher konkrete Code beschleunigt werden soll kann wichtig bei der Auswahl des Werkzeugs sein. Oder vielleicht auch bei der Frage ob es sich überhaupt sinnvoll beschleunigen lässt. Bei dem gezeigten Beispiel würde ich das zum Beispiel verneinen. Das erscheint mir in jeder Sprache unsinnig. Ob man da nun in Python, Fortran, C, oder sonstwas drauf wartet…

Aus der Liste würde ich Pyrex rauswerfen, denn Cython kann im Grunde das gleiche und dann noch mehr. Mit `weave` habe ich keine Erfahrung und um C++ würde ich persönlich einen Bogen machen. C käme eventuell in Frage. `psyco` fehlt in der Liste.

Es gibt keine magische Lösung, man muss schon schauen und ausprobieren was bei dem konkreten Problem etwas bringt.

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Freitag 6. Mai 2011, 22:04
von pillmuncher
Wenn man wüsste wie dein langsamer Code aussieht, könnte man vielleicht ein paar Tips geben, wie man ihn verschnellern könnte. Ihn einfach mal auf gut Glück in C++ nachzubauen ist wenig sinnvoll, wenn du nicht schon von vornherein weißt, wo der Flaschenhals sitzt. Also bitte herzeigen.

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Samstag 7. Mai 2011, 09:59
von sma
die gezeigte Funktion hängt eigentlich nur von der Bibliotheksfunktion random.gauss und deren Performance ab. Sie ist implementiert als:

Code: Alles auswählen

def gauss(self, mu, sigma):
        random = self.random
        z = self.gauss_next
        self.gauss_next = None
        if z is None:
            x2pi = random() * TWOPI
            g2rad = _sqrt(-2.0 * _log(1.0 - random()))
            z = _cos(x2pi) * g2rad
            self.gauss_next = _sin(x2pi) * g2rad

        return mu + z*sigma
random() selbst ist eine C-Funktion. Das gilt garantiert auch für _sqrt, _log, _cos und _sin. Wenn überhaupt, lohnt es daher, eine schnellere Funktion für diese Gauss-Verteilung zu finden. Sei es ein besserer Algorithmus (falls es den gibt) oder eben davon direkt eine Implementation in C.

Das gezeigte Programm selbst lohnt nicht zu optimieren, weil es selbst vernachlässigbar ist, was die Zeit angeht - ne while-Schleife und ein Test und eine Variablenzuweisung. Man könnte es so umschreiben:

Code: Alles auswählen

import random # rausziehen!
def dummeFunktion(a, b, c, d):
  while True:
    x = random.gauss(a, b)
    if x == random.gauss(c, d):
      return x
Stefan

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Samstag 7. Mai 2011, 10:04
von BlackJack
Man könnte noch den Attributzugriff eliminieren:

Code: Alles auswählen

from random import gauss

def dumme_funktion(a, b, c, d):
    while True:
        x = gauss(a, b)
        if x == gauss(c, d):
            return x
Und vielleicht wäre es eine gute Idee vor Eintritt in die Schleife zu prüfen ob die Bedingung jemals erfüllbar ist. :-)

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Samstag 7. Mai 2011, 14:30
von noisefloor
Hallo,

@Tyrax: Willst du denn nur diese ein Funktion "schnell" implementieren und der Rest bleibt Python?

Und ob das ganze schnell oder langsam ist hängt ja auch davon ab, wie oft die while-Schleife durchlaufen wird. Im Idealfall ist es ja nur 1x - dafür muss man nicht optimieren. ;-)

Gruß, noisefloor

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Samstag 7. Mai 2011, 16:09
von Tyrax
Hallo zusammen,

erstmal danke für die Kommentare. Hier mal eine Beschreibung der Aufgabe, die Eure Nachfragen hoffentlich beantwortet:

- Ich betrachte zwei Random Walker und interessiere mich für die Verteilung der Zeiten (Anzahl der Schritte) nach denen sie sich treffen.
- Wegen der Verteilungen, lasse ich die while-Schleife *oft* laufen.
- Das ganze hängt von einer Reihe von Parametern ab - für jeden Parametersatz gibt's ne andere Verteilung.
- Der Inhalt der while-Schleife besteht aus ein paar ifs, whiles und eben dem Erzeugen von Pseudozufallszahlen gemäß zB der Normalverteilung (Daher meine offensichtlich sinnlose Beispielfunktion).

Laut zB http://www.scipy.org/PerformancePython lässt sich Python-Code in einigen Fällen wesentlich beschleunigen -- das käme mir durchaus gelegen. Die ganze Verwaltungsarbeit (Ausgaben erzeugen, Daten sortieren und Co) will ich in Python lassen -- das geht sowieso schnell.

Falls möglich (dazu gerne weitere Kommetare) will ich also die Erzeugung der einzelnen Random-Walk-Zeiten beschleunigen. Meines Erachtens ist das der bottleneck des Prozesses (10^9 Durchläufe der while-Schleife sind durchaus möglich).

Danke und beste Grüße, Tyrax

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Samstag 7. Mai 2011, 17:30
von BlackJack
@Tyrax: Versuch doch erst einmal das "Meines Erachtens…" im letzten Beitrag durch "Meines Wissens…" zu ersetzen. Messen wie oft was aufgerufen wird und wie viel Zeit es verbraucht.

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Samstag 7. Mai 2011, 20:03
von noisefloor
Hallo,

und dann vielleicht auch erstmal probieren, was es bringt, die Optimierungen zu nutzen, die Python an sich so bringt (z.B. optimierter Byte-Code).

Ansonsten ist die Funktion nicht sooo komplex. Du kannst sie ja auch mal aus Spaß an der Freunde in anderen Sprachen, die als "schnell" gelten (z.B. C, Lua) zu implementieren und dann misst du, was der Unterschied zu Python ist.

Gruß, noisefloor

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Sonntag 8. Mai 2011, 01:56
von Leonidas
noisefloor hat geschrieben:und dann vielleicht auch erstmal probieren, was es bringt, die Optimierungen zu nutzen, die Python an sich so bringt (z.B. optimierter Byte-Code).
Wenn du mit "optimierter Byte-Code" .pyo-Dateien meinst, dann ist die Antwort "nichts", denn .pyo-Dateien sind nicht im Performance-Sinne optimiert, sondern enthalten einfach keine Docstrings.

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Sonntag 8. Mai 2011, 16:18
von Tyrax
Hallo,

ich hab' mal durchgezählt. Pro Schleifendurchlauf sind es (im Mittel)
- zwei random.gauss-Aufrufe,
- vier Vergleiche für if/while,
- vier Additionen,
- vier Multiplikationen,
- eine Division.

Also im wesentlichen kommt jede der Aufgaben etwa gleich oft vor. Ich habe den Aufwand der Operationen mal verglichen. Für jeweils 10^6 Berechnungen bekomme ich:

1000000 mal ne leere Funktion mit einer Zuweisung aufrufen dauert 0.416296958923 Sekunden.
1000000 mal ne for-Schleife mit je einem random.gauss-Aufruf durchlaufen lassen dauert 2.10397410393 Sekunden.
1000000 mal ne for-Schleife mit je einer Addition durchlaufen lassen dauert 0.0695428848267 Sekunden.
1000000 mal ne for-Schleife mit je einer Multiplikation durchlaufen lassen dauert 0.0685050487518 Sekunden.
1000000 mal ne for-Schleife mit je einer Division durchlaufen lassen dauert 0.132606983185 Sekunden.

Da ich bei weitem nicht so oft Funktionen aufrufe, wie ich Zufallszahlen ziehe, würde ich also sagen, dass der Aufruf von random.gauss der Knackpunkt ist. Die Division kann ich vielleicht noch loswerden, mal sehen.

Ich werde mal versuchen, die gleichen Sachen in C hinzuschreiben und die Ergebnisse vergleichen. Bis dahin freue ich mich auf weitere Kommentare.

@sma: die import-Anweisung innerhalb der Funktion war nur ein Unfall beim Erstellen des Beispiels. Trotzdem danke für den Hinweis.

Danke und Grüße, Tyrax

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Sonntag 8. Mai 2011, 16:28
von Leonidas
Also ``random.gauss(c, d)`` ist doch eh konstant in der Schleife... oder übersehe ich grad das offensichtliche?

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Sonntag 8. Mai 2011, 16:50
von lunar
@Leonidas: Wieso sollte "gauss(c, d)" konstant sein?!

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Sonntag 8. Mai 2011, 17:58
von HerrHagen
@Tyrax: Hast du es mal mit numpy versucht? Damit kannst du gleich Tausende Zufallszahlen auf einmal in Windeseile erzeugen. Wenn ich deine Funktion mal (mehr oder weniger) 1:1 übersetze, komme ich auf folgende Funktion:

Code: Alles auswählen

def dumme_funktion_mal_n(a, b, c, d, n=10000):
  x = numpy.random.normal(a, b, size=n)
  y = numpy.random.normal(c, d, size=n)
  return (x == y).any()
Für n=10000 Wiederholungen braucht diese Funktion 0.004s.
Allerdings werd ich irgendwie aus deiner Aufgabenstellung nicht so recht schlau. Was ist der Nutzen dieser Funktion? Willst du wirklich 10000 mal probieren ob eine normalverteilte Zufallszahl exakt (!) gleich einer anderen ist? Was soll das bringen? Wiilst du nicht eher vergleichen ob die Zufallszahlen in einem bestimmten Bereich liegen?

MFG HerrHagen

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Sonntag 8. Mai 2011, 18:08
von BlackJack
@HerrHagen: Soweit ich das verstanden habe gibt es zwei "Walker" die zufällige Schritte machen, und wenn die sich Treffen bricht die Schleife ab. Das eigentliche Problem ist also nicht das zwei Zufallszahlen gleich sind, sondern das zwei Folgen von Zufallszahlen zu einem Weg führen der beim gleichen Punkt landet. http://en.wikipedia.org/wiki/Random_walk

Ich verstehe ehrlich gesagt nicht so ganz warum uns nicht das ganze Problem gezeigt wird, sondern nur so ein Ersatz an dem nicht sieht, was denn nun eigentlich genau beschleunigt werden soll, und der deshalb zu solchen Missverständnissen führt. Hier sind ja keine allgemeinen Beschleunigungstechniken gefragt sondern konkret etwas für den vorhandenen aber nicht gezeigten Code. Und das kann man allgemein halt nicht beantworten.

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Sonntag 8. Mai 2011, 18:52
von Leonidas
lunar hat geschrieben:@Leonidas: Wieso sollte "gauss(c, d)" konstant sein?!
Sorry, heute ist wohl nicht mein Tag. Bin schon seit Stunden dabei, mit EFI zu kämpfen :(

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Sonntag 8. Mai 2011, 21:29
von Tyrax
@BlackJack: Ich habe versucht, ein Minimalbeispiel hinzuschreiben, dass die auftretenden Methoden enthält. Das sollte keine Geheimniskrämerei sein sondern lediglich das Problem auf das Wesentliche reduzieren.

Wenn man - wie Du richtig schreibst - herausfinden will, wann sich zwei Random Walker treffen, muss man natürlich auch noch ein Intervall definieren, wo die beiden herumirren und im Fall normalverteilter Schrittlängen auch noch eine "Kontaktdistanz" damit der Prozess auch mal zu einem Ende kommt. Dazu kommen noch ein paar andere Paramter, die imho für die Beschleunigung nicht entscheidend sind.

Wenn ich weiß, wie ich meine dummeFunktion schneller bekomme, kann ich das auf mein aktuelles und ggf. auf andere Probleme anwenden.

@HerrHagen: Da ich nicht vorher weiß, wann der Prozess endet, habe ich wenig davon 10^4 Zufallszahlen auf einmal zu ziehen - es kann halt immer sein, dass ich nur die ersten zwei brauche. Falls numpy auch für einzelne Zufallszahlen deutlich schneller ist, würde mich Dein Vorschlag weiterbringen.

Meine Beispielfunktion ist tatsächlich ziemlich sinnlos (daher der Name), es sollte halt ein Minimalbsp sein.


Beste Grüße, Tyrax

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Montag 9. Mai 2011, 07:56
von BlackJack
@Tyrax: Man kann so halt nicht so gut Abschätzen wie umfangreich so etwas zum Beispiel in C wird. Manche Python-Zeilen lassen sich in wenigen C-Zeilen ausdrücken, in anderen Fällen bräuchte man für eine Python-Zeile deutlich mehr in C oder vielleicht sogar eine Bibliothek, damit sich eine Umsetzung lohnt.

Als Vorbereitung würde ich erst einmal ein paar "seeds" für den Zufallsgenerator suchen bei dem die beiden Walker etwas länger unterwegs sind, oder vielleicht noch besser den Test ob sie sich getroffen haben durch einen Zähler ersetzen. Dann hast Du zwar nicht mehr ganz das was Du letztendlich beschleunigen willst, aber die ganzen Rechenschritte sind drin und man kann verschiedene Läufe besser miteinander vergleichen.

Ich würde an Deiner Stelle erst einmal `psyco` ausprobieren. Wenn das möglich ist und hinreichend beschleunigt, dann ist das wohl am wenigsten Arbeit.

Als zweites könnte man Cython versuchen und da so viel wie möglich in Richtung "C" verschieben. Inklusive der `random.Random.gauss()`-Implementierung.

Falls das nicht schnell genug wird, würde ich es komplett in C als Bibliothek/DLL programmieren und über `ctypes` darauf zugreifen. Da müsste man sich dann aber eine äquivalente Quelle für Zufallszahlen suchen. Die Glib hat zum Beispiel einen "Mersenne Twister", der mit `g_random_double()` auch sehr einfach zu benutzen ist.

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Montag 9. Mai 2011, 19:12
von Tyrax
@BlackJack: Danke, Dein letzter Beitrag ist in etwa die Einsicht, die ich von dem thread erhofft hatte. Wahrscheinlich hätte ich die Diskussion durch einen exaktere Problembeschreibung beschleunigen können ...

Wegen Psyco: Ich habe mir mal die mutmaßliche Homepage http://psyco.sourceforge.net angesehen, auf der auf das Nachfolgeprojekt PyPy hingewiesen wird. Ich habe mir dazu einige Seiten angesehen und hatte den Eindruck, dass PyPy keine Nachteile gegenüber Psyco hat. Liege ich da richtig?

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Montag 9. Mai 2011, 19:54
von BlackJack
@Tyrax: `psyco` ist ein Modul für CPython und PyPy ist eine komplette Python-Implementierung. Wenn Du Dein Programm mit PyPy laufen lassen kannst, also keine Abhängigkeiten hast, die mit PyPy nicht funktionieren, dann ginge das natürlich auch.