You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "mapleFU (via GitHub)" <gi...@apache.org> on 2026/06/02 13:18:04 UTC
[PR] optimize(interleave): implement interleave for FixedSizeList/Map type [arrow-rs]
mapleFU opened a new pull request, #10046:
URL: https://github.com/apache/arrow-rs/pull/10046
# Which issue does this PR close?
- Closes #10045 .
# Rationale for this change
Implement interleave for Map/FSL type.
Note: This might a slow implementation for FSL. For map it's a struct type, and at would have two childs. So even if it's `Map<i32, i32>`, it wouldn't be slower than before.
For FSL, if it's fixed sized list with short i32 list, it may hit the problem in https://github.com/apache/arrow-rs/pull/10025 , making them use same code to handle list is better.
# What changes are included in this PR?
Implement interleave for Map/FSL type.
# Are these changes tested?
1. Test covered by existing
2. benchmark is provided
# 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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] optimize(interleave): implement interleave for FixedSizeList/Map type [arrow-rs]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on code in PR #10046:
URL: https://github.com/apache/arrow-rs/pull/10046#discussion_r3396491118
##########
arrow-select/src/interleave.rs:
##########
@@ -513,6 +517,81 @@ fn interleave_list<O: OffsetSizeTrait>(
Ok(Arc::new(list_array))
}
+fn interleave_fixed_size_list(
+ values: &[&dyn Array],
+ indices: &[(usize, usize)],
+ field: &FieldRef,
+ size: i32,
+) -> Result<ArrayRef, ArrowError> {
+ let interleaved = Interleave::<'_, FixedSizeListArray>::new(values, indices);
+ let capacity = indices.len() * size as usize;
+
+ macro_rules! fsl_primitive_helper {
+ ($t:ty) => {
+ interleave_list_like_primitive_child::<FixedSizeListArray, $t>(
+ &interleaved,
+ indices,
+ capacity,
+ field.data_type(),
+ )
+ };
+ }
+
+ let interleaved_values = downcast_primitive! {
+ field.data_type() => (fsl_primitive_helper),
+ _ => {
+ interleave_list_like_child(&interleaved, indices, capacity)?
+ }
+ };
+
+ let array = FixedSizeListArray::new(field.clone(), size, interleaved_values, interleaved.nulls);
+ Ok(Arc::new(array))
+}
+
+fn interleave_map(
Review Comment:
map child is always complex type, so doesn't call the primitive fn
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] optimize(interleave): implement interleave for FixedSizeList/Map type [arrow-rs]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #10046:
URL: https://github.com/apache/arrow-rs/pull/10046#issuecomment-4956039316
🤖 Arrow criterion benchmark completed (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/10046#issuecomment-4955961573)
**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 interleave-fsl-map main
----- ------------------ ----
interleave fixed_size_list<i64,5>(0.0,0.0) 100 [0..100, 100..230, 450..1000] 1.00 485.5±1.87ns ? ?/sec 5.44 2.6±0.01µs ? ?/sec
interleave fixed_size_list<i64,5>(0.0,0.0) 1024 [0..100, 100..230, 450..1000, 0..1000] 1.00 3.0±0.01µs ? ?/sec 5.00 14.8±0.04µs ? ?/sec
interleave fixed_size_list<i64,5>(0.0,0.0) 1024 [0..100, 100..230, 450..1000] 1.00 2.9±0.00µs ? ?/sec 4.88 14.2±0.02µs ? ?/sec
interleave fixed_size_list<i64,5>(0.0,0.0) 400 [0..100, 100..230, 450..1000] 1.00 1268.8±4.83ns ? ?/sec 4.94 6.3±0.01µs ? ?/sec
interleave fixed_size_list<i64,5>(0.1,0.1) 100 [0..100, 100..230, 450..1000] 1.00 2.2±0.03µs ? ?/sec 2.29 5.1±0.02µs ? ?/sec
interleave fixed_size_list<i64,5>(0.1,0.1) 1024 [0..100, 100..230, 450..1000, 0..1000] 1.00 18.6±0.24µs ? ?/sec 1.86 34.6±0.08µs ? ?/sec
interleave fixed_size_list<i64,5>(0.1,0.1) 1024 [0..100, 100..230, 450..1000] 1.00 18.6±0.24µs ? ?/sec 1.84 34.3±0.07µs ? ?/sec
interleave fixed_size_list<i64,5>(0.1,0.1) 400 [0..100, 100..230, 450..1000] 1.00 7.6±0.10µs ? ?/sec 1.91 14.5±0.03µs ? ?/sec
interleave map<utf8,i64>(0.0,5,8) 100 [0..100, 100..230, 450..1000] 1.00 2.5±0.00µs ? ?/sec 3.10 7.8±0.01µs ? ?/sec
interleave map<utf8,i64>(0.0,5,8) 1024 [0..100, 100..230, 450..1000, 0..1000] 1.00 19.0±0.04µs ? ?/sec 2.20 41.6±0.03µs ? ?/sec
interleave map<utf8,i64>(0.0,5,8) 1024 [0..100, 100..230, 450..1000] 1.00 18.8±0.03µs ? ?/sec 2.19 41.2±0.03µs ? ?/sec
interleave map<utf8,i64>(0.0,5,8) 400 [0..100, 100..230, 450..1000] 1.00 7.9±0.02µs ? ?/sec 2.41 19.1±0.03µs ? ?/sec
interleave map<utf8,i64>(0.1,5,8) 100 [0..100, 100..230, 450..1000] 1.00 2.6±0.00µs ? ?/sec 4.04 10.5±0.01µs ? ?/sec
interleave map<utf8,i64>(0.1,5,8) 1024 [0..100, 100..230, 450..1000, 0..1000] 1.00 19.3±0.03µs ? ?/sec 3.28 63.2±0.05µs ? ?/sec
interleave map<utf8,i64>(0.1,5,8) 1024 [0..100, 100..230, 450..1000] 1.00 18.9±0.03µs ? ?/sec 3.29 62.3±0.04µs ? ?/sec
interleave map<utf8,i64>(0.1,5,8) 400 [0..100, 100..230, 450..1000] 1.00 7.9±0.02µs ? ?/sec 3.48 27.4±0.03µs ? ?/sec
```
</p>
</details>
<details><summary>Resource Usage</summary>
**base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 160.0s |
| Peak memory | 15.2 MiB |
| Avg memory | 11.2 MiB |
| CPU user | 155.9s |
| CPU sys | 0.0s |
| Peak spill | 0 B |
**branch**
| Metric | Value |
|--------|-------|
| Wall time | 160.0s |
| Peak memory | 16.0 MiB |
| Avg memory | 11.4 MiB |
| CPU user | 156.2s |
| CPU sys | 0.0s |
| 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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] optimize(interleave): implement interleave for FixedSizeList/Map type [arrow-rs]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on code in PR #10046:
URL: https://github.com/apache/arrow-rs/pull/10046#discussion_r3565850467
##########
arrow-select/src/interleave.rs:
##########
@@ -513,6 +517,81 @@ fn interleave_list<O: OffsetSizeTrait>(
Ok(Arc::new(list_array))
}
+fn interleave_fixed_size_list(
+ values: &[&dyn Array],
+ indices: &[(usize, usize)],
+ field: &FieldRef,
+ size: i32,
+) -> Result<ArrayRef, ArrowError> {
+ let interleaved = Interleave::<'_, FixedSizeListArray>::new(values, indices);
+ let capacity = indices.len() * size as usize;
+
+ macro_rules! fsl_primitive_helper {
+ ($t:ty) => {
+ interleave_list_like_primitive_child::<FixedSizeListArray, $t>(
+ &interleaved,
+ indices,
+ capacity,
+ field.data_type(),
+ )
+ };
+ }
+
+ let interleaved_values = downcast_primitive! {
+ field.data_type() => (fsl_primitive_helper),
+ _ => {
+ interleave_list_like_child(&interleaved, indices, capacity)?
+ }
+ };
+
+ let array = FixedSizeListArray::new(field.clone(), size, interleaved_values, interleaved.nulls);
+ Ok(Arc::new(array))
+}
+
+fn interleave_map(
+ values: &[&dyn Array],
+ indices: &[(usize, usize)],
+ field: &FieldRef,
+ ordered: bool,
+) -> Result<ArrayRef, ArrowError> {
+ let interleaved = Interleave::<'_, MapArray>::new(values, indices);
+
+ let mut capacity = 0usize;
+ let mut offsets = Vec::with_capacity(indices.len() + 1);
Review Comment:
🤔counting `capacity` and offsets in one loop and pushing? The loop might be:
```
for &(array, row) in indices {
let o = interleaved.arrays[array].value_offsets();
let element_len = (o[row + 1] - o[row]) as usize;
capacity += element_len;
if capacity >= i32::MAX {
return Err(...);
}
builder.push_length(..);
}
```
I'm fine with either approach.
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] optimize(interleave): implement interleave for FixedSizeList/Map type [arrow-rs]
Posted by "Jefffrey (via GitHub)" <gi...@apache.org>.
Jefffrey merged PR #10046:
URL: https://github.com/apache/arrow-rs/pull/10046
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] optimize(interleave): implement interleave for FixedSizeList/Map type [arrow-rs]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on code in PR #10046:
URL: https://github.com/apache/arrow-rs/pull/10046#discussion_r3341499344
##########
arrow/benches/interleave_kernels.rs:
##########
@@ -183,6 +189,10 @@ fn add_benchmark(c: &mut Criterion) {
("list_view<i64>(0.1,0.1,20)", &list_view_i64),
("list_view<i64>(0.0,0.0,20)", &list_view_i64_no_nulls),
("list_view_overlapping<i64>(80x,20)", &list_view_overlapping),
+ ("fixed_size_list<i64,5>(0.0,0.0)", &fsl_i64),
+ ("fixed_size_list<i64,5>(0.1,0.1)", &fsl_i64_nulls),
Review Comment:
Maybe I can also support large fsl, like `vector<1024, f32>`
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] optimize(interleave): implement interleave for FixedSizeList/Map type [arrow-rs]
Posted by "Jefffrey (via GitHub)" <gi...@apache.org>.
Jefffrey commented on PR #10046:
URL: https://github.com/apache/arrow-rs/pull/10046#issuecomment-4955961573
run benchmark interleave_kernels
env:
BENCH_FILTER: map|fixed_size_list
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] optimize(interleave): implement interleave for FixedSizeList/Map type [arrow-rs]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on code in PR #10046:
URL: https://github.com/apache/arrow-rs/pull/10046#discussion_r3341475888
##########
arrow-select/src/interleave.rs:
##########
@@ -419,6 +421,77 @@ fn interleave_list<O: OffsetSizeTrait>(
Ok(Arc::new(list_array))
}
+fn interleave_fixed_size_list(
Review Comment:
This might reusing an optimization with https://github.com/apache/arrow-rs/pull/10025 . Otherwise it might get slower in some 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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] optimize(interleave): implement interleave for FixedSizeList/Map type [arrow-rs]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on PR #10046:
URL: https://github.com/apache/arrow-rs/pull/10046#issuecomment-4910700171
Sorry for late reply, I'll extract to separate prs
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] optimize(interleave): implement interleave for FixedSizeList/Map type [arrow-rs]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on code in PR #10046:
URL: https://github.com/apache/arrow-rs/pull/10046#discussion_r3565859722
##########
arrow-select/src/interleave.rs:
##########
@@ -513,6 +517,81 @@ fn interleave_list<O: OffsetSizeTrait>(
Ok(Arc::new(list_array))
}
+fn interleave_fixed_size_list(
+ values: &[&dyn Array],
+ indices: &[(usize, usize)],
+ field: &FieldRef,
+ size: i32,
+) -> Result<ArrayRef, ArrowError> {
+ let interleaved = Interleave::<'_, FixedSizeListArray>::new(values, indices);
+ let capacity = indices.len() * size as usize;
+
+ macro_rules! fsl_primitive_helper {
+ ($t:ty) => {
+ interleave_list_like_primitive_child::<FixedSizeListArray, $t>(
+ &interleaved,
+ indices,
+ capacity,
+ field.data_type(),
+ )
+ };
+ }
+
+ let interleaved_values = downcast_primitive! {
+ field.data_type() => (fsl_primitive_helper),
+ _ => {
+ interleave_list_like_child(&interleaved, indices, capacity)?
+ }
+ };
+
+ let array = FixedSizeListArray::new(field.clone(), size, interleaved_values, interleaved.nulls);
+ Ok(Arc::new(array))
+}
+
+fn interleave_map(
+ values: &[&dyn Array],
+ indices: &[(usize, usize)],
+ field: &FieldRef,
+ ordered: bool,
+) -> Result<ArrayRef, ArrowError> {
+ let interleaved = Interleave::<'_, MapArray>::new(values, indices);
+
+ let mut capacity = 0usize;
+ let mut offsets = Vec::with_capacity(indices.len() + 1);
Review Comment:
Oh, I forgot this, this logic is just same as:
```
fn interleave_list<O: OffsetSizeTrait>(
values: &[&dyn Array],
indices: &[(usize, usize)],
field: &FieldRef,
) -> Result<ArrayRef, ArrowError>
```
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] optimize(interleave): implement interleave for FixedSizeList/Map type [arrow-rs]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on code in PR #10046:
URL: https://github.com/apache/arrow-rs/pull/10046#discussion_r3341978354
##########
arrow/benches/interleave_kernels.rs:
##########
Review Comment:
I don't know should I extract benchmark to a separate pr ( containing this and concat benchmark?)
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] optimize(interleave): implement interleave for FixedSizeList/Map type [arrow-rs]
Posted by "Jefffrey (via GitHub)" <gi...@apache.org>.
Jefffrey commented on PR #10046:
URL: https://github.com/apache/arrow-rs/pull/10046#issuecomment-4751912648
ill try take a look at this soon; wouldnt be a bad idea to split the benchmarks into a separate PR to make running benchmarks via bot easier
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] optimize(interleave): implement interleave for FixedSizeList/Map type [arrow-rs]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #10046:
URL: https://github.com/apache/arrow-rs/pull/10046#issuecomment-4955985618
🤖 Arrow criterion benchmark running (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/10046#issuecomment-4955961573)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c4955961573-1019-9vgcq 6.12.85+ #1 SMP Mon May 11 08:17:35 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 interleave-fsl-map (1fc8fa4dc0b08d30e9ca293632817fd1b879a1e0) to 543b806 (merge-base) [diff](https://github.com/apache/arrow-rs/compare/543b8069252976d0d3e0dd73e33e555a5110010c..1fc8fa4dc0b08d30e9ca293632817fd1b879a1e0)
BENCH_NAME=interleave_kernels
BENCH_COMMAND=cargo bench --features=arrow,async,test_common,experimental,object_store --bench interleave_kernels
BENCH_FILTER=map|fixed_size_list
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] optimize(interleave): implement interleave for FixedSizeList/Map type [arrow-rs]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on PR #10046:
URL: https://github.com/apache/arrow-rs/pull/10046#issuecomment-4676525929
Will refactor since https://github.com/apache/arrow-rs/pull/10025 is merged
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] optimize(interleave): implement interleave for FixedSizeList/Map type [arrow-rs]
Posted by "Jefffrey (via GitHub)" <gi...@apache.org>.
Jefffrey commented on code in PR #10046:
URL: https://github.com/apache/arrow-rs/pull/10046#discussion_r3569181094
##########
arrow-select/src/interleave.rs:
##########
@@ -513,6 +517,81 @@ fn interleave_list<O: OffsetSizeTrait>(
Ok(Arc::new(list_array))
}
+fn interleave_fixed_size_list(
+ values: &[&dyn Array],
+ indices: &[(usize, usize)],
+ field: &FieldRef,
+ size: i32,
+) -> Result<ArrayRef, ArrowError> {
+ let interleaved = Interleave::<'_, FixedSizeListArray>::new(values, indices);
+ let capacity = indices.len() * size as usize;
+
+ macro_rules! fsl_primitive_helper {
+ ($t:ty) => {
+ interleave_list_like_primitive_child::<FixedSizeListArray, $t>(
+ &interleaved,
+ indices,
+ capacity,
+ field.data_type(),
+ )
+ };
+ }
+
+ let interleaved_values = downcast_primitive! {
+ field.data_type() => (fsl_primitive_helper),
+ _ => {
+ interleave_list_like_child(&interleaved, indices, capacity)?
+ }
+ };
+
+ let array = FixedSizeListArray::new(field.clone(), size, interleaved_values, interleaved.nulls);
+ Ok(Arc::new(array))
+}
+
+fn interleave_map(
+ values: &[&dyn Array],
+ indices: &[(usize, usize)],
+ field: &FieldRef,
+ ordered: bool,
+) -> Result<ArrayRef, ArrowError> {
+ let interleaved = Interleave::<'_, MapArray>::new(values, indices);
+
+ let mut capacity = 0usize;
+ let mut offsets = Vec::with_capacity(indices.len() + 1);
Review Comment:
My suggestion to use the builder was actually not correct since it seems vec is preferred for performance anyway 😅
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] optimize(interleave): implement interleave for FixedSizeList/Map type [arrow-rs]
Posted by "Jefffrey (via GitHub)" <gi...@apache.org>.
Jefffrey commented on code in PR #10046:
URL: https://github.com/apache/arrow-rs/pull/10046#discussion_r3456978481
##########
arrow-select/src/interleave.rs:
##########
@@ -1941,4 +2020,145 @@ mod tests {
&[3]
);
}
+
+ #[test]
+ fn test_interleave_fixed_size_list() {
+ // a: [[1, 2], [3, 4], [5, 6]]
+ let field = Arc::new(Field::new("item", DataType::Int32, false));
+ let a = FixedSizeListArray::new(
+ field.clone(),
+ 2,
+ Arc::new(Int32Array::from(vec![1, 2, 3, 4, 5, 6])),
+ None,
+ );
+ // b: [[7, 8], [9, 10]]
+ let b = FixedSizeListArray::new(
+ field.clone(),
+ 2,
+ Arc::new(Int32Array::from(vec![7, 8, 9, 10])),
+ None,
+ );
+
+ let result = interleave(&[&a, &b], &[(0, 2), (1, 0), (0, 0), (1, 1), (0, 1)]).unwrap();
+ let result = result.as_fixed_size_list();
+ assert_eq!(result.len(), 5);
+ assert_eq!(result.value_length(), 2);
+
+ let values = result.values().as_primitive::<Int32Type>();
+ // [[5,6], [7,8], [1,2], [9,10], [3,4]]
+ assert_eq!(values.values(), &[5, 6, 7, 8, 1, 2, 9, 10, 3, 4]);
+ }
+
+ #[test]
+ fn test_interleave_fixed_size_list_with_nulls() {
Review Comment:
do we have a test for fixedsizelist with non-primitive child?
##########
arrow-select/src/interleave.rs:
##########
@@ -513,6 +517,81 @@ fn interleave_list<O: OffsetSizeTrait>(
Ok(Arc::new(list_array))
}
+fn interleave_fixed_size_list(
+ values: &[&dyn Array],
+ indices: &[(usize, usize)],
+ field: &FieldRef,
+ size: i32,
+) -> Result<ArrayRef, ArrowError> {
+ let interleaved = Interleave::<'_, FixedSizeListArray>::new(values, indices);
+ let capacity = indices.len() * size as usize;
+
+ macro_rules! fsl_primitive_helper {
+ ($t:ty) => {
+ interleave_list_like_primitive_child::<FixedSizeListArray, $t>(
+ &interleaved,
+ indices,
+ capacity,
+ field.data_type(),
+ )
+ };
+ }
+
+ let interleaved_values = downcast_primitive! {
+ field.data_type() => (fsl_primitive_helper),
+ _ => {
+ interleave_list_like_child(&interleaved, indices, capacity)?
+ }
+ };
+
+ let array = FixedSizeListArray::new(field.clone(), size, interleaved_values, interleaved.nulls);
+ Ok(Arc::new(array))
+}
+
+fn interleave_map(
+ values: &[&dyn Array],
+ indices: &[(usize, usize)],
+ field: &FieldRef,
+ ordered: bool,
+) -> Result<ArrayRef, ArrowError> {
+ let interleaved = Interleave::<'_, MapArray>::new(values, indices);
+
+ let mut capacity = 0usize;
+ let mut offsets = Vec::with_capacity(indices.len() + 1);
+ offsets.push(0i32);
+ for &(array, row) in indices {
+ let o = interleaved.arrays[array].value_offsets();
+ let element_len = (o[row + 1] - o[row]) as usize;
+ capacity += element_len;
+ offsets
+ .push(i32::try_from(capacity).map_err(|_| ArrowError::OffsetOverflowError(capacity))?);
+ }
+
+ let mut child_indices = Vec::with_capacity(capacity);
+ for &(array, row) in indices {
+ let o = interleaved.arrays[array].value_offsets();
+ let start = o[row] as usize;
+ let end = o[row + 1] as usize;
+ child_indices.extend((start..end).map(|i| (array, i)));
+ }
+
+ let entries_arrays: Vec<&dyn Array> = interleaved
+ .arrays
+ .iter()
+ .map(|m| m.entries() as &dyn Array)
+ .collect();
+ let interleaved_entries = interleave(&entries_arrays, &child_indices)?;
+
+ let offsets = OffsetBuffer::new(offsets.into());
+ let entries = interleaved_entries
+ .as_any()
+ .downcast_ref::<StructArray>()
+ .unwrap()
+ .clone();
Review Comment:
```suggestion
let entries = interleaved_entries.as_struct().clone();
```
##########
arrow-select/src/interleave.rs:
##########
@@ -513,6 +517,81 @@ fn interleave_list<O: OffsetSizeTrait>(
Ok(Arc::new(list_array))
}
+fn interleave_fixed_size_list(
+ values: &[&dyn Array],
+ indices: &[(usize, usize)],
+ field: &FieldRef,
+ size: i32,
+) -> Result<ArrayRef, ArrowError> {
+ let interleaved = Interleave::<'_, FixedSizeListArray>::new(values, indices);
+ let capacity = indices.len() * size as usize;
+
+ macro_rules! fsl_primitive_helper {
+ ($t:ty) => {
+ interleave_list_like_primitive_child::<FixedSizeListArray, $t>(
+ &interleaved,
+ indices,
+ capacity,
+ field.data_type(),
+ )
+ };
+ }
+
+ let interleaved_values = downcast_primitive! {
+ field.data_type() => (fsl_primitive_helper),
+ _ => {
+ interleave_list_like_child(&interleaved, indices, capacity)?
+ }
+ };
+
+ let array = FixedSizeListArray::new(field.clone(), size, interleaved_values, interleaved.nulls);
+ Ok(Arc::new(array))
+}
+
+fn interleave_map(
+ values: &[&dyn Array],
+ indices: &[(usize, usize)],
+ field: &FieldRef,
+ ordered: bool,
+) -> Result<ArrayRef, ArrowError> {
+ let interleaved = Interleave::<'_, MapArray>::new(values, indices);
+
+ let mut capacity = 0usize;
+ let mut offsets = Vec::with_capacity(indices.len() + 1);
Review Comment:
could consider using [`OffsetBufferBuilder`](https://docs.rs/arrow/latest/arrow/array/struct.OffsetBufferBuilder.html)
though i suppose it doesn't have a way to handle overflow without panicking 🤔
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] optimize(interleave): implement interleave for FixedSizeList/Map type [arrow-rs]
Posted by "mapleFU (via GitHub)" <gi...@apache.org>.
mapleFU commented on PR #10046:
URL: https://github.com/apache/arrow-rs/pull/10046#issuecomment-4950355027
@Jefffrey I've addressed the comments, now we can run ci bench to see the performance enhancement
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] optimize(interleave): implement interleave for FixedSizeList/Map type [arrow-rs]
Posted by "Jefffrey (via GitHub)" <gi...@apache.org>.
Jefffrey commented on PR #10046:
URL: https://github.com/apache/arrow-rs/pull/10046#issuecomment-4966767578
thanks @mapleFU
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] optimize(interleave): implement interleave for FixedSizeList/Map type [arrow-rs]
Posted by "Copilot (via GitHub)" <gi...@apache.org>.
Copilot commented on code in PR #10046:
URL: https://github.com/apache/arrow-rs/pull/10046#discussion_r3396543482
##########
arrow/src/util/bench_util.rs:
##########
@@ -871,3 +873,81 @@ pub fn create_f64_array_with_seed(size: usize, nan_density: f32, seed: u64) -> F
})
.collect()
}
+
+/// Create a FixedSizeList array of primitive values
+///
+/// Arguments:
+/// - `size`: number of fixed-size lists in the array
+/// - `null_density`: density of nulls in the fixed-size list array (row-level nulls)
+/// - `value_null_density`: density of nulls in the primitive values inside each list
+/// - `list_size`: fixed size of each list element
+pub fn create_primitive_fixed_size_list_array<T>(
+ size: usize,
+ null_density: f32,
+ value_null_density: f32,
+ list_size: i32,
+) -> FixedSizeListArray
+where
+ T: ArrowPrimitiveType,
+ StandardUniform: Distribution<T::Native>,
+{
+ let mut rng = seedable_rng();
+ let list_size_usize = list_size as usize;
+ let values: PrimitiveArray<T> = (0..size * list_size_usize)
+ .map(|_| {
+ if rng.random::<f32>() < value_null_density {
+ None
+ } else {
+ Some(rng.random())
+ }
+ })
+ .collect();
+ let field = Arc::new(Field::new("item", T::DATA_TYPE, value_null_density > 0.0));
+ let nulls = (null_density > 0.0).then(|| {
+ NullBuffer::new(arrow_buffer::BooleanBuffer::collect_bool(size, |_| {
+ rng.random::<f32>() >= null_density
+ }))
+ });
+ FixedSizeListArray::new(field, list_size, Arc::new(values), nulls)
+}
+
+/// Create a Map array with string keys and primitive values
+///
+/// Arguments:
+/// - `size`: number of map entries in the array
+/// - `null_density`: density of nulls in the map array (row-level nulls)
+/// - `max_map_size`: maximum number of key-value pairs per map entry
+/// (actual size is random between 0 and max_map_size)
+/// - `key_len`: length of each random string key
+pub fn create_string_map_array<T>(
+ size: usize,
+ null_density: f32,
+ max_map_size: usize,
+ key_len: usize,
+) -> MapArray
+where
+ T: ArrowPrimitiveType,
+ StandardUniform: Distribution<T::Native>,
+{
+ let mut rng = seedable_rng();
+ let mut builder = builder::MapBuilder::new(
+ None,
+ builder::StringBuilder::new(),
+ builder::PrimitiveBuilder::<T>::new(),
+ );
Review Comment:
`builder::MapBuilder` / `builder::StringBuilder` / `builder::PrimitiveBuilder` won’t resolve here: `use crate::array::*;` re-exports the builder types, but not a `builder` module. This will fail to compile for the benchmarks.
##########
arrow/src/util/bench_util.rs:
##########
@@ -871,3 +873,81 @@ pub fn create_f64_array_with_seed(size: usize, nan_density: f32, seed: u64) -> F
})
.collect()
}
+
+/// Create a FixedSizeList array of primitive values
+///
+/// Arguments:
+/// - `size`: number of fixed-size lists in the array
+/// - `null_density`: density of nulls in the fixed-size list array (row-level nulls)
+/// - `value_null_density`: density of nulls in the primitive values inside each list
+/// - `list_size`: fixed size of each list element
+pub fn create_primitive_fixed_size_list_array<T>(
+ size: usize,
+ null_density: f32,
+ value_null_density: f32,
+ list_size: i32,
+) -> FixedSizeListArray
+where
+ T: ArrowPrimitiveType,
+ StandardUniform: Distribution<T::Native>,
+{
+ let mut rng = seedable_rng();
+ let list_size_usize = list_size as usize;
+ let values: PrimitiveArray<T> = (0..size * list_size_usize)
+ .map(|_| {
Review Comment:
`list_size` is an `i32` and is cast to `usize` before any validation. If a negative `list_size` is passed, this will wrap to a huge `usize` and can attempt an enormous allocation (`size * list_size_usize`) before `FixedSizeListArray::new` has a chance to reject the negative size.
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org