Accélérer Python avec C : trois façons d’appeler du code C (exemple Levenshtein)

Lorsque l’on rencontre une limite de performances en Python, il est souvent tentant de chercher des bibliotheques externes comme NumPy. Mais certaines approches d’optimisation ne conviennent pas aux algorithmes qui sont par nature sequenciels. Cet article illustre comment appeler du code C depuis Python pour gagner en vitesse, en utilisant l’algorithme de distance de Levenshtein comme banc d’essai.

Le contexte et l’algorithme

La distance de Levenshtein, definie par Vladimir Levenshtein en 1965, mesure le nombre minimal d’operations elementaires (insertion, suppression, substitution d’un caractere) necessaires pour transformer une chaine en une autre. Elle est utilisee, entre autres, dans les correcteurs orthographiques et la reconnaissance optique de caracteres.

Exemples :

• « book » -> « black » : book -> baok (substitution), baok -> back (substitution), back -> black (insertion) ; distance = 3.
• « superb » -> « super » : superb -> super (suppression de ‘b’) ; distance = 1.

Prerequis

Les exemples ont ete realises sous Windows. L’auteur a utilise Visual Studio Build Tools 2022 pour compiler le code C en ligne de commande. Sur Windows il convient d’ouvrir le « Developer command prompt for VS 2022 » pour initialiser l’environnement de compilation.

Les benchs s’executent depuis un environnement Python, typiquement un Jupyter Notebook. Dans l’article d’origine, un environnement virtuel est cree puis Jupyter est installe :

• uv init pythonc
• uv venv pythonc
• source pythonc/bin/activate (ou l’equivalent sous Windows)
• uv pip install jupyter

Methode 1 : subprocess (lev_sub.c)

La methode la plus simple consiste a compiler le code C en executable et a l’appeler depuis Python via le module subprocess. Le coeur de l’algorithme est la meme implemenation iteratif de Levenshtein mais compilee en executable.

Commande de compilation utilisee pour produire l’executable :

cl /O2 /Fe:lev_sub.exe lev_sub.c

Resultats du benchmark (chaque cas execute plusieurs fois, on retient le meilleur temps) :

• n=2000 m=2000 : Python : 1.276s -> 1768 ; Subproc : 0.024s -> 1768
• n=4000 m=4000 : Python : 5.015s -> 3519 ; Subproc : 0.050s -> 3519

Conclusion provisoire : appeler un executable C via subprocess donne deja un gain de temps tres significatif par rapport a une implementation pure Python.

Methode 2 : ctypes (lev.c)

ctypes est une interface FFI integree a Python qui permet de charger des bibliotheques partagées (DLL sous Windows) et d’appeler des fonctions C directement. Il faut exporter la fonction dans la DLL (sur Windows, par example avec __declspec(dllexport)) puis compiler :

cl /O2 /LD lev.c /Fe:lev.dll

Exemple d’appel depuis Python : on charge la DLL avec ctypes.CDLL, on precise argtypes et restype, puis on appelle la fonction apres avoir encode les chaines en bytes.

Resultats du benchmark :

• n=2000 m=2000 : Python : 1.258s -> 1769 ; ctypes : 0.019s -> 1769
• n=4000 m=4000 : Python : 5.138s -> 3521 ; ctypes : 0.035s -> 3521

Interpretation : ctypes evite le cout d’un processus externe et garde une integration simple, tout en offrant des temps comparables a la methode par subprocess.

Methode 3 : extensions C pour Python (lev_cext.c)

Pour une integration la plus etroite et des performances optimales, on peut ecrire une extension native en C en utilisant l’API CPython (Python.h). Cela requiert un peu plus de travail : on doit fournir une fonction d’enveloppe qui parse les arguments Python, appelle l’implementation C et retourne un objet Python.

Le module est compile avec setuptools via un setup.py et la commande :

python setup.py build_ext --inplace

Resultats du benchmark :

• 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

La meilleure performance est obtenue avec l’extension C native. Dans le second cas, la version C est plus de 150 fois plus rapide que l’implementation Python pure.

Et NumPy dans tout ca ?

NumPy est excellent pour les operations vectorisees sur tableaux numeriques et, pour des algorithmes qui se prete a la vectorisation, il offre des performances comparables a du C optimise. Mais le calcul de la distance de Levenshtein est essentiellement sequenciel et ne se mappe pas facilement en operations vectorisees. Dans ce cas, l’usage direct de C, via subprocess, ctypes ou une extension, apporte un vrai gain de temps.

L’auteur signale egalement avoir execute des tests supplementaires sur du code amenable a la vectorisation : dans ces cas, NumPy atteint des performances equivalentes a du C, ce qui est logique puisque NumPy repose lui-meme sur du code C optimise.

Resume et recommandations

• Subprocess : mise en place la plus simple, gros gain de temps, mais cout d’un processus externe.
• ctypes : bon compromis ; charge une DLL et appelle des fonctions C sans ecrire d’extension Python complete.
• Extension C : integraton la plus etroite et meilleures performances, mais installation et compilation plus complexes.

Quand Python devient limitant pour des taches intensives en calcul, externaliser le calcul vers du C est une solution efficace. On peut commencer par la methode la plus simple (subprocess), puis evoluer vers ctypes ou une extension native si on a besoin de meilleurs perfs ou d’une integration plus propre.