David Mollitor created SPARK-59386:
--------------------------------------
Summary: 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
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]
