[
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: [email protected]
For additional commands, e-mail: [email protected]
