Make Python As much as 150× Quicker with C

Scaling Characteristic Engineering Pipelines with Feast and Ray

Optimizing Token Era in PyTorch Decoder Fashions

, eventually, you’re going to hit a block relating to your code execution pace. 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.

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 after I needed 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 in school many years in the past however hadn’t utilized in anger for about 15 years. That’s the place issues received 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 actual fact, 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, equivalent to spell checkers and optical character recognition methods.

To provide 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”.

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

So, the LD on this case is three.

Calculate the LD between the phrases “very good” and “tremendous”.

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 operating this on MS Home windows, I wanted a method of compiling C packages. The simplest method 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 primary Visible Studio downloads web page. On the second display, you’ll see a search field. Sort “Construct Instruments” into the search subject 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, while you click on on the little plus button to open a brand new terminal, you must see an choice to open a “Developer command immediate for VS 2022”.

Most of my Python code might be operating on a Jupyter Pocket book, so you must arrange a brand new growth setting and set up Jupyter. Do this now if you wish to observe alongside. I’m utilizing the UV software 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 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 
#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 major(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 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, kind 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 a 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 = record(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 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)
    finest = float("inf"); out_best = None
    for _ in vary(repeat):
        t0 = time.perf_counter(); out = fn(*args); dt = time.perf_counter() - t0
        if dt < finest: finest, out_best = dt, out
    return out_best, finest

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 reasonably important 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 customary library. It allows you to load and name capabilities from shared libraries written in C (DLLs on Home windows, .so information on Linux, .dylib on macOS) straight from Python, without having to write down an entire extension module in C.

First, right here is our C model of the LD algorithm, utilising ctypes. It’s nearly equivalent to our subprocess C operate, 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
*/

#embrace 
#embrace 

/* beneath line consists of 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) slightly 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)
    finest = float("inf"); out_best = None
    for _ in vary(repeat):
        t0 = time.perf_counter(); out = fn(*args); dt = time.perf_counter() - t0
        if dt < finest: finest, out_best = dt, out
    return out_best, finest

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

Now we 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 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 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 outcome as a Python integer (PyLong_FromLong). The Strategies desk registers this operate 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.

This sort of module should 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 suitable embrace paths for Python.h
Passing the proper compiler and linker flags
Producing a .pyd file with the suitable 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 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
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 might be unchanged from the earlier examples.

# c-ext benchmark

import time, random, string
import numpy as np
import levext  # be sure 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)
    finest = float("inf"); out_best = None
    for _ in vary(repeat):
        t0 = time.perf_counter(); out = fn(*args); dt = time.perf_counter() - t0
        if dt < finest: finest, out_best = dt, out
    return out_best, finest

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 displaying up as over 150 occasions quicker than pure Python within the second check case above.

Not too shabby.

However what about NumPy?

A few of you could be questioning why NumPy wasn’t used. Nicely, NumPy is improbable 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 instances, dropping into C through subprocess, ctypes, or a native C extension supplies actual runtime speedups whereas nonetheless being callable from Python.

PS. I ran some further 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 help you 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 straight load and name capabilities from C shared libraries without having 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 retaining 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 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 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 a couple of different strategies which I like to recommend you learn up on if this subject pursuits you.