david-mollitor-db opened a new pull request, #58672: URL: https://github.com/apache/spark/pull/58672
### What changes were proposed in this pull request? `UTF8String` stores UTF-8, a variable-width encoding, so locating the i-th code point is O(N): the string must be scanned from the start, advancing past each code point by its byte width (`numBytesForFirstByte` of the leading byte). There is no O(1) random access to the i-th character the way there is for a fixed-width array. To avoid an O(N) character lookup inside the dynamic-programming loop — which would push the whole computation to O(n^2 * m) — `levenshteinDistance` carries the byte offsets `i_bytes`/`j_bytes` alongside the character indices `i`/`j` and advances them by each code point's width as it goes. That per-character width bookkeeping sits on the innermost hot path, and the unlimited `levenshteinDistance(UTF8String)` overload currently does it redundantly: `numBytesForFirstByte(s.getByte(i_bytes))` is evaluated both in the loop increment and again in the comparison, and `s.getByte(i_bytes)` / `t.getByte(j_bytes)` are re-read within the body. This PR reads the source byte and its width once per iteration into locals and hoists the loop-invariant target byte out to the outer loop. The redundancy exists only in the unlimited overload. The limited/threshold overload `levenshteinDistance(UTF8String, int)` already reads each source byte once per iteration and does not read `t.getByte(j_bytes)` in its inner loop (it uses the precomputed `num_bytes_j` with `arrayEquals`), so it is left unchanged. ### Why are the changes needed? The inner loop runs O(n*m) times, so removing the duplicated per-character byte reads and width computations reduces the constant factor of a hot path. It is a constant-factor improvement; the O(n*m) complexity is unchanged. ### Does this PR introduce _any_ user-facing change? No. ### How was this patch tested? Existing `UTF8StringSuite` passes (51/51), including the multi-byte `levenshteinDistance` case. This is a behavior-preserving refactor, so no new tests were added. ### Was this patch authored or co-authored using generative AI tooling? Yes. Generated-by: Claude Code -- 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]
