Make Python As much as 150× Quicker with C

, in the end, you’re going to hit a block with regards to your code execution velocity. Should you’ve ever written a computationally heavy algorithm in Python, comparable to string distance, matrix math, or cryptographic hashing, you’ll know what I imply.

Positive, 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 downside after I wished to benchmark a specific algorithm, which determines the variety of edits required to rework one string into one other.

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

I first needed to reply the query, “Are you able to name C from Python?”. After some analysis, it shortly grew to become clear that the reply was certainly sure. The truth is, 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 advanced, we’ll take a look at utilizing,

• a subprocess
• ctypes
• Python C extensions

The algorithm that we’ll be testing with 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 functions in varied instruments, comparable to spell checkers and optical character recognition techniques.

To present you a clearer image of what we’re speaking about, listed below 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 “very good” and “tremendous”.

1. very good → 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 applications. The best manner I discovered to do that was to obtain the Visible Studio Construct instruments for 2022. This lets you compile C applications on the command line.

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

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

Most of my Python code might be working on a Jupyter Pocket book, so you need to arrange a brand new growth atmosphere and set up Jupyter. Try this now if you wish to observe alongside. I’m utilizing the UV instrument for this half, however be happy to make use of whichever technique 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 strategy 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 
#embrace 
#embrace 

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  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 sort the next to make sure we’re optimising the compilation for 64-bit structure.

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

Subsequent, we are able to compile our C code utilizing this command.

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

That can create an executable file.

Benchmarking the subprocessing code

In a Jupyter pocket book, sort within the following code, which might be frequent to all our benchmarking. It generates random lowercase strings of size N and calculates the variety of edits required to rework 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.selection(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 = listing(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 technique. We run every technique in opposition to a 2000 and a 4000 set of random phrases 3 times and take the quickest of these instances.

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__":
    circumstances = [(2000,2000),(4000, 4000)]
    print("Benchmark: Pythonvs C (subprocess)n")
    for n, m in circumstances:
        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 here 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 international perform interface (FFI) library constructed proper into Python’s normal library. It enables you to load and name capabilities from shared libraries written in C (DLLs on Home windows, .so information on Linux, .dylib on macOS) instantly from Python, while not having to put in writing 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 perform, 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 
#embrace 

/* under line contains this perform within the 
 * DLL's export desk so different applications 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) relatively 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 capabilities on this code snippet, as they’re similar to these within the earlier instance. Sort 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__":
    circumstances = [(2000,2000),(4000, 4000)]
    print("Benchmark: Python vs NumPy vs C (ctypes)n")
    for n, m in circumstances:
        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 have now 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 fundamental 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 outcome as a Python integer.

The perform levext_lev acts as a wrapper. It parses two string arguments from Python (PyArg_ParseTuple), calls the C perform lev_impl to compute the space, handles reminiscence errors, and returns the outcome as a Python integer (PyLong_FromLong). The Strategies desk registers this perform beneath 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 
#embrace 
#embrace 

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 have now to construct the C code in a different way.

Any such 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 attain this, we create a Python module known as setup.py, which imports the setuptools library to facilitate this course of. It automates:

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

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

Right here is the code we want.

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 capabilities which can be unchanged from the earlier examples.

# c-ext benchmark

import time, random, string
import numpy as np
import levext  # be sure that 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__":
    circumstances = [(2000, 2000), (4000, 4000)]
    print("Benchmark: Python vs NumPy vs C (C extension)n")
    for n, m in circumstances:
        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 displaying up as over 150 instances quicker than pure Python within the second check case above. 

Not too shabby.

However what about NumPy?

A few of you might be questioning why NumPy wasn’t used. Nicely, NumPy is incredible for vectorised numeric array operations, comparable to 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 circumstances, dropping into C through subprocess, ctypes, or a native C extension gives actual runtime speedups whereas nonetheless being callable from Python.

PS. I ran some further checks 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 beneath 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, comparable to 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 typically stay impervious to NumPy’s optimisations.

To handle this, I demonstrated three integration patterns, starting from easiest to most superior, that permit 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 simple to arrange and already exhibits an enormous speedup in comparison with pure Python.

ctypes. Utilizing ctypes lets Python instantly load and name capabilities from C shared libraries while not having to put in writing a full Python extension module. This makes it a lot less complicated and quicker to combine performance-critical C code into Python, avoiding the overhead of working exterior processes whereas nonetheless holding your code largely in Python.

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

The benchmarks present that C implementations of the Levenshtein algorithm run over 100× quicker than pure Python. Whereas an exterior library comparable to 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 circumstances.

Should you hit efficiency limits in Python, offloading heavy computation to C can present huge velocity enhancements and is value 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 preferred methods to combine C code with Python, however there are a couple of different strategies which I like to recommend you learn up on if this matter pursuits you.