Python-Code (mit Cython) beschleunigen

26.08.2020, 10:32 - Autor: Jasmin Horvath

PYPY - Der schnellere Interpreter

Bevor wir uns mit Cython beschäftigen wollen wir einmal zwei typische Zeitfresser betrachten...

Erstellen und durchsuchen von Listen:

import time
max_nr = 100000

ts = time.time()
l = []
for i in range(max_nr):
    l.append(i+1)

found = 0
for i in range(max_nr):
    if i in l:
        found += 1
te = time.time()
print(str(te - ts) + " Sek. für das Erstellen und Durchsuchen der Liste")

Bei diesem Beispiel wir eine Liste erstellt und mit 100.000 Einträgen (den Zahlen 1 bis 100.000) befüllt. Danach werden die Zahlen 0 - 99.999 durchlaufen und in der Liste gesucht. Sollten Sie probleme haben diesen einfach Codebeispielen zu folgen sollten Sie sich zuerst den Python 3.x Crashkurs ansehen! Lassen wir das Programm mit dem Python 3.x Interpreter laufen erhalten wir folgende Meldung: 

mark@debian ~$ python3 liste.py 
27.124310970306396 Sek. für das Erstellen und Durchsuchen der Liste

PyPy ist ein alternativer Interpreter der auf Geschwindigkeit optimiert ist - allerdings hinkt das Projekt dem aktuellen Stand etwas hinterher und daher ist es ratsam lieber 1 oder 2 Versionen hinter den aktuellen Version zu bleiben. Außerdem sind einige Module nicht mit PyPy kompatibel. Nähere Intfomationen finden sich auf der Homepage des Projektes: https://pypy.org/ 

mark@debian ~$ pypy liste.py 
1.3602039814 Sek. für das Erstellen und Durchsuchen der Liste

Nicht ganz 1,4 Sekunden statt über 27,1 Sekunden kann ich durchaus sehen lassen und das ohne jegliche Veränderungen am Programm!

Das verarbeiten von größeren Datenmengen:

import time, sys

def sum_all(n):
    sum = 0
    for i in range(1, n + 1):
        sum += i
    return sum

max_nr = 1000000009

ts = time.time()
print(sum_all(max_nr))
te = time.time()
print(str(te - ts) + " Sek. mit " + sys.executable)

Um das Verarbeiten von großen Datenmengen zu simulieren habe ich dieses kurze Testprogramm geschrieben das mit Hilfe der Funktion sum_all() die Zahlen von 1 bis n aufsummiert. Lassen wir das Programm laufen:

mark@debian ~$ python3 test_pypy.py 
500000000500000045
36.72523760795593 Sek. mit /usr/bin/python3

Und nun mit PyPy:

mark@debian ~$ pypy test_pypy.py 
500000000500000045
0.786007165909 Sek. mit /usr/bin/pypy

... auch hier liefert PyPy eine extreme Geschwindigkeitssteigerung ohne jegliche Anpassungen! Aber sehen wir uns nun noch Cython an...

C-Module mit Cython erstellen

Cython hat den Vorteil, dass wir damit eigene C-Module erstellen können und das ganz ohne C bzw C++ zu beherrschen. Damit können wir den offiziellen Python-Interpreter verwenden und haben auch eine Kompatibilitätsprobleme mit diversen Modulen. Allerdings müssen wir den Code etwas modifizieren und vor allem zuerst identifizieren welche Teile des Codes die meiste Prozessorzeit belegen.

Dann müssen wir cython installieren. Dies können wir mit pip3 install cython bzw. py.exe -3.6 -m pip install cython unter Windows erreichen.

Danach können wir das entsprechende C-Modul schreiben und unter sum_all.pyx speichern:

cpdef long sum_all(long n):
    cdef long sum = 0
    cdef long i
    for i in range(1, n + 1):
        sum += i
    return sum

Aus dem def wurde ein cpdef, was soviel bedeutet wie eine Funktion die von C und von Python aus aufgerufen werden kann. Außerdem haben wir mit long sum_all(...) den Rückgabewert der Funktion typisiert. Genau das gleiche macht long n für den Funktionsparameter. Die so genannte dynamische Typisierung von Python ist bei der Ausführung ein echter Zeitfresser denn der Interpreter ist ständig gezwungen den Typ zu Vergleichen bzw. zu ermitteln um was für einen Typ es sich im Moment handelt. Was uns Entwicklern also ein wenig lästige Tipparbeit erspart verursacht einen sehr hohen Aufwand bei der Ausführung und bremst ein Programm ungemein aus!

Mit cdef long sum = 0 initialisieren wir die Variable sum mit 0 und lgen fest, dass sie nur von C aus ansprechbar ist. Da die Funktion einen Rückgabewert hat der ohnehin zurückgeliefert wird muss die Funktionsvariable sum nicht von Python aus erreichbar sein. In diesem Fall wäre dies ohnehin nicht der Fall, da eine Funktionsvariable nicht von anderen Teilen des Programms ansprechbar ist aber je genauer wir hier arbeiten umso performanter läuft der Code später. Gleiches erreichen wir mit der Schleifenvariable i die wir auch vorab initialisieren allerdings ohne ihr einen Wert zuzuweisen.

Damit haben wir die Typen für alle Variablen fest definiert. Hierbei sollte man allerdings beachten, dass damit auch einige Probleme einher gehen. Wenn man den Wertebereich eines Datentyps verlässt kommt es zu einem Speicherüberlauf und damit zu falschen Ergebnissen und sollte man immer den größtmöglichen Datentyp verwenden riskiert man übermäßig viel Speicher zu verschwenden! Man ist also in dem gleichen "Dilemma" wie ein C Programmierer. Dazu später mehr...

Danach müssen wir eine setup.py erstellen: 

from distutils.core import setup
from Cython.Build import cythonize

setup(ext_modules = cythonize("sum_all.pyx"))

... und das Cython-Modul kompilieren:

mark@debian ~$  python3 setup.py build_ext --inplace
Compiling sum_all.pyx because it changed.
[1/1] Cythonizing sum_all.pyx
/home/mark/.local/lib/python3.6/site-packages/Cython/Compiler/Main.py:369: FutureWarning: Cython directive 'language_level' not set, using 2 for now (Py2). This will change in a later release! File: /home/mark/sum_all.pyx
  tree = Parsing.p_module(s, pxd, full_module_name)
running build_ext
building 'sum_all' extension
x86_64-linux-gnu-gcc -pthread -DNDEBUG -g -fwrapv -O2 -Wall -g -fstack-protector-strong -Wformat -Werror=format-security -Wdate-time -D_FORTIFY_SOURCE=2 -fPIC -I/usr/include/python3.6m -c sum_all.c -o build/temp.linux-x86_64-3.6/sum_all.o
x86_64-linux-gnu-gcc -pthread -shared -Wl,-O1 -Wl,-Bsymbolic-functions -Wl,-Bsymbolic-functions -Wl,-z,relro -Wl,-Bsymbolic-functions -Wl,-z,relro -g -fstack-protector-strong -Wformat -Werror=format-security -Wdate-time -D_FORTIFY_SOURCE=2 build/temp.linux-x86_64-3.6/sum_all.o -o /home/mark/sum_all.cpython-36m-x86_64-linux-gnu.so

Hierbei wird die Datei sum_all.cpython-36m-x86_64-linux-gnu.so erstellt. Sobald dies erfolgt ist können wir das neue Modul verwenden:

#!/usr/bin/python
import sum_all, time

def sum_all_py(n):
    sum = 0
    for i in range(1, n + 1):
        sum += i
    return sum

max_nr = 1000000009

ts = time.time()
print(sum_all.sum_all(max_nr))
te = time.time()
print(str(te - ts) + " Sek. mit Cython")

ts = time.time()
print(sum_all_py(max_nr))
te = time.time()
print(str(te - ts) + " Sek. mit Python")

Zuerst wurde das neue erstelle Modul mit import sum_all importiert.

Um einen direkten Vergleich zu haben, haben wir die Funktion sum_all() nochmals in der ursprünglichen Version in die Datei eingefügt. Danach haben wir jeweils die Startzeit (ts) genommen, die Funktion aus dem Modul bzw. direkt aus dem Python-Code aufgerufen sowie das Ergebnis ausgegeben, die Endzeit (te) festgehalten und eine Meldung mit der Ausführungszeit der jeweiligen Methode ausgegeben:

mark@debian ~$ python3 use_cmodule.py 
500000000500000045
0.2465343475341797 Sek. mit Cython
500000000500000045
37.35157293891907 Sek. mit Python

... und das Ergebnis kann sich sehenlassen - die 0.24 Sekunden sind im Vergliech zu PyPy nochmals über drei mal so schnell!

Das Problem bei der statischen Typisierung

Um zu zeigen was passiert wenn wir den Wertebereich eines Datentyps überschreiten haben wir das Cython-Modul wie folgt angepasst: 
cpdef char sum_all(long n):
    cdef char sum = 0
    cdef long i
    for i in range(1, n + 1):
        sum += i
    return sum

... wir haben also anstatt des Datentyps long den Datentyp char verwendet. Übersetzen wir das Modul und passen das Programm nun erneut laufen erhalten wir folgende Ausgabe:

mark@debian ~$ python3 use_cmodule.py  
45
0.2448270320892334 Sek. mit Cython
500000000500000045
39.131327867507935 Sek. mit Python

Ok, hier spingt uns der Fehler direkt ins Auge denn beim Summieren von so großen und so vielen positiven Zahlen kann das Ergebnis unmöglich 45 sein! Aber oftmals sind derartige Fehler nicht so einfach zu erkennen! Wer also die Komfortzone von Python verlässt muss sich dann auch mit derartigen Problemen beschäfrtigen. Aber sehen wir uns das Beispiel einfach einmal näher an was genau passiert:

Wir haben die Variable sum und den Rückgabewert der Funktion als char anstatt long definiert. Dieser Datentyp ist nur 1 Byte bzw. 8 Bit lang und kann daher nur die Werte von -128 bis 127 darstellen. Dazu sollen wir uns ansehen wie die Werte intern gespeichert werden:
Wert -128 64 32 16 8 4 2 1
1 0 0 0 0 0 0 0 1
12 0 0 0 0 1 1 0 0
127 0 1 1 1 1 1 1 1
-128 1 0 0 0 0 0 0 0
-127 1 0 0 0 0 0 0 1

Die Binärzahl 10000001 enspricht also 1 x -128 + 1 x 1 also der Zahl -127 und die Binärzahl 0b00001100 entspricht 1 x 8 + 1 x 4 also der Zahl 12. Daher ist die größte positive Binärzahl 01111111 also 1 x 64 + 1 x 32 + 1 x 16 + 1 x 8 + 1 x 4 + 1 x 2 + 1 x 1! In so eineem Fall spricht man auch von einem signed Datentyp - also einem Datentyp der sowohl positive als auch negative Zahlen darstellen kann. Würde man nun die Zahl 128 binär darstellen wollen dann wäre das 10000000. Bei einem unsigned int mit 8 Bit wäre die 8. Stelle auch die postive 128 und das würde klappen. Aber spätenstens bei 100000000 also der Zahl 256 würden die 8 bit auch nicht mehr reichen und es würde ein 9. Bit an Speicher benötigt werden.

Sie sehen also es ist essentiell wichtig ist wie ein Bitmuster im Speicher zu interpretieren ist um das nochmals zu verdeutlichen hier ein kleines Beispiel wie ein und das selbe Bitmuster unterschiedliche Ergebnisse liefert je nach dem wie man es interpretiert:

>>> bin = "10100111"
>>> int(bin, 2)
167
>>> if bin[0:1] == "1": -128 + int(bin[1:], 2)
-89
>>> chr(int(bin, 2))
"§"

Zuerst definieren wir die Variable bin mit dem Muster 10100111 und dann wird diese mit der int() Funktion in eine positive Ganzzahl umgewandelt. Die zweite Konvertierung prüft ob die erste Stelle (bin[0:1]) eine 1 enthält und addiert dann -128 mit dem Ergebnis der Umwandlung der Stellen 2 bis 8 (int(bin[1:], 2)) des Binmusters um das Muster so als unsigned Integer zu behandeln. Schließlich wird die Indexzahl 167 noch mit Hilfe der ASCII-Tabelle als ein Zeichen interpretiert und dies ergibt §. Python nimmt uns Entwicklern diese Arbeit ab und kümmert sich darum immer zu wissen welche Variable gerade welchen Datentyp hat und übernimmt in einigen eindeutigen Fällen sogar die Typenkonvertierung für uns. Sobald wir von dieser dynamischen Typisierung zur statischen Typisierung wechseln und selber festlegen welcher Datentyp für welche Variable gelten soll und welcher Datentyp von einer Funktion zurückgegeben wird obliegt es auch uns als Entwickler sicherzustellen, dass die Daten richtig interpretiert werden und die Datentypen ausreichend große Daten aufnehmen können.

Vor allem die Größe ist ein wirkliches Problem denn auch hier nimmt und Python die Speicherveraltung ab:

>>> a = 1
>>> type(a)
<class "int">
>>> a.__sizeof__()
28
>>> a = 999999999999999 * 88888888888888
>>> type(a)
<class "int">
>>> a.__sizeof__()
40
>>> a = "bla"
>>> type(a)
<class "str">
>>> a.__sizeof__()
52
>>> a = "Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua."
>>> type(a)
<class "str">
>>> a.__sizeof__()
204

Aber sehen wir uns einmal an wie C und C++ mit Speichergrößen umgehen und was passiert wenn die maxiamal mögliche größe überschritten wird. Bleiben wir dabei bei dem bereits bekannten Beispiel der 8 Bit langen Ganzzahl. Sobald wir eine größere Zahl als 255 abspeichern wollen reichen selbst bei einem unsigned Integer die 8 bit nicht mehr aus - sehen wir uns dazu die folgende Zahlen an:

 11111111 (1 x 128 + 1 x 64 + 1 x 32 + 1 x 16 + 1 x 8 + 1 x 4 + 1 x 2 + 1 x 1 = 255)
100000000 (1 x 256 + 0 x 128 + 0 x 64 + 0 x 32 + 0 x 16 + 0 x 8 + 0 x 4 + 0 x 2 + 0 x 1 = 256)
100000001 (1 x 256 + 0 x 128 + 0 x 64 + 0 x 32 + 0 x 16 + 0 x 8 + 0 x 4 + 0 x 2 + 1 x 1 = 257)

Sie sehen aber auch, dass wir ab 256 9 statt 8 Bit benötigen also sehen wir uns ein vereinfachtes Beispiel an wie dies im RAM-Speicher aussehen könnte:

0x7F171CEFC374 0x7F171CEFC375
bit1 bit2 bit3 bit4 bit5 bit6 bit7 bit8 bit1 bit2 bit3 bit4 bit5 bit6 bit7 bit8
0 0 1 1 1 0 1 0 1 1 1 1 1 1 1 1

Nehmen wir nun an, dass in der Speicheradresse 0x7F171CEFC374 das Zeichen : bzw. der Binärwärt 00111010 einer anderen Variable bespeichert sind. Dies könnte zB das letzte Zeichen einer Zeichenkette darstellen. In der Speicheradresse 0x7F171CEFC374 legen wir dann die Ganzzahl 255 in einem 8 bit Integer ab (11111111). Danach veranlassen wir das Programm zu dieser Zahl die 1 zu addieren und dies würde den Speicher wie folgt verändern:

0x7F171CEFC374 0x7F171CEFC375
bit1 bit2 bit3 bit4 bit5 bit6 bit7 bit8 bit1 bit2 bit3 bit4 bit5 bit6 bit7 bit8
0 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0

Wie Sie sehen ist die 9. Stelle hinaus gewandert und hat auch die Speicheradresse 0x7F171CEFC374 verändert. Wir haben also zwei Probleme:

1. wurde aus dem : am Ende der Zeichenkette nun ein ;. Damit wurde diese Variable unabsichtlich verändert. Dies kann dazu führen, dass Berechnungen mit falschen Werten ausgeführt werden oder Daten übersprungen werden wenn ein Zäher plötzlich unabsichtlich um eins erhöht würde.

2. wird beim Auslesen der Variable nur die Speicheradresse 0x7F171CEFC375 berüchsichtigt. Das eine bit ist also abgeschnitten worden und der Wert der Variable ist nun 0 statt 256!

Genau darum erhielten wir auch das falsche Ergebnis als wir die Variable sum und den Rückgabewert der Funktion auf den Datentyp char gesetzt hatten. Der Wert wurde immer und immer wieder überschritten und andere Bereiche im RAM-Speicher überschrieben was zu allen möglichen weiteren Seiteneffekten führen könnte und dadruch wurde immer nur ein Teil des Bitmusters der eigentlichen Summe berücksichtigt und damit weiter gerechnet was das falsche Ergebnis erklärt.

Fazit

Python-Programme müssen nicht unbedingt langsam laufen. Außerdem geht es durchaus einfache Lösungen ohne langwierig mit der Verarbeitungsgeschwindigkeit der diversen Datentypen zu experimentieren oder diverse Module und Funktionen miteinander zu vergleichen um die performanteste Lösung zu finden. Dabei sind weder C/C++ Kenntnisse (abgesehen von den Datentypen und deren Wertebereiche) nötig um C-Module mit Cython zu schreiben!

Wenn Sie dies erwägen sollten Sie sich aber auch der "Tücken" und "Probleme" bewusst sein die eine für C/C++ typische statische Typisierung mit sich bringen und diese in der Planung und Umsetzung des C-Modules berücksichtigen um keine unerwarteten Überraschungen zu erleben.