andygrove opened a new pull request, #10334: URL: https://github.com/apache/arrow-rs/pull/10334
# Which issue does this PR close? N/A — performance improvement to an existing kernel. # Rationale for this change `substring_by_char` calls `val.chars().count()` on every value, which is a full UTF-8 decode of the entire string. The result is only used when `start < 0`, so for the common non-negative `start` case the work is thrown away. When `start < 0`, the string is then walked a second time from the front to convert the char index back into a byte offset. It also decodes UTF-8 unconditionally, even when the array is entirely ASCII, where a char index is a byte index and the bounds can be computed arithmetically. The doc comment currently tells users to reach for `substring` themselves in that case; the kernel can just detect it. This is a port of the approach taken in apache/datafusion-comet#4903, which replaced this kernel with a local copy for exactly these reasons. # What changes are included in this PR? - `substring_by_char` picks a bounds function once per array: `ascii_bounds` (integer arithmetic on byte offsets) when `is_ascii()` holds, `utf8_bounds` otherwise. `substring_by_char_impl` does the shared buffer building. - The unconditional `chars().count()` is gone. Negative starts use `char_indices().nth_back()`, which decodes only as far back as needed rather than scanning the whole value twice. - `utf8_bounds` short-circuits the end scan when the requested char length is at least the remaining byte length, since a char is never smaller than one byte. - The value buffer capacity is bounded by an upper estimate of the output element size, so a short substring of long strings no longer allocates the full input size. - Semantics are unchanged, including the clamping of out-of-range starts in both directions. The output is still built with the checked `GenericStringArray::new`. Skipping the redundant UTF-8 validation with `new_unchecked` is possible (every slice is on a char boundary of an already-valid string) but is left out of this PR. Benchmark, 65,536 rows x 1,000-char strings: | Benchmark | Before | After | Change | |---|---|---|---| | substring utf8 by char (existing) | 33.97 ms | 4.84 ms | -85.7% | | ascii, prefix (start=0, length=10) | 2.61 ms | 2.34 ms | -10.1% | | ascii, tail (start=-10) | 31.76 ms | 2.41 ms | -92.4% | | non-ascii, prefix | 3.95 ms | 1.34 ms | -66.1% | | non-ascii, tail | 65.62 ms | 1.06 ms | -98.4% | The ASCII prefix case gains the least because it is dominated by the copy and the output validation, but it still comes out ahead of the `is_ascii()` scan it now pays for. # Are these changes tested? Yes. The existing `substring_by_char` tests all mix ASCII and non-ASCII values in a single array, so they only ever exercised the UTF-8 path. Added an ASCII-only test matrix (`ascii_string_by_char` / `ascii_large_string_by_char`) covering identity, positive and negative starts, out-of-range starts in both directions, zero length, and a `u64::MAX` length to pin the saturating-add clamp. Added four benchmarks to `substring_kernels.rs` (ASCII and non-ASCII, prefix and tail) plus a non-ASCII array generator; the existing bench name is unchanged so its history stays comparable. # Are there any user-facing changes? No API change. `substring_by_char` is faster, and its `# Performance` doc note is updated to mention the ASCII fast path. -- 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]
