[jira] [Resolved] (SPARK-59386) Avoid redundant byte reads in the UTF8String.levenshteinDistance inner loop

["Uroš Bojanić (Jira)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/SPARK-59386?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Uroš Bojanić resolved SPARK-59386.
----------------------------------
    Fix Version/s: 4.4.0
       Resolution: Fixed

Issue resolved by pull request 58672
[https://github.com/apache/spark/pull/58672]

> Avoid redundant byte reads in the UTF8String.levenshteinDistance inner loop
> ---------------------------------------------------------------------------
>
>                 Key: SPARK-59386
>                 URL: https://issues.apache.org/jira/browse/SPARK-59386
>             Project: Spark
>          Issue Type: Improvement
>          Components: Spark Core
>    Affects Versions: 4.1.0
>            Reporter: David Mollitor
>            Assignee: David Mollitor
>            Priority: Minor
>              Labels: pull-request-available
>             Fix For: 4.4.0
>
>
> h2. Summary
> The unlimited {{levenshteinDistance(UTF8String)}} has an O(n*m) inner loop that, on each iteration, reads the source byte {{s.getByte(i_bytes)}} two or three times, recomputes {{numBytesForFirstByte(...)}} up to twice, and re-reads the loop-invariant {{{}t.getByte(j_bytes){}}}. This reads the source byte and its width once into locals, and hoists the invariant target byte out to the outer loop.
> Small, behavior-preserving micro-optimization; no functional change.
> h2. Background: UTF-8 character lookup is O(N)
> UTF8String stores UTF-8, a variable-width encoding, so locating the i-th code point is O(N): you must scan from the start of the string, 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 DP – which would push the whole computation to O(n^2 * m) – the algorithm 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 is therefore on the innermost hot path, and the current code 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 change removes those duplicated reads. It reduces the constant factor of the O(n*m) loop; it does not change the complexity class.



--
This message was sent by Atlassian Jira
(v8.20.10#820010)

---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@spark.apache.org
For additional commands, e-mail: issues-help@spark.apache.org