Rendre Python jusqu’à 150 fois plus rapide avec C

tôt ou tard, vous allez rencontrer un blocage en ce qui concerne la vitesse d’exécution de votre code. Si vous avez déjà écrit un algorithme lourd en calcul en Python, tel que la distance entre chaînes, les mathématiques matricielles ou le hachage cryptographique, vous saurez ce que je veux dire.

Bien sûr, il y a des moments où des bibliothèques externes comme NumPy peuvent venir à votre secours, mais que se passe-t-il lorsque l’algorithme est intrinsèquement séquentiel? C’était précisément mon problème lorsque je voulais comparer un algorithme particulier, qui détermine le nombre de modifications nécessaires pour transformer une chaîne en une autre.

J’ai essayé Python. J’ai essayé NumPy. Et puis je me suis tourné vers le C, un langage que j’ai appris pour la première fois à l’université il y a des décennies mais que je n’avais pas utilisé avec colère depuis environ 15 ans. C’est là que les choses sont devenues intéressantes.

J’ai d’abord dû répondre à la question « Pouvez-vous appeler C depuis Python ? ». Après quelques recherches, il est rapidement devenu clair que la réponse était bien Oui. En fait, il s’avère que vous pouvez le faire de plusieurs manières, et dans cet article, j’examinerai trois des façons les plus courantes de le faire.

Du plus simple au plus complexe, nous examinerons l’utilisation,

• un sous-processus
• types
• Extensions Python C

L’algorithme avec lequel nous allons tester s’appelle le Distance de Levenshtein (LD) algorithme. La distance de Levenshtein entre deux mots est le nombre minimum de modifications d’un seul caractère (insertions, suppressions ou substitutions) requises pour transformer un mot en un autre. Il porte le nom du mathématicien soviétique Vladimir Levenshtein, qui a défini la métrique en 1965. Il a des applications dans divers outils, tels que les correcteurs orthographiques et les systèmes de reconnaissance optique de caractères.

Pour vous donner une idée plus claire de ce dont nous parlons, voici quelques exemples.

Calculez le LD entre les mots « livre » et « noir ».

1. livre → baok (substitution de « a » à « o »),
2. baok → retour (substitution de « c » à « o »)
3. retour → noir (ajouter la lettre « l »)

Ainsi, le LD dans ce cas est de trois.

Calculez le LD entre les mots « superbe » et « super ».

1. superbe → super (supprimer la lettre « b »)

Le LD dans ce cas n’en est qu’un.

Nous coderons l’algorithme LD en Python et C, puis établirons des tests de performance pour tester le temps nécessaire à son exécution en utilisant du code Python pur par rapport au temps nécessaire à son exécution en code C appelé depuis Python.

Conditions préalables

Comme je l’exécutais sous MS Windows, j’avais besoin d’un moyen de compiler des programmes C. Le moyen le plus simple que j’ai trouvé pour le faire était de télécharger les outils Visual Studio Build pour 2022. Cela vous permet de compiler des programmes C sur la ligne de commande.

Pour installer, allez d’abord dans la page principale Page de téléchargement de Visual Studio. Sur le deuxième écran, vous verrez un champ de recherche. Taper « Construire des outils » dans le champ de recherche et cliquez sur Rechercher. La recherche devrait renvoyer un écran qui ressemble à ceci,

Cliquez sur le bouton Télécharger et suivez les instructions d’installation. Une fois installé, dans une fenêtre de terminal DOS, lorsque vous cliquez sur le petit bouton plus pour ouvrir un nouveau terminal, vous devriez voir une option pour ouvrir une « invite de commande développeur pour VS 2022 ».

La plupart de mon code Python s’exécutera sur un Jupyter Notebook, vous devez donc configurer un nouvel environnement de développement et installer Jupyter. Faites-le maintenant si vous voulez suivre. J’utilise l’outil UV pour cette partie, mais n’hésitez pas à utiliser la méthode avec laquelle vous êtes le plus à l’aise.

c:\> uv init pythonc
c:\> cd pythonc
c:\> uv venv pythonc
c:\> source pythonc/bin/activate
(pythonc) c:\> uv pip install jupyter

L’algorithme LD en C

Nous avons besoin de versions légèrement différentes de l’algorithme LD en C, selon la méthode utilisée pour l’appeler. Il s’agit de la version de notre premier exemple, où nous utilisons le sous-traitement pour appeler un exécutable C.

1/ sous-traitement : lev_sub.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int levenshtein(const char* a, const char* b) {
    size_t n = strlen(a), m = strlen(b);
    if (n == 0) return (int)m;
    if (m == 0) return (int)n;
    int* prev = (int*)malloc((m + 1) * sizeof(int));
    int* curr = (int*)malloc((m + 1) * sizeof(int));
    if (!prev || !curr) { free(prev); free(curr); return -1; }
    for (size_t j = 0; j <= m; ++j) prev[j] = (int)j;
    for (size_t i = 1; i <= n; ++i) {
        curr[0] = (int)i; char ca = a[i - 1];
        for (size_t j = 1; j <= m; ++j) {
            int cost = (ca == b[j - 1]) ? 0 : 1;
            int del = prev[j] + 1, ins = curr[j - 1] + 1, sub = prev[j - 1] + cost;
            int d = del < ins ? del : ins; curr[j] = d < sub ? d : sub;
        }
        int* tmp = prev; prev = curr; curr = tmp;
    }
    int ans = prev[m]; free(prev); free(curr); return ans;
}

int main(int argc, char** argv) {
    if (argc != 3) { fprintf(stderr, "usage: %s <s1> <s2>\n", argv[0]); return 2; }
    int d = levenshtein(argv[1], argv[2]);
    if (d < 0) return 1;
    printf("%d\n", d);
    return 0;
}

Pour compiler cela, démarrez une nouvelle invite de commande de développeur pour VS Code 2022 et tapez ce qui suit pour vous assurer que nous optimisons la compilation pour l’architecture 64 bits.

(pythonc) c:\> "%VSINSTALLDIR%VC\Auxiliary\Build\vcvarsall.bat" x64

Ensuite, nous pouvons compiler notre code C à l’aide de cette commande.

(pythonc) c:\> cl /O2 /Fe:lev_sub.exe lev_sub.c

Cela créera un fichier exécutable.

Analyse comparative du code de sous-traitement

Dans un notebook Jupyter, saisissez le code suivant, qui sera commun à tous nos benchmarks. Il génère des chaînes minuscules aléatoires de longueur N et calcule le nombre de modifications nécessaires pour transformer chaîne1 en chaîne2.

# Sub-process benchmark
import time, random, string, subprocess
import numpy as np

EXE = r"lev_sub.exe"  

def rnd_ascii(n):
    return ''.join(random.choice(string.ascii_lowercase) for _ in range(n))

def lev_py(a: str, b: str) -> int:
    n, m = len(a), len(b)
    if n == 0: return m
    if m == 0: return n
    prev = list(range(m+1))
    curr = [0]*(m+1)
    for i, ca in enumerate(a, 1):
        curr[0] = i
        for j, cb in enumerate(b, 1):
            cost = 0 if ca == cb else 1
            curr[j] = min(prev[j] + 1, curr[j-1] + 1, prev[j-1] + cost)
        prev, curr = curr, prev
    return prev[m]

Vient ensuite le code d’analyse comparative réel et les résultats d’exécution. Pour exécuter la partie C du code, nous générons un sous-processus qui exécute le fichier de code C compilé que nous avons créé précédemment et mesure le temps nécessaire à son exécution, en le comparant avec la méthode Python pure. Nous exécutons chaque méthode trois fois sur un ensemble de 2 000 et 4 000 mots aléatoires et prenons le temps le plus rapide.

def lev_subprocess(a: str, b: str) -> int:
    out = subprocess.check_output([EXE, a, b], text=True)
    return int(out.strip())

def bench(fn, *args, repeat=3, warmup=1):
    for _ in range(warmup): fn(*args)
    best = float("inf"); out_best = None
    for _ in range(repeat):
        t0 = time.perf_counter(); out = fn(*args); dt = time.perf_counter() - t0
        if dt < best: best, out_best = dt, out
    return out_best, best

if __name__ == "__main__":
    cases = [(2000,2000),(4000, 4000)]
    print("Benchmark: Pythonvs C (subprocess)\n")
    for n, m in cases:
        a, b = rnd_ascii(n), rnd_ascii(m)
        py_out, py_t = bench(lev_py, a, b, repeat=3)
        sp_out, sp_t = bench(lev_subprocess, a, b, repeat=3)
        print(f"n={n} m={m}")
        print(f"  Python   : {py_t:.3f}s -> {py_out}")
        print(f"  Subproc  : {sp_t:.3f}s -> {sp_out}\n")

Voici les résultats.

Benchmark: Python vs C (subprocess)

n=2000 m=2000 
  Python   : 1.276s -> 1768
  Subproc  : 0.024s -> 1768

n=4000 m=4000 
  Python   : 5.015s -> 3519
  Subproc  : 0.050s -> 3519

C’est une amélioration assez significative du temps d’exécution de C par rapport à Python.

2. ctypes : niveau.c

ctypes est un interface de fonction étrangère (FFI) bibliothèque intégrée directement à la bibliothèque standard de Python. Il permet de charger et d’appeler des fonctions depuis des bibliothèques partagées écrites en C (DLL sous Windows, .so fichiers sous Linux, .dylib sur macOS) directement depuis Pythonsans avoir besoin d’écrire un module d’extension complet en C.

Tout d’abord, voici notre version C de l’algorithme LD, utilisant des ctypes. C’est presque identique à notre fonction C de sous-processus, avec l’ajout d’une ligne qui nous permet d’utiliser Python pour appeler la DLL après sa compilation.

/* 
 * lev.c
*/

#include <stdlib.h>
#include <string.h>

/* below line includes this function in the 
 * DLL's export table so other programs can use it.
 */
__declspec(dllexport)

int levenshtein(const char* a, const char* b) {
    size_t n = strlen(a), m = strlen(b);
    if (n == 0) return (int)m;
    if (m == 0) return (int)n;

    int* prev = (int*)malloc((m + 1) * sizeof(int));
    int* curr = (int*)malloc((m + 1) * sizeof(int));
    if (!prev || !curr) { free(prev); free(curr); return -1; }

    for (size_t j = 0; j <= m; ++j) prev[j] = (int)j;

    for (size_t i = 1; i <= n; ++i) {
        curr[0] = (int)i;
        char ca = a[i - 1];
        for (size_t j = 1; j <= m; ++j) {
            int cost = (ca == b[j - 1]) ? 0 : 1;
            int del = prev[j] + 1;
            int ins = curr[j - 1] + 1;
            int sub = prev[j - 1] + cost;
            int d = del < ins ? del : ins;
            curr[j] = d < sub ? d : sub;
        }
        int* tmp = prev; prev = curr; curr = tmp;
    }
    int ans = prev[m];
    free(prev); free(curr);
    return ans;
}

Lorsque nous utilisons des ctypes pour appeler C en Python, nous devons convertir notre code C en une bibliothèque de liens dynamiques (DLL) plutôt qu’en exécutable. Voici la commande build dont vous avez besoin pour cela.

(pythonc) c:\> cl /O2 /LD lev.c /Fe:lev.dll

Analyse comparative du code ctypes

j’omets le lev_py et rnd_ascii Fonctions Python dans cet extrait de code, car elles sont identiques à celles de l’exemple précédent. Tapez ceci dans votre cahier.

#ctypes benchmark

import time, random, string, ctypes
import numpy as np

DLL = r"lev.dll"  

levdll = ctypes.CDLL(DLL)
levdll.levenshtein.argtypes = [ctypes.c_char_p, ctypes.c_char_p]
levdll.levenshtein.restype  = ctypes.c_int

def lev_ctypes(a: str, b: str) -> int:
    return int(levdll.levenshtein(a.encode('utf-8'), b.encode('utf-8')))

def bench(fn, *args, repeat=3, warmup=1):
    for _ in range(warmup): fn(*args)
    best = float("inf"); out_best = None
    for _ in range(repeat):
        t0 = time.perf_counter(); out = fn(*args); dt = time.perf_counter() - t0
        if dt < best: best, out_best = dt, out
    return out_best, best

if __name__ == "__main__":
    cases = [(2000,2000),(4000, 4000)]
    print("Benchmark: Python vs NumPy vs C (ctypes)\n")
    for n, m in cases:
        a, b = rnd_ascii(n), rnd_ascii(m)
        py_out, py_t = bench(lev_py, a, b, repeat=3)
        ct_out, ct_t = bench(lev_ctypes, a, b, repeat=3)
        print(f"n={n} m={m}")
        print(f"  Python   : {py_t:.3f}s -> {py_out}")
        print(f"  ctypes   : {ct_t:.3f}s -> {ct_out}\n")

Et les résultats ?

Benchmark: Python vs C (ctypes)

n=2000 m=2000  
  Python   : 1.258s -> 1769
  ctypes   : 0.019s -> 1769

n=4000 m=4000 
  Python   : 5.138s -> 3521
  ctypes   : 0.035s -> 3521

Nous avons des résultats très similaires au premier exemple.

3/ Extensions Python C : lev_cext.c

Lorsque vous utilisez des extensions Python C, cela demande un peu plus de travail. Tout d’abord, examinons le code C. L’algorithme de base est inchangé. C’est juste que nous devons ajouter un peu plus d’échafaudage pour permettre au code d’être appelé depuis Python. Il utilise l’API de CPython (Python.h) pour analyser les arguments Python, exécuter le code C et renvoyer le résultat sous forme d’entier Python.

La fonction levext_lev agit comme un emballage. Il analyse deux arguments de chaîne de Python (PyArg_ParseTuple), appelle la fonction C lev_impl pour calculer la distance, gère les erreurs de mémoire et renvoie le résultat sous forme d’entier Python (PyLong_FromLong). La table Méthodes enregistre cette fonction sous le nom « levenshtein », elle peut donc être appelée à partir du code Python. Enfin, PyInit_levext définit et initialise le module levextle rendant importable en Python avec la commande import levext.

#include <Python.h>
#include <string.h>
#include <stdlib.h>

static int lev_impl(const char* a, const char* b) {
    size_t n = strlen(a), m = strlen(b);
    if (n == 0) return (int)m;
    if (m == 0) return (int)n;
    int* prev = (int*)malloc((m + 1) * sizeof(int));
    int* curr = (int*)malloc((m + 1) * sizeof(int));
    if (!prev || !curr) { free(prev); free(curr); return -1; }
    for (size_t j = 0; j <= m; ++j) prev[j] = (int)j;
    for (size_t i = 1; i <= n; ++i) {
        curr[0] = (int)i; char ca = a[i - 1];
        for (size_t j = 1; j <= m; ++j) {
            int cost = (ca == b[j - 1]) ? 0 : 1;
            int del = prev[j] + 1, ins = curr[j - 1] + 1, sub = prev[j - 1] + cost;
            int d = del < ins ? del : ins; curr[j] = d < sub ? d : sub;
        }
        int* tmp = prev; prev = curr; curr = tmp;
    }
    int ans = prev[m]; free(prev); free(curr); return ans;
}

static PyObject* levext_lev(PyObject* self, PyObject* args) {
    const char *a, *b;
    if (!PyArg_ParseTuple(args, "ss", &a, &b)) return NULL;
    int d = lev_impl(a, b);
    if (d < 0) { PyErr_SetString(PyExc_MemoryError, "alloc failed"); return NULL; }
    return PyLong_FromLong(d);
}

static PyMethodDef Methods[] = {
    {"levenshtein", levext_lev, METH_VARARGS, "Levenshtein distance"},
    {NULL, NULL, 0, NULL}
};

static struct PyModuleDef mod = { PyModuleDef_HEAD_INIT, "levext", NULL, -1, Methods };
PyMODINIT_FUNC PyInit_levext(void) { return PyModule_Create(&mod); }

Parce que cette fois, nous ne construisons pas seulement un exécutable mais un module d’extension Python natif, nous devons construire le code C différemment.

Ce type de module doit être compilé avec les en-têtes de Python et lié de manière appropriée au runtime de Python afin qu’il se comporte comme un module Python intégré.

Pour y parvenir, nous créons un module Python appelé setup.py, qui importe la bibliothèque setuptools pour faciliter ce processus. Il automatise :

• Trouver les bons chemins d’inclusion pour Python.h
• Passer les bons indicateurs du compilateur et de l’éditeur de liens
• Produire un fichier .pyd avec la convention de dénomination adaptée à votre version et plate-forme Python

En faisant cela à la main avec le cl La commande du compilateur serait fastidieuse et sujette aux erreurs, car vous devrez spécifier manuellement tous ces chemins et indicateurs.

Voici le code dont nous avons besoin.

from setuptools import setup, Extension
setup(
    name="levext",
    version="0.1.0",
    ext_modules=[Extension("levext", ["lev_cext.c"], extra_compile_args=["/O2"])],
)

Nous l’exécutons en utilisant Python standard sur la ligne de commande, comme indiqué ici.

(pythonc) c:\> python setup.py build_ext --inplace

#output
running build_ext
copying build\lib.win-amd64-cpython-312\levext.cp312-win_amd64.pyd ->

Analyse comparative du code des extensions Python C

Maintenant, voici le code Python pour appeler notre C. Encore une fois, j’ai omis les deux fonctions d’assistance Python qui restent inchangées par rapport aux exemples précédents.

# c-ext benchmark

import time, random, string
import numpy as np
import levext  # make sure levext.cp312-win_amd64.pyd is built & importable

def lev_extension(a: str, b: str) -> int:
    return levext.levenshtein(a, b)

def bench(fn, *args, repeat=3, warmup=1):
    for _ in range(warmup): fn(*args)
    best = float("inf"); out_best = None
    for _ in range(repeat):
        t0 = time.perf_counter(); out = fn(*args); dt = time.perf_counter() - t0
        if dt < best: best, out_best = dt, out
    return out_best, best

if __name__ == "__main__":
    cases = [(2000, 2000), (4000, 4000)]
    print("Benchmark: Python vs NumPy vs C (C extension)\n")
    for n, m in cases:
        a, b = rnd_ascii(n), rnd_ascii(m)
        py_out, py_t = bench(lev_py, a, b, repeat=3)
        ex_out, ex_t = bench(lev_extension, a, b, repeat=3)
        print(f"n={n} m={m} ")
        print(f"  Python   : {py_t:.3f}s -> {py_out}")
        print(f"  C ext    : {ex_t:.3f}s -> {ex_out}\n")

Voici le résultat.

Benchmark: Python vs C (C extension)

n=2000 m=2000  
  Python   : 1.204s -> 1768
  C ext    : 0.010s -> 1768

n=4000 m=4000  
  Python   : 5.039s -> 3526
  C ext    : 0.033s -> 3526

C’est donc cela qui a donné les résultats les plus rapides. La version C apparaît comme plus de 150 fois plus rapide que Python pur dans le deuxième scénario de test ci-dessus.

Pas trop mal.

Mais qu’en est-il de NumPy ?

Certains d’entre vous se demandent peut-être pourquoi NumPy n’a pas été utilisé. Eh bien, NumPy est fantastique pour les opérations sur tableaux numériques vectorisés, telles que les produits scalaires, mais tous les algorithmes ne correspondent pas proprement à la vectorisation. Le calcul des distances de Levenshtein est un processus intrinsèquement séquentiel, donc NumPy ne fournit pas beaucoup d’aide. Dans ces cas, passer en C via sous-processus, typesou un extension C native fournit de réelles accélérations d’exécution tout en restant appelable depuis Python.

PS. J’ai effectué quelques tests supplémentaires en utilisant du code compatible avec NumPy, et il n’était pas surprenant que NumPy soit aussi rapide que le code C appelé. Il faut s’y attendre car NumPy utilise C sous le capot et a de nombreuses années de développement et d’optimisation derrière lui.

Résumé

L’article explore comment les développeurs Python peuvent surmonter les goulots d’étranglement en termes de performances dans les tâches à forte intensité de calcul, telles que le calcul du Distance de Levenshtein— un algorithme de similarité de chaînes — en intégrant du code C dans Python. Alors que les bibliothèques comme NumPy accélèrent les opérations vectorisées, les algorithmes séquentiels comme Levenshtein restent souvent imperméables aux optimisations de NumPy.

Pour résoudre ce problème, j’ai démontré trois modèles d’intégration allant du plus simple au plus avancé, qui vous permettent d’appeler du code C rapide depuis Python.

Sous-processus. Compilez le code C dans un exécutable (par exemple, avec gcc ou Visual Studio Build Tools) et exécutez-le depuis Python à l’aide du module de sous-processus. Ceci est facile à configurer et montre déjà une énorme accélération par rapport au Python pur.

ctypes.L’utilisation de ctypes permet à Python de charger et d’appeler directement des fonctions à partir de bibliothèques partagées C sans avoir besoin d’écrire un module d’extension Python complet. Cela rend beaucoup plus simple et plus rapide l’intégration de code C critique en termes de performances dans Python, évitant ainsi la surcharge liée à l’exécution de processus externes tout en conservant votre code principalement en Python.

Extensions Python C . Écrivez une extension Python complète en C à l’aide de l’API CPython (python.h). Cela nécessite plus de configuration mais offre les performances les plus rapides et l’intégration la plus fluide, vous permettant d’appeler des fonctions C comme s’il s’agissait de fonctions Python natives.

Les tests montrent que les implémentations C de l’algorithme de Levenshtein s’exécutent plus de 100 fois plus rapide que du Python pur. Alors qu’une bibliothèque externe telle que NumPyexcelle dans les opérations numériques vectorisées, il n’améliore pas de manière significative les performances des algorithmes intrinsèquement séquentiels comme Levenshtein, ce qui fait de l’intégration C un meilleur choix dans de tels cas.

Si vous atteignez les limites de performances en Python, transférer des calculs lourds vers C peut apporter des améliorations de vitesse considérables et mérite d’être envisagé. Vous pouvez commencer simplement avec un sous-processus, puis passer aux ctypes ou aux extensions C complètes pour une intégration plus étroite et de meilleures performances.

Je n’ai décrit que trois des méthodes les plus populaires pour intégrer du code C à Python, mais il existe quelques autres méthodes que je vous recommande de lire si ce sujet vous intéresse.