You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "neilconway (via GitHub)" <gi...@apache.org> on 2026/05/05 20:48:05 UTC
[PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
neilconway opened a new pull request, #22029:
URL: https://github.com/apache/datafusion/pull/22029
## Which issue does this PR close?
- Closes #21997 (potentially).
## Rationale for this change
This PR adds two new APIs to `GenericStringArrayBuilder` and `StringViewArrayBuilder`:
1. `append_with` appends a row whose bytes are produced by invoking a closure that is passed a `StringWriter`
2. `append_byte_map` appends a row whose bytes are produced by mapping each byte of the input with a byte-to-byte map closure.
For `StringViewArrayBuilder`, `StringWriter` is an append-only string writer that switches between writing to a new inline view (for short strings) or to the in-progress data block automatically. For `GenericStringArrayBuilder`, `StringWriter` just appends to the value buffer directly.
(We need two new APIs because `append_byte_map` vectorizes a lot better than `append_with`, so callers that fit the byte-to-byte map pattern should prefer it.)
Both of these new APIs allow string UDFs to avoid creating an intermediate data copy in many cases. To illustrate this, this PR adopts the new APIs in `replace`.
Benchmarks (Arm64):
ASCII single-byte from (byte-map path)
- size=1024 str_len=32 nulls=0 : 15.2 µs -> 12.7 µs (−16.4%)
- size=1024 str_len=32 nulls=0.2 : 13.8 µs -> 12.0 µs (−13.1%)
- size=1024 str_len=128 nulls=0 : 10.8 µs -> 8.0 µs (−26.6%)
- size=1024 str_len=128 nulls=0.2 : 10.6 µs -> 7.7 µs (−27.0%)
- size=4096 str_len=32 nulls=0 : 59.7 µs -> 48.4 µs (−18.9%)
- size=4096 str_len=32 nulls=0.2 : 53.0 µs -> 46.1 µs (−13.0%)
- size=4096 str_len=128 nulls=0 : 40.7 µs -> 30.7 µs (−24.6%)
- size=4096 str_len=128 nulls=0.2 : 38.8 µs -> 28.0 µs (−27.9%)
Multi-byte from, StringArray (Writer general path)
- size=1024 str_len=32 nulls=0 : 24.4 µs -> 20.9 µs (−14.5%)
- size=1024 str_len=32 nulls=0.2 : 19.0 µs -> 16.6 µs (−12.7%)
- size=1024 str_len=128 nulls=0 : 39.8 µs -> 34.5 µs (−13.4%)
- size=1024 str_len=128 nulls=0.2 : 31.2 µs -> 28.0 µs (−10.1%)
- size=4096 str_len=32 nulls=0 : 99.4 µs -> 83.6 µs (−15.9%)
- size=4096 str_len=32 nulls=0.2 : 78.2 µs -> 67.6 µs (−13.5%)
- size=4096 str_len=128 nulls=0 : 180.9 µs -> 160.3 µs (−11.4%)
- size=4096 str_len=128 nulls=0.2 : 137.4 µs -> 124.3 µs (−9.5%)
Multi-byte from, StringViewArray (Writer general path)
- size=1024 str_len=32 nulls=0 : 24.7 µs -> 21.2 µs (−14.0%)
- size=1024 str_len=32 nulls=0.2 : 19.4 µs -> 17.0 µs (−12.3%)
- size=1024 str_len=128 nulls=0 : 39.6 µs -> 34.7 µs (−12.6%)
- size=1024 str_len=128 nulls=0.2 : 31.9 µs -> 28.3 µs (−11.0%)
- size=4096 str_len=32 nulls=0 : 100.1 µs -> 84.0 µs (−16.1%)
- size=4096 str_len=32 nulls=0.2 : 79.9 µs -> 69.7 µs (−12.9%)
- size=4096 str_len=128 nulls=0 : 177.5 µs -> 158.1 µs (−10.9%)
- size=4096 str_len=128 nulls=0.2 : 139.3 µs -> 127.3 µs (−8.6%)
## What changes are included in this PR?
* Add `append_byte_map` and `append_with` to both of the bulk-NULL string builders
* Add unit tests
* Adopt the new APIs in `replace`
## Are these changes tested?
Yes; new tests added.
## Are there any user-facing changes?
No.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#issuecomment-4421064389
FYI @martin-g @Dandandan -- if you have a moment to review this, I'd love to be able to start using it with other string UDFs :)
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on code in PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#discussion_r3211160908
##########
datafusion/functions/src/string/replace.rs:
##########
@@ -230,71 +226,77 @@ fn replace<T: OffsetSizeTrait>(args: &[ArrayRef]) -> Result<ArrayRef> {
let string = unsafe { string_array.value_unchecked(i) };
let from = unsafe { from_array.value_unchecked(i) };
let to = unsafe { to_array.value_unchecked(i) };
- buffer.clear();
- replace_into_string(&mut buffer, string, from, to);
- builder.append_value(&buffer);
+ apply_replace(&mut builder, string, from, to);
}
} else {
for i in 0..len {
// SAFETY: i < len, and no input has a null buffer.
let string = unsafe { string_array.value_unchecked(i) };
let from = unsafe { from_array.value_unchecked(i) };
let to = unsafe { to_array.value_unchecked(i) };
- buffer.clear();
- replace_into_string(&mut buffer, string, from, to);
- builder.append_value(&buffer);
+ apply_replace(&mut builder, string, from, to);
}
}
Ok(Arc::new(builder.finish(nulls)?) as ArrayRef)
}
-/// Helper function to perform string replacement into a reusable String buffer
#[inline]
-fn replace_into_string(buffer: &mut String, string: &str, from: &str, to: &str) {
+fn apply_replace<B: BulkNullStringArrayBuilder>(
+ builder: &mut B,
+ string: &str,
+ from: &str,
+ to: &str,
+) {
if from.is_empty() {
- // When from is empty, insert 'to' at the beginning, between each character, and at the end
- // This matches the behavior of str::replace()
- buffer.push_str(to);
- for ch in string.chars() {
- buffer.push(ch);
- buffer.push_str(to);
- }
+ // Empty `from`: insert `to` before each character and at both ends
+ builder.append_with(|w| {
+ w.write_str(to);
+ for ch in string.chars() {
+ w.write_char(ch);
Review Comment:
Really interesting! Thanks for raising this.
I didn't quite follow your comment about the per-write tradeoff: I don't think there's anything fundamental about `append_with` that should be slower for the many-small-writes case (and we still are able to avoid a final `memcpy`). However, I can reproduce the significant slowdown you suggested for the "empty `from`" case. I dug into why, and it seems that repeatedly extending an Arrow `MutableBuffer` is relatively slow: `StringWriter::write_str()` does `MutableBuffer::extend_from_slice(&[byte])`, which results in a libc `memcpy` for every call, which is obviously slower than per-char `String::push(c)`, as the original code does. I don't think `MutableBuffer::extend_from_slice(&[byte])` is inherently slow, but there was enough helper functions / abstractions here that LLVM didn't inline, which lead to the per-call `memcpy`.
A few options:
1. Ignore it, because `replace` with empty-from is a corner-case. But it's unfortunate to leave `append_with` with a performance footgun like this.
2. Fix it by reverting to a `mut String` buffer for the empty-from case. Fixes this specific workload but doesn't fix the underlyling issue in `StringWriter`.
3. Optimize `StringWriter` for small-string writes.
I've implemented (3). A combination of special-casing the string length and marking functions as `#[inline(always)]` appears to convince LLVM to skip `memcpy` for small `to` values, which is a nice win (30-40% faster than `main` for the empty-from benchmark with a 3-byte `to` value). All the inlining might in theory cause code bloat for other callers but it doesn't appear to regress any other `replace` benchmarks, at least.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#issuecomment-4441630010
run benchmark replace
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#issuecomment-4382985211
My initial thought was to have an API where the closure is passed a caller-sized byte slice. That has two shortcomings: (1) caller needs to size the byte-slice in advance (2) for efficiency, we can't initialize the contents of the slice, so (a) this needs unsafe code (b) the closure must be careful to write to EXACTLY the specified number of bytes, no more and no less. That seemed like a footgun, so I started with these safer APIs instead.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#issuecomment-4442661848
🤖 Criterion benchmark running (GKE) | [trigger](https://github.com/apache/datafusion/pull/22029#issuecomment-4442635030)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c4442635030-35-vd79t 6.12.68+ #1 SMP Wed Apr 1 02:23:28 UTC 2026 aarch64 GNU/Linux`
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
Comparing neilc/perf-builder-append-writer (60b85427fe3713a7e6c2e9279dab4d3f1a4919d4) to b76970b (merge-base) [diff](https://github.com/apache/datafusion/compare/b76970b4f979111eb84337c778685c9df0f9cea9..60b85427fe3713a7e6c2e9279dab4d3f1a4919d4)
BENCH_NAME=replace
BENCH_COMMAND=cargo bench --features=parquet --bench replace
BENCH_FILTER=
Results will be posted here when complete
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb merged PR #22029:
URL: https://github.com/apache/datafusion/pull/22029
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#issuecomment-4442798485
🤖 Criterion benchmark completed (GKE) | [trigger](https://github.com/apache/datafusion/pull/22029#issuecomment-4442635030)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
<details><summary>Details</summary>
<p>
```
group main neilc_perf-builder-append-writer
----- ---- --------------------------------
replace size=1024/replace_string [size=1024, str_len=128, nulls=0.2] 1.00 45.3±0.19µs ? ?/sec 1.00 45.2±0.26µs ? ?/sec
replace size=1024/replace_string [size=1024, str_len=128, nulls=0] 1.00 58.6±0.25µs ? ?/sec 1.03 60.3±0.25µs ? ?/sec
replace size=1024/replace_string [size=1024, str_len=32, nulls=0.2] 1.06 22.3±0.01µs ? ?/sec 1.00 21.1±0.04µs ? ?/sec
replace size=1024/replace_string [size=1024, str_len=32, nulls=0] 1.03 26.8±0.02µs ? ?/sec 1.00 25.9±0.12µs ? ?/sec
replace size=1024/replace_string_ascii_single [size=1024, str_len=128, nulls=0.2] 1.24 14.7±0.01µs ? ?/sec 1.00 11.9±0.04µs ? ?/sec
replace size=1024/replace_string_ascii_single [size=1024, str_len=128, nulls=0] 1.19 15.7±0.00µs ? ?/sec 1.00 13.3±0.07µs ? ?/sec
replace size=1024/replace_string_ascii_single [size=1024, str_len=32, nulls=0.2] 1.10 9.8±0.01µs ? ?/sec 1.00 8.9±0.00µs ? ?/sec
replace size=1024/replace_string_ascii_single [size=1024, str_len=32, nulls=0] 1.11 10.6±0.10µs ? ?/sec 1.00 9.5±0.00µs ? ?/sec
replace size=1024/replace_string_empty_from [size=1024, str_len=128] 1.00 343.2±0.07µs ? ?/sec
replace size=1024/replace_string_empty_from [size=1024, str_len=32] 1.00 88.8±0.25µs ? ?/sec
replace size=1024/replace_string_view [size=1024, str_len=128, nulls=0.2] 1.00 45.0±0.36µs ? ?/sec 1.02 46.0±0.33µs ? ?/sec
replace size=1024/replace_string_view [size=1024, str_len=128, nulls=0] 1.00 58.3±0.43µs ? ?/sec 1.03 60.2±0.42µs ? ?/sec
replace size=1024/replace_string_view [size=1024, str_len=32, nulls=0.2] 1.06 22.3±0.01µs ? ?/sec 1.00 21.0±0.04µs ? ?/sec
replace size=1024/replace_string_view [size=1024, str_len=32, nulls=0] 1.06 27.3±0.19µs ? ?/sec 1.00 25.8±0.08µs ? ?/sec
replace size=1024/replace_string_view_empty_from [size=1024, str_len=128] 1.00 343.8±0.06µs ? ?/sec
replace size=1024/replace_string_view_empty_from [size=1024, str_len=32] 1.00 88.7±0.04µs ? ?/sec
replace size=4096/replace_string [size=4096, str_len=128, nulls=0.2] 1.03 243.5±0.57µs ? ?/sec 1.00 236.7±0.61µs ? ?/sec
replace size=4096/replace_string [size=4096, str_len=128, nulls=0] 1.03 301.6±1.06µs ? ?/sec 1.00 294.1±0.60µs ? ?/sec
replace size=4096/replace_string [size=4096, str_len=32, nulls=0.2] 1.01 103.6±0.70µs ? ?/sec 1.00 102.6±0.87µs ? ?/sec
replace size=4096/replace_string [size=4096, str_len=32, nulls=0] 1.00 131.2±0.59µs ? ?/sec 1.01 132.4±0.69µs ? ?/sec
replace size=4096/replace_string_ascii_single [size=4096, str_len=128, nulls=0.2] 1.31 52.7±0.09µs ? ?/sec 1.00 40.4±0.27µs ? ?/sec
replace size=4096/replace_string_ascii_single [size=4096, str_len=128, nulls=0] 1.23 55.6±0.20µs ? ?/sec 1.00 45.2±0.32µs ? ?/sec
replace size=4096/replace_string_ascii_single [size=4096, str_len=32, nulls=0.2] 1.20 33.7±0.09µs ? ?/sec 1.00 28.1±0.01µs ? ?/sec
replace size=4096/replace_string_ascii_single [size=4096, str_len=32, nulls=0] 1.17 37.2±0.34µs ? ?/sec 1.00 31.7±0.01µs ? ?/sec
replace size=4096/replace_string_view [size=4096, str_len=128, nulls=0.2] 1.02 241.2±0.78µs ? ?/sec 1.00 237.4±0.54µs ? ?/sec
replace size=4096/replace_string_view [size=4096, str_len=128, nulls=0] 1.03 298.9±0.75µs ? ?/sec 1.00 290.8±0.56µs ? ?/sec
replace size=4096/replace_string_view [size=4096, str_len=32, nulls=0.2] 1.00 102.7±0.30µs ? ?/sec 1.02 105.2±0.84µs ? ?/sec
replace size=4096/replace_string_view [size=4096, str_len=32, nulls=0] 1.00 128.1±0.46µs ? ?/sec 1.01 129.2±0.81µs ? ?/sec
```
</p>
</details>
<details><summary>Resource Usage</summary>
**base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 350.1s |
| Peak memory | 4.2 GiB |
| Avg memory | 4.2 GiB |
| CPU user | 389.5s |
| CPU sys | 0.9s |
| Peak spill | 0 B |
**branch**
| Metric | Value |
|--------|-------|
| Wall time | 410.1s |
| Peak memory | 4.2 GiB |
| Avg memory | 4.2 GiB |
| CPU user | 458.8s |
| CPU sys | 0.4s |
| Peak spill | 0 B |
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#issuecomment-4441795645
🤖 Criterion benchmark completed (GKE) | [trigger](https://github.com/apache/datafusion/pull/22029#issuecomment-4441630010)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
<details><summary>Details</summary>
<p>
```
group main neilc_perf-builder-append-writer
----- ---- --------------------------------
replace size=1024/replace_string [size=1024, str_len=128, nulls=0.2] 1.02 43.4±0.31µs ? ?/sec 1.00 42.5±0.22µs ? ?/sec
replace size=1024/replace_string [size=1024, str_len=128, nulls=0] 1.04 58.5±0.26µs ? ?/sec 1.00 56.1±0.23µs ? ?/sec
replace size=1024/replace_string [size=1024, str_len=32, nulls=0.2] 1.02 22.2±0.03µs ? ?/sec 1.00 21.9±0.04µs ? ?/sec
replace size=1024/replace_string [size=1024, str_len=32, nulls=0] 1.01 26.7±0.03µs ? ?/sec 1.00 26.3±0.29µs ? ?/sec
replace size=1024/replace_string_ascii_single [size=1024, str_len=128, nulls=0.2] 1.18 14.4±0.00µs ? ?/sec 1.00 12.1±0.01µs ? ?/sec
replace size=1024/replace_string_ascii_single [size=1024, str_len=128, nulls=0] 1.18 15.8±0.03µs ? ?/sec 1.00 13.4±0.01µs ? ?/sec
replace size=1024/replace_string_ascii_single [size=1024, str_len=32, nulls=0.2] 1.12 10.0±0.06µs ? ?/sec 1.00 8.9±0.03µs ? ?/sec
replace size=1024/replace_string_ascii_single [size=1024, str_len=32, nulls=0] 1.09 10.6±0.11µs ? ?/sec 1.00 9.7±0.01µs ? ?/sec
replace size=1024/replace_string_empty_from [size=1024, str_len=128] 1.00 346.3±0.08µs ? ?/sec
replace size=1024/replace_string_empty_from [size=1024, str_len=32] 1.00 90.0±0.01µs ? ?/sec
replace size=1024/replace_string_view [size=1024, str_len=128, nulls=0.2] 1.07 45.2±0.51µs ? ?/sec 1.00 42.2±0.22µs ? ?/sec
replace size=1024/replace_string_view [size=1024, str_len=128, nulls=0] 1.03 57.5±0.73µs ? ?/sec 1.00 55.6±0.65µs ? ?/sec
replace size=1024/replace_string_view [size=1024, str_len=32, nulls=0.2] 1.04 22.1±0.01µs ? ?/sec 1.00 21.3±0.04µs ? ?/sec
replace size=1024/replace_string_view [size=1024, str_len=32, nulls=0] 1.03 27.0±0.14µs ? ?/sec 1.00 26.2±0.09µs ? ?/sec
replace size=1024/replace_string_view_empty_from [size=1024, str_len=128] 1.00 346.7±0.13µs ? ?/sec
replace size=1024/replace_string_view_empty_from [size=1024, str_len=32] 1.00 89.6±0.01µs ? ?/sec
replace size=4096/replace_string [size=4096, str_len=128, nulls=0.2] 1.02 242.9±1.09µs ? ?/sec 1.00 237.2±0.86µs ? ?/sec
replace size=4096/replace_string [size=4096, str_len=128, nulls=0] 1.04 302.9±1.03µs ? ?/sec 1.00 291.6±0.62µs ? ?/sec
replace size=4096/replace_string [size=4096, str_len=32, nulls=0.2] 1.00 102.7±0.66µs ? ?/sec 1.02 104.6±0.86µs ? ?/sec
replace size=4096/replace_string [size=4096, str_len=32, nulls=0] 1.02 130.8±0.63µs ? ?/sec 1.00 128.7±0.62µs ? ?/sec
replace size=4096/replace_string_ascii_single [size=4096, str_len=128, nulls=0.2] 1.26 52.8±0.11µs ? ?/sec 1.00 41.8±0.13µs ? ?/sec
replace size=4096/replace_string_ascii_single [size=4096, str_len=128, nulls=0] 1.24 56.7±0.17µs ? ?/sec 1.00 45.6±0.17µs ? ?/sec
replace size=4096/replace_string_ascii_single [size=4096, str_len=32, nulls=0.2] 1.17 33.8±0.19µs ? ?/sec 1.00 29.0±0.06µs ? ?/sec
replace size=4096/replace_string_ascii_single [size=4096, str_len=32, nulls=0] 1.14 37.2±0.41µs ? ?/sec 1.00 32.7±0.01µs ? ?/sec
replace size=4096/replace_string_view [size=4096, str_len=128, nulls=0.2] 1.04 240.9±1.18µs ? ?/sec 1.00 232.6±0.63µs ? ?/sec
replace size=4096/replace_string_view [size=4096, str_len=128, nulls=0] 1.02 298.7±1.00µs ? ?/sec 1.00 293.1±2.13µs ? ?/sec
replace size=4096/replace_string_view [size=4096, str_len=32, nulls=0.2] 1.04 102.3±1.54µs ? ?/sec 1.00 98.6±1.70µs ? ?/sec
replace size=4096/replace_string_view [size=4096, str_len=32, nulls=0] 1.02 128.7±1.67µs ? ?/sec 1.00 126.4±1.27µs ? ?/sec
```
</p>
</details>
<details><summary>Resource Usage</summary>
**base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 350.1s |
| Peak memory | 4.2 GiB |
| Avg memory | 4.2 GiB |
| CPU user | 390.0s |
| CPU sys | 1.0s |
| Peak spill | 0 B |
**branch**
| Metric | Value |
|--------|-------|
| Wall time | 410.1s |
| Peak memory | 4.2 GiB |
| Avg memory | 4.2 GiB |
| CPU user | 462.2s |
| CPU sys | 0.4s |
| Peak spill | 0 B |
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#discussion_r3234763331
##########
datafusion/functions/src/strings.rs:
##########
@@ -673,18 +911,123 @@ impl StringViewArrayBuilder {
}
}
+/// [`StringWriter`] for [`StringViewArrayBuilder`].
+///
+/// The writer accumulates the first up-to-12 bytes of a row in a stack
+/// buffer; if the row stays inline-sized, it never touches the data block.
+/// On the first write that would exceed 12 bytes, the stack buffer is
+/// spilled into the builder's in-progress block and subsequent writes go
+/// directly there.
+pub(crate) struct StringViewWriter<'a> {
+ inline_buf: [u8; 12],
+ inline_len: u8,
+ /// `None` while the row fits inline; becomes `Some(start)` (offset of
+ /// the row's first byte in `in_progress`) at first spill.
+ spill_cursor: Option<usize>,
+ builder: &'a mut StringViewArrayBuilder,
+}
+
+impl StringWriter for StringViewWriter<'_> {
+ #[inline]
+ fn write_str(&mut self, s: &str) {
+ let bytes = s.as_bytes();
+ match self.spill_cursor {
+ None => {
+ let inline_len = self.inline_len as usize;
+ let new_len = inline_len + bytes.len();
+ if new_len <= 12 {
+ self.inline_buf[inline_len..new_len].copy_from_slice(bytes);
+ self.inline_len = new_len as u8;
+ } else {
+ // First spill of this row: reserve capacity (which may
+ // flush the current block — safe, no row-data is in it
+ // yet for this row), copy the buffered prefix, then
+ // write the new bytes.
+ self.builder.ensure_long_capacity(new_len as u32);
+ let cursor = self.builder.in_progress.len();
+ self.builder
+ .in_progress
+ .extend_from_slice(&self.inline_buf[..inline_len]);
+ self.builder.in_progress.extend_from_slice(bytes);
+ self.spill_cursor = Some(cursor);
+ }
+ }
+ Some(_) => {
+ self.builder.in_progress.extend_from_slice(bytes);
+ }
+ }
+ }
+
+ #[inline]
+ fn write_char(&mut self, c: char) {
+ let len = c.len_utf8();
+ match self.spill_cursor {
+ None => {
+ let inline_len = self.inline_len as usize;
+ let new_len = inline_len + len;
+ if new_len <= 12 {
+ c.encode_utf8(&mut self.inline_buf[inline_len..new_len]);
+ self.inline_len = new_len as u8;
+ } else {
+ self.builder.ensure_long_capacity(new_len as u32);
+ let cursor = self.builder.in_progress.len();
+ self.builder
+ .in_progress
+ .extend_from_slice(&self.inline_buf[..inline_len]);
+ push_char_to_vec(&mut self.builder.in_progress, c);
+ self.spill_cursor = Some(cursor);
+ }
+ }
+ Some(_) => {
+ push_char_to_vec(&mut self.builder.in_progress, c);
+ }
+ }
+ }
+}
+
+#[inline]
+fn push_char_to_vec(v: &mut Vec<u8>, c: char) {
+ let len = c.len_utf8();
+ let old_len = v.len();
+ v.reserve(len);
+ // SAFETY: we reserved `len` bytes above, write valid UTF-8 into those
+ // bytes, then update the initialized length to include them.
+ unsafe {
+ let dst = v.as_mut_ptr().add(old_len);
+ if len == 1 {
+ *dst = c as u8;
+ } else {
+ c.encode_utf8(std::slice::from_raw_parts_mut(dst, len));
+ }
+ v.set_len(old_len + len);
+ }
+}
+
/// Trait abstracting over the bulk-NULL string array builders.
///
/// Similar to Arrow's `StringLikeArrayBuilder`, this allows generic dispatch
/// over the three string array types (Utf8, LargeUtf8, Utf8View) when the
/// function body is uniform across them.
pub(crate) trait BulkNullStringArrayBuilder {
+ /// Per-builder concrete writer type, exposed as a GAT so generic callers
+ /// can use the inherent (non-`dyn`) writer methods without vtable
+ /// dispatch.
+ type Writer<'a>: StringWriter
+ where
+ Self: 'a;
+
fn append_value(&mut self, value: &str);
Review Comment:
I think it would help if we also added documentation for these methods -- and maybe some commentary about when to use one ro the other.
Specifically this context seem valuable and non-obvious when reading the code for the first time
> (We need two new APIs because append_byte_map vectorizes a lot better than append_with, so callers that fit the byte-to-byte map pattern should prefer it.)
I think you already have most of these comments on the implementations in StringViewArrayBuilder, etc -- so maybe you could conlidate the docs in the trait and update the builders to have a doc link to `BulkNullStringArrayBuilder`
##########
datafusion/functions/src/strings.rs:
##########
@@ -983,6 +1400,174 @@ mod tests {
let _ = builder.finish(None);
}
+ #[test]
+ fn string_view_array_builder_append_with_inline() {
Review Comment:
I wonder if we could reduce the repeitition of these tests a bit by
1. Defining the input (as a closure)
2. Defining the expected output
3. Running the same inputs/otuput through all three types of builders
For example soemthing like
```rust
#[test] // would need to do this for StringViewArray, StringArray, LargeStringArray
fn bulk_string_view_inline() {
let inputs = vec![Some("hello"), Some("world"), None, Some("0123456789ab")];
let ouput = build_array<StringViewArrayBuilder>(|builder| {
for s in &inputs {
builder.append_with(|w| w.write_str(s));
}
}
let expected= StringViewArray::from(inputs);
assert_eq!(ouput, expected)
}
```
I think it would take some fiddling to get the generics right, but once that was done I think the tests would be easier to understand (much more concise) and add more coverge
It seems like you did something similar with `bulk_null_trait_append_with_string` below
##########
datafusion/functions/src/strings.rs:
##########
@@ -673,18 +911,123 @@ impl StringViewArrayBuilder {
}
}
+/// [`StringWriter`] for [`StringViewArrayBuilder`].
+///
+/// The writer accumulates the first up-to-12 bytes of a row in a stack
+/// buffer; if the row stays inline-sized, it never touches the data block.
+/// On the first write that would exceed 12 bytes, the stack buffer is
+/// spilled into the builder's in-progress block and subsequent writes go
+/// directly there.
+pub(crate) struct StringViewWriter<'a> {
Review Comment:
This is definitely something we could consider porting up stream to arrow-rs 🤔
##########
datafusion/functions/src/strings.rs:
##########
@@ -673,18 +911,123 @@ impl StringViewArrayBuilder {
}
}
+/// [`StringWriter`] for [`StringViewArrayBuilder`].
+///
+/// The writer accumulates the first up-to-12 bytes of a row in a stack
+/// buffer; if the row stays inline-sized, it never touches the data block.
+/// On the first write that would exceed 12 bytes, the stack buffer is
+/// spilled into the builder's in-progress block and subsequent writes go
+/// directly there.
+pub(crate) struct StringViewWriter<'a> {
+ inline_buf: [u8; 12],
+ inline_len: u8,
+ /// `None` while the row fits inline; becomes `Some(start)` (offset of
+ /// the row's first byte in `in_progress`) at first spill.
+ spill_cursor: Option<usize>,
+ builder: &'a mut StringViewArrayBuilder,
+}
+
+impl StringWriter for StringViewWriter<'_> {
+ #[inline]
+ fn write_str(&mut self, s: &str) {
+ let bytes = s.as_bytes();
+ match self.spill_cursor {
+ None => {
+ let inline_len = self.inline_len as usize;
+ let new_len = inline_len + bytes.len();
+ if new_len <= 12 {
+ self.inline_buf[inline_len..new_len].copy_from_slice(bytes);
+ self.inline_len = new_len as u8;
+ } else {
+ // First spill of this row: reserve capacity (which may
+ // flush the current block — safe, no row-data is in it
+ // yet for this row), copy the buffered prefix, then
+ // write the new bytes.
+ self.builder.ensure_long_capacity(new_len as u32);
+ let cursor = self.builder.in_progress.len();
+ self.builder
+ .in_progress
+ .extend_from_slice(&self.inline_buf[..inline_len]);
+ self.builder.in_progress.extend_from_slice(bytes);
+ self.spill_cursor = Some(cursor);
+ }
+ }
+ Some(_) => {
+ self.builder.in_progress.extend_from_slice(bytes);
+ }
+ }
+ }
+
+ #[inline]
+ fn write_char(&mut self, c: char) {
+ let len = c.len_utf8();
+ match self.spill_cursor {
+ None => {
+ let inline_len = self.inline_len as usize;
+ let new_len = inline_len + len;
+ if new_len <= 12 {
+ c.encode_utf8(&mut self.inline_buf[inline_len..new_len]);
+ self.inline_len = new_len as u8;
+ } else {
+ self.builder.ensure_long_capacity(new_len as u32);
+ let cursor = self.builder.in_progress.len();
+ self.builder
+ .in_progress
+ .extend_from_slice(&self.inline_buf[..inline_len]);
+ push_char_to_vec(&mut self.builder.in_progress, c);
+ self.spill_cursor = Some(cursor);
+ }
+ }
+ Some(_) => {
+ push_char_to_vec(&mut self.builder.in_progress, c);
+ }
+ }
+ }
+}
+
+#[inline]
+fn push_char_to_vec(v: &mut Vec<u8>, c: char) {
Review Comment:
Do you evaluate a more safe version like
```rust
fn push_char_to_vec(v: &mut Vec<u8>, c: char) {
let mut buf = [0u8; 4];
v.extend_from_slice(c.encode_utf8(&mut buf).as_bytes());
}
```
In theory that is another copy, but LLVM might be smart enough to inline / elide the copy
Maybe some justification about why this was needed would help
##########
datafusion/functions/src/strings.rs:
##########
@@ -627,6 +733,138 @@ impl StringViewArrayBuilder {
self.placeholder_count += 1;
}
+ /// Ensure the in-progress block has room for `length` more bytes,
+ /// flushing the current block and starting a new (doubled) one if not.
+ /// Caller must only invoke this between rows — flushing mid-row would
+ /// orphan partial row data.
+ #[inline]
+ fn ensure_long_capacity(&mut self, length: u32) {
+ let required_cap = self.in_progress.len() + length as usize;
+ if self.in_progress.capacity() < required_cap {
+ self.flush_in_progress();
+ let to_reserve = (length as usize).max(self.next_block_size() as usize);
+ self.in_progress.reserve(to_reserve);
+ }
+ }
+
+ /// Encode a long-form view referencing `length` bytes already written
+ /// into the in-progress block at `offset`. `prefix_bytes` is the row's
+ /// data slice (or any slice starting with the row's first 4 bytes).
+ ///
+ /// Built inline rather than going through `make_view`, which is
+ /// `[inline(never)]`.
+ #[inline]
+ fn make_long_view(&self, length: u32, offset: u32, prefix_bytes: &[u8]) -> u128 {
+ let buffer_index: u32 = i32::try_from(self.completed.len())
+ .expect("buffer count exceeds i32::MAX")
+ as u32;
+ ByteView {
+ length,
+ // length > 12, so prefix_bytes has at least 4 bytes.
+ prefix: u32::from_le_bytes(prefix_bytes[..4].try_into().unwrap()),
+ buffer_index,
+ offset,
+ }
+ .into()
+ }
+
+ /// Append a row whose bytes are produced by mapping each byte of `src`
+ /// through `map`, in order. Output length equals `src.len()`.
+ ///
+ /// Because output length is known up front, this is more efficient than
+ /// `append_with` when computing a byte-to-byte mapping.
+ ///
+ /// # Safety
+ ///
+ /// The bytes produced by `map` over `src.iter()`, in order, must form
+ /// valid UTF-8.
+ ///
+ /// # Panics
+ ///
+ /// Panics under the same conditions as [`Self::append_value`]: if
+ /// `src.len()`, the in-progress buffer offset, or the number of completed
+ /// buffers exceeds `i32::MAX`.
+ #[inline]
+ pub unsafe fn append_byte_map<F: FnMut(u8) -> u8>(&mut self, src: &[u8], mut map: F) {
+ let length: u32 =
+ i32::try_from(src.len()).expect("value length exceeds i32::MAX") as u32;
+ if length <= 12 {
Review Comment:
this looks similar to https://docs.rs/arrow/latest/arrow/array/fn.make_view.html - I wonder if we could use that instead of the replicatin
##########
datafusion/functions/src/strings.rs:
##########
@@ -538,6 +584,79 @@ pub(crate) const STRING_VIEW_INIT_BLOCK_SIZE: u32 = 8 * 1024;
/// grows to; matches Arrow's `GenericByteViewBuilder` default.
pub(crate) const STRING_VIEW_MAX_BLOCK_SIZE: u32 = 2 * 1024 * 1024;
+/// Append-only writer handed to closures passed to `append_with`.
+pub(crate) trait StringWriter {
+ fn write_str(&mut self, s: &str);
+ fn write_char(&mut self, c: char);
+}
+
+/// [`StringWriter`] for [`GenericStringArrayBuilder`]. Writes go straight to
+/// the value buffer.
+pub(crate) struct GenericStringWriter<'a> {
+ value_buffer: &'a mut MutableBuffer,
+}
+
+impl StringWriter for GenericStringWriter<'_> {
+ #[inline(always)]
+ fn write_str(&mut self, s: &str) {
+ push_bytes_to_mutable_buffer(self.value_buffer, s.as_bytes());
+ }
+
+ #[inline(always)]
+ fn write_char(&mut self, c: char) {
+ push_char_to_mutable_buffer(self.value_buffer, c);
+ }
+}
+
+/// Write `bytes` into `value_buffer`. For repeated small writes,
+/// MutableBuffer::extend_from_slice can be slow (memcpy per call), so we extend
+/// the buffer here directly and force inlining.
+#[inline(always)]
+fn push_bytes_to_mutable_buffer(value_buffer: &mut MutableBuffer, bytes: &[u8]) {
+ let n = bytes.len();
+ let old_len = value_buffer.len();
+ value_buffer.reserve(n);
+
+ // SAFETY: we reserved `n` bytes; the source and destination do not alias
+ // because `bytes` was passed in by the caller and `value_buffer` is owned.
+ unsafe {
+ let dst = value_buffer.as_mut_ptr().add(old_len);
+ let src = bytes.as_ptr();
+ match n {
+ 0 => {}
+ 1 => std::ptr::copy_nonoverlapping(src, dst, 1),
+ 2 => std::ptr::copy_nonoverlapping(src, dst, 2),
+ 3 => std::ptr::copy_nonoverlapping(src, dst, 3),
+ 4 => std::ptr::copy_nonoverlapping(src, dst, 4),
+ 5 => std::ptr::copy_nonoverlapping(src, dst, 5),
+ 6 => std::ptr::copy_nonoverlapping(src, dst, 6),
+ 7 => std::ptr::copy_nonoverlapping(src, dst, 7),
+ 8 => std::ptr::copy_nonoverlapping(src, dst, 8),
+ _ => std::ptr::copy_nonoverlapping(src, dst, n),
+ }
+ value_buffer.set_len(old_len + n);
+ }
+}
+
+#[inline(always)]
+fn push_char_to_mutable_buffer(value_buffer: &mut MutableBuffer, c: char) {
+ let len = c.len_utf8();
+ let old_len = value_buffer.len();
+ value_buffer.reserve(len);
+
+ // SAFETY: we reserved `len` bytes above, write valid UTF-8 into those
Review Comment:
same question as ablow -- can we avoid the unsafe by copying to a local stack variable first?
##########
datafusion/functions/src/strings.rs:
##########
@@ -627,6 +733,138 @@ impl StringViewArrayBuilder {
self.placeholder_count += 1;
}
+ /// Ensure the in-progress block has room for `length` more bytes,
+ /// flushing the current block and starting a new (doubled) one if not.
+ /// Caller must only invoke this between rows — flushing mid-row would
+ /// orphan partial row data.
+ #[inline]
+ fn ensure_long_capacity(&mut self, length: u32) {
+ let required_cap = self.in_progress.len() + length as usize;
+ if self.in_progress.capacity() < required_cap {
+ self.flush_in_progress();
+ let to_reserve = (length as usize).max(self.next_block_size() as usize);
+ self.in_progress.reserve(to_reserve);
+ }
+ }
+
+ /// Encode a long-form view referencing `length` bytes already written
+ /// into the in-progress block at `offset`. `prefix_bytes` is the row's
+ /// data slice (or any slice starting with the row's first 4 bytes).
+ ///
+ /// Built inline rather than going through `make_view`, which is
+ /// `[inline(never)]`.
+ #[inline]
+ fn make_long_view(&self, length: u32, offset: u32, prefix_bytes: &[u8]) -> u128 {
+ let buffer_index: u32 = i32::try_from(self.completed.len())
+ .expect("buffer count exceeds i32::MAX")
+ as u32;
+ ByteView {
+ length,
+ // length > 12, so prefix_bytes has at least 4 bytes.
+ prefix: u32::from_le_bytes(prefix_bytes[..4].try_into().unwrap()),
+ buffer_index,
+ offset,
+ }
+ .into()
+ }
+
+ /// Append a row whose bytes are produced by mapping each byte of `src`
+ /// through `map`, in order. Output length equals `src.len()`.
+ ///
+ /// Because output length is known up front, this is more efficient than
+ /// `append_with` when computing a byte-to-byte mapping.
+ ///
+ /// # Safety
+ ///
+ /// The bytes produced by `map` over `src.iter()`, in order, must form
+ /// valid UTF-8.
+ ///
+ /// # Panics
+ ///
+ /// Panics under the same conditions as [`Self::append_value`]: if
+ /// `src.len()`, the in-progress buffer offset, or the number of completed
+ /// buffers exceeds `i32::MAX`.
+ #[inline]
+ pub unsafe fn append_byte_map<F: FnMut(u8) -> u8>(&mut self, src: &[u8], mut map: F) {
+ let length: u32 =
+ i32::try_from(src.len()).expect("value length exceeds i32::MAX") as u32;
+ if length <= 12 {
+ // `iter_mut().zip()` over a stack array is the canonical autovec
+ // pattern.
+ let mut bytes = [0u8; 12];
+ for (d, &b) in bytes[..src.len()].iter_mut().zip(src) {
+ *d = map(b);
+ }
+ self.views.push(make_view(&bytes[..src.len()], 0, 0));
+ return;
+ }
+
+ self.ensure_long_capacity(length);
+
+ let cursor = self.in_progress.len();
+ let offset: u32 = i32::try_from(cursor).expect("offset exceeds i32::MAX") as u32;
+ self.in_progress.extend(src.iter().map(|&b| map(b)));
+ self.views
+ .push(self.make_long_view(length, offset, &self.in_progress[cursor..]));
+ }
+
+ /// Append a row whose bytes are produced by `f` calling write methods on
+ /// the supplied [`StringWriter`].
+ ///
+ /// Initial writes accumulate in a 12-byte stack buffer. If the row stays
Review Comment:
this feels like documentation that should go on StringViewWriter (they sort of already are)
##########
datafusion/functions/src/strings.rs:
##########
@@ -673,18 +911,123 @@ impl StringViewArrayBuilder {
}
}
+/// [`StringWriter`] for [`StringViewArrayBuilder`].
+///
+/// The writer accumulates the first up-to-12 bytes of a row in a stack
+/// buffer; if the row stays inline-sized, it never touches the data block.
+/// On the first write that would exceed 12 bytes, the stack buffer is
+/// spilled into the builder's in-progress block and subsequent writes go
+/// directly there.
+pub(crate) struct StringViewWriter<'a> {
+ inline_buf: [u8; 12],
+ inline_len: u8,
+ /// `None` while the row fits inline; becomes `Some(start)` (offset of
+ /// the row's first byte in `in_progress`) at first spill.
+ spill_cursor: Option<usize>,
+ builder: &'a mut StringViewArrayBuilder,
+}
+
+impl StringWriter for StringViewWriter<'_> {
+ #[inline]
+ fn write_str(&mut self, s: &str) {
+ let bytes = s.as_bytes();
+ match self.spill_cursor {
+ None => {
+ let inline_len = self.inline_len as usize;
+ let new_len = inline_len + bytes.len();
+ if new_len <= 12 {
+ self.inline_buf[inline_len..new_len].copy_from_slice(bytes);
+ self.inline_len = new_len as u8;
+ } else {
+ // First spill of this row: reserve capacity (which may
+ // flush the current block — safe, no row-data is in it
+ // yet for this row), copy the buffered prefix, then
+ // write the new bytes.
+ self.builder.ensure_long_capacity(new_len as u32);
+ let cursor = self.builder.in_progress.len();
+ self.builder
+ .in_progress
+ .extend_from_slice(&self.inline_buf[..inline_len]);
+ self.builder.in_progress.extend_from_slice(bytes);
+ self.spill_cursor = Some(cursor);
+ }
+ }
+ Some(_) => {
+ self.builder.in_progress.extend_from_slice(bytes);
+ }
+ }
+ }
+
+ #[inline]
+ fn write_char(&mut self, c: char) {
+ let len = c.len_utf8();
+ match self.spill_cursor {
+ None => {
+ let inline_len = self.inline_len as usize;
+ let new_len = inline_len + len;
+ if new_len <= 12 {
+ c.encode_utf8(&mut self.inline_buf[inline_len..new_len]);
+ self.inline_len = new_len as u8;
+ } else {
+ self.builder.ensure_long_capacity(new_len as u32);
+ let cursor = self.builder.in_progress.len();
+ self.builder
+ .in_progress
+ .extend_from_slice(&self.inline_buf[..inline_len]);
+ push_char_to_vec(&mut self.builder.in_progress, c);
+ self.spill_cursor = Some(cursor);
+ }
+ }
+ Some(_) => {
+ push_char_to_vec(&mut self.builder.in_progress, c);
+ }
+ }
+ }
+}
+
+#[inline]
+fn push_char_to_vec(v: &mut Vec<u8>, c: char) {
+ let len = c.len_utf8();
+ let old_len = v.len();
+ v.reserve(len);
+ // SAFETY: we reserved `len` bytes above, write valid UTF-8 into those
+ // bytes, then update the initialized length to include them.
+ unsafe {
+ let dst = v.as_mut_ptr().add(old_len);
+ if len == 1 {
+ *dst = c as u8;
+ } else {
+ c.encode_utf8(std::slice::from_raw_parts_mut(dst, len));
+ }
+ v.set_len(old_len + len);
+ }
+}
+
/// Trait abstracting over the bulk-NULL string array builders.
///
/// Similar to Arrow's `StringLikeArrayBuilder`, this allows generic dispatch
/// over the three string array types (Utf8, LargeUtf8, Utf8View) when the
/// function body is uniform across them.
pub(crate) trait BulkNullStringArrayBuilder {
+ /// Per-builder concrete writer type, exposed as a GAT so generic callers
+ /// can use the inherent (non-`dyn`) writer methods without vtable
+ /// dispatch.
+ type Writer<'a>: StringWriter
+ where
+ Self: 'a;
+
fn append_value(&mut self, value: &str);
fn append_placeholder(&mut self);
+ fn append_with<F>(&mut self, f: F)
+ where
+ F: for<'a> FnOnce(&mut Self::Writer<'a>);
+ unsafe fn append_byte_map<F: FnMut(u8) -> u8>(&mut self, src: &[u8], map: F);
Review Comment:
I also think documenting carefully what is needed to use this `unsafe` API safely is important (namely that the output bytes for valid UTF8 I think)
##########
datafusion/functions/src/strings.rs:
##########
@@ -493,6 +493,52 @@ impl<O: OffsetSizeTrait> GenericStringArrayBuilder<O> {
self.placeholder_count += 1;
}
+ /// Append a row whose bytes are produced by mapping each byte of `src`
Review Comment:
see comments below -- I think it would be good to consolidate the documentation on the BulkNullStringArrayBuilder trait and leave a pointer here -- that way the documentation won't drift.
Replication is ok too, but I think it would be better to avoid if possible
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on code in PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#discussion_r3236893353
##########
datafusion/functions/src/strings.rs:
##########
@@ -627,6 +733,138 @@ impl StringViewArrayBuilder {
self.placeholder_count += 1;
}
+ /// Ensure the in-progress block has room for `length` more bytes,
+ /// flushing the current block and starting a new (doubled) one if not.
+ /// Caller must only invoke this between rows — flushing mid-row would
+ /// orphan partial row data.
+ #[inline]
+ fn ensure_long_capacity(&mut self, length: u32) {
+ let required_cap = self.in_progress.len() + length as usize;
+ if self.in_progress.capacity() < required_cap {
+ self.flush_in_progress();
+ let to_reserve = (length as usize).max(self.next_block_size() as usize);
+ self.in_progress.reserve(to_reserve);
+ }
+ }
+
+ /// Encode a long-form view referencing `length` bytes already written
+ /// into the in-progress block at `offset`. `prefix_bytes` is the row's
+ /// data slice (or any slice starting with the row's first 4 bytes).
+ ///
+ /// Built inline rather than going through `make_view`, which is
+ /// `[inline(never)]`.
+ #[inline]
+ fn make_long_view(&self, length: u32, offset: u32, prefix_bytes: &[u8]) -> u128 {
+ let buffer_index: u32 = i32::try_from(self.completed.len())
+ .expect("buffer count exceeds i32::MAX")
+ as u32;
+ ByteView {
+ length,
+ // length > 12, so prefix_bytes has at least 4 bytes.
+ prefix: u32::from_le_bytes(prefix_bytes[..4].try_into().unwrap()),
+ buffer_index,
+ offset,
+ }
+ .into()
+ }
+
+ /// Append a row whose bytes are produced by mapping each byte of `src`
+ /// through `map`, in order. Output length equals `src.len()`.
+ ///
+ /// Because output length is known up front, this is more efficient than
+ /// `append_with` when computing a byte-to-byte mapping.
+ ///
+ /// # Safety
+ ///
+ /// The bytes produced by `map` over `src.iter()`, in order, must form
+ /// valid UTF-8.
+ ///
+ /// # Panics
+ ///
+ /// Panics under the same conditions as [`Self::append_value`]: if
+ /// `src.len()`, the in-progress buffer offset, or the number of completed
+ /// buffers exceeds `i32::MAX`.
+ #[inline]
+ pub unsafe fn append_byte_map<F: FnMut(u8) -> u8>(&mut self, src: &[u8], mut map: F) {
+ let length: u32 =
+ i32::try_from(src.len()).expect("value length exceeds i32::MAX") as u32;
+ if length <= 12 {
Review Comment:
Hmm -- we already use `make_view` in the short-string code path. For long strings, I found that `make_long_view` is worth it: it avoids the 13-way match on string length and also can be inlined (`make_view` is marked never-inline). Lmk if that sounds reasonable or if there's another approach you think we should explore.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on code in PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#discussion_r3236841362
##########
datafusion/functions/src/strings.rs:
##########
@@ -983,6 +1400,174 @@ mod tests {
let _ = builder.finish(None);
}
+ #[test]
+ fn string_view_array_builder_append_with_inline() {
Review Comment:
Good idea. I introduced a test helper and refactored the tests to use it. Thanks!
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on code in PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#discussion_r3211160908
##########
datafusion/functions/src/string/replace.rs:
##########
@@ -230,71 +226,77 @@ fn replace<T: OffsetSizeTrait>(args: &[ArrayRef]) -> Result<ArrayRef> {
let string = unsafe { string_array.value_unchecked(i) };
let from = unsafe { from_array.value_unchecked(i) };
let to = unsafe { to_array.value_unchecked(i) };
- buffer.clear();
- replace_into_string(&mut buffer, string, from, to);
- builder.append_value(&buffer);
+ apply_replace(&mut builder, string, from, to);
}
} else {
for i in 0..len {
// SAFETY: i < len, and no input has a null buffer.
let string = unsafe { string_array.value_unchecked(i) };
let from = unsafe { from_array.value_unchecked(i) };
let to = unsafe { to_array.value_unchecked(i) };
- buffer.clear();
- replace_into_string(&mut buffer, string, from, to);
- builder.append_value(&buffer);
+ apply_replace(&mut builder, string, from, to);
}
}
Ok(Arc::new(builder.finish(nulls)?) as ArrayRef)
}
-/// Helper function to perform string replacement into a reusable String buffer
#[inline]
-fn replace_into_string(buffer: &mut String, string: &str, from: &str, to: &str) {
+fn apply_replace<B: BulkNullStringArrayBuilder>(
+ builder: &mut B,
+ string: &str,
+ from: &str,
+ to: &str,
+) {
if from.is_empty() {
- // When from is empty, insert 'to' at the beginning, between each character, and at the end
- // This matches the behavior of str::replace()
- buffer.push_str(to);
- for ch in string.chars() {
- buffer.push(ch);
- buffer.push_str(to);
- }
+ // Empty `from`: insert `to` before each character and at both ends
+ builder.append_with(|w| {
+ w.write_str(to);
+ for ch in string.chars() {
+ w.write_char(ch);
Review Comment:
Really interesting! Thanks for raising this.
I didn't quite follow your comment about the per-write tradeoff: I don't think there's anything fundamental about `append_with` that should be slower for the many-small-writes case (and we still are able to avoid a final `memcpy`). However, I can reproduce the significant slowdown you suggested for the "empty `from`" case. I dug into why, and it seems that repeatedly extending an Arrow `MutableBuffer` is relatively slow: `StringWriter::write_str()` does `MutableBuffer::extend_from_slice(&[byte])`, which results in a libc `memcpy` for every call, which is obviously slower than per-char `String::push(c)`, as the original code does. I don't think `MutableBuffer::extend_from_slice(&[byte])` is inherently slow, but there was enough helper functions / abstractions here that LLVM didn't inline, which lead to the per-call `memcpy`.
A few options:
1. Ignore it, because `replace` with empty-from is a corner-case. But it's unfortunate to leave `append_with` with a performance footgun like this.
2. Fix it by reverting to a `mut String` buffer for the empty-from case. Fixes this specific workload but doesn't fix the underlyling issue in `StringWriter`.
3. Optimize `StringWriter` for small-string writes.
I've implemented (3). A combination of special-casing the string length and marking functions as `#[inline(always)]` appears to convince LLVM to vectorize this code path, which is a nice win (30-40% faster than `main` for the empty-from). All the inlining might in theory cause code block for other callers but it doesn't appear to regress any other `replace` benchmarks, at least.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on code in PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#discussion_r3235411309
##########
datafusion/functions/src/strings.rs:
##########
@@ -538,6 +584,79 @@ pub(crate) const STRING_VIEW_INIT_BLOCK_SIZE: u32 = 8 * 1024;
/// grows to; matches Arrow's `GenericByteViewBuilder` default.
pub(crate) const STRING_VIEW_MAX_BLOCK_SIZE: u32 = 2 * 1024 * 1024;
+/// Append-only writer handed to closures passed to `append_with`.
+pub(crate) trait StringWriter {
+ fn write_str(&mut self, s: &str);
+ fn write_char(&mut self, c: char);
+}
+
+/// [`StringWriter`] for [`GenericStringArrayBuilder`]. Writes go straight to
+/// the value buffer.
+pub(crate) struct GenericStringWriter<'a> {
+ value_buffer: &'a mut MutableBuffer,
+}
+
+impl StringWriter for GenericStringWriter<'_> {
+ #[inline(always)]
+ fn write_str(&mut self, s: &str) {
+ push_bytes_to_mutable_buffer(self.value_buffer, s.as_bytes());
+ }
+
+ #[inline(always)]
+ fn write_char(&mut self, c: char) {
+ push_char_to_mutable_buffer(self.value_buffer, c);
+ }
+}
+
+/// Write `bytes` into `value_buffer`. For repeated small writes,
+/// MutableBuffer::extend_from_slice can be slow (memcpy per call), so we extend
+/// the buffer here directly and force inlining.
+#[inline(always)]
+fn push_bytes_to_mutable_buffer(value_buffer: &mut MutableBuffer, bytes: &[u8]) {
+ let n = bytes.len();
+ let old_len = value_buffer.len();
+ value_buffer.reserve(n);
+
+ // SAFETY: we reserved `n` bytes; the source and destination do not alias
+ // because `bytes` was passed in by the caller and `value_buffer` is owned.
+ unsafe {
+ let dst = value_buffer.as_mut_ptr().add(old_len);
+ let src = bytes.as_ptr();
+ match n {
+ 0 => {}
+ 1 => std::ptr::copy_nonoverlapping(src, dst, 1),
+ 2 => std::ptr::copy_nonoverlapping(src, dst, 2),
+ 3 => std::ptr::copy_nonoverlapping(src, dst, 3),
+ 4 => std::ptr::copy_nonoverlapping(src, dst, 4),
+ 5 => std::ptr::copy_nonoverlapping(src, dst, 5),
+ 6 => std::ptr::copy_nonoverlapping(src, dst, 6),
+ 7 => std::ptr::copy_nonoverlapping(src, dst, 7),
+ 8 => std::ptr::copy_nonoverlapping(src, dst, 8),
+ _ => std::ptr::copy_nonoverlapping(src, dst, n),
+ }
+ value_buffer.set_len(old_len + n);
+ }
+}
+
+#[inline(always)]
+fn push_char_to_mutable_buffer(value_buffer: &mut MutableBuffer, c: char) {
+ let len = c.len_utf8();
+ let old_len = value_buffer.len();
+ value_buffer.reserve(len);
+
+ // SAFETY: we reserved `len` bytes above, write valid UTF-8 into those
Review Comment:
This was the specific case I ran into with the "empty-`from`" benchmark regression, so I believe this one earns its keep.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#issuecomment-4382974325
Other places where these APIs should be useful:
* `initcap`
* `lower`
* `upper`
* `translate`
* `reverse` (might need a slightly different API)
* `to_char` (might need a small API extension)
* `lpad`, `rpad` (needs a closer look)
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on code in PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#discussion_r3211160908
##########
datafusion/functions/src/string/replace.rs:
##########
@@ -230,71 +226,77 @@ fn replace<T: OffsetSizeTrait>(args: &[ArrayRef]) -> Result<ArrayRef> {
let string = unsafe { string_array.value_unchecked(i) };
let from = unsafe { from_array.value_unchecked(i) };
let to = unsafe { to_array.value_unchecked(i) };
- buffer.clear();
- replace_into_string(&mut buffer, string, from, to);
- builder.append_value(&buffer);
+ apply_replace(&mut builder, string, from, to);
}
} else {
for i in 0..len {
// SAFETY: i < len, and no input has a null buffer.
let string = unsafe { string_array.value_unchecked(i) };
let from = unsafe { from_array.value_unchecked(i) };
let to = unsafe { to_array.value_unchecked(i) };
- buffer.clear();
- replace_into_string(&mut buffer, string, from, to);
- builder.append_value(&buffer);
+ apply_replace(&mut builder, string, from, to);
}
}
Ok(Arc::new(builder.finish(nulls)?) as ArrayRef)
}
-/// Helper function to perform string replacement into a reusable String buffer
#[inline]
-fn replace_into_string(buffer: &mut String, string: &str, from: &str, to: &str) {
+fn apply_replace<B: BulkNullStringArrayBuilder>(
+ builder: &mut B,
+ string: &str,
+ from: &str,
+ to: &str,
+) {
if from.is_empty() {
- // When from is empty, insert 'to' at the beginning, between each character, and at the end
- // This matches the behavior of str::replace()
- buffer.push_str(to);
- for ch in string.chars() {
- buffer.push(ch);
- buffer.push_str(to);
- }
+ // Empty `from`: insert `to` before each character and at both ends
+ builder.append_with(|w| {
+ w.write_str(to);
+ for ch in string.chars() {
+ w.write_char(ch);
Review Comment:
Really interesting! Thanks for raising this.
I didn't quite follow your comment about the per-write tradeoff: I don't think there's anything fundamental about `append_with` that should be slower for the many-small-writes case (and we still are able to avoid a final `memcpy`). However, I can reproduce the significant slowdown you suggested for the "empty `from`" case. I dug into why, and it seems that repeatedly extending an Arrow `MutableBuffer` is relatively slow: `StringWriter::write_str()` does `MutableBuffer::extend_from_slice(&[byte])`, which results in a libc `memcpy` for every call, which is obviously slower than per-char `String::push(c)`, as the original code does. I don't think `MutableBuffer::extend_from_slice(&[byte])` is inherently slow, but there was enough helper functions / abstractions here that LLVM didn't inline, which lead to the per-call `memcpy`.
A few options:
1. Ignore it, because `replace` with empty-from is a corner-case. But it's unfortunate to leave `append_with` with a performance footgun like this.
2. Fix it by reverting to a `mut String` buffer for the empty-from case. Fixes this specific workload but doesn't fix the underlyling issue in `StringWriter`.
3. Optimize `StringWriter` for small-string writes.
I've implemented (3). A combination of special-casing the string length and marking functions as `#[inline(always)]` appears to convince LLVM to skip `memcpy` for small `to` values, which is a nice win (30-40% faster than `main` for the empty-from benchmark with a 3-byte `to` value). All the inlining might in theory cause code block for other callers but it doesn't appear to regress any other `replace` benchmarks, at least.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "lyne7-sc (via GitHub)" <gi...@apache.org>.
lyne7-sc commented on code in PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#discussion_r3199437877
##########
datafusion/functions/src/string/replace.rs:
##########
@@ -230,71 +226,77 @@ fn replace<T: OffsetSizeTrait>(args: &[ArrayRef]) -> Result<ArrayRef> {
let string = unsafe { string_array.value_unchecked(i) };
let from = unsafe { from_array.value_unchecked(i) };
let to = unsafe { to_array.value_unchecked(i) };
- buffer.clear();
- replace_into_string(&mut buffer, string, from, to);
- builder.append_value(&buffer);
+ apply_replace(&mut builder, string, from, to);
}
} else {
for i in 0..len {
// SAFETY: i < len, and no input has a null buffer.
let string = unsafe { string_array.value_unchecked(i) };
let from = unsafe { from_array.value_unchecked(i) };
let to = unsafe { to_array.value_unchecked(i) };
- buffer.clear();
- replace_into_string(&mut buffer, string, from, to);
- builder.append_value(&buffer);
+ apply_replace(&mut builder, string, from, to);
}
}
Ok(Arc::new(builder.finish(nulls)?) as ArrayRef)
}
-/// Helper function to perform string replacement into a reusable String buffer
#[inline]
-fn replace_into_string(buffer: &mut String, string: &str, from: &str, to: &str) {
+fn apply_replace<B: BulkNullStringArrayBuilder>(
+ builder: &mut B,
+ string: &str,
+ from: &str,
+ to: &str,
+) {
if from.is_empty() {
- // When from is empty, insert 'to' at the beginning, between each character, and at the end
- // This matches the behavior of str::replace()
- buffer.push_str(to);
- for ch in string.chars() {
- buffer.push(ch);
- buffer.push_str(to);
- }
+ // Empty `from`: insert `to` before each character and at both ends
+ builder.append_with(|w| {
+ w.write_str(to);
+ for ch in string.chars() {
+ w.write_char(ch);
Review Comment:
Wondering about the `from.is_empty()` branch — the per-write trade-off looks unusually unfavorable here. Is it worth adding a `from_empty` benchmark case?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#issuecomment-4442396113
Benchmark results look good: https://github.com/apache/datafusion/pull/22029#issuecomment-4441795645
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on code in PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#discussion_r3235381723
##########
datafusion/functions/src/strings.rs:
##########
@@ -673,18 +911,123 @@ impl StringViewArrayBuilder {
}
}
+/// [`StringWriter`] for [`StringViewArrayBuilder`].
+///
+/// The writer accumulates the first up-to-12 bytes of a row in a stack
+/// buffer; if the row stays inline-sized, it never touches the data block.
+/// On the first write that would exceed 12 bytes, the stack buffer is
+/// spilled into the builder's in-progress block and subsequent writes go
+/// directly there.
+pub(crate) struct StringViewWriter<'a> {
+ inline_buf: [u8; 12],
+ inline_len: u8,
+ /// `None` while the row fits inline; becomes `Some(start)` (offset of
+ /// the row's first byte in `in_progress`) at first spill.
+ spill_cursor: Option<usize>,
+ builder: &'a mut StringViewArrayBuilder,
+}
+
+impl StringWriter for StringViewWriter<'_> {
+ #[inline]
+ fn write_str(&mut self, s: &str) {
+ let bytes = s.as_bytes();
+ match self.spill_cursor {
+ None => {
+ let inline_len = self.inline_len as usize;
+ let new_len = inline_len + bytes.len();
+ if new_len <= 12 {
+ self.inline_buf[inline_len..new_len].copy_from_slice(bytes);
+ self.inline_len = new_len as u8;
+ } else {
+ // First spill of this row: reserve capacity (which may
+ // flush the current block — safe, no row-data is in it
+ // yet for this row), copy the buffered prefix, then
+ // write the new bytes.
+ self.builder.ensure_long_capacity(new_len as u32);
+ let cursor = self.builder.in_progress.len();
+ self.builder
+ .in_progress
+ .extend_from_slice(&self.inline_buf[..inline_len]);
+ self.builder.in_progress.extend_from_slice(bytes);
+ self.spill_cursor = Some(cursor);
+ }
+ }
+ Some(_) => {
+ self.builder.in_progress.extend_from_slice(bytes);
+ }
+ }
+ }
+
+ #[inline]
+ fn write_char(&mut self, c: char) {
+ let len = c.len_utf8();
+ match self.spill_cursor {
+ None => {
+ let inline_len = self.inline_len as usize;
+ let new_len = inline_len + len;
+ if new_len <= 12 {
+ c.encode_utf8(&mut self.inline_buf[inline_len..new_len]);
+ self.inline_len = new_len as u8;
+ } else {
+ self.builder.ensure_long_capacity(new_len as u32);
+ let cursor = self.builder.in_progress.len();
+ self.builder
+ .in_progress
+ .extend_from_slice(&self.inline_buf[..inline_len]);
+ push_char_to_vec(&mut self.builder.in_progress, c);
+ self.spill_cursor = Some(cursor);
+ }
+ }
+ Some(_) => {
+ push_char_to_vec(&mut self.builder.in_progress, c);
+ }
+ }
+ }
+}
+
+#[inline]
+fn push_char_to_vec(v: &mut Vec<u8>, c: char) {
Review Comment:
Cool -- I tried this out and it seems that it doesn't regress performance. I'll switch to the safe variant and re-run the benchmarks via the bot to be sure.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on code in PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#discussion_r3235432474
##########
datafusion/functions/src/strings.rs:
##########
@@ -673,18 +911,123 @@ impl StringViewArrayBuilder {
}
}
+/// [`StringWriter`] for [`StringViewArrayBuilder`].
+///
+/// The writer accumulates the first up-to-12 bytes of a row in a stack
+/// buffer; if the row stays inline-sized, it never touches the data block.
+/// On the first write that would exceed 12 bytes, the stack buffer is
+/// spilled into the builder's in-progress block and subsequent writes go
+/// directly there.
+pub(crate) struct StringViewWriter<'a> {
Review Comment:
Yeah, definitely -- although offhand I'd think we won't be able to get a ton of value from the arrow-rs versions, unless we're able to push all of our StringBuilder upstream... But still might be useful for Arrow separately from DF.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#issuecomment-4450634164
I took a look at the cleanups -- looks great to me. Thanks @neilconway
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on code in PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#discussion_r3211160908
##########
datafusion/functions/src/string/replace.rs:
##########
@@ -230,71 +226,77 @@ fn replace<T: OffsetSizeTrait>(args: &[ArrayRef]) -> Result<ArrayRef> {
let string = unsafe { string_array.value_unchecked(i) };
let from = unsafe { from_array.value_unchecked(i) };
let to = unsafe { to_array.value_unchecked(i) };
- buffer.clear();
- replace_into_string(&mut buffer, string, from, to);
- builder.append_value(&buffer);
+ apply_replace(&mut builder, string, from, to);
}
} else {
for i in 0..len {
// SAFETY: i < len, and no input has a null buffer.
let string = unsafe { string_array.value_unchecked(i) };
let from = unsafe { from_array.value_unchecked(i) };
let to = unsafe { to_array.value_unchecked(i) };
- buffer.clear();
- replace_into_string(&mut buffer, string, from, to);
- builder.append_value(&buffer);
+ apply_replace(&mut builder, string, from, to);
}
}
Ok(Arc::new(builder.finish(nulls)?) as ArrayRef)
}
-/// Helper function to perform string replacement into a reusable String buffer
#[inline]
-fn replace_into_string(buffer: &mut String, string: &str, from: &str, to: &str) {
+fn apply_replace<B: BulkNullStringArrayBuilder>(
+ builder: &mut B,
+ string: &str,
+ from: &str,
+ to: &str,
+) {
if from.is_empty() {
- // When from is empty, insert 'to' at the beginning, between each character, and at the end
- // This matches the behavior of str::replace()
- buffer.push_str(to);
- for ch in string.chars() {
- buffer.push(ch);
- buffer.push_str(to);
- }
+ // Empty `from`: insert `to` before each character and at both ends
+ builder.append_with(|w| {
+ w.write_str(to);
+ for ch in string.chars() {
+ w.write_char(ch);
Review Comment:
Really interesting! Thanks for raising this.
I didn't quite follow your comment about the per-write tradeoff: I don't think there's anything fundamental about `append_with` that should be slower for the many-small-writes case (and we still are able to avoid a final `memcpy`). However, I can reproduce the significant slowdown you suggested for the "empty `from`" case. I dug into why, and it seems that repeatedly extending an Arrow `MutableBuffer` is relatively slow: `StringWriter::write_str()` does `MutableBuffer::extend_from_slice(&[byte])`, which results in a libc `memcpy` for every call, which is obviously slower than per-char `String::push(c)`, as the original code does. I don't think `MutableBuffer::extend_from_slice(&[byte])` is inherently slow, but there was enough helper functions / abstractions here that LLVM didn't inline, which lead to the per-call `memcpy`.
A few options:
1. Ignore it, because `replace` with empty-from is a corner-case. But it's unfortunate to leave `append_with` with a performance footgun like this.
2. Fix it by reverting to a `mut String` buffer for the empty-from case. Fixes this specific workload but doesn't fix the underlyling issue in `StringWriter`.
3. Optimize `StringWriter` for small-string writes.
I've implemented #3. A combination of special-casing the string length and marking functions as `#[inline(always)]` appears to convince LLVM to vectorize this code path, which is a nice win (30-40% faster than `main` for the empty-from). All the inlining might in theory cause code block for other callers but it doesn't appear to regress any other `replace` benchmarks, at least.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "lyne7-sc (via GitHub)" <gi...@apache.org>.
lyne7-sc commented on code in PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#discussion_r3199437877
##########
datafusion/functions/src/string/replace.rs:
##########
@@ -230,71 +226,77 @@ fn replace<T: OffsetSizeTrait>(args: &[ArrayRef]) -> Result<ArrayRef> {
let string = unsafe { string_array.value_unchecked(i) };
let from = unsafe { from_array.value_unchecked(i) };
let to = unsafe { to_array.value_unchecked(i) };
- buffer.clear();
- replace_into_string(&mut buffer, string, from, to);
- builder.append_value(&buffer);
+ apply_replace(&mut builder, string, from, to);
}
} else {
for i in 0..len {
// SAFETY: i < len, and no input has a null buffer.
let string = unsafe { string_array.value_unchecked(i) };
let from = unsafe { from_array.value_unchecked(i) };
let to = unsafe { to_array.value_unchecked(i) };
- buffer.clear();
- replace_into_string(&mut buffer, string, from, to);
- builder.append_value(&buffer);
+ apply_replace(&mut builder, string, from, to);
}
}
Ok(Arc::new(builder.finish(nulls)?) as ArrayRef)
}
-/// Helper function to perform string replacement into a reusable String buffer
#[inline]
-fn replace_into_string(buffer: &mut String, string: &str, from: &str, to: &str) {
+fn apply_replace<B: BulkNullStringArrayBuilder>(
+ builder: &mut B,
+ string: &str,
+ from: &str,
+ to: &str,
+) {
if from.is_empty() {
- // When from is empty, insert 'to' at the beginning, between each character, and at the end
- // This matches the behavior of str::replace()
- buffer.push_str(to);
- for ch in string.chars() {
- buffer.push(ch);
- buffer.push_str(to);
- }
+ // Empty `from`: insert `to` before each character and at both ends
+ builder.append_with(|w| {
+ w.write_str(to);
+ for ch in string.chars() {
+ w.write_char(ch);
Review Comment:
Wondering about the `from.is_empty()` branch — the per-write trade-off looks unusually unfavorable here. The per-call overhead might dominate the saved memcpy, and the benchmark table doesn't seem to cover this path. Is it worth adding a `from_empty` benchmark case?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "lyne7-sc (via GitHub)" <gi...@apache.org>.
lyne7-sc commented on code in PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#discussion_r3199742463
##########
datafusion/functions/src/string/replace.rs:
##########
@@ -230,71 +226,77 @@ fn replace<T: OffsetSizeTrait>(args: &[ArrayRef]) -> Result<ArrayRef> {
let string = unsafe { string_array.value_unchecked(i) };
let from = unsafe { from_array.value_unchecked(i) };
let to = unsafe { to_array.value_unchecked(i) };
- buffer.clear();
- replace_into_string(&mut buffer, string, from, to);
- builder.append_value(&buffer);
+ apply_replace(&mut builder, string, from, to);
}
} else {
for i in 0..len {
// SAFETY: i < len, and no input has a null buffer.
let string = unsafe { string_array.value_unchecked(i) };
let from = unsafe { from_array.value_unchecked(i) };
let to = unsafe { to_array.value_unchecked(i) };
- buffer.clear();
- replace_into_string(&mut buffer, string, from, to);
- builder.append_value(&buffer);
+ apply_replace(&mut builder, string, from, to);
}
}
Ok(Arc::new(builder.finish(nulls)?) as ArrayRef)
}
-/// Helper function to perform string replacement into a reusable String buffer
#[inline]
-fn replace_into_string(buffer: &mut String, string: &str, from: &str, to: &str) {
+fn apply_replace<B: BulkNullStringArrayBuilder>(
+ builder: &mut B,
+ string: &str,
+ from: &str,
+ to: &str,
+) {
if from.is_empty() {
- // When from is empty, insert 'to' at the beginning, between each character, and at the end
- // This matches the behavior of str::replace()
- buffer.push_str(to);
- for ch in string.chars() {
- buffer.push(ch);
- buffer.push_str(to);
- }
+ // Empty `from`: insert `to` before each character and at both ends
+ builder.append_with(|w| {
+ w.write_str(to);
+ for ch in string.chars() {
+ w.write_char(ch);
Review Comment:
FYI, I ran the benchmarks locally for the empty_from cases and it does look like this branch causes a regression.
```
group main pr-22029-bench
----- ---- --------------
replace size=1024/replace_string_empty_from [size=1024, str_len=128, nulls=0.2] 1.00 280.0±1.26µs ? ?/sec 1.41 394.3±2.06µs ? ?/sec
replace size=1024/replace_string_empty_from [size=1024, str_len=128, nulls=0] 1.00 339.0±2.10µs ? ?/sec 1.48 502.4±11.19µs ? ?/sec
replace size=1024/replace_string_empty_from [size=1024, str_len=32, nulls=0.2] 1.00 78.9±0.71µs ? ?/sec 1.27 100.1±0.64µs ? ?/sec
replace size=1024/replace_string_empty_from [size=1024, str_len=32, nulls=0] 1.00 97.4±0.59µs ? ?/sec 1.33 129.8±2.01µs ? ?/sec
replace size=1024/replace_string_view_empty_from [size=1024, str_len=128, nulls=0.2] 1.00 281.4±3.73µs ? ?/sec 1.41 396.2±6.00µs ? ?/sec
replace size=1024/replace_string_view_empty_from [size=1024, str_len=128, nulls=0] 1.00 338.2±2.78µs ? ?/sec 1.47 498.1±4.54µs ? ?/sec
replace size=1024/replace_string_view_empty_from [size=1024, str_len=32, nulls=0.2] 1.00 78.3±0.18µs ? ?/sec 1.28 100.5±0.28µs ? ?/sec
replace size=1024/replace_string_view_empty_from [size=1024, str_len=32, nulls=0] 1.00 97.8±0.70µs ? ?/sec 1.31 128.0±1.11µs ? ?/sec
replace size=4096/replace_string_empty_from [size=4096, str_len=128, nulls=0.2] 1.00 1140.6±6.91µs ? ?/sec 1.43 1625.6±11.65µs ? ?/sec
replace size=4096/replace_string_empty_from [size=4096, str_len=128, nulls=0] 1.00 1411.9±17.41µs ? ?/sec 1.50 2.1±0.01ms ? ?/sec
replace size=4096/replace_string_empty_from [size=4096, str_len=32, nulls=0.2] 1.00 317.6±2.31µs ? ?/sec 1.28 405.6±1.73µs ? ?/sec
replace size=4096/replace_string_empty_from [size=4096, str_len=32, nulls=0] 1.00 396.4±3.03µs ? ?/sec 1.29 511.2±5.86µs ? ?/sec
replace size=4096/replace_string_view_empty_from [size=4096, str_len=128, nulls=0.2] 1.00 1147.6±9.87µs ? ?/sec 1.42 1624.8±13.37µs ? ?/sec
replace size=4096/replace_string_view_empty_from [size=4096, str_len=128, nulls=0] 1.00 1433.2±23.33µs ? ?/sec 1.46 2.1±0.01ms ? ?/sec
replace size=4096/replace_string_view_empty_from [size=4096, str_len=32, nulls=0.2] 1.00 318.2±1.08µs ? ?/sec 1.29 409.3±2.62µs ? ?/sec
replace size=4096/replace_string_view_empty_from [size=4096, str_len=32, nulls=0] 1.00 397.6±5.38µs ? ?/sec 1.30 517.0±6.47µs ? ?/sec
```
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "lyne7-sc (via GitHub)" <gi...@apache.org>.
lyne7-sc commented on code in PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#discussion_r3213307556
##########
datafusion/functions/src/string/replace.rs:
##########
@@ -230,71 +226,77 @@ fn replace<T: OffsetSizeTrait>(args: &[ArrayRef]) -> Result<ArrayRef> {
let string = unsafe { string_array.value_unchecked(i) };
let from = unsafe { from_array.value_unchecked(i) };
let to = unsafe { to_array.value_unchecked(i) };
- buffer.clear();
- replace_into_string(&mut buffer, string, from, to);
- builder.append_value(&buffer);
+ apply_replace(&mut builder, string, from, to);
}
} else {
for i in 0..len {
// SAFETY: i < len, and no input has a null buffer.
let string = unsafe { string_array.value_unchecked(i) };
let from = unsafe { from_array.value_unchecked(i) };
let to = unsafe { to_array.value_unchecked(i) };
- buffer.clear();
- replace_into_string(&mut buffer, string, from, to);
- builder.append_value(&buffer);
+ apply_replace(&mut builder, string, from, to);
}
}
Ok(Arc::new(builder.finish(nulls)?) as ArrayRef)
}
-/// Helper function to perform string replacement into a reusable String buffer
#[inline]
-fn replace_into_string(buffer: &mut String, string: &str, from: &str, to: &str) {
+fn apply_replace<B: BulkNullStringArrayBuilder>(
+ builder: &mut B,
+ string: &str,
+ from: &str,
+ to: &str,
+) {
if from.is_empty() {
- // When from is empty, insert 'to' at the beginning, between each character, and at the end
- // This matches the behavior of str::replace()
- buffer.push_str(to);
- for ch in string.chars() {
- buffer.push(ch);
- buffer.push_str(to);
- }
+ // Empty `from`: insert `to` before each character and at both ends
+ builder.append_with(|w| {
+ w.write_str(to);
+ for ch in string.chars() {
+ w.write_char(ch);
Review Comment:
Really nice work on this! Thanks for diving deep into the root cause and the detailed explanation. Makes sense to me.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on code in PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#discussion_r3235245367
##########
datafusion/functions/src/strings.rs:
##########
@@ -673,18 +911,123 @@ impl StringViewArrayBuilder {
}
}
+/// [`StringWriter`] for [`StringViewArrayBuilder`].
+///
+/// The writer accumulates the first up-to-12 bytes of a row in a stack
+/// buffer; if the row stays inline-sized, it never touches the data block.
+/// On the first write that would exceed 12 bytes, the stack buffer is
+/// spilled into the builder's in-progress block and subsequent writes go
+/// directly there.
+pub(crate) struct StringViewWriter<'a> {
+ inline_buf: [u8; 12],
+ inline_len: u8,
+ /// `None` while the row fits inline; becomes `Some(start)` (offset of
+ /// the row's first byte in `in_progress`) at first spill.
+ spill_cursor: Option<usize>,
+ builder: &'a mut StringViewArrayBuilder,
+}
+
+impl StringWriter for StringViewWriter<'_> {
+ #[inline]
+ fn write_str(&mut self, s: &str) {
+ let bytes = s.as_bytes();
+ match self.spill_cursor {
+ None => {
+ let inline_len = self.inline_len as usize;
+ let new_len = inline_len + bytes.len();
+ if new_len <= 12 {
+ self.inline_buf[inline_len..new_len].copy_from_slice(bytes);
+ self.inline_len = new_len as u8;
+ } else {
+ // First spill of this row: reserve capacity (which may
+ // flush the current block — safe, no row-data is in it
+ // yet for this row), copy the buffered prefix, then
+ // write the new bytes.
+ self.builder.ensure_long_capacity(new_len as u32);
+ let cursor = self.builder.in_progress.len();
+ self.builder
+ .in_progress
+ .extend_from_slice(&self.inline_buf[..inline_len]);
+ self.builder.in_progress.extend_from_slice(bytes);
+ self.spill_cursor = Some(cursor);
+ }
+ }
+ Some(_) => {
+ self.builder.in_progress.extend_from_slice(bytes);
+ }
+ }
+ }
+
+ #[inline]
+ fn write_char(&mut self, c: char) {
+ let len = c.len_utf8();
+ match self.spill_cursor {
+ None => {
+ let inline_len = self.inline_len as usize;
+ let new_len = inline_len + len;
+ if new_len <= 12 {
+ c.encode_utf8(&mut self.inline_buf[inline_len..new_len]);
+ self.inline_len = new_len as u8;
+ } else {
+ self.builder.ensure_long_capacity(new_len as u32);
+ let cursor = self.builder.in_progress.len();
+ self.builder
+ .in_progress
+ .extend_from_slice(&self.inline_buf[..inline_len]);
+ push_char_to_vec(&mut self.builder.in_progress, c);
+ self.spill_cursor = Some(cursor);
+ }
+ }
+ Some(_) => {
+ push_char_to_vec(&mut self.builder.in_progress, c);
+ }
+ }
+ }
+}
+
+#[inline]
+fn push_char_to_vec(v: &mut Vec<u8>, c: char) {
+ let len = c.len_utf8();
+ let old_len = v.len();
+ v.reserve(len);
+ // SAFETY: we reserved `len` bytes above, write valid UTF-8 into those
+ // bytes, then update the initialized length to include them.
+ unsafe {
+ let dst = v.as_mut_ptr().add(old_len);
+ if len == 1 {
+ *dst = c as u8;
+ } else {
+ c.encode_utf8(std::slice::from_raw_parts_mut(dst, len));
+ }
+ v.set_len(old_len + len);
+ }
+}
+
/// Trait abstracting over the bulk-NULL string array builders.
///
/// Similar to Arrow's `StringLikeArrayBuilder`, this allows generic dispatch
/// over the three string array types (Utf8, LargeUtf8, Utf8View) when the
/// function body is uniform across them.
pub(crate) trait BulkNullStringArrayBuilder {
+ /// Per-builder concrete writer type, exposed as a GAT so generic callers
+ /// can use the inherent (non-`dyn`) writer methods without vtable
+ /// dispatch.
+ type Writer<'a>: StringWriter
+ where
+ Self: 'a;
+
fn append_value(&mut self, value: &str);
Review Comment:
Yep, makes sense -- I consolidated most of the docs in the trait and added back-links.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#issuecomment-4442635030
run benchmark replace
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#issuecomment-4441652172
🤖 Criterion benchmark running (GKE) | [trigger](https://github.com/apache/datafusion/pull/22029#issuecomment-4441630010)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c4441630010-32-kbkx2 6.12.68+ #1 SMP Wed Apr 1 02:23:28 UTC 2026 aarch64 GNU/Linux`
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
Comparing neilc/perf-builder-append-writer (7708aa2dc61271423a5c334bd2e2025b5e275133) to b76970b (merge-base) [diff](https://github.com/apache/datafusion/compare/b76970b4f979111eb84337c778685c9df0f9cea9..7708aa2dc61271423a5c334bd2e2025b5e275133)
BENCH_NAME=replace
BENCH_COMMAND=cargo bench --features=parquet --bench replace
BENCH_FILTER=
Results will be posted here when complete
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on code in PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#discussion_r3236859837
##########
datafusion/functions/src/strings.rs:
##########
@@ -673,18 +911,123 @@ impl StringViewArrayBuilder {
}
}
+/// [`StringWriter`] for [`StringViewArrayBuilder`].
+///
+/// The writer accumulates the first up-to-12 bytes of a row in a stack
+/// buffer; if the row stays inline-sized, it never touches the data block.
+/// On the first write that would exceed 12 bytes, the stack buffer is
+/// spilled into the builder's in-progress block and subsequent writes go
+/// directly there.
+pub(crate) struct StringViewWriter<'a> {
+ inline_buf: [u8; 12],
+ inline_len: u8,
+ /// `None` while the row fits inline; becomes `Some(start)` (offset of
+ /// the row's first byte in `in_progress`) at first spill.
+ spill_cursor: Option<usize>,
+ builder: &'a mut StringViewArrayBuilder,
+}
+
+impl StringWriter for StringViewWriter<'_> {
+ #[inline]
+ fn write_str(&mut self, s: &str) {
+ let bytes = s.as_bytes();
+ match self.spill_cursor {
+ None => {
+ let inline_len = self.inline_len as usize;
+ let new_len = inline_len + bytes.len();
+ if new_len <= 12 {
+ self.inline_buf[inline_len..new_len].copy_from_slice(bytes);
+ self.inline_len = new_len as u8;
+ } else {
+ // First spill of this row: reserve capacity (which may
+ // flush the current block — safe, no row-data is in it
+ // yet for this row), copy the buffered prefix, then
+ // write the new bytes.
+ self.builder.ensure_long_capacity(new_len as u32);
+ let cursor = self.builder.in_progress.len();
+ self.builder
+ .in_progress
+ .extend_from_slice(&self.inline_buf[..inline_len]);
+ self.builder.in_progress.extend_from_slice(bytes);
+ self.spill_cursor = Some(cursor);
+ }
+ }
+ Some(_) => {
+ self.builder.in_progress.extend_from_slice(bytes);
+ }
+ }
+ }
+
+ #[inline]
+ fn write_char(&mut self, c: char) {
+ let len = c.len_utf8();
+ match self.spill_cursor {
+ None => {
+ let inline_len = self.inline_len as usize;
+ let new_len = inline_len + len;
+ if new_len <= 12 {
+ c.encode_utf8(&mut self.inline_buf[inline_len..new_len]);
+ self.inline_len = new_len as u8;
+ } else {
+ self.builder.ensure_long_capacity(new_len as u32);
+ let cursor = self.builder.in_progress.len();
+ self.builder
+ .in_progress
+ .extend_from_slice(&self.inline_buf[..inline_len]);
+ push_char_to_vec(&mut self.builder.in_progress, c);
+ self.spill_cursor = Some(cursor);
+ }
+ }
+ Some(_) => {
+ push_char_to_vec(&mut self.builder.in_progress, c);
+ }
+ }
+ }
+}
+
+#[inline]
+fn push_char_to_vec(v: &mut Vec<u8>, c: char) {
Review Comment:
Benchmark results seem reasonable!
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#issuecomment-4444527481
@alamb Amazing, thank you for the review! I believe I addressed all the comments; PTAL when you get a chance.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on code in PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#discussion_r3211160908
##########
datafusion/functions/src/string/replace.rs:
##########
@@ -230,71 +226,77 @@ fn replace<T: OffsetSizeTrait>(args: &[ArrayRef]) -> Result<ArrayRef> {
let string = unsafe { string_array.value_unchecked(i) };
let from = unsafe { from_array.value_unchecked(i) };
let to = unsafe { to_array.value_unchecked(i) };
- buffer.clear();
- replace_into_string(&mut buffer, string, from, to);
- builder.append_value(&buffer);
+ apply_replace(&mut builder, string, from, to);
}
} else {
for i in 0..len {
// SAFETY: i < len, and no input has a null buffer.
let string = unsafe { string_array.value_unchecked(i) };
let from = unsafe { from_array.value_unchecked(i) };
let to = unsafe { to_array.value_unchecked(i) };
- buffer.clear();
- replace_into_string(&mut buffer, string, from, to);
- builder.append_value(&buffer);
+ apply_replace(&mut builder, string, from, to);
}
}
Ok(Arc::new(builder.finish(nulls)?) as ArrayRef)
}
-/// Helper function to perform string replacement into a reusable String buffer
#[inline]
-fn replace_into_string(buffer: &mut String, string: &str, from: &str, to: &str) {
+fn apply_replace<B: BulkNullStringArrayBuilder>(
+ builder: &mut B,
+ string: &str,
+ from: &str,
+ to: &str,
+) {
if from.is_empty() {
- // When from is empty, insert 'to' at the beginning, between each character, and at the end
- // This matches the behavior of str::replace()
- buffer.push_str(to);
- for ch in string.chars() {
- buffer.push(ch);
- buffer.push_str(to);
- }
+ // Empty `from`: insert `to` before each character and at both ends
+ builder.append_with(|w| {
+ w.write_str(to);
+ for ch in string.chars() {
+ w.write_char(ch);
Review Comment:
Really interesting! Thanks for raising this.
I didn't quite follow your comment about the per-write tradeoff: I don't think there's anything fundamental about `append_with` that should be slower for the many-small-writes case (and we still are able to avoid a final `memcpy`). However, I can reproduce the significant slowdown you suggested for the "empty `from`" case. I dug into why, and it seems that repeatedly extending an Arrow `MutableBuffer` is relatively slow: `StringWriter::write_str()` does `MutableBuffer::extend_from_slice(&[byte])`, which results in a libc `memcpy` for every call, which is obviously slower than per-char `String::push(c)`, as the original code does.
Arguably that's a performance bug in Arrow.
A few options:
1. Ignore it, because `replace` with empty-from is a corner-case. But it's unfortunate to leave `append_with` with a performance footgun like this.
2. Fix it by reverting to a `mut String` buffer for the empty-from case. Fixes this specific workload but doesn't fix the underlyling issue in `StringWriter`.
3. Optimize `StringWriter` for small-string writes.
I've implemented #3. A combination of special-casing the string length and marking functions as `#[inline(always)]` appears to convince LLVM to vectorize this code path, which is a nice win (30-40% faster than `main` for the empty-from). All the inlining might in theory cause code block for other callers but it doesn't appear to regress any other `replace` benchmarks, at least.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Add `append_with` to string builders, use in `replace` [datafusion]
Posted by "lyne7-sc (via GitHub)" <gi...@apache.org>.
lyne7-sc commented on code in PR #22029:
URL: https://github.com/apache/datafusion/pull/22029#discussion_r3199437877
##########
datafusion/functions/src/string/replace.rs:
##########
@@ -230,71 +226,77 @@ fn replace<T: OffsetSizeTrait>(args: &[ArrayRef]) -> Result<ArrayRef> {
let string = unsafe { string_array.value_unchecked(i) };
let from = unsafe { from_array.value_unchecked(i) };
let to = unsafe { to_array.value_unchecked(i) };
- buffer.clear();
- replace_into_string(&mut buffer, string, from, to);
- builder.append_value(&buffer);
+ apply_replace(&mut builder, string, from, to);
}
} else {
for i in 0..len {
// SAFETY: i < len, and no input has a null buffer.
let string = unsafe { string_array.value_unchecked(i) };
let from = unsafe { from_array.value_unchecked(i) };
let to = unsafe { to_array.value_unchecked(i) };
- buffer.clear();
- replace_into_string(&mut buffer, string, from, to);
- builder.append_value(&buffer);
+ apply_replace(&mut builder, string, from, to);
}
}
Ok(Arc::new(builder.finish(nulls)?) as ArrayRef)
}
-/// Helper function to perform string replacement into a reusable String buffer
#[inline]
-fn replace_into_string(buffer: &mut String, string: &str, from: &str, to: &str) {
+fn apply_replace<B: BulkNullStringArrayBuilder>(
+ builder: &mut B,
+ string: &str,
+ from: &str,
+ to: &str,
+) {
if from.is_empty() {
- // When from is empty, insert 'to' at the beginning, between each character, and at the end
- // This matches the behavior of str::replace()
- buffer.push_str(to);
- for ch in string.chars() {
- buffer.push(ch);
- buffer.push_str(to);
- }
+ // Empty `from`: insert `to` before each character and at both ends
+ builder.append_with(|w| {
+ w.write_str(to);
+ for ch in string.chars() {
+ w.write_char(ch);
Review Comment:
Wondering about the `from.is_empty()` branch — the per-write trade-off looks unusually unfavorable here. The per-call overhead might dominate the saved memcpy. Is it worth adding a `from_empty` benchmark case?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org