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]

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 in den folgenden drei Schritten ereichen:

  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:

def dist(x, y):
    """Calculate the distance"""
    return sum((xi - yi) ** 2 for xi, yi in zip(x, y))


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):
        counts[label] += 1
        centers[label] = [a + b for a, b in zip(centers[label], point)]

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


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 der iPython Profiler oder scalene genutzt werden.

Siehe auch

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.

Anti-Patterns finden#

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

Siehe auch

Vektorisierungen mit NumPy#

NumPy verlagert sich wiederholte Operationen in eine statisch typisierte kompilierte Schicht, um so die schnelle Entwicklungszeit von Python mit der schnellen Ausführungszeit von C zu kombinieren. 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.

Mit NumPy können wir auf einige Schleifen verzichten:

import numpy as np

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.

Spezielle Datenstrukturen#

pandas

für SQL-ähnliche Gruppenoperationen und Aggregation.

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

import pandas as pd

def compute_centers(points, labels):
    """Calculate the cluster centres."""
    df = pd.DataFrame(points)
    return df.groupby(labels).mean().values
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:

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-diemensional 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.

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.

Siehe auch

Wenn ihr mit eurem Projekt nicht bis zur Veröffentlichung von Python 3.11 in der finalen Version voraussichtlich am 24. Oktober 2022 warten wollt, könnt ihr euch auch die folgenden Python-Interpreter anschauen:

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. 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:

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.:

import numba

@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)
    return labels

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

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:

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

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()

Multithreading, Multiprocessing und Async#

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