andygrove opened a new pull request, #23543:
URL: https://github.com/apache/datafusion/pull/23543
> This PR was created by an LLM as a draft PR. I will mark it as ready for
review after human review.
## Which issue does this PR close?
N/A — autonomous exploratory PR.
## Rationale for this change
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.
## 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?
Correctness: unit tests + seeded differential fuzz (bit-identical Arrow
output vs `main`).
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?
<!--
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.
-->
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
