# How to import C in Python In this article I am going to tell you how to implement a function in C, to compile it and import in Python. This can be helpful for boosting performance in some certain code sections in your Python application. Below I will describe and implement the algorithm of the [longest common subsequence](https://en.wikipedia.org/wiki/Longest_common_subsequence) in Python and C importing it into Python. And in the end I will benchmark these solutions. The repository: [https://github.com/fomalhaut88/how-to-import-c-in-python](https://github.com/fomalhaut88/how-to-import-c-in-python) ## The task ### Formulation We have two sequences of elements (numbers or symbols, for example). It is necessary to find the longest subsequence each element of which is represented in both of given ones keeping the order. Read more about it in [Wikipedia](https://en.wikipedia.org/wiki/Longest_common_subsequence). I thing most of programmers know about this task. Particularly, the algorithm is included in the standard utility [difflib](https://docs.python.org/3/library/difflib.html) that compares the contents of two files for differences. As a sequence let us consider symbols in a string, and instead of the subsequence itself we will calculate its length only. Deep and comprehensive solution is not our goal is this article, we just need an example of an algorithm that is not trivial on one hand, and is easy to implement on another one. ### Python implementation ```python # lcs_py.py def solve(s1, s2): n1 = len(s1) n2 = len(s2) row = [0 for _ in range(n1)] for i2 in range(n2): row_p = row[:] for i1 in range(n1): if s1[i1] == s2[i2]: row[i1] = 1 + (row_p[i1 - 1] if i1 > 0 else 0) else: row[i1] = max(row[i1 - 1] if i1 > 0 else 0, row_p[i1]) return row[-1] ``` ### Cythonization Cythonization is a way to boost the performance of a Python function. Shortly, the main idea is to modify your Python code in some places (in order to convert it into Cython code), then it is possible to compile it into a C-code and into DLL. After that this library is accessible as a Python module with the accustomed syntax. ```python # lcs_pyx.pyx def solve(str s1, str s2): n1 = len(s1) n2 = len(s2) row = [0 for _ in range(n1)] for i2 in range(n2): row_p = row[:] for i1 in range(n1): if s1[i1] == s2[i2]: row[i1] = 1 + (row_p[i1 - 1] if i1 > 0 else 0) else: row[i1] = max(row[i1 - 1] if i1 > 0 else 0, row_p[i1]) return row[-1] ``` Before importing it we need an auxiliary file to compile: ```python # setup_pyx.py from distutils.core import setup from Cython.Build import cythonize setup( ext_modules=cythonize("lcs_pyx.pyx") ) ``` You also need to have `Cython` installed. If not, use this command: ``` $ python -m pip install Cython ``` Compilation command: ``` $ python setup_pyx.py build_ext --inplace ``` After that the compiled files will appear called `build`, `lcs_pyx.c` and `lcs_pyx.cpython-312-x86_64-linux-gnu.so` ### C implementation Same algorithm in C would look like: ```c /* lcs_c.h */ int solve(const char* s1, const char* s2); ``` ```c /* lcs_c.c */ #include <string.h> #include <stdlib.h> #include "lcs_c.h" #define max(x, y) (((x) >= (y)) ? x : y) int solve(const char* s1, const char* s2) { int n1 = strlen(s1); int n2 = strlen(s2); int* row = (int*)calloc(sizeof(int), n1); int* row_p = (int*)calloc(sizeof(int), n1); memset(row, 0, sizeof(int) * n1); for (int i2 = 0; i2 < n2; i2++) { memcpy(row_p, row, sizeof(int) * n1); for (int i1 = 0; i1 < n1; i1++) { if (s1[i1] == s2[i2]) { row[i1] = 1 + ((i1 > 0) ? row_p[i1 - 1] : 0); } else { row[i1] = max( (i1 > 0) ? row[i1 - 1] : 0, row_p[i1] ); } } } int result = row[n1 - 1]; free(row); free(row_p); return result; } ``` Compiling it: ``` $ gcc -fPIC lcs_c.c -shared -O3 -o lcs_c.so ``` ## Benchmark ```python # bench.py import os import ctypes from time import time from random import choice import lcs_py import lcs_pyx so_path = os.path.join(os.path.dirname(__file__), 'lcs_c.so') lcs_c = ctypes.CDLL(so_path) lcs_c_solve = lambda s1, s2: lcs_c.solve( ctypes.c_char_p(s1.encode('utf-8')), ctypes.c_char_p(s2.encode('utf-8')) ) LENGTH = 5000 def gen_random_word(length): return ''.join(choice('0123456789abcdef') for _ in range(length)) def test(func, word1, word2): tb = time() res = func(word1, word2) te = time() print("time: {:.3f} secs, result: {}".format(te - tb, res)) word1 = gen_random_word(LENGTH) word2 = gen_random_word(LENGTH) test(lcs_py.solve, word1, word2) test(lcs_pyx.solve, word1, word2) test(lcs_c_solve, word1, word2) ``` In the script I generate words with length `LENGTH = 5000` consisting of random digits and letters from `a` to `f`. After that I measure the execution time. The result impresses. On my machine it is following: ``` $ python bench.py time: 3.899 secs, result: 1954 time: 2.174 secs, result: 1954 time: 0.024 secs, result: 1954 ``` As we see, pure Python is about 150 times slower than C. Cythonization did help but it is about 2 times faster only. ## Conclusion I think the conclusion is obvious. Each approach is acceptable depending on the task, time for developing, performance requirements and other factors. For example, if performance is not the goal, Python seems to be a good choice. Otherwise you should write in C. Cython is an intermediate option, it is especially convenient if you already have a code in Python and it won't take much time to make the necessary pyx-file adding the types and other little modifications.