Accelerating Our Alignment Module: From Python to C++

Edit Distance - An Overview

Edit Distance is a well-known way to measure how similar two strings are. Also referred to as the “Levenshtein Distance,” it calculates the minimum number of edit operations — insertions, deletions, or substitutions — needed to transform one string into another. Fewer edits indicate a greater degree of similarity.

To compute the edit distance, we often use a dynamic programming approach: we build a matrix where each cell captures the cost (in terms of edits) to transform the first i characters of one string into the first j characters of the other. The matrix is filled iteratively, with each cell’s value derived from the neighbouring cells, reflecting whether the last characters match or require an edit operation. The value in the bottom-right cell reveals the total edit distance.

For those familiar with computer science notation, the time complexity of this algorithm is O(m×n) — in other words, it grows proportionally to the product of the number of characters in the two strings. You can learn more about the algorithm in this blog post on edit distance.

Edit Distance Matrix for strings, “sitting” and “kitten”. Source: Ethan Nam

Challenges with Edit Distance

For our oral reading fluency tool, introduced in a previous blog post, we rely heavily on this algorithm to align the reading passage with the transcript of what the student actually spoke. The matrix generated during alignment can be used to compile a report for the child, highlighting which words were read correctly, which were misread, any omitted words, and any extra words the student might have inserted. Because passages and transcripts can be as long as 1000 characters each, the algorithm’s computational cost can quickly add up and introduce significant latency when deployed in scenarios that must handle a few hundred assessments per second on constrained compute resources.

Get Ayush Deva’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

To address this bottleneck, we experimented with implementing a dedicated C++ module for alignment that seamlessly interacts with the rest of our Python application. We used Pybind, a lightweight library that generates Python bindings for C++ code, enabling Python to call C++ functions directly (and vice versa) with minimal overhead.

Comparing Latency - Python v/s C++

Below, we present our findings on latency across Python and C++ implementations. Each number reflects the time to compute the distance for a reference and transcript pair of about 1000 characters each when repeated 10 times in sequence. We evaluated four distinct scenarios:

1. Pure Python — A baseline implementation in raw Python.
2. Pure C++ — A standalone C++ implementation (executed outside of Python).
3. C++ via Pybind (distance retrieval) — Python calls a C++ function to compute the distance, returning just the final value.
4. C++ via Pybind (matrix retrieval) — Python calls a C++ function to build and return the entire distance matrix, then extracts the distance.

Takeaways

1. C++ for Performance-Critical Tasks
   Offloading intensive code to C++ can provide a massive speed boost — up to 50x in our case.
2. Data Transfer Overhead
   The latency also depends on the size of the data being transferred from the C++ module to Python. We saw about an 8x difference when returning a single integer versus returning a 1000×1000 matrix.