# Damerau-Levenshtein distance performance improvements

I am working on a Python C-extension to calculate Damerau-Levenshtein distance. I am not really familiar with C at all--I just know that it generally has better performance. However, I am not sure how to bring about these performance gains. I translated a Python version from https://github.com/jamesturk/jellyfish/blob/main/jellyfish/_jellyfish.py basically 1:1, and the speed is fine, but I suspect I am making performance concessions an experienced C programmer would not. I would be grateful if anyone could point out anything inefficient I am doing! Also, I am just worried dealing with ASCII characters.

#define PY_SSIZE_T_CLEAN
#include <Python.h>
#include <string.h>

// This is a 1:1 translation of https://github.com/jamesturk/jellyfish/blob/main/jellyfish/_jellyfish.py

int min_int(int arr[], size_t size)
{
// simply loop over an array of integers to find the min
int min = arr[0];
for (size_t i = 1; i < size; i++)
{
int val = arr[i];
if (val < min)
{
min = val;
}
}

return min;
}

static PyObject* distance(PyObject *self, PyObject *args)
{
const char* s1;
const char* s2;

if ( !PyArg_ParseTuple(args, "ss", &s1, &s2) ) // s means string argument
{
return NULL;
}

int len1 = strlen(s1);
int len2 = strlen(s2);
int infinite = len1 + len2;

int nrows = len1 + 2;
int ncols = len2 + 2;

// initialize distance matrix
int score[nrows][ncols];
for (size_t i = 0; i < nrows; i++)
{
for (size_t j = 0; j < ncols; j++)
{
score[i][j] = 0;
}
}

score[0][0] = infinite;
for (size_t i = 0; i <= len1; i++)
{
score[i + 1][0] = infinite;
score[i + 1][1] = i;
}
for (size_t i = 0; i <= len2; i++)
{
score[0][i + 1] = infinite;
score[1][i + 1] = i;
}

// Since we are only dealing with ascii characters, this is equivalent to the dictionary
// in the Python implementation. Instead of accessing using the character as the index, we
// can cast the character to its integer version, and access by index.
int da[256] = { 0 };

for (size_t i = 1; i <= len1; i++)
{
int db = 0;
for (size_t j = 1; j <= len2; j++)
{
const char s2_char = s2[j - 1];
int i1 = da[(int)s2_char];
int j1 = db;
int cost = 1;
if (s1[i - 1] == s2_char)
{
cost = 0;
db = j;
}

int arr[4] = {
score[i][j] + cost,
score[i + 1][j] + 1,
score[i][j + 1] + 1,
score[i1][j1] + (i - i1 - 1) + 1 + (j - j1 - 1)
};
score[i + 1][j + 1] = min_int(arr, 4);
}
const char s1_char = s1[i - 1];
da[(int)s1_char] = i;
}

long distance = score[len1 + 1][len2 + 1];

return PyLong_FromLong(distance);
}


The compiler flags are -Wsign-compare -Wunreachable-code -fno-common -dynamic -DNDEBUG -g -fwrapv -O3 -Wall -isysroot /Library/Developer/CommandLineTools/SDKs/MacOSX12.sdk

It's available to view and play with on Godbolt. I am compiling on MacOS x86_64-apple-darwin21.6.0, clang version 14.

• Do you optimize the code before linking it with the python code? Mar 16 at 15:07
• Sorry, I am not sure I understand your question. This is my current, full C code. In terms of compilation, that is handled by setuptools (a Python packaging library), which to my understanding uses the same compiler flags that version of Python is compiled with. I think it uses -02? Mar 16 at 15:11
• The reason I asked is because the loops you have written are slow, but they would be fixed by the -O2 flag. Mar 16 at 15:14
• I see, I will do some more research on the compiler flags setuptools uses and edit my question. Thanks! Mar 16 at 15:53
• A godbolt.org link for the target you're testing would be helpful.
– J_H
Mar 16 at 16:29

int min_int(int arr[], size_t size)
{
assert(size > 0);


That will avoid UB, and give the caller a nice diagnostic if he messes up his contract. Or if asserts might be disabled, add an explicit if.

Also, it would be useful to write down why this code doesn't target C++20 or similar which offers std::min. You voice concerns about speed of your code. Using code that others wrote and tuned is one of the best ways to address such concerns.

In distance, kudos on the very helpful "ss" comment, thank you.

I am sad the function isn't named damerau_levenshtein_distance, for better traceability to the python source. Establishing traceability is important whenever one artifact is supposed to correspond 1:1 to another artifact. Kudos on nicely preserving all the variable names.

The corresponding python source raises a nicely diagnostic TypeError if caller messed up. Here, maybe a NULL does something similar? That is, we're not returning a None object to caller, are we? Oh, I see, there's an exception teed up and ready to go when it returns false, good.

Zeroing out the score matrix works fine. If you benchmark you might observe memset doing it quicker. Or, ask that it be zeroed at allocation time. (Side note: the python code uses integer objects, implying a lot of object pointer chasing. There's an opportunity for it to use an array instead.)

            int arr[4] = {


I understand why you create a temporary array, going for a literal rendering of the min argument in the python code. But it feels more natural here to just compute ordinary min(), more than once if necessary. (Or #define min4 if you feel it improves legibility.)

        da[(int)s1_char] = i;


I guess we should prefer an unsigned ssize_t cast, right?

And, I know you said there's an "ASCII" assumption (7 bit?), but the const char s1_char declaration should probably be unsigned. What I'm shooting for is to help the compiler easily prove it has a valid da index.

The score entries are positive, with a signed representation, and that seems OK. There is an opportunity to make each entry consume fewer bits.

The "not Unicode" assumption could be written down more clearly. Also, for a pair of strings with fewer than 256 distinct codepoints, a preprocessor could map the glyphs to small values that work directly with the current (unmodified) function.

Here's a design consideration.

I assume a python app will call this function repeatedly in a loop.

Does it make sense to offer a bigger API than what the original python source offers? That is, would we bench quicker if an extra function let caller pass in a container of words to compute distance on? The idea being that C iterates through them faster than a python for loop would.

• Performance question for everyone: Does it make a difference where we allocate score in the C source? Like, maybe we can get improved cache line alignment? For repeated invocations, does it make sense to cache previous allocation and only grow it if current word lengths exceed the cached size? (Tiny consideration: the app logic doesn't need a zeroed allocation since it overwrites each element anyway.)
– J_H
Mar 16 at 17:19
• From what I can see the score is allocated on stack. That the best option performance wise. Your compiler should optimize for cache line alignment for objects stored on the stack. But I am not sure that the code even compiles. You can't have a dynamically sized array on cache Mar 16 at 17:37
• I tried searching for a min() function for C, but couldn't find one. From what I understand std::min() is from C++, is this incorrect? Thank you for the detailed answer! Mar 16 at 18:44
• Yes, that is correct. I suppose I usually see #define min(a, b) ((a) < (b) ? (a) : (b)), or some such foolishness. Downside with that is poor branch prediction. There are bit-twiddling tricks to compute min with no branches, so we keep the instruction pipeline full. Which is another reason to rely on code that others went to the trouble of optimizing, rather than tackling it yourself. Sometimes a compiler will choose a CMOV instruction FTW.
– J_H
Mar 16 at 19:15
• @stressed I believe the upcoming C2x has min()/max() functions. Mar 17 at 6:00