Donnerstag, 18. Januar 2018

Python und Geschwindigkeit (oder: Beschleunigung ist ganz einfach)

Es heißt ja schon mal gerne "Python ist langsam". Mal abgesehen davon, dass solch pauschale Aussagen generell fragwürdig sind, ist in der Aussage ein entscheidender Fehler: Python beschreibt die (Programmier-) Sprache an sich - aber es gibt diverse Implementierung, die sich in Sachen Geschwindigkeit teilweise erheblich unterscheiden.

Richtig ist, dass im allgemeinen "Python" mit der Referenzimplementierung CPython gleichgesetzt wird, welches die (mit Abstand) am meisten genutzte Implementierung ist. Auch verwende ich hier im Blog in der Regel das Wort Python als Synonym für CPython.
CPython arbeitet Code in zwei Schritten ab: zuerst wird der Quellcode in (plattformunabhängigen) Bytecode übersetzt, mit Hilfe eines Compilers. Der Bytecode wird dann in einer virtuellen Maschine (nicht zu verwechseln mit VirtualBox, VMware & Co) Anweisung für Anweisung ausgeführt.
Und CPython ist in der Tat nicht auf Geschwindigkeit optimiert, der Fokus der Entwicklung liegt auf anderen Punkten.

Im folgenden geht es darum, wie man die Ausführung von Python-Skripten beschleunigen kann.
Dazu sei noch angemerkt: Es werden im folgenden in erster Linie einige Möglichkeiten gezeigt. Es geht nicht darum, jede noch mögliche (Mikro-) Optimierung zu nutzen, um noch die ein oder andere Zehntelsekunde extra heraus zu holen.
Auch habe ich keine (aufwendigen) Benchmarks genutzt, sondern einfach nur einen recht rechenintensiven Code zur Prüfung von Primzahlen. Die absoluten Werte der Laufzeit des Codes sind auch sekundär, interessanter ist der relative Unterschied zwischen den verschieden Methoden der Ausführung.
Alle Messungen wurden auf meinem Laptop gemacht, welcher einen Intel® Core™ i5-5200U CPU Prozessor mit 2.20 GHz und vier Kernen hat. Das Betriebssystem ist Ubuntu 16.04 (mit ruhendem Desktop, d.h. es liefen keine weiteren Programme), die CPython-Version ist Python 3.5.3, was Ubuntu 16.04 standardmäßig installiert hat.

Der Code ist an ein Beispiel aus der Python-Doku angelehnt:
import math

PRIMES = [
    112272535095293,
    112582705942171,
    112272535095293,
    115280095190773,
    115797848077099,
    1099726899285419,
    777777722155555333,
    777777722155555335,
    9999999900000001,
    2327074306453592351,
    2327074306453592353]

def is_prime(n):
    if n % 2 == 0:
        return False

    sqrt_n = int(math.floor(math.sqrt(n)))
    for i in range(3, sqrt_n + 1, 2):
        if n % i == 0:
            return False
    return True

def main():
    for number in PRIMES:
        prime = is_prime(number)
        print('{} is prime: {}'.format(number, prime))

if __name__ == '__main__':
    main()
Es wird also einfach nur für elf Zahlen geprüft, ob diese eine Primzahl sind (Tipp: wer diesen Code auf einem langsamen Rechner wie z.B. dem Raspberry Pi ausführen möchte, sollte die Liste kürzen und z.B. nach 777777722155555333 Schluss machen, damit der Code nicht zu lange läuft).

Dieser Code braucht bei mir auf meinem Laptop 3 Minuten 23 Sekunden. Das ist der Referenzwert für die im folgenden besprochenen Methoden zur Beschleunigung.

Natürlich lässt sich dieses Problem sehr gut parallelisieren. Dem concurrent.futures Beispiel aus der Python-Doku folgend zum Beispiel, in dem man das Rechnen auf mehrere Prozesse verteilt:
import concurrent.futures
import math

...

def is_prime(n):
    ...

def main():
    with concurrent.futures.ProcessPoolExecutor(max_workers=4) as executor:
        for number, prime in zip(PRIMES, executor.map(is_prime, PRIMES)):
            print('%d is prime: %s' % (number, prime))

if __name__ == '__main__':
    main()
Hier werden vier parallele Prozesse gestartet und damit gerechnet.
Ergebnis: 2 Minuten 15 Sekunden, also etwas mehr als 1 Minute schneller.

Nun lassen sich aber nicht alle Programme bzw. Berechnungen so leicht parallelisieren wie das Prüfen von Primzahlen. Was auch nicht weiter schlimm ist, denn es gibt auch Methoden, nicht-parallelisierten Code zu beschleunigen.

Die für Python wahrscheinliche bekannteste Methode ist der Einsatz von PyPy. PyPy ist kompatibel zu CPython, der Code wird aber von einem Just-in-Time Compiler übersetzt. Der Aufruf des Codes erfolgt einfach durch:
$ pypy name_des_skripts.py
Das Skript aus dem ersten Beispiel (also ohne Parallelisierung) wird von PyPy (Version 5.10.0) in 24 Sekunden ausgeführt. D.h. die Ausführungsgeschwindigkeit ist um einen Faktor von ca. 8,5 (!) höher, nur durch Einsatz der Python-Implementierung PyPy, ohne weitere Änderungen am Code.

Eine weitere Möglichkeit der Beschleunigung ist der Einsatz des Just-in-Time Compilers Numba. Dieser ist standardmäßig bei der Python-Distribution Anaconda an Bord. Numba kann zwar auch manuell installiert werden, dass ist aber vergleichsweise aufwendig, weswegen für den Test von Numba die Version 0.36.2 aus Anaconda (in Kombination mit Python 3.6.3) zum Einsatz kam.
Um Code bzw. Funktionen mit Numba zu beschleunigen, müssen diese lediglich mit einem Dekorator versehen werden:
import math
from numba import jit

PRIMES = [
    ...]

@jit
def is_prime(n):
    ...

def main():
    for number in PRIMES:
        prime = is_prime(number)
        print('{} is prime: {}'.format(number, prime))

if __name__ == '__main__':
    main()
Diese unscheinbare Änderung bewirkt, dass die Funktion is_prime vom Numba Just-in-Time Compiler ausgeführt wird. Das Ergebnis ist eine Laufzeit von 19 Sekunden, also eine Beschleunigung vom eine  Faktor von ca. 10,5.

Jetzt gibt auch die Möglichkeit, Python zu C-Code kompilieren lassen. Dazu wurden der Python-Compiler Nuitka und eine Kombination aus Cython und gcc getestet.

Nuitka (welches ich bis dahin noch nie verwendet hatte) hat zum Ziel, einen "extremely compatible Python compiler" bereit zustellen, entsprechend liegt der Entwicklungsfokus darauf, (Geschwindigkeits-) Optimierungen sollen später erst einfließen.
Entsprechend ist auch das Ergebnis: die Laufzeit ist 3 Minuten und 7 Sekunden, also unwesentlich schneller als CPython. Die eingesetzte Nuitka Version ist 0.5.24. Laut Aussage auf der Homepage ist Nutika-Homepage ist Nuitka bei größeren / umfangreicheren Benchmarks aber doch spürbar schneller als CPython.

Zweiter Testkandidat ist eine Kombination aus Cython (Version 0.27.3) und dem gcc Compiler (Version 5.4.0). Dazu wurde der Code aus dem ersten Beispiel zuerst einfach mit Cython in C-Code übersetzt und dann mit gcc zu einer ausführbaren Datei kompiliert:
$ cython prime_code_linear_cython.py --embed
$ gcc -Os -I /usr/include/python3.5m -o prime_code_linear_cython prime_code_linear_cython.c
-lpython3.5m -lpthread -lm -lutil -ldl
Das Ergebnis ist eine Laufzeit von 2 Minuten 39 Sekunden, also rund 1 Minute schneller als CPython. Nicht schlecht, aber für kompilierten Code auch nicht wirklich viel - jedenfalls nicht im Vergleich zu PyPy und Numba.

Das ganze kann man aber verbessern, wenn man von der dynamischen Typisierung, die Python standardmäßig hat, Abschied nimmt und statisch typisiert. Dadurch sind Optimierung seitens Cython möglich, welche die Ausführung (erheblich) beschleunigen. Ändert man den Code wie folgt:
import math

PRIMES = [
    112272535095293,
    ...]

cdef bint is_prime(long n):
    cdef int sqrt_n, i
    if n % 2 == 0:
        return False

    sqrt_n = int(math.floor(math.sqrt(n)))
    for i in range(3, sqrt_n + 1, 2):
        if n % i == 0:
            return False
    return True

def main():
    cdef long number
    cdef bint prime 
    for number in PRIMES:
        prime = is_prime(number)
        print('{} is prime: {}'.format(number, prime))

if __name__ == '__main__':
    main()
und kompiliert erneut, dann liegt die Ausführungsgeschwindigkeit bei 18 Sekunden, das ist die schnellste Ausführung (wenn auch nur unwesentlich schneller als Numba).
Der Nachteil: Der Code funktioniert tatsächlich nur noch, wenn die Primzahlen vom Typ long sind, d.h. der Code wird unflexibler. Fügt man z.B. eine 5 in die Liste der Primzahlen ein, bricht die Übersetzung mit Cython von Python nach C mit einer Fehlermeldung ab, weil 5 vom Typ int ist (und kein long). Wer mehr Infos zu Cython und Beschleunigung mittels statischer Typisierung sucht, für den ist die Seite Faster code via static typing in der Cython-Doku ein guter Startpunkt.

Zum Abschluss noch mal alle Ergebnisse auf einen Blick:
  • CPython 3.5.3: 3 Minuten 23 Sekunde
  • CPython + concurrent.futures.ProcessPoolExecutor: 2 Minuten 15 Sekunden
  • PyPy 5.10.0: 24 Sekunden
  • Python 3.6.3 + Numba 0.36.2: 19 Sekunden
  • Nuitka 0.5.24: 3 Minuten 7 Sekunden
  • Cython 0.27.3 + gcc 5.4.0: 2 Minuten 39 Sekunden
  • Cython mit statischer Typisierung + gcc: 18 Sekunden
Fazit:
Es gibt verschiedenen Möglichkeiten rechenintensive / CPU-intensive Python-Skripte zu beschleunigen, teilweise erheblich zu beschleunigen.
Die einfachste Möglichkeit ist sicherlich PyPy - hier muss am Code nichts geändert werden, das Skript muss lediglich mit PyPy statt CPython aufgerufen werden. Wie auch Guido van Rossum (der "Erfinder" von Python) sagte: “If you want your code to run faster, you should probably just use PyPy.”
Der tatsächliche Beschleunigungsfaktor des eigenen Codes kann natürlich auch noch vom Code an sich abhängen. Gegenfalls macht es dann Sinn, die verschieden Optionen - PyPy, Numba und Cython + gcc - zu prüfen, um die für sich beste herauszufinden.