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]

[1]

Donald Knuth, Begründer des Literate programming, in Computer Programming as an Art (1974)

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:

py_kmeans.py

# SPDX-FileCopyrightText: 2021 Veit Schiele
#
# SPDX-License-Identifier: BSD-3-Clause


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

• airspeed velocity (asv) ist ein Werkzeug zum Benchmarking von Python-Paketen während ihrer Lebensdauer. Laufzeit, Speicherverbrauch und sogar benutzerdefinierte Werte können aufgezeichnet und in einem interaktiven Web-Frontend angezeigt werden.

• Python Speed Center

• Tracing the Python GIL

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:

• sklearn.cluster.KMeans

  from sklearn.cluster import KMeans
  
  
  KMeans(10).fit_predict(points)
  

• dask_ml.cluster.KMeans

  from dask_ml.cluster import KMeans
  
  
  KMeans(10).fit(points).predict(points)
  

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

• Effective Python

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:

np_kmeans.py

# SPDX-FileCopyrightText: 2021 Veit Schiele
#
# SPDX-License-Identifier: BSD-3-Clause

import numpy as np


def find_labels(points, centers):

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:

pd_kmeans.py

#
# SPDX-License-Identifier: BSD-3-Clause

    diff = points[:, None, :] - centers
    distances = (diff**2).sum(-1)
    return distances.argmin(1)

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

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

• Faster CPython

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:

cy_kmeans.pyx

# SPDX-FileCopyrightText: 2023 Veit Schiele
#
# SPDX-License-Identifier: BSD-3-Clause

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:

Siehe auch

• Cython Tutorials

Numba

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

nb_kmeans.py

# SPDX-FileCopyrightText: 2021 Veit Schiele
#
# SPDX-License-Identifier: BSD-3-Clause

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

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:

• ipyparallel integriert sich einfach in ein JupyterHub.

• Dask imitiert pandas, NumPy, Iteratoren, Toolz und PySpark bei der Verteilung ihrer Aufgaben.

• Ray bietet eine einfache, universelle API für den Aufbau verteilter Anwendungen.

  • RLlib skaliert insbesondere reinforcement Learning.

  • Ein Backend für Joblib unterstützt verteilte scikit-learn-Programme.

  • XGBoost-Ray ist ein Backend für verteiltes XGBoost.

  • LightGBM-Ray ist ein Backend für verteiltes LightGBM

  • Collective Communication Lib bietet eine Reihe von nativen Collective-Primitiven für Gloo und die NVIDIA Collective Communication Library (NCCL).

Unser Beispiel könnte mit Dask so aussehen:

ds_kmeans.py

# SPDX-FileCopyrightText: 2021 Veit Schiele
#
# SPDX-License-Identifier: BSD-3-Clause

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

Multithreading, Multiprocessing und Async

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