.. SPDX-FileCopyrightText: 2021 cusy GmbH
..
.. SPDX-License-Identifier: BSD-3-Clause

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,
:abbr:`z.B. (zum Beispiel)` 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.«[#]_

.. [#] Donald Knuth, Begründer des `Literate programming
       <http://www.literateprogramming.com/>`_, in Computer Programming as an
       Art (1974)

.. seealso::
   * `Speed up your data science and scientific computing code
     <https://pythonspeed.com/datascience/>`_

k-Means-Beispiel
----------------

Im Folgenden zeige ich Beispiele für den `k-Means-Algorithmus
<https://de.wikipedia.org/wiki/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
<https://de.wikipedia.org/wiki/K-Means-Algorithmus#MacQueen’s_Algorithmus>`_ in
den folgenden drei Schritten erreichen:

#. Wähle die ersten :samp:`k` Elemente als Clusterzentren
#. Weise jedes neue Element dem Cluster zu, bei dem sich die Varianz am
   wenigsten erhöht
#. 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:

.. literalinclude:: py_kmeans.py
   :caption: py_kmeans.py
   :name: py_kmeans.py
   :lines: 6-

Beispieldaten können wir uns erstellen mit:

.. code-block:: python

    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:

.. code-block:: python

    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 :abbr:`z. B. (zum Beispiel)`
:doc:`cProfile <tracing>`, :doc:`ipython-profiler`, :doc:`scalene`, :doc:`tprof`
oder :doc:`memray` genutzt werden. Bisher führe ich meist die folgenden Schritte
aus:

#. Ich profiliere das gesamte Programm mit :doc:`cProfile <tracing>` oder
   `py-spy <https://github.com/benfred/py-spy>`_, um langsame Funktionen zu
   finden.
#. :abbr:`Ggf (Gegebenenfalls)` finde ich mit dem `line_profiler
   <https://github.com/pyutils/line_profiler>`_ die langsamen Stellen innerhalb
   der Funktion
#. 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.
#. Schließlich erstelle ich ein neues Profil und filtere das Ergebnis meiner
   optimierten Version heraus um die Ergebnisse vergleichen zu können.

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

   :mod:`profiling.tracing`
       deterministische Funktionsaufrufverfolgung, die aus :doc:`cProfile
       <tracing>` verschoben wurde.
   :mod:`profiling.sampling`
       der neue statistische Sampling-Profiler :doc:`tachyon`.

.. seealso::
    * `airspeed velocity (asv) <https://asv.readthedocs.io/en/stable/>`_ 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 <https://speed.python.org/>`_
    * `Tracing the Python GIL
      <https://www.maartenbreddels.com/perf/jupyter/python/tracing/gil/2021/01/14/Tracing-the-Python-GIL.html>`_

.. toctree::
    :hidden:
    :titlesonly:
    :maxdepth: 0

    tracing
    ipython-profiler.ipynb
    scalene.ipynb
    tprof
    memray
    tachyon

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:

* `sklearn.cluster.KMeans
  <https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html>`_

  .. code-block:: python

     from sklearn.cluster import KMeans


     KMeans(10).fit_predict(points)

* `dask_ml.cluster.KMeans
  <https://ml.dask.org/modules/generated/dask_ml.cluster.KMeans.html>`_

  .. code-block:: python

     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 <https://scikit-learn.org/stable/>`_ oder
`Dask-ML <https://ml.dask.org>`_ 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 :doc:`perflint` euren Code durchsuchen nach den
häufigsten Performance-Anti-Patterns in Python.

.. toctree::
    :hidden:
    :titlesonly:
    :maxdepth: 0

    perflint

.. seealso::
   * `Effective Python <https://effectivepython.com>`_

3. Vektorisierungen mit NumPy
-----------------------------

:doc:`../workspace/numpy/index` 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  | 14,046ms      |          |
| – Basis       |               |          |
+---------------+---------------+----------+
| NumPy         | 27ms          | 520x     |
+---------------+---------------+----------+

:abbr:`Evtl. (Eventuell)` könnt ihr :doc:`../workspace/numpy/ufunc`,
:doc:`Vektorisierung <../workspace/numpy/vectorisation>` und
:doc:`../workspace/numpy/indexing-slicing` in allen Kombinationen nutzen um sich
wiederholende Operationen in kompilierten Code zu verschieben und damit langsame
Schleifen zu vermeiden, :abbr:`z. B. (zum Beispiel)`:

.. literalinclude:: np_kmeans.py
   :caption: np_kmeans.py
   :name: np_kmeans.py
   :lines: 5-12

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.

.. seealso::
   * `Speeding up NumPy with parallelism
     <https://pythonspeed.com/articles/numpy-parallelism/>`_ by Itamar
     Turner-Trauring

4. Spezielle Datenstrukturen
----------------------------

:doc:`../workspace/pandas/index`
    für SQL-ähnliche :doc:`../workspace/pandas/group-operations` und
    :doc:`../workspace/pandas/aggregation`.

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

    .. literalinclude:: pd_kmeans.py
       :caption: pd_kmeans.py
       :name: pd_kmeans.py
       :lines: 5-8, 16-19

`scipy.spatial <https://docs.scipy.org/doc/scipy/reference/spatial.html>`_
    für räumliche Abfragen wie Entfernungen, nächstgelegene Nachbarn,  k-Means
    :abbr:`usw. (und so weiter)`

    Unsere ``find_labels``-Methode kann dann noch spezifischer geschrieben
    werden:

    .. literalinclude:: sp_kmeans.py
       :caption: sp_kmeans.py
       :name: sp_kmeans.py
       :lines: 5-14

`scipy.sparse <https://docs.scipy.org/doc/scipy/reference/sparse.html>`_
    `dünnbesetzte Matrizen <https://de.wikipedia.org/wiki/Dünnbesetzte_Matrix>`_
    für 2-dimensionale strukturierte Daten.
`Sparse <https://sparse.pydata.org/en/stable/>`_
    für N-dimensional strukturierte Daten.
`scipy.sparse.csgraph <https://docs.scipy.org/doc/scipy/reference/sparse.csgraph.html>`_
    für graphenähnliche Probleme, :abbr:`z.B. (zum Beispiel)` die Suche nach
    kürzesten Wegen.
`Xarray <https://docs.xarray.dev/en/stable/>`_
    für die Gruppierung über mehrere Dimensionen hinweg.

.. toctree::
    :hidden:
    :titlesonly:
    :maxdepth: 0

    parallelise-pandas

5. Compiler wählen
------------------

Faster Cpython
~~~~~~~~~~~~~~

Auf der PyCon US im Mai 2021 stellte Guido van Rossum mit `Faster CPython
<https://github.com/faster-cpython>`_ ein Projekt vor, das die Geschwindigkeit
von Python 3.11 verdoppeln soll. Die Zusammenarbeit mit den anderen
Python-Kernentwicklern ist in :pep:`PEP 659 – Specializing Adaptive Interpreter
<659>` geregelt. Zudem gibt es einen offenen `Issue Tracker
<https://github.com/faster-cpython/ideas/issues>`_ und diverse `Werkzeuge zum
Sammeln von Bytecode-Statistiken <https://github.com/faster-cpython/tools>`_.
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          |         |
+------------------+---------+

.. seealso::
   * `Faster CPython
     <https://web.archive.org/web/20221007175548/https://faster-cpython.readthedocs.io/>`__
   * `Faster CPython Benchmark Infrastructure
     <https://github.com/faster-cpython/benchmarking-public?tab=readme-ov-file>`_

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  | 1,242ms |         | 14,046ms      |          |
| – Basis       |         |         |               |          |
+---------------+---------+---------+---------------+----------+
| CPython 3.14t | 1,513ms | 0.82x   | 14,551ms      | 0.97x    |
+---------------+---------+---------+---------------+----------+

– Quelle: `The Optimization Ladder
<https://cemrehancavdar.com/2026/03/10/optimization-ladder/>`_

Python JIT compiler
~~~~~~~~~~~~~~~~~~~

.. versionadded:: Python3.15
   Der `JIT-Compiler <https://de.wikipedia.org/wiki/Just-in-time-Kompilierung>`_
   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.

   .. seealso::
      * `The JIT Compiler
        <https://github.com/python/cpython/blob/main/Tools/jit/README.md>`_
      * :ref:`whatsnew315-jit`

+------------------+---------+
| Version          |         |
+==================+=========+
| CPython 3.15.0a0 | 1.001x  |
| (JIT)            |         |
+------------------+---------+
| 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 <https://cython.org>`_ hilfreich
sein.

+---------------+---------+---------+---------------+----------+
| Version       | N-body  | vs 3.14 | Spectral-norm | vs 3.14x |
+===============+=========+=========+===============+==========+
| CPython 3.14  | 1,242ms |         | 14,046ms      |          |
| – Basis       |         |         |               |          |
+---------------+---------+---------+---------------+----------+
| 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:

.. literalinclude:: cy_kmeans.pyx
   :caption: cy_kmeans.pyx
   :name: cy_kmeans.pyx
   :lines: 5-32

.. seealso::
   * `Cython Tutorials
     <https://cython.readthedocs.io/en/latest/src/tutorial/>`_
   * `The Cython Minefield
     <https://github.com/cemrehancavdar/faster-python-bench/blob/main/docs/cython-minefield.md>`_

Numba
~~~~~

`Numba <http://numba.pydata.org/>`_ ist ein JIT-Compiler, der vor allem
wissenschaftlichen Python- und NumPy-Code in schnellen Maschinencode
übersetzt, :abbr:`z.B. (zum Beispiel)`:

.. literalinclude:: nb_kmeans.py
   :caption: nb_kmeans.py
   :name: nb_kmeans.py
   :lines: 5-29

Numba benötigt allerdings `LLVM <https://de.wikipedia.org/wiki/LLVM>`_ und
einige Python-Konstrukte werden nicht unterstützt.

+---------------+---------+---------+---------------+----------+
| Version       | N-body  | vs 3.14 | Spectral-norm | vs 3.14x |
+===============+=========+=========+===============+==========+
| CPython 3.14  | 1,242ms |         | 14,046ms      |          |
| – Basis       |         |         |               |          |
+---------------+---------+---------+---------------+----------+
| Numba         | 22ms    | 56x     | 104ms         | 135x     |
+---------------+---------+---------+---------------+----------+

6. Aufgabenplaner
-----------------

:doc:`jupyter-tutorial:hub/ipyparallel/index`, :doc:`dask` und `Ray
<https://docs.ray.io/en/latest/>`_ können Aufgaben in einem Cluster verteilen.
Dabei haben sie unterschiedliche Schwerpunkte:

* ``ipyparallel`` integriert sich einfach in ein
  :doc:`jupyter-tutorial:hub/index`.
* :doc:`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 <https://docs.ray.io/en/latest/rllib/>`_ skaliert insbesondere
    reinforcement Learning.
  * Ein `Backend für Joblib
    <https://docs.ray.io/en/latest/ray-more-libs/joblib.html>`_ unterstützt
    verteilte `scikit-learn <https://scikit-learn.org/stable/>`_-Programme.
  * `XGBoost-Ray
    <https://docs.ray.io/en/latest/train/distributed-xgboost-lightgbm.html>`_
    ist ein Backend für verteiltes `XGBoost
    <https://xgboost.readthedocs.io/en/latest/>`_.
  * `LightGBM-Ray
    <https://docs.ray.io/en/latest/train/distributed-xgboost-lightgbm.html>`_
    ist ein Backend für verteiltes `LightGBM
    <https://lightgbm.readthedocs.io/en/latest/>`_
  * `Collective Communication Lib
    <https://docs.ray.io/en/latest/ray-more-libs/ray-collective.html>`_ bietet
    eine Reihe von nativen Collective-Primitiven für `Gloo
    <https://github.com/facebookincubator/gloo>`_ und die `NVIDIA Collective
    Communication Library (NCCL)
    <https://docs.nvidia.com/deeplearning/nccl/user-guide/docs/index.html>`_.

Unser Beispiel könnte mit Dask so aussehen:

.. literalinclude:: ds_kmeans.py
   :caption: ds_kmeans.py
   :name: ds_kmeans.py
   :lines: 5-

.. toctree::
    :hidden:
    :titlesonly:
    :maxdepth: 0

    dask.ipynb

7. Multithreading, Multiprocessing und Async
--------------------------------------------

Nach einem kurzen :doc:`Überblick <multiprocessing-threading-async>`
werden anhand von drei Beispielen zu :doc:`Threading <threading-example>`,
:doc:`Multiprocessing <multiprocessing>` und :doc:`Async <asyncio-example>`
die Regeln und Best Practices veranschaulicht.

.. toctree::
    :hidden:
    :titlesonly:
    :maxdepth: 0

    multiprocessing-threading-async
    threading-example.ipynb
    multiprocessing.ipynb
    threading-forking-combined.ipynb
    asyncio-example.ipynb