You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@spark.apache.org by ur...@apache.org on 2026/09/22 11:06:40 UTC

(spark) branch master updated: [SPARK-59389][CORE] Avoid per-character UTF8String allocation in trimLeft/trimRight with a trim set

This is an automated email from the ASF dual-hosted git repository.

uros-b pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/spark.git


The following commit(s) were added to refs/heads/master by this push:
     new 3471bcc9568e [SPARK-59389][CORE] Avoid per-character UTF8String allocation in trimLeft/trimRight with a trim set
3471bcc9568e is described below

commit 3471bcc9568e6258bc5d1bb6e693c47a3a8d5fa8
Author: david-mollitor-db <da...@databricks.com>
AuthorDate: Tue Sep 22 11:06:26 2026 +0000

    [SPARK-59389][CORE] Avoid per-character UTF8String allocation in trimLeft/trimRight with a trim set
    
    ### What changes were proposed in this pull request?
    
    The trim overloads that take a set of trim characters — `trimLeft(UTF8String)` and `trimRight(UTF8String)`, with `trim(UTF8String)` delegating to both — allocate a throwaway `UTF8String` for every source character they examine. Each iteration calls `copyUTF8String(...)` (a `new byte[]` + `copyMemory` + `fromBytes`) only to pass that one character to `trimString.find(searchChar, 0)`. Trimming *k* leading/trailing characters does O(k) heap allocations.
    
    The character under test is already a byte range in this string's backing memory, so the membership check can read it directly. This factors `find` into a raw-bytes overload; the public method delegates to it (byte-for-byte the same scan):
    
    ```java
    public int find(UTF8String str, int start) {
      return find(str.base, str.offset, str.numBytes, start);
    }
    
    private int find(Object strBase, long strOffset, int strNumBytes, int start) {
      assert (strNumBytes > 0);
      while (start <= numBytes - strNumBytes) {
        if (ByteArrayMethods.arrayEquals(base, offset + start, strBase, strOffset, strNumBytes)) {
          return start;
        }
        start += 1;
      }
      return -1;
    }
    ```
    
    `trimLeft`/`trimRight` then compute the (clamped) code-point length and search the source bytes in place instead of building a `UTF8String`:
    
    ```java
    // trimLeft inner loop
    byte leadByte = this.getByte(searchIdx);
    int searchCharBytes = Math.min(numBytesForFirstByte(leadByte), numBytes - searchIdx);
    if (trimString.find(this.base, this.offset + searchIdx, searchCharBytes, 0) >= 0) {
      trimIdx += searchCharBytes;
    } else {
      break;
    }
    searchIdx += searchCharBytes;
    ```
    
    The `Math.min(width, remaining)` clamp reproduces `copyUTF8String`'s handling of a truncated trailing multi-byte leader exactly. `trimRight` gets the same substitution inside its existing right-to-left loop.
    
    The two `int[numBytes]` arrays `trimRight` builds up front are deliberately left in place — removing them would require a right-to-left walk that changes how truncated trailing multi-byte sequences are handled, a separate and riskier change.
    
    ### Why are the changes needed?
    
    For a leading/trailing run of *k* trim characters, the old code allocates *k* throwaway `UTF8String` objects (each a `byte[]` + wrapper) purely to run a membership check. Reading the source character's bytes in place turns O(k) allocations into O(1), reducing GC pressure on trim-heavy workloads at no cost to non-matching inputs.
    
    ### Does this PR introduce _any_ user-facing change?
    
    No. The needle bytes/length are identical to what `copyUTF8String` produced (same clamp) and `find` runs the same `arrayEquals` subsequence scan, so results are byte-for-byte identical, including empty `trimString` (nothing trimmed) and truncated trailing leaders. The set-membership semantics are unchanged.
    
    ### How was this patch tested?
    
    Existing `UTF8StringSuite` passes (51/51), including `trimBothWithTrimString`, `trimLeftWithTrimString`, and `trimRightWithTrimString` — which cover empty/single/multi-char trim sets, multi-byte characters, all- and nothing-trimmed, and mixed ASCII+multibyte. 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
    
    Closes #58675 from david-mollitor-db/utf8-trim-no-alloc.
    
    Authored-by: david-mollitor-db <da...@databricks.com>
    Signed-off-by: Uros Bojanic <22...@users.noreply.github.com>
---
 .../org/apache/spark/unsafe/types/UTF8String.java  | 34 ++++++++++++----------
 1 file changed, 19 insertions(+), 15 deletions(-)

diff --git a/common/unsafe/src/main/java/org/apache/spark/unsafe/types/UTF8String.java b/common/unsafe/src/main/java/org/apache/spark/unsafe/types/UTF8String.java
index c5112689f3b7..f9be3f48d5c0 100644
--- a/common/unsafe/src/main/java/org/apache/spark/unsafe/types/UTF8String.java
+++ b/common/unsafe/src/main/java/org/apache/spark/unsafe/types/UTF8String.java
@@ -1065,11 +1065,12 @@ public final class UTF8String implements Comparable<UTF8String>, Externalizable,
     int trimIdx = 0;
 
     while (searchIdx < numBytes) {
-      UTF8String searchChar = copyUTF8String(
-          searchIdx, searchIdx + numBytesForFirstByte(this.getByte(searchIdx)) - 1);
-      int searchCharBytes = searchChar.numBytes;
-      // try to find the matching for the searchChar in the trimString set
-      if (trimString.find(searchChar, 0) >= 0) {
+      byte leadByte = this.getByte(searchIdx);
+      // Clamp to the remaining bytes so a truncated trailing leader is handled as copyUTF8String
+      // would have been.
+      int searchCharBytes = Math.min(numBytesForFirstByte(leadByte), numBytes - searchIdx);
+      // try to find the matching for the search char in the trimString set
+      if (trimString.find(this.base, this.offset + searchIdx, searchCharBytes, 0) >= 0) {
         trimIdx += searchCharBytes;
       } else {
         // no matching, exit the search
@@ -1147,13 +1148,12 @@ public final class UTF8String implements Comparable<UTF8String>, Externalizable,
     // the source string.
     int trimEnd = numBytes - 1;
     while (numChars > 0) {
-      UTF8String searchChar = copyUTF8String(
-          stringCharPos[numChars - 1],
-          stringCharPos[numChars - 1] + stringCharLen[numChars - 1] - 1);
-      if (trimString.find(searchChar, 0) >= 0) {
-        // Advance by the bytes the character actually occupies. A truncated trailing leader is
-        // shorter than the width its leader byte declares, so use the (clamped) search char.
-        trimEnd -= searchChar.numBytes;
+      int pos = stringCharPos[numChars - 1];
+      // Advance by the bytes the character actually occupies. A truncated trailing leader is
+      // shorter than the width its leader byte declares, so clamp to the remaining bytes.
+      int searchCharBytes = Math.min(stringCharLen[numChars - 1], numBytes - pos);
+      if (trimString.find(this.base, this.offset + pos, searchCharBytes, 0) >= 0) {
+        trimEnd -= searchCharBytes;
       } else {
         break;
       }
@@ -1400,9 +1400,13 @@ public final class UTF8String implements Comparable<UTF8String>, Externalizable,
    * Find the `str` from left to right.
    */
   public int find(UTF8String str, int start) {
-    assert (str.numBytes > 0);
-    while (start <= numBytes - str.numBytes) {
-      if (ByteArrayMethods.arrayEquals(base, offset + start, str.base, str.offset, str.numBytes)) {
+    return find(str.base, str.offset, str.numBytes, start);
+  }
+
+  private int find(Object strBase, long strOffset, int strNumBytes, int start) {
+    assert (strNumBytes > 0);
+    while (start <= numBytes - strNumBytes) {
+      if (ByteArrayMethods.arrayEquals(base, offset + start, strBase, strOffset, strNumBytes)) {
         return start;
       }
       start += 1;


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