mbutrovich opened a new issue, #11717: URL: https://github.com/apache/arrow-rs/issues/11717
### Is your feature request related to a problem or challenge? [`PrimitiveBuilder::finish`](https://github.com/apache/arrow-rs/blob/3327fbef1c3381a149e9a413a5bb22813e11639e/arrow-array/src/builder/primitive_builder.rs#L365-L376) builds an `ArrayData` and converts it into a `PrimitiveArray`. As #9128 says, an `ArrayData` costs at least one allocation, for its `Vec` of buffers. Every `finish` pays that cost, so it adds up for callers that finish many small arrays. [`BooleanBuilder::finish`](https://github.com/apache/arrow-rs/blob/3327fbef1c3381a149e9a413a5bb22813e11639e/arrow-array/src/builder/boolean_builder.rs#L162-L173), [`GenericByteBuilder::finish`](https://github.com/apache/arrow-rs/blob/3327fbef1c3381a149e9a413a5bb22813e11639e/arrow-array/src/builder/generic_bytes_builder.rs#L216-L228) and [`FixedSizeBinaryBuilder::finish`](https://github.com/apache/arrow-rs/blob/3327fbef1c3381a149e9a413a5bb22813e11639e/arrow-array/src/builder/fixed_size_binary_builder.rs#L132-L141) do the same. I haven't checked the other builders. In a microbenchmark, `UInt64Builder` costs a fixed 24-28 ns per array more than building a `Vec<u64>` and calling `UInt64Array::new`, for arrays of up to 64 values. Both versions append their values in bulk, with `append_trusted_len_iter` on the builder and `Vec::extend` on the `Vec`. They differ only in the builder wrapper and `finish`. These are two runs of the program below: | Values per array | Builder + `finish` | `Vec` + `UInt64Array::new` | Difference | | --- | --- | --- | --- | | 1 | 42.6 ns, 43.0 ns | 15.0 ns, 18.9 ns | 27.6 ns, 24.1 ns | | 8 | 43.9 ns, 45.4 ns | 16.0 ns, 19.4 ns | 27.9 ns, 26.0 ns | | 64 | 54.7 ns, 55.0 ns | 26.4 ns, 30.5 ns | 28.3 ns, 24.5 ns | | 512 | 73.0 ns, 78.9 ns | 61.2 ns, 63.2 ns | 11.8 ns, 15.7 ns | | 4096 | 291.7 ns, 341.0 ns | 328.1 ns, 337.0 ns | -36.4 ns, 4.0 ns | At 512 values and more, filling the array dominates and the runs vary more than the difference. DataFusion's sort-merge join finishes two `UInt64Builder`s for each chunk of output indices ([code](https://github.com/apache/datafusion/blob/287d0a00b83674d15435aa8a1597f7309b30180d/datafusion/physical-plan/src/joins/sort_merge_join/materializing_stream.rs#L1590-L1594)), and a chunk can hold a few rows. On top of apache/datafusion#26277, I replaced those builders with a `Vec<u64>`, a `NullBufferBuilder` and `UInt64Array::try_new`. That made its benchmark with 8-row chunks 19% faster. When I built the same `Vec`-backed arrays through `ArrayData` again, that gain fell to 4%. ### Describe the solution you'd like Build the typed array directly in `finish`, as #9129, #9294, #9497 and #10261 did for other code paths. For `PrimitiveBuilder`, that could look like this: ```rust pub fn finish(&mut self) -> PrimitiveArray<T> { let nulls = self.null_buffer_builder.finish(); let values = std::mem::take(&mut self.values_builder).into(); PrimitiveArray::new(values, nulls).with_data_type(self.data_type.clone()) } ``` The builder already keeps `values` and `nulls` the same length, and `with_data_type` checks the data type. So this keeps what `build_unchecked` and `From<ArrayData>` check today, without the allocation. ### Describe alternatives you've considered Callers can use `Vec` directly. The [`PrimitiveBuilder` docs](https://github.com/apache/arrow-rs/blob/3327fbef1c3381a149e9a413a5bb22813e11639e/arrow-array/src/builder/primitive_builder.rs#L100-L124) recommend that, and #7591 was closed in favor of it. But the same docs recommend the builder when null positions aren't known up front, and those callers still pay this cost on every `finish`. ### Additional context I measured on an Apple M5 Max (aarch64) with rustc 1.99.0 and arrow-array 60.0.0, in release with `lto = true` and `codegen-units = 1`. Each number is the best of seven passes over 2^24 values. I haven't measured on x86_64. <details> <summary>Microbenchmark</summary> ```rust use arrow_array::builder::UInt64Builder; use arrow_array::UInt64Array; use std::hint::black_box; use std::time::Instant; #[inline(never)] fn builder(k: usize, base: u64) -> UInt64Array { let mut b = UInt64Builder::with_capacity(k); // SAFETY: Range<u64> has an exact size_hint. unsafe { b.append_trusted_len_iter(base..base + k as u64) }; b.finish() } #[inline(never)] fn vec_new(k: usize, base: u64) -> UInt64Array { let mut v = Vec::with_capacity(k); v.extend(base..base + k as u64); UInt64Array::new(v.into(), None) } fn time(name: &str, k: usize, f: fn(usize, u64) -> UInt64Array) { let chunks = (1 << 24) / k; let mut best = f64::MAX; for _ in 0..7 { let t = Instant::now(); let mut s = 0usize; for c in 0..chunks { s += black_box(f(black_box(k), c as u64)).len(); } black_box(s); best = best.min(t.elapsed().as_secs_f64() * 1e9 / chunks as f64); } println!("{name:8} k={k:4} {best:7.1} ns/array"); } fn main() { for k in [1, 8, 64, 512, 4096] { time("builder", k, builder); time("vec_new", k, vec_new); } } ``` </details> -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
