Damerau-Levenshtein distance performance improvements

Question

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.

Answer 1

Please write this

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.