You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by gi...@apache.org on 2026/09/16 20:54:46 UTC
(datafusion) 01/01: perf: optimize `levenshtein` (#23543)
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-23543-140c7c5a4cbde4409a4d29a4c04032d618c3b8ce
in repository https://gitbox.apache.org/repos/asf/datafusion.git
commit 8b802acd11457514554e960452a9ff801b493c66
Author: Andy Grove <ag...@apache.org>
AuthorDate: Wed Sep 16 20:54:19 2026 +0000
perf: optimize `levenshtein` (#23543)
## Which issue does this PR close?
N/A
## Rationale for this change
Optimize existing expression.
## What changes are included in this PR?
Added Myers' bit-parallel Levenshtein fast path for ASCII inputs whose
shorter side fits in a 64-bit word, replacing the per-cell
character-wise DP with a few bitwise ops per text character.
## Are these changes tested?
Existing tests + new unit tests.
Benchmark (criterion):
- levenshtein_string [size=1024, str_len=32]: 83.81% faster (base
662708ns -> cand 107290ns)
- levenshtein_string [size=1024, str_len=8]: 54.904% faster (base
58165ns -> cand 26230ns)
- levenshtein_string [size=4096, str_len=32]: 83.79% faster (base
2640918ns -> cand 428103ns)
- levenshtein_string [size=4096, str_len=8]: 54.274% faster (base
227761ns -> cand 104146ns)
Full criterion output:
```text
levenshtein size=1024/levenshtein_string [size=1024, str_len=8]
time: [26.188 µs 26.230 µs 26.298 µs]
change: [−55.035% −54.904% −54.755%] (p = 0.00 < 0.05)
Performance has improved.
Found 1 outliers among 10 measurements (10.00%)
1 (10.00%) high severe
levenshtein size=1024/levenshtein_string [size=1024, str_len=32]
time: [107.24 µs 107.29 µs 107.35 µs]
change: [−83.837% −83.810% −83.768%] (p = 0.00 < 0.05)
Performance has improved.
Found 2 outliers among 10 measurements (20.00%)
2 (20.00%) high mild
levenshtein size=4096/levenshtein_string [size=4096, str_len=8]
time: [104.07 µs 104.15 µs 104.24 µs]
change: [−54.330% −54.274% −54.218%] (p = 0.00 < 0.05)
Performance has improved.
Found 1 outliers among 10 measurements (10.00%)
1 (10.00%) high mild
levenshtein size=4096/levenshtein_string [size=4096, str_len=32]
time: [427.90 µs 428.10 µs 428.33 µs]
change: [−83.799% −83.790% −83.780%] (p = 0.00 < 0.05)
Performance has improved.
Found 2 outliers among 10 measurements (20.00%)
2 (20.00%) high mild
```
## Are there any user-facing changes?
No
<!--
If there are user-facing changes then we may require documentation to be
updated before approving the PR.
-->
<!--
If there are any breaking changes to public APIs, please add the `api
change` label.
-->
---
datafusion/functions/src/string/levenshtein.rs | 196 +++++++++++++++++++++++--
1 file changed, 181 insertions(+), 15 deletions(-)
diff --git a/datafusion/functions/src/string/levenshtein.rs b/datafusion/functions/src/string/levenshtein.rs
index 38fa8fa878..859d2cead8 100644
--- a/datafusion/functions/src/string/levenshtein.rs
+++ b/datafusion/functions/src/string/levenshtein.rs
@@ -121,6 +121,113 @@ impl ScalarUDFImpl for LevenshteinFunc {
}
}
+/// Longest pattern, in bytes, that the bit-parallel path can encode in a single
+/// machine word. That path is ASCII-only, so this is a character count too.
+const MYERS_MAX_PATTERN_LEN: usize = u64::BITS as usize;
+
+/// Pattern length up to which resetting the match table character by character
+/// beats zeroing the whole of it. Above this, a vectorized fill is cheaper than
+/// the scattered stores.
+const MYERS_SPARSE_RESET_LEN: usize = 32;
+
+/// Scratch space reused across rows so that no single row has to allocate.
+struct LevenshteinScratch {
+ /// Dynamic-programming row for the character-wise fallback.
+ cache: Vec<usize>,
+ /// Bitmask of the positions at which each ASCII character occurs in the
+ /// Myers pattern. Characters absent from the pattern match nowhere, hence 0.
+ /// Left all-zero between rows so that each row can fill it in directly.
+ peq: [u64; 128],
+}
+
+impl LevenshteinScratch {
+ fn new() -> Self {
+ Self {
+ cache: Vec::new(),
+ peq: [0; 128],
+ }
+ }
+}
+
+/// Levenshtein distance between `a` and `b`.
+///
+/// Uses Myers' bit-parallel algorithm when both inputs are ASCII and the shorter
+/// one fits in a single 64-bit word, which computes a whole column of the
+/// dynamic-programming matrix per text character instead of one cell at a time.
+/// Longer or non-ASCII inputs fall back to the character-wise implementation and
+/// stay quadratic.
+#[inline]
+fn levenshtein_distance(a: &str, b: &str, scratch: &mut LevenshteinScratch) -> usize {
+ // The distance is symmetric, so the shorter side can always be the pattern.
+ let (pattern, text) = if a.len() <= b.len() { (a, b) } else { (b, a) };
+
+ if pattern.len() <= MYERS_MAX_PATTERN_LEN && pattern.is_ascii() && text.is_ascii() {
+ myers_distance(pattern.as_bytes(), text.as_bytes(), &mut scratch.peq)
+ } else {
+ // The fallback sizes its buffer from the second argument, so give it the
+ // shorter side.
+ datafusion_strsim::levenshtein_with_buffer(text, pattern, &mut scratch.cache)
+ }
+}
+
+/// Myers' bit-parallel Levenshtein distance. Both inputs must be ASCII and
+/// `pattern` must be at most [`MYERS_MAX_PATTERN_LEN`] bytes long.
+///
+/// `vp`/`vn` hold the vertical deltas (+1 / -1) of the current matrix column as
+/// bitmasks, one bit per pattern character, and `score` tracks the value of that
+/// column's last cell.
+///
+/// `peq` must be all-zero on entry and is left all-zero on return.
+fn myers_distance(pattern: &[u8], text: &[u8], peq: &mut [u64; 128]) -> usize {
+ debug_assert!(pattern.is_ascii() && text.is_ascii());
+ debug_assert!(pattern.len() <= MYERS_MAX_PATTERN_LEN);
+ debug_assert!(peq.iter().all(|&mask| mask == 0));
+
+ let m = pattern.len();
+ if m == 0 {
+ return text.len();
+ }
+
+ for (i, &c) in pattern.iter().enumerate() {
+ peq[c as usize] |= 1 << i;
+ }
+
+ let last_bit = 1u64 << (m - 1);
+ let mut vp = u64::MAX;
+ let mut vn = 0u64;
+ let mut score = m;
+
+ for &c in text {
+ let eq = peq[c as usize];
+ let x = eq | vn;
+ let d0 = (vp.wrapping_add(x & vp) ^ vp) | x;
+ let hn = vp & d0;
+ let hp = vn | !(vp | d0);
+
+ if hp & last_bit != 0 {
+ score += 1;
+ } else if hn & last_bit != 0 {
+ score -= 1;
+ }
+
+ let hp = (hp << 1) | 1;
+ let hn = hn << 1;
+ vp = hn | !(d0 | hp);
+ vn = hp & d0;
+ }
+
+ // Restore the all-zero invariant for the next row.
+ if m <= MYERS_SPARSE_RESET_LEN {
+ for &c in pattern {
+ peq[c as usize] = 0;
+ }
+ } else {
+ peq.fill(0);
+ }
+
+ score
+}
+
///Returns the Levenshtein distance between the two given strings.
/// LEVENSHTEIN('kitten', 'sitting') = 3
fn levenshtein<T: OffsetSizeTrait>(args: &[ArrayRef]) -> Result<ArrayRef> {
@@ -147,17 +254,16 @@ fn levenshtein<T: OffsetSizeTrait>(args: &[ArrayRef]) -> Result<ArrayRef> {
let str1_array = as_string_view_array(&str1)?;
let str2_array = as_string_view_array(&str2)?;
- // Reusable buffer to avoid allocating for each row
- let mut cache = Vec::new();
+ // Reusable scratch space to avoid allocating for each row
+ let mut scratch = LevenshteinScratch::new();
let result = str1_array
.iter()
.zip(str2_array.iter())
.map(|(string1, string2)| match (string1, string2) {
(Some(string1), Some(string2)) => {
- Some(datafusion_strsim::levenshtein_with_buffer(
- string1, string2, &mut cache,
- ) as i32)
+ Some(levenshtein_distance(string1, string2, &mut scratch)
+ as i32)
}
_ => None,
})
@@ -168,17 +274,16 @@ fn levenshtein<T: OffsetSizeTrait>(args: &[ArrayRef]) -> Result<ArrayRef> {
let str1_array = as_generic_string_array::<T>(&str1)?;
let str2_array = as_generic_string_array::<T>(&str2)?;
- // Reusable buffer to avoid allocating for each row
- let mut cache = Vec::new();
+ // Reusable scratch space to avoid allocating for each row
+ let mut scratch = LevenshteinScratch::new();
let result = str1_array
.iter()
.zip(str2_array.iter())
.map(|(string1, string2)| match (string1, string2) {
(Some(string1), Some(string2)) => {
- Some(datafusion_strsim::levenshtein_with_buffer(
- string1, string2, &mut cache,
- ) as i32)
+ Some(levenshtein_distance(string1, string2, &mut scratch)
+ as i32)
}
_ => None,
})
@@ -189,17 +294,16 @@ fn levenshtein<T: OffsetSizeTrait>(args: &[ArrayRef]) -> Result<ArrayRef> {
let str1_array = as_generic_string_array::<T>(&str1)?;
let str2_array = as_generic_string_array::<T>(&str2)?;
- // Reusable buffer to avoid allocating for each row
- let mut cache = Vec::new();
+ // Reusable scratch space to avoid allocating for each row
+ let mut scratch = LevenshteinScratch::new();
let result = str1_array
.iter()
.zip(str2_array.iter())
.map(|(string1, string2)| match (string1, string2) {
(Some(string1), Some(string2)) => {
- Some(datafusion_strsim::levenshtein_with_buffer(
- string1, string2, &mut cache,
- ) as i64)
+ Some(levenshtein_distance(string1, string2, &mut scratch)
+ as i64)
}
_ => None,
})
@@ -241,4 +345,66 @@ mod tests {
Ok(())
}
+
+ /// The bit-parallel path must agree with the reference implementation for
+ /// every input it accepts, including empty strings and pattern lengths at
+ /// the 64-character word boundary.
+ #[test]
+ fn myers_matches_reference() {
+ let alphabets: [&[u8]; 3] = [b"ab", b"abcdefg", b"kitensg -0"];
+ let mut state = 0x2545_f491_4f6c_dd1du64;
+ let mut next = move || {
+ state ^= state << 13;
+ state ^= state >> 7;
+ state ^= state << 17;
+ state
+ };
+ let mut scratch = LevenshteinScratch::new();
+
+ for alphabet in alphabets {
+ for len1 in [0usize, 1, 2, 5, 16, 63, 64, 65, 100] {
+ for len2 in [0usize, 1, 3, 8, 32, 64, 65, 120] {
+ for _ in 0..8 {
+ let make = |n: usize, next: &mut dyn FnMut() -> u64| {
+ (0..n)
+ .map(|_| {
+ alphabet[(next() % alphabet.len() as u64) as usize]
+ as char
+ })
+ .collect::<String>()
+ };
+ let a = make(len1, &mut next);
+ let b = make(len2, &mut next);
+ assert_eq!(
+ levenshtein_distance(&a, &b, &mut scratch),
+ datafusion_strsim::levenshtein(&a, &b),
+ "levenshtein({a:?}, {b:?})"
+ );
+ }
+ }
+ }
+ }
+ }
+
+ #[test]
+ fn myers_known_distances() {
+ let mut scratch = LevenshteinScratch::new();
+ for (a, b, expected) in [
+ ("kitten", "sitting", 3),
+ ("", "", 0),
+ ("", "abc", 3),
+ ("abc", "", 3),
+ ("abc", "abc", 0),
+ ("flaw", "lawn", 2),
+ // Non-ASCII falls back to the character-wise implementation.
+ ("café", "cafe", 1),
+ ("😀abc", "abc", 1),
+ ] {
+ assert_eq!(
+ levenshtein_distance(a, b, &mut scratch),
+ expected,
+ "{a} {b}"
+ );
+ }
+ }
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org