Make Python Up to 150× Faster with C

, eventually, you’re going to hit a block in relation to your code execution velocity. When you’ve ever written a computationally heavy algorithm in Python, equivalent 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 drawback once I wished to benchmark a selected 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 in school many years in the past however hadn’t utilized in anger for about 15 years. That’s the place issues bought attention-grabbing.

I first needed to reply the query, “Are you able to name C from Python?”. After some analysis, it rapidly turned clear that the reply was certainly sure. In reality, 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 most typical 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 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 numerous instruments, equivalent to spell checkers and optical character recognition techniques.

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 “very good” and “tremendous”.

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

The LD on this case is just 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. 

Conditions

As I used to be operating this on MS Home windows, I wanted a approach of compiling C packages. The simplest approach 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. Sort “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, 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 will probably be operating on a Jupyter Pocket book, so you need to arrange a brand new growth atmosphere and set up Jupyter. Do this now if you wish to comply with alongside. I’m utilizing the UV instrument for this half, however be happy to make use of whichever technique you’re most snug 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’d like barely totally 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

#embody 
#embody 
#embody 

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 value = (ca == b[j - 1]) ? 0 : 1;
            int del = prev[j] + 1, ins = curr[j - 1] + 1, sub = prev[j - 1] + value;
            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 primary(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, kind within the following code, which will probably be widespread 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):
            value = 0 if ca == cb else 1
            curr[j] = min(prev[j] + 1, curr[j-1] + 1, prev[j-1] + value)
        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 towards a 2000 and a 4000 set of random phrases thrice 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 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 reasonably 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 customary library. It enables you to load and name capabilities from shared libraries written in C (DLLs on Home windows, .so recordsdata on Linux, .dylib on macOS) immediately from Python, with no need 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 equivalent to our subprocess C perform, with the addition of a line that permits us to make use of Python to name the DLL after it has been compiled.

/* 
 * lev.c
*/

#embody 
#embody 

/* under line contains this perform 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 value = (ca == b[j - 1]) ? 0 : 1;
            int del = prev[j] + 1;
            int ins = curr[j - 1] + 1;
            int sub = prev[j - 1] + value;
            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 equivalent 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 comparable 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 consequence 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 gap, handles reminiscence errors, and returns the consequence as a Python integer (PyLong_FromLong). The Strategies desk registers this perform beneath the identify “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.

#embody 
#embody 
#embody 

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 value = (ca == b[j - 1]) ? 0 : 1;
            int del = prev[j] + 1, ins = curr[j - 1] + 1, sub = prev[j - 1] + value;
            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 otherwise.

This kind of module have to be compiled towards 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 embody paths for Python.h
• Passing the right 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 need to specify all of these paths and flags manually.

Right here is the code we’d like.

from setuptools import setup, Extension
setup(
    identify="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
operating 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 it’s possible you’ll be questioning why NumPy wasn’t used. Properly, NumPy is unbelievable for vectorised numeric array operations, equivalent 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 offers actual runtime speedups whereas nonetheless being callable from Python.

PS. I ran some extra exams 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, equivalent 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 usually 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 straightforward to arrange and already exhibits an enormous speedup in comparison with pure Python.

ctypes. Utilizing ctypes lets Python immediately load and name capabilities from C shared libraries with no need to write down a full Python extension module. This makes it a lot easier and quicker to combine performance-critical C code into Python, avoiding the overhead of operating exterior processes whereas nonetheless maintaining 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 gives the quickest efficiency and smoothest integration, permitting you to name C capabilities as in the event that they have 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 equivalent to NumPy excels at vectorised numeric operations, it doesn’t considerably enhance efficiency for inherently sequential algorithms like Levenshtein, making C integration a better option in such circumstances.

When you hit efficiency limits in Python, offloading heavy computation to C can present huge velocity 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 a couple of different strategies which I like to recommend you learn up on if this subject pursuits you.