Make Python Up to 150× Faster with C

, ultimately, you’re going to hit a block in terms of your code execution pace. When you’ve ever written a computationally heavy algorithm in Python, resembling string distance, matrix math, or cryptographic hashing, you’ll know what I imply.

Certain, there are occasions when exterior libraries like NumPy can come to your rescue, however what occurs when the algorithm is inherently sequential? That was exactly my drawback once I wished to benchmark a selected algorithm, which determines the variety of edits required to remodel one string into one other.

I attempted Python. I attempted NumPy. After which I turned to C, a language I first realized at school many years in the past however hadn’t utilized in anger for about 15 years. That’s the place issues obtained attention-grabbing.

I first needed to reply the query, “Are you able to name C from Python?”. After some analysis, it shortly turned clear that the reply was certainly sure. In truth, it seems you are able to do it in a number of methods, and on this article, I’ll take a look at three of the commonest methods of doing so. 

From best to most complicated, we’ll take a look at utilizing,

• a subprocess
• ctypes
• Python C extensions

The algorithm that we’ll be testing with is known as the Levenshtein Distance (LD) algorithm. The Levenshtein distance between two phrases is the minimal variety of single-character edits (insertions, deletions or substitutions) required to alter one phrase into the opposite. It’s named after Soviet mathematician Vladimir Levenshtein, who outlined the metric in 1965. It has purposes in varied instruments, resembling spell checkers and optical character recognition programs.

To offer you a clearer image of what we’re speaking about, listed here are a few examples. 

Calculate the LD between the phrases “e book” and “black”.

1. e book → baok (substitution of “a” for “o”),
2. baok → again (substitution of “c” for “o”)
3. again → black (add the letter “l”)

So, the LD on this case is three.

Calculate the LD between the phrases “excellent” and “tremendous”.

1. excellent → tremendous (take away letter “b”)

The LD on this case is solely one.

We’ll code up the LD algorithm in Python and C, then arrange benchmarks to check how lengthy it takes to run it utilizing pure Python code versus the time it takes to run it in C code known as from Python. 

Stipulations

As I used to be working this on MS Home windows, I wanted a manner of compiling C packages. The simplest manner I discovered to do that was to obtain the Visible Studio Construct instruments for 2022. This lets you compile C packages on the command line.

To put in, first go to the principle Visual Studio downloads page. On the second display screen, you’ll see a search field. Kind “Construct Instruments” into the search subject and click on Search. The search ought to return a display screen that appears like this,

Click on the Obtain button and comply with any set up directions. As soon as it’s been put in, in a DOS terminal window, while you click on on the little plus button to open a brand new terminal, it is best to see an choice to open a “Developer command immediate for VS 2022”. 

Most of my Python code will likely be working on a Jupyter Pocket book, so it is best to arrange a brand new growth atmosphere and set up Jupyter. Try this now if you wish to comply with alongside. I’m utilizing the UV device for this half, however be at liberty to make use of whichever methodology you’re most comfy with.

c:> uv init pythonc
c:> cd pythonc
c:> uv venv pythonc
c:> supply pythonc/bin/activate
(pythonc) c:> uv pip set up jupyter

The LD algorithm in C

We want barely completely different variations of the LD algorithm in C, relying on the tactic used to name it. That is the model for our first instance, the place we use subprocessing to name a C executable.

1/ subprocessing: lev_sub.c

#embrace <stdio.h>
#embrace <stdlib.h>
#embrace <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 price = (ca == b[j - 1]) ? 0 : 1;
            int del = prev[j] + 1, ins = curr[j - 1] + 1, sub = prev[j - 1] + price;
            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 predominant(int argc, char** argv) {
    if (argc != 3) { fprintf(stderr, "utilization: %s <s1> <s2>n", argv[0]); return 2; }
    int d = levenshtein(argv[1], argv[2]);
    if (d < 0) return 1;
    printf("%dn", d);
    return 0;
}

To compile this, begin a brand new Developer Command Immediate for VS Code 2022 and kind the next to make sure we’re optimising the compilation for 64-bit structure.

(pythonc) c:> "%VSINSTALLDIRpercentVCAuxiliaryBuildvcvarsall.bat" x64

Subsequent, we will compile our C code utilizing this command.

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

That may create an executable file.

Benchmarking the subprocessing code

In a Jupyter pocket book, sort within the following code, which will likely be widespread to all our benchmarking. It generates random lowercase strings of size N and calculates the variety of edits required to remodel string1 into string2.

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

EXE = r"lev_sub.exe"  

def rnd_ascii(n):
    return ''.be part of(random.alternative(string.ascii_lowercase) for _ in vary(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 = checklist(vary(m+1))
    curr = [0]*(m+1)
    for i, ca in enumerate(a, 1):
        curr[0] = i
        for j, cb in enumerate(b, 1):
            price = 0 if ca == cb else 1
            curr[j] = min(prev[j] + 1, curr[j-1] + 1, prev[j-1] + price)
        prev, curr = curr, prev
    return prev[m]

Subsequent is the precise benchmarking code and run outcomes. To run the C a part of the code, we spawn a subprocess that executes the compiled C code file we beforehand created and measures the time it takes to run, evaluating it with the pure Python methodology. We run every methodology in opposition to a 2000 and a 4000 set of random phrases thrice and take the quickest of these occasions.

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

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

if __name__ == "__main__":
    instances = [(2000,2000),(4000, 4000)]
    print("Benchmark: Pythonvs C (subprocess)n")
    for n, m in instances:
        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")

 Listed below are the outcomes.

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

That’s a fairly vital enchancment within the run-time of C over Python.

2. ctypes: lev.c

ctypes is a overseas operate interface (FFI) library constructed proper into Python’s commonplace library. It enables you to load and name features from shared libraries written in C (DLLs on Home windows, .so recordsdata on Linux, .dylib on macOS) immediately from Python, without having to write down a whole extension module in C.

First, right here is our C model of the LD algorithm, utilising ctypes. It’s virtually similar to our subprocess C operate, with the addition of a line that allows us to make use of Python to name the DLL after it has been compiled.

/* 
 * lev.c
*/

#embrace <stdlib.h>
#embrace <string.h>

/* beneath line contains this operate within the 
 * DLL's export desk so different packages 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 price = (ca == b[j - 1]) ? 0 : 1;
            int del = prev[j] + 1;
            int ins = curr[j - 1] + 1;
            int sub = prev[j - 1] + price;
            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;
}

When utilizing ctypes to name C in Python, we have to convert our C code right into a dynamic hyperlink library (DLL) quite than an executable. Right here is the construct command you want for that.

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

Benchmarking the ctypes code

I’m omitting the lev_py and rnd_ascii Python features on this code snippet, as they’re similar to these within the earlier instance. Kind this into your pocket book.

#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 vary(warmup): fn(*args)
    greatest = float("inf"); out_best = None
    for _ in vary(repeat):
        t0 = time.perf_counter(); out = fn(*args); dt = time.perf_counter() - t0
        if dt < greatest: greatest, out_best = dt, out
    return out_best, greatest

if __name__ == "__main__":
    instances = [(2000,2000),(4000, 4000)]
    print("Benchmark: Python vs NumPy vs C (ctypes)n")
    for n, m in instances:
        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")

And the outcomes?

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

We now have very related outcomes to the primary instance.

3/ Python C extensions: lev_cext.c

When utilizing Python C extensions, there’s barely extra work concerned. First, let’s look at the C code. The essential algorithm is unchanged. It’s simply that we have to add a bit extra scaffolding to allow the code to be known as from Python. It makes use of CPython’s API (Python.h) to parse Python arguments, run the C code, and return the consequence as a Python integer.

The operate levext_lev acts as a wrapper. It parses two string arguments from Python (PyArg_ParseTuple), calls the C operate lev_impl to compute the gap, handles reminiscence errors, and returns the consequence as a Python integer (PyLong_FromLong). The Strategies desk registers this operate underneath the title “levenshtein”, so it may be known as from Python code. Lastly, PyInit_levext defines and initialises the module levext, making it importable in Python with the import levext command.

#embrace <Python.h>
#embrace <string.h>
#embrace <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 price = (ca == b[j - 1]) ? 0 : 1;
            int del = prev[j] + 1, ins = curr[j - 1] + 1, sub = prev[j - 1] + price;
            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 Strategies[] = {
    {"levenshtein", levext_lev, METH_VARARGS, "Levenshtein distance"},
    {NULL, NULL, 0, NULL}
};

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

As a result of we aren’t simply constructing an executable this time however a local Python extension module, we’ve got to construct the C code in a different way.

This sort of module have to be compiled in opposition to Python’s headers and appropriately linked to Python’s runtime so it behaves like a built-in Python module. 

To realize this, we create a Python module known as setup.py, which imports the setuptools library to facilitate this course of. It automates:

• Discovering the appropriate embrace paths for Python.h
• Passing the proper compiler and linker flags
• Producing a .pyd file with the appropriate naming conference on your Python model and platform

Doing this by hand with the cl compiler command can be tedious and error-prone, since you’d should specify all of these paths and flags manually.

Right here is the code we’d like.

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

We run it utilizing common Python on the command line, as proven right here.

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

#output
working build_ext
copying buildlib.win-amd64-cpython-312levext.cp312-win_amd64.pyd ->

Benchmarking the Python C extensions code

Now, right here is the Python code to name our C. Once more, I’ve omitted the 2 Python helper features which might be unchanged from the earlier examples.

# c-ext benchmark

import time, random, string
import numpy as np
import levext  # ensure levext.cp312-win_amd64.pyd is constructed & importable

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

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

if __name__ == "__main__":
    instances = [(2000, 2000), (4000, 4000)]
    print("Benchmark: Python vs NumPy vs C (C extension)n")
    for n, m in instances:
        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")

Right here is the output.

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

So this gave the quickest outcomes. The C model is exhibiting up as over 150 occasions sooner than pure Python within the second check case above. 

Not too shabby.

However what about NumPy?

A few of chances are you’ll be questioning why NumPy wasn’t used. Effectively, NumPy is improbable for vectorised numeric array operations, resembling dot merchandise, however not all algorithms map cleanly to vectorisation. Calculating Levenshtein distances is an inherently sequential course of, so NumPy doesn’t present a lot assist. In these instances, dropping into C by way of subprocess, ctypes, or a native C extension gives actual runtime speedups whereas nonetheless being callable from Python.

PS. I ran some extra assessments utilizing code that was amenable to utilizing NumPy, and it was no shock that NumPy was as quick because the known as C code. That’s to be anticipated as NumPy makes use of C underneath the hood and has a few years of growth and optimisation behind it.

Abstract

The article explores how Python builders can overcome efficiency bottlenecks in computationally intensive duties, resembling calculating the Levenshtein distance — a string similarity algorithm —by integrating C code into Python. Whereas libraries like NumPy speed up vectorised operations, sequential algorithms like Levenshtein usually stay impervious to NumPy’s optimisations.

To deal with this, I demonstrated three integration patterns, starting from easiest to most superior, that assist you to name quick C code from Python.

Subprocess. Compile the C code into an executable (e.g., with gcc or Visible Studio Construct Instruments) and run it from Python utilizing the subprocess module. That is straightforward to arrange and already reveals an enormous speedup in comparison with pure Python.

ctypes. Utilizing ctypes lets Python immediately load and name features from C shared libraries without having to write down a full Python extension module. This makes it a lot less complicated and sooner to combine performance-critical C code into Python, avoiding the overhead of working exterior processes whereas nonetheless holding your code principally in Python.

Python C Extensions. Write a full Python extension in C utilizing the CPython API (python.h). This requires extra setup however presents the quickest efficiency and smoothest integration, permitting you to name C features as in the event that they had been native Python features.

The benchmarks present that C implementations of the Levenshtein algorithm run over 100× sooner than pure Python. Whereas an exterior library resembling NumPy excels at vectorised numeric operations, it doesn’t considerably enhance efficiency for inherently sequential algorithms like Levenshtein, making C integration a more sensible choice in such instances.

When you hit efficiency limits in Python, offloading heavy computation to C can present large pace enhancements and is price contemplating. You can begin easy with subprocess, then transfer to ctypes or full C extensions for tighter integration and higher efficiency.

I’ve solely outlined three of the most well-liked methods to combine C code with Python, however there are just a few different strategies which I like to recommend you learn up on if this subject pursuits you.