Performance

Mit Python lässt sich zwar schnell Code schreiben und testen, da es eine interpretierte Sprache ist, die dynamisch typisiert. Dies sind jedoch auch die Gründe, die sie bei der wiederholten Ausführung von einfachen Aufgaben, z.B. in Schleifen, langsam macht.

Bei der Entwicklung von Code kann es häufig zu Kompromissen zwischen verschiedenen Implementierungen kommen. Zu Beginn der Entwicklung eines Algorithmus ist es jedoch meist kontraproduktiv, sich um die Effizienz des Codes zu kümmern.

»Wir sollten kleine Effizienzsteigerungen in sagen wir etwa 97 % der Zeit, vergessen: Vorzeitige Optimierung ist die Wurzel allen Übels. Dennoch sollten wir unsere Chancen in diesen kritischen 3 % nicht verpassen.«[1]

Siehe auch

k-Means-Beispiel

Im Folgenden zeige ich Beispiele für den k-Means-Algorithmus, um aus einer Menge von Objekten eine vorher bekannte Anzahl von Gruppen zu bilden. Dies lässt sich mit dem MacQueen’s Algorithmus in den folgenden drei Schritten erreichen:

  1. Wähle die ersten k Elemente als Clusterzentren

  2. Weise jedes neue Element dem Cluster zu, bei dem sich die Varianz am wenigsten erhöht

  3. Aktualisiere das Clusterzentrum

Die Schritte 2 und 3 werden dabei so lange wiederholt, bis sich die Zuordnungen nicht mehr ändern.

Eine mögliche Implementierung mit reinem Python könnte so aussehen:

py_kmeans.py
def dist(x, y):
    """Calculate the distance"""
    return sum((xi - yi) ** 2 for xi, yi in zip(x, y, strict=True))


def find_labels(points, centers):
    """Assign points to a cluster."""
    labels = []
    for point in points:
        distances = [dist(point, center) for center in centers]
        labels.append(distances.index(min(distances)))
    return labels


def compute_centers(points, labels):
    """Calculate the cluster centres."""
    n_centers = len(set(labels))
    n_dims = len(points[0])

    centers = [[0 for i in range(n_dims)] for j in range(n_centers)]
    counts = [0 for j in range(n_centers)]

    for label, point in zip(labels, points, strict=True):
        counts[label] += 1
        centers[label] = [
            a + b for a, b in zip(centers[label], point, strict=True)
        ]

    return [
        [x / count for x in center]
        for center, count in zip(centers, counts, strict=True)
    ]


def kmeans(points, n_clusters):
    """Calculates the cluster centres repeatedly until nothing changes."""
    centers = points[-n_clusters:].tolist()
    while True:
        old_centers = centers
        labels = find_labels(points, centers)
        centers = compute_centers(points, labels)
        if centers == old_centers:
            break
    return labels

Beispieldaten können wir uns erstellen mit:

from sklearn.datasets import make_blobs


points, labels_true = make_blobs(
    n_samples=1000, centers=3, random_state=0, cluster_std=0.60
)

Und schließlich können wir die Berechnung ausführen mit:

kmeans(points, 10)

Performance-Messungen

Wenn ihr erst einmal mit eurem Code gearbeitet habt, kann es nützlich sein, die Effizienz genauer zu untersuchen. Hierfür kann z. B. cProfile, iPython Profiler, scalene, tprof oder Memray genutzt werden. Bisher führe ich meist die folgenden Schritte aus:

  1. Ich profiliere das gesamte Programm mit cProfile oder py-spy, um langsame Funktionen zu finden.

  2. Ggf finde ich mit dem line_profiler die langsamen Stellen innerhalb der Funktion

  3. Sofern die langsame Funktion rechenintensiv ist, versuche ich eine der folgen den Optimierungen; sofern jedoch die Anwendung datenintensiv ist (Dicts, Strings, I/O)), schaue ich mir die Architektur nochmal genauer an.

  4. Schließlich erstelle ich ein neues Profil und filtere das Ergebnis meiner optimierten Version heraus um die Ergebnisse vergleichen zu können.

Added in version Python3.15: Mit PEP 799 wird ein spezielles Profiling-Modul zur Verfügung stehen, das die in Python integrierten Profiling-Tools unter einem einheitlichen Namespace organisiert. Dieses Modul enthält:

profiling.tracing

deterministische Funktionsaufrufverfolgung, die aus cProfile verschoben wurde.

profiling.sampling

der neue statistische Sampling-Profiler Tachyon.

Siehe auch

1. Suche nach bestehenden Implementierungen

Ihr solltet nicht das Rad neu erfinden wollen: Wenn es bestehende Implementierungen gibt, solltet ihr diese auch verwenden. für den k-Means-Algorithmus gibt es sogar gleich zwei Implementierungen:

Gegen diese bestehenden Lösungen könnte bestenfalls sprechen, dass sie einen erheblichen Overhead in eurem Projekt erzeugen könnten wenn ihr nicht schon an anderen Stellen scikit-learn oder Dask-ML einsetzt. Im Folgenden werde ich daher weitere Möglichkeiten zeigen, euren eigenen Code zu optimieren.

2. Anti-Patterns finden

Anschließend könnt ihr mit perflint euren Code durchsuchen nach den häufigsten Performance-Anti-Patterns in Python.

Siehe auch

3. Vektorisierungen mit NumPy

NumPy verlagert sich wiederholende Operationen in eine statisch typisierte kompilierte Schicht, um so die schnelle Entwicklungszeit von Python mit der schnellen Ausführungszeit von C zu kombinieren.

Version

Spectral-norm

vs 3.14x

CPython 3.14 – Basis

14,046ms

NumPy

27ms

520x

Evtl. könnt ihr Universelle Funktionen (ufunc), Vektorisierung und Indizierung und Slicing in allen Kombinationen nutzen um sich wiederholende Operationen in kompilierten Code zu verschieben und damit langsame Schleifen zu vermeiden, z. B.:

np_kmeans.py

def find_labels(points, centers):
    """Assign points to a cluster."""
    diff = points[:, None, :] - centers
    distances = (diff**2).sum(-1)
    return distances.argmin(1)

Die Vorteile von NumPy sind, dass der Python-Overhead nur je Array und nicht je Array-Element auftritt. Da NumPy eine spezifische Sprache für Array-Operationen verwendet, erfordert es jedoch auch eine andere Denkweise beim Schreiben von Code. Schließlich können die Batch-Operationen auch zu übermäßigem Speicherverbrauch führen.

Siehe auch

4. Spezielle Datenstrukturen

pandas

für SQL-ähnliche Gruppenoperationen und Aggregation.

So könnt ihr auch die Schleife in der Methode compute_centers umgehen:

pd_kmeans.py
import pandas as pd


def find_labels(points, centers):
    """Calculate the cluster centres."""
    df = pd.DataFrame(points)
    return df.groupby(labels).mean().to_numpy()
scipy.spatial

für räumliche Abfragen wie Entfernungen, nächstgelegene Nachbarn, k-Means usw.

Unsere find_labels-Methode kann dann noch spezifischer geschrieben werden:

sp_kmeans.py
import numpy as np
import pandas as pd

from scipy.spatial import cKDTree


def find_labels(points, centers):
    """Assign points to a cluster."""
    _distances, labels = cKDTree(centers).query(points, 1)
    return labels
scipy.sparse

dünnbesetzte Matrizen für 2-dimensionale strukturierte Daten.

Sparse

für N-dimensional strukturierte Daten.

scipy.sparse.csgraph

für graphenähnliche Probleme, z.B. die Suche nach kürzesten Wegen.

Xarray

für die Gruppierung über mehrere Dimensionen hinweg.

5. Compiler wählen

Faster Cpython

Auf der PyCon US im Mai 2021 stellte Guido van Rossum mit Faster CPython ein Projekt vor, das die Geschwindigkeit von Python 3.11 verdoppeln soll. Die Zusammenarbeit mit den anderen Python-Kernentwicklern ist in PEP 659 – Specializing Adaptive Interpreter geregelt. Zudem gibt es einen offenen Issue Tracker und diverse Werkzeuge zum Sammeln von Bytecode-Statistiken. Von den Änderungen profitieren dürfte vor allem CPU-intensiver Python-Code; bereits in C geschriebener Code, I/O-lastige Prozesse und Multithreading-Code dürften hingegen kaum profitieren.

Und tatsächlich sind die cPython-Versionen seitdem deutlich performanter geworden:

Version

CPython 3.10.4

1.422x

CPython 3.12.0

1.093x

CPython 3.13.0

1.024x

CPython 3.15.0a0 – Basis

Siehe auch

In einen anderen Vergleich wurde auch Free-threaded Python einbezogen:

Version

N-body

vs 3.14

Spectral-norm

vs 3.14x

CPython 3.10

1,663ms

0.75x

16,826ms

0.83x

CPython 3.11

1,200ms

1.04x

13,430ms

1.05x

CPython 3.13

1,134ms

1.10x

13,637ms

1.03x

CPython 3.14 – Basis

1,242ms

14,046ms

CPython 3.14t

1,513ms

0.82x

14,551ms

0.97x

– Quelle: The Optimization Ladder

Python JIT compiler

Added in version Python3.15: Der JIT-Compiler in Python 3.15 zeigt eine mittlere Leistungssteigerung von 3–4 gegenüber dem Standard-CPython-Interpreter, wobei die Performance-Messungen schwanken zwischen -20 und über 100 % auf x86-64-Linux- und AArch64-macOS-Systemen.

Siehe auch

Version

CPython 3.15.0a0 (JIT)

1.001x

CPython 3.15.0a0 – Basis

Cython

Bei intensiven numerischen Operationen kann Python sehr langsam sein, auch wenn ihr alle Anti-Patterns vermieden und Vektorisierungen mit NumPy genutzt habt. Dann kann das Übersetzen von Code in Cython hilfreich sein.

Version

N-body

vs 3.14

Spectral-norm

vs 3.14x

CPython 3.14 – Basis

1,242ms

14,046ms

Cython

10ms

124x

142ms

99x

Leider muss der Code jedoch häufig umstrukturiert werden und nimmt dadurch an Komplexität zu. Auch werden explizite Type Annotations und das Bereitstellen des Codes umständlicher.

Unser Beispiel könnte dann so aussehen:

cy_kmeans.pyx
cimport numpy as np
import numpy as np


cdef double dist(double[:] x, double[:] y):
    """Calculate the distance"""
    cdef double dist = 0
    for i in range(len(x)):
        dist += (x[i] - y[i]) ** 2
    return dist

def find_labels(double[:, :] points, double[:, :] centers):
    """Assign points to a cluster."""
    cdef int n_points = points.shape[0]
    cdef int n_centers = centers.shape[0]
    cdef double[:] labels = np.zeros(n_points)
    cdef double distance, nearest_distance
    cdef int nearest_index

    for i in range(n_points):
        nearest_distance = np.inf
        for j in range(n_centers):
            distance = dist(points[i], centers[j])
            if distance < nearest_distance:
                nearest_distance = distance
                nearest_index = j
        labels[i] = nearest_index
    return np.asarray(labels)

Siehe auch

Numba

Numba ist ein JIT-Compiler, der vor allem wissenschaftlichen Python- und NumPy-Code in schnellen Maschinencode übersetzt, z.B.:

nb_kmeans.py
import numba
import numpy as np


@numba.jit(nopython=True)
def dist(x, y):
    """Calculate the distance"""
    dist = 0
    for i in range(len(x)):
        dist += (x[i] - y[i]) ** 2
    return dist


@numba.jit(nopython=True)
def find_labels(points, centers):
    """Assign points to a cluster."""
    labels = []
    min_dist = np.inf
    min_label = 0
    for i in range(len(points)):
        for j in range(len(centers)):
            distance = dist(points[i], centers[j])
            if distance < min_dist:
                min_dist, min_label = distance, j
        labels.append(min_label)

Numba benötigt allerdings LLVM und einige Python-Konstrukte werden nicht unterstützt.

Version

N-body

vs 3.14

Spectral-norm

vs 3.14x

CPython 3.14 – Basis

1,242ms

14,046ms

Numba

22ms

56x

104ms

135x

6. Aufgabenplaner

ipyparallel, Dask und Ray können Aufgaben in einem Cluster verteilen. Dabei haben sie unterschiedliche Schwerpunkte:

Unser Beispiel könnte mit Dask so aussehen:

ds_kmeans.py
import numpy as np

from dask import array as da
from dask import dataframe as dd


def find_labels(points, centers):
    """Assign points to a cluster."""
    diff = points[:, None, :] - centers
    distances = (diff**2).sum(-1)
    return distances.argmin(1)


def compute_centers(points, labels):
    """Calculate the cluster centres."""
    points_df = dd.from_dask_array(points)
    labels_df = dd.from_dask_array(labels)
    return points_df.groupby(labels_df).mean()


def kmeans(points, n_clusters):
    """Calculates the cluster centres repeatedly until nothing changes."""
    centers = points[-n_clusters:]
    points = da.from_array(points, 1000)
    while True:
        old_centers = centers
        labels = find_labels(points, da.from_array(centers, 5))
        centers = compute_centers(points, labels)
        centers = centers.compute().values
        if np.all(centers == old_centers):
            break
    return labels.compute()

7. Multithreading, Multiprocessing und Async

Nach einem kurzen Überblick werden anhand von drei Beispielen zu Threading, Multiprocessing und Async die Regeln und Best Practices veranschaulicht.