You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "lyne7-sc (via GitHub)" <gi...@apache.org> on 2026/02/28 14:58:10 UTC

[PR] perf: add fast path for uniform fill values in `array_resize` [datafusion]

lyne7-sc opened a new pull request, #20617:
URL: https://github.com/apache/datafusion/pull/20617

   ## Which issue does this PR close?
   
   <!--
   We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123.
   -->
   
   - Closes #.
   
   ## Rationale for this change
   
   <!--
    Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed.
    Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes.  
   -->
   
   `array_resize` currently does extra per-row work when resizing list arrays. This pr optimizes the common fast path where the fill value is uniform.
   
   ## What changes are included in this PR?
   
   - Add a fast path in `array_resize` for uniform fill values.
   - Precompute the maximum required growth and reuse a single fill buffer in the uniform-fill path.
   
   ### Benchmarks
   ```
   group                                                main                                   optimized
   -----                                                ----                                   ---------
   array_resize_i64/grow_default_null_fill_10_to_500    11.24     3.2±0.07ms        ? ?/sec    1.00   283.9±20.10µs        ? ?/sec
   array_resize_i64/grow_uniform_fill_10_to_500         4.15  1648.0±38.12µs        ? ?/sec    1.00   397.2±20.46µs        ? ?/sec
   array_resize_i64/grow_variable_fill_10_to_500        1.00  1667.7±50.31µs        ? ?/sec    1.02  1692.8±61.54µs        ? ?/sec
   array_resize_i64/mixed_grow_shrink_1000x_100         4.83    373.0±8.91µs        ? ?/sec    1.00     77.1±5.90µs        ? ?/sec
   array_resize_i64/shrink_uniform_fill_500_to_10       1.00      8.1±0.51µs        ? ?/sec    1.06      8.5±0.50µs        ? ?/sec
   ```
   
   <!--
   There is no need to duplicate the description in the issue here but it is sometimes worth providing a summary of the individual changes in this PR.
   -->
   
   ## Are these changes tested?
    Yes
   
   <!--
   We typically require tests for all PRs in order to:
   1. Prevent the code from being accidentally broken by subsequent changes
   2. Serve as another way to document the expected behavior of the code
   
   If tests are not included in your PR, please explain why (for example, are they covered by existing tests)?
   -->
   
   ## Are there any user-facing changes?
   No
   
   <!--
   If there are user-facing changes then we may require documentation to be updated before approving the PR.
   -->
   
   <!--
   If there are any breaking changes to public APIs, please add the `api change` label.
   -->
   


-- 
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 fast path for uniform fill values in `array_resize` [datafusion]

Posted by "lyne7-sc (via GitHub)" <gi...@apache.org>.
lyne7-sc commented on PR #20617:
URL: https://github.com/apache/datafusion/pull/20617#issuecomment-3980376769

   Thanks for the review @neilconway
   
   The existing SLTs already hit the fast path, but I added another array test case to cover the multi-row case more explicitly.
   


-- 
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 fast path for uniform fill values in `array_resize` [datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb merged PR #20617:
URL: https://github.com/apache/datafusion/pull/20617


-- 
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 fast path for uniform fill values in `array_resize` [datafusion]

Posted by "lyne7-sc (via GitHub)" <gi...@apache.org>.
lyne7-sc commented on code in PR #20617:
URL: https://github.com/apache/datafusion/pull/20617#discussion_r3068963952


##########
datafusion/functions-nested/src/resize.rs:
##########
@@ -232,21 +321,13 @@ fn general_list_resize<O: OffsetSizeTrait + TryInto<i64>>(
         let count = O::usize_as(count);
         let start = offset_window[0];
         if start + count > offset_window[1] {
-            let extra_count =
-                (start + count - offset_window[1]).try_into().map_err(|_| {
-                    internal_datafusion_err!(
-                        "array_resize: failed to convert size to i64"
-                    )
-                })?;
+            let extra_count = (start + count - offset_window[1]).to_usize().unwrap();

Review Comment:
   Yes, this would panic in the same cases as the `unwrap()` calls below.



-- 
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 fast path for uniform fill values in `array_resize` [datafusion]

Posted by "lyne7-sc (via GitHub)" <gi...@apache.org>.
lyne7-sc commented on PR #20617:
URL: https://github.com/apache/datafusion/pull/20617#issuecomment-4228356821

   Hi @alamb — gentle ping, this PR has been open for a while. I’ve rebased and resolved conflicts, would appreciate a review when you have time.


-- 
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 fast path for uniform fill values in `array_resize` [datafusion]

Posted by "lyne7-sc (via GitHub)" <gi...@apache.org>.
lyne7-sc commented on code in PR #20617:
URL: https://github.com/apache/datafusion/pull/20617#discussion_r2869298735


##########
datafusion/functions-nested/src/resize.rs:
##########
@@ -206,7 +206,103 @@ fn general_list_resize<O: OffsetSizeTrait + TryInto<i64>>(
     let values = array.values();
     let original_data = values.to_data();
 
-    // create default element array
+    // Track the largest per-row growth so the uniform-fill fast path can
+    // materialize one reusable fill buffer of the required size.
+    let mut max_extra: usize = 0;
+    for (row_index, offset_window) in array.offsets().windows(2).enumerate() {
+        if array.is_null(row_index) {
+            continue;
+        }
+        let target_count = count_array.value(row_index).to_usize().ok_or_else(|| {
+            internal_datafusion_err!("array_resize: failed to convert size to usize")
+        })?;
+        let current_len = (offset_window[1] - offset_window[0]).to_usize().unwrap();
+        if target_count > current_len {
+            let extra = target_count - current_len;
+            if extra > max_extra {
+                max_extra = extra;
+            }
+        }
+    }
+
+    // The fast path is valid when at least one row grows and every row would
+    // use the same fill value.
+    let is_uniform_fill = max_extra > 0
+        && match &default_element {
+            None => true,
+            Some(fill_array) => {
+                let len = fill_array.len();
+                let null_count = fill_array.logical_null_count();
+
+                len <= 1
+                    || null_count == len
+                    || (null_count == 0 && {
+                        let first = fill_array.slice(0, 1);
+                        (1..len)
+                            .all(|i| fill_array.slice(i, 1).as_ref() == first.as_ref())
+                    })
+            }
+        };
+
+    // Fast path: at least one row needs to grow and all rows share
+    // the same fill value.
+    if is_uniform_fill {
+        let fill_scalar = match &default_element {
+            None => ScalarValue::try_from(&data_type)?,
+            Some(fill_array) if fill_array.logical_null_count() == fill_array.len() => {
+                ScalarValue::try_from(&data_type)?
+            }
+            Some(fill_array) => ScalarValue::try_from_array(fill_array.as_ref(), 0)?,
+        };
+        let default_element = fill_scalar.to_array_of_size(max_extra)?;
+        let default_value_data = default_element.to_data();
+
+        let capacity = Capacities::Array(original_data.len() + default_value_data.len());

Review Comment:
   thanks for the reminder. I added capacity calculation in the pre-scan and use for the allocation.
   



-- 
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 fast path for uniform fill values in `array_resize` [datafusion]

Posted by "lyne7-sc (via GitHub)" <gi...@apache.org>.
lyne7-sc commented on code in PR #20617:
URL: https://github.com/apache/datafusion/pull/20617#discussion_r3068970644


##########
datafusion/functions-nested/src/resize.rs:
##########
@@ -232,21 +321,13 @@ fn general_list_resize<O: OffsetSizeTrait + TryInto<i64>>(
         let count = O::usize_as(count);
         let start = offset_window[0];
         if start + count > offset_window[1] {
-            let extra_count =
-                (start + count - offset_window[1]).try_into().map_err(|_| {
-                    internal_datafusion_err!(
-                        "array_resize: failed to convert size to i64"
-                    )
-                })?;
+            let extra_count = (start + count - offset_window[1]).to_usize().unwrap();

Review Comment:
   a more robust option might be to add an overflow check here. Do you think that would be worth adding?



-- 
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 fast path for uniform fill values in `array_resize` [datafusion]

Posted by "lyne7-sc (via GitHub)" <gi...@apache.org>.
lyne7-sc commented on code in PR #20617:
URL: https://github.com/apache/datafusion/pull/20617#discussion_r2869303532


##########
datafusion/functions-nested/src/resize.rs:
##########
@@ -206,7 +206,103 @@ fn general_list_resize<O: OffsetSizeTrait + TryInto<i64>>(
     let values = array.values();
     let original_data = values.to_data();
 
-    // create default element array
+    // Track the largest per-row growth so the uniform-fill fast path can
+    // materialize one reusable fill buffer of the required size.
+    let mut max_extra: usize = 0;
+    for (row_index, offset_window) in array.offsets().windows(2).enumerate() {
+        if array.is_null(row_index) {
+            continue;
+        }
+        let target_count = count_array.value(row_index).to_usize().ok_or_else(|| {
+            internal_datafusion_err!("array_resize: failed to convert size to usize")
+        })?;
+        let current_len = (offset_window[1] - offset_window[0]).to_usize().unwrap();
+        if target_count > current_len {
+            let extra = target_count - current_len;
+            if extra > max_extra {
+                max_extra = extra;
+            }
+        }
+    }
+
+    // The fast path is valid when at least one row grows and every row would
+    // use the same fill value.
+    let is_uniform_fill = max_extra > 0
+        && match &default_element {
+            None => true,
+            Some(fill_array) => {
+                let len = fill_array.len();
+                let null_count = fill_array.logical_null_count();
+
+                len <= 1
+                    || null_count == len
+                    || (null_count == 0 && {
+                        let first = fill_array.slice(0, 1);
+                        (1..len)
+                            .all(|i| fill_array.slice(i, 1).as_ref() == first.as_ref())
+                    })
+            }
+        };
+
+    // Fast path: at least one row needs to grow and all rows share
+    // the same fill value.
+    if is_uniform_fill {

Review Comment:
   I think `use_bulk_fill` is pretty clear, I renamed it to that, 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 fast path for uniform fill values in `array_resize` [datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #20617:
URL: https://github.com/apache/datafusion/pull/20617#discussion_r3067864875


##########
datafusion/functions-nested/src/resize.rs:
##########
@@ -232,21 +321,13 @@ fn general_list_resize<O: OffsetSizeTrait + TryInto<i64>>(
         let count = O::usize_as(count);
         let start = offset_window[0];
         if start + count > offset_window[1] {
-            let extra_count =
-                (start + count - offset_window[1]).try_into().map_err(|_| {
-                    internal_datafusion_err!(
-                        "array_resize: failed to convert size to i64"
-                    )
-                })?;
+            let extra_count = (start + count - offset_window[1]).to_usize().unwrap();

Review Comment:
   why was this changed to unwrap (which will panic) from a internal error?



##########
datafusion/functions-nested/src/resize.rs:
##########
@@ -232,21 +321,13 @@ fn general_list_resize<O: OffsetSizeTrait + TryInto<i64>>(
         let count = O::usize_as(count);
         let start = offset_window[0];
         if start + count > offset_window[1] {
-            let extra_count =
-                (start + count - offset_window[1]).try_into().map_err(|_| {
-                    internal_datafusion_err!(
-                        "array_resize: failed to convert size to i64"
-                    )
-                })?;
+            let extra_count = (start + count - offset_window[1]).to_usize().unwrap();

Review Comment:
   Maybe because the calls below to `unwrap()` would have panic'd anyways



-- 
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 fast path for uniform fill values in `array_resize` [datafusion]

Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on PR #20617:
URL: https://github.com/apache/datafusion/pull/20617#issuecomment-4183988789

   @lyne7-sc Can you resolve the merge conflicts?


-- 
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 fast path for uniform fill values in `array_resize` [datafusion]

Posted by "lyne7-sc (via GitHub)" <gi...@apache.org>.
lyne7-sc commented on code in PR #20617:
URL: https://github.com/apache/datafusion/pull/20617#discussion_r2869305422


##########
datafusion/functions-nested/src/resize.rs:
##########
@@ -206,7 +206,103 @@ fn general_list_resize<O: OffsetSizeTrait + TryInto<i64>>(
     let values = array.values();
     let original_data = values.to_data();
 
-    // create default element array
+    // Track the largest per-row growth so the uniform-fill fast path can
+    // materialize one reusable fill buffer of the required size.
+    let mut max_extra: usize = 0;
+    for (row_index, offset_window) in array.offsets().windows(2).enumerate() {
+        if array.is_null(row_index) {
+            continue;
+        }
+        let target_count = count_array.value(row_index).to_usize().ok_or_else(|| {
+            internal_datafusion_err!("array_resize: failed to convert size to usize")
+        })?;
+        let current_len = (offset_window[1] - offset_window[0]).to_usize().unwrap();
+        if target_count > current_len {
+            let extra = target_count - current_len;
+            if extra > max_extra {
+                max_extra = extra;
+            }
+        }
+    }
+
+    // The fast path is valid when at least one row grows and every row would
+    // use the same fill value.
+    let is_uniform_fill = max_extra > 0
+        && match &default_element {
+            None => true,
+            Some(fill_array) => {
+                let len = fill_array.len();
+                let null_count = fill_array.logical_null_count();
+
+                len <= 1
+                    || null_count == len
+                    || (null_count == 0 && {
+                        let first = fill_array.slice(0, 1);
+                        (1..len)
+                            .all(|i| fill_array.slice(i, 1).as_ref() == first.as_ref())
+                    })
+            }
+        };
+
+    // Fast path: at least one row needs to grow and all rows share
+    // the same fill value.
+    if is_uniform_fill {
+        let fill_scalar = match &default_element {
+            None => ScalarValue::try_from(&data_type)?,
+            Some(fill_array) if fill_array.logical_null_count() == fill_array.len() => {
+                ScalarValue::try_from(&data_type)?
+            }
+            Some(fill_array) => ScalarValue::try_from_array(fill_array.as_ref(), 0)?,
+        };
+        let default_element = fill_scalar.to_array_of_size(max_extra)?;
+        let default_value_data = default_element.to_data();
+
+        let capacity = Capacities::Array(original_data.len() + default_value_data.len());
+        let mut offsets = vec![O::usize_as(0)];
+        let mut mutable = MutableArrayData::with_capacities(
+            vec![&original_data, &default_value_data],
+            false,
+            capacity,
+        );
+
+        let mut null_builder = NullBufferBuilder::new(array.len());
+
+        for (row_index, offset_window) in array.offsets().windows(2).enumerate() {

Review Comment:
   yes, the main difference is the fill behavior, and the surrounding control flow is very similar. I’ll take a look to see what can be cleanly refactored there.



-- 
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 fast path for uniform fill values in `array_resize` [datafusion]

Posted by "lyne7-sc (via GitHub)" <gi...@apache.org>.
lyne7-sc commented on code in PR #20617:
URL: https://github.com/apache/datafusion/pull/20617#discussion_r2872805876


##########
datafusion/functions-nested/src/resize.rs:
##########
@@ -206,7 +206,103 @@ fn general_list_resize<O: OffsetSizeTrait + TryInto<i64>>(
     let values = array.values();
     let original_data = values.to_data();
 
-    // create default element array
+    // Track the largest per-row growth so the uniform-fill fast path can
+    // materialize one reusable fill buffer of the required size.
+    let mut max_extra: usize = 0;
+    for (row_index, offset_window) in array.offsets().windows(2).enumerate() {
+        if array.is_null(row_index) {
+            continue;
+        }
+        let target_count = count_array.value(row_index).to_usize().ok_or_else(|| {
+            internal_datafusion_err!("array_resize: failed to convert size to usize")
+        })?;
+        let current_len = (offset_window[1] - offset_window[0]).to_usize().unwrap();
+        if target_count > current_len {
+            let extra = target_count - current_len;
+            if extra > max_extra {
+                max_extra = extra;
+            }
+        }
+    }
+
+    // The fast path is valid when at least one row grows and every row would
+    // use the same fill value.
+    let is_uniform_fill = max_extra > 0
+        && match &default_element {
+            None => true,
+            Some(fill_array) => {
+                let len = fill_array.len();
+                let null_count = fill_array.logical_null_count();
+
+                len <= 1
+                    || null_count == len
+                    || (null_count == 0 && {
+                        let first = fill_array.slice(0, 1);
+                        (1..len)
+                            .all(|i| fill_array.slice(i, 1).as_ref() == first.as_ref())
+                    })
+            }
+        };
+
+    // Fast path: at least one row needs to grow and all rows share
+    // the same fill value.
+    if is_uniform_fill {
+        let fill_scalar = match &default_element {
+            None => ScalarValue::try_from(&data_type)?,
+            Some(fill_array) if fill_array.logical_null_count() == fill_array.len() => {
+                ScalarValue::try_from(&data_type)?
+            }
+            Some(fill_array) => ScalarValue::try_from_array(fill_array.as_ref(), 0)?,
+        };
+        let default_element = fill_scalar.to_array_of_size(max_extra)?;
+        let default_value_data = default_element.to_data();
+
+        let capacity = Capacities::Array(original_data.len() + default_value_data.len());
+        let mut offsets = vec![O::usize_as(0)];
+        let mut mutable = MutableArrayData::with_capacities(
+            vec![&original_data, &default_value_data],
+            false,
+            capacity,
+        );
+
+        let mut null_builder = NullBufferBuilder::new(array.len());
+
+        for (row_index, offset_window) in array.offsets().windows(2).enumerate() {

Review Comment:
   I refactored it to pull the shared loop out of the fast and slow paths.



-- 
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 fast path for uniform fill values in `array_resize` [datafusion]

Posted by "lyne7-sc (via GitHub)" <gi...@apache.org>.
lyne7-sc commented on PR #20617:
URL: https://github.com/apache/datafusion/pull/20617#issuecomment-4196984161

   > @lyne7-sc Can you resolve the merge conflicts?
   
   Sure, the conflicts have been resolved.


-- 
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 fast path for uniform fill values in `array_resize` [datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #20617:
URL: https://github.com/apache/datafusion/pull/20617#discussion_r3095485458


##########
datafusion/functions-nested/src/resize.rs:
##########
@@ -232,21 +321,13 @@ fn general_list_resize<O: OffsetSizeTrait + TryInto<i64>>(
         let count = O::usize_as(count);
         let start = offset_window[0];
         if start + count > offset_window[1] {
-            let extra_count =
-                (start + count - offset_window[1]).try_into().map_err(|_| {
-                    internal_datafusion_err!(
-                        "array_resize: failed to convert size to i64"
-                    )
-                })?;
+            let extra_count = (start + count - offset_window[1]).to_usize().unwrap();

Review Comment:
   Let's add the check as a follow on PR



-- 
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 fast path for uniform fill values in `array_resize` [datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #20617:
URL: https://github.com/apache/datafusion/pull/20617#issuecomment-4262547692

   I merged thsi PR up from main


-- 
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 fast path for uniform fill values in `array_resize` [datafusion]

Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on code in PR #20617:
URL: https://github.com/apache/datafusion/pull/20617#discussion_r2869049316


##########
datafusion/functions-nested/src/resize.rs:
##########
@@ -206,7 +206,103 @@ fn general_list_resize<O: OffsetSizeTrait + TryInto<i64>>(
     let values = array.values();
     let original_data = values.to_data();
 
-    // create default element array
+    // Track the largest per-row growth so the uniform-fill fast path can
+    // materialize one reusable fill buffer of the required size.
+    let mut max_extra: usize = 0;
+    for (row_index, offset_window) in array.offsets().windows(2).enumerate() {
+        if array.is_null(row_index) {
+            continue;
+        }
+        let target_count = count_array.value(row_index).to_usize().ok_or_else(|| {
+            internal_datafusion_err!("array_resize: failed to convert size to usize")
+        })?;
+        let current_len = (offset_window[1] - offset_window[0]).to_usize().unwrap();
+        if target_count > current_len {
+            let extra = target_count - current_len;
+            if extra > max_extra {
+                max_extra = extra;
+            }
+        }
+    }
+
+    // The fast path is valid when at least one row grows and every row would
+    // use the same fill value.
+    let is_uniform_fill = max_extra > 0
+        && match &default_element {
+            None => true,
+            Some(fill_array) => {
+                let len = fill_array.len();
+                let null_count = fill_array.logical_null_count();
+
+                len <= 1
+                    || null_count == len
+                    || (null_count == 0 && {
+                        let first = fill_array.slice(0, 1);
+                        (1..len)
+                            .all(|i| fill_array.slice(i, 1).as_ref() == first.as_ref())
+                    })
+            }
+        };
+
+    // Fast path: at least one row needs to grow and all rows share
+    // the same fill value.
+    if is_uniform_fill {

Review Comment:
   The naming is a bit confusing: `is_uniform_fill` is false if the fill value is uniform but there are no rows that need to grow. How about `use_batch_fill` or `use_bulk_fill` or similar?



##########
datafusion/functions-nested/src/resize.rs:
##########
@@ -206,7 +206,103 @@ fn general_list_resize<O: OffsetSizeTrait + TryInto<i64>>(
     let values = array.values();
     let original_data = values.to_data();
 
-    // create default element array
+    // Track the largest per-row growth so the uniform-fill fast path can
+    // materialize one reusable fill buffer of the required size.
+    let mut max_extra: usize = 0;
+    for (row_index, offset_window) in array.offsets().windows(2).enumerate() {
+        if array.is_null(row_index) {
+            continue;
+        }
+        let target_count = count_array.value(row_index).to_usize().ok_or_else(|| {
+            internal_datafusion_err!("array_resize: failed to convert size to usize")
+        })?;
+        let current_len = (offset_window[1] - offset_window[0]).to_usize().unwrap();
+        if target_count > current_len {
+            let extra = target_count - current_len;
+            if extra > max_extra {
+                max_extra = extra;
+            }

Review Comment:
   ```suggestion
               max_extra = max_extra.max(extra);
   ```



##########
datafusion/functions-nested/src/resize.rs:
##########
@@ -206,7 +206,103 @@ fn general_list_resize<O: OffsetSizeTrait + TryInto<i64>>(
     let values = array.values();
     let original_data = values.to_data();
 
-    // create default element array
+    // Track the largest per-row growth so the uniform-fill fast path can
+    // materialize one reusable fill buffer of the required size.
+    let mut max_extra: usize = 0;
+    for (row_index, offset_window) in array.offsets().windows(2).enumerate() {
+        if array.is_null(row_index) {
+            continue;
+        }
+        let target_count = count_array.value(row_index).to_usize().ok_or_else(|| {
+            internal_datafusion_err!("array_resize: failed to convert size to usize")
+        })?;
+        let current_len = (offset_window[1] - offset_window[0]).to_usize().unwrap();
+        if target_count > current_len {
+            let extra = target_count - current_len;
+            if extra > max_extra {
+                max_extra = extra;
+            }
+        }
+    }
+
+    // The fast path is valid when at least one row grows and every row would
+    // use the same fill value.
+    let is_uniform_fill = max_extra > 0
+        && match &default_element {
+            None => true,
+            Some(fill_array) => {
+                let len = fill_array.len();
+                let null_count = fill_array.logical_null_count();
+
+                len <= 1
+                    || null_count == len
+                    || (null_count == 0 && {
+                        let first = fill_array.slice(0, 1);
+                        (1..len)
+                            .all(|i| fill_array.slice(i, 1).as_ref() == first.as_ref())
+                    })
+            }
+        };
+
+    // Fast path: at least one row needs to grow and all rows share
+    // the same fill value.
+    if is_uniform_fill {
+        let fill_scalar = match &default_element {
+            None => ScalarValue::try_from(&data_type)?,
+            Some(fill_array) if fill_array.logical_null_count() == fill_array.len() => {
+                ScalarValue::try_from(&data_type)?
+            }
+            Some(fill_array) => ScalarValue::try_from_array(fill_array.as_ref(), 0)?,
+        };
+        let default_element = fill_scalar.to_array_of_size(max_extra)?;
+        let default_value_data = default_element.to_data();
+
+        let capacity = Capacities::Array(original_data.len() + default_value_data.len());

Review Comment:
   Is this right? `default_value_data.len()` is the per-row growth, I think we want the total estimated output size.



##########
datafusion/functions-nested/src/resize.rs:
##########
@@ -206,7 +206,103 @@ fn general_list_resize<O: OffsetSizeTrait + TryInto<i64>>(
     let values = array.values();
     let original_data = values.to_data();
 
-    // create default element array
+    // Track the largest per-row growth so the uniform-fill fast path can
+    // materialize one reusable fill buffer of the required size.
+    let mut max_extra: usize = 0;
+    for (row_index, offset_window) in array.offsets().windows(2).enumerate() {
+        if array.is_null(row_index) {
+            continue;
+        }
+        let target_count = count_array.value(row_index).to_usize().ok_or_else(|| {
+            internal_datafusion_err!("array_resize: failed to convert size to usize")
+        })?;
+        let current_len = (offset_window[1] - offset_window[0]).to_usize().unwrap();
+        if target_count > current_len {
+            let extra = target_count - current_len;
+            if extra > max_extra {
+                max_extra = extra;
+            }
+        }
+    }
+
+    // The fast path is valid when at least one row grows and every row would
+    // use the same fill value.
+    let is_uniform_fill = max_extra > 0
+        && match &default_element {
+            None => true,
+            Some(fill_array) => {
+                let len = fill_array.len();
+                let null_count = fill_array.logical_null_count();
+
+                len <= 1
+                    || null_count == len
+                    || (null_count == 0 && {
+                        let first = fill_array.slice(0, 1);
+                        (1..len)
+                            .all(|i| fill_array.slice(i, 1).as_ref() == first.as_ref())
+                    })
+            }
+        };
+
+    // Fast path: at least one row needs to grow and all rows share
+    // the same fill value.
+    if is_uniform_fill {
+        let fill_scalar = match &default_element {
+            None => ScalarValue::try_from(&data_type)?,
+            Some(fill_array) if fill_array.logical_null_count() == fill_array.len() => {
+                ScalarValue::try_from(&data_type)?
+            }
+            Some(fill_array) => ScalarValue::try_from_array(fill_array.as_ref(), 0)?,
+        };
+        let default_element = fill_scalar.to_array_of_size(max_extra)?;
+        let default_value_data = default_element.to_data();
+
+        let capacity = Capacities::Array(original_data.len() + default_value_data.len());
+        let mut offsets = vec![O::usize_as(0)];
+        let mut mutable = MutableArrayData::with_capacities(
+            vec![&original_data, &default_value_data],
+            false,
+            capacity,
+        );
+
+        let mut null_builder = NullBufferBuilder::new(array.len());
+
+        for (row_index, offset_window) in array.offsets().windows(2).enumerate() {

Review Comment:
   The fast path and slow path are doing very similar work and there's a bunch of duplicate code. I wonder if it would be possible to refactor them -- the key difference is just how the fill itself is done, no?



##########
datafusion/functions-nested/src/resize.rs:
##########
@@ -206,7 +206,103 @@ fn general_list_resize<O: OffsetSizeTrait + TryInto<i64>>(
     let values = array.values();
     let original_data = values.to_data();
 
-    // create default element array
+    // Track the largest per-row growth so the uniform-fill fast path can
+    // materialize one reusable fill buffer of the required size.
+    let mut max_extra: usize = 0;
+    for (row_index, offset_window) in array.offsets().windows(2).enumerate() {
+        if array.is_null(row_index) {
+            continue;
+        }
+        let target_count = count_array.value(row_index).to_usize().ok_or_else(|| {
+            internal_datafusion_err!("array_resize: failed to convert size to usize")
+        })?;
+        let current_len = (offset_window[1] - offset_window[0]).to_usize().unwrap();
+        if target_count > current_len {
+            let extra = target_count - current_len;
+            if extra > max_extra {
+                max_extra = extra;
+            }
+        }
+    }
+
+    // The fast path is valid when at least one row grows and every row would
+    // use the same fill value.
+    let is_uniform_fill = max_extra > 0
+        && match &default_element {
+            None => true,
+            Some(fill_array) => {
+                let len = fill_array.len();
+                let null_count = fill_array.logical_null_count();
+
+                len <= 1
+                    || null_count == len
+                    || (null_count == 0 && {
+                        let first = fill_array.slice(0, 1);
+                        (1..len)
+                            .all(|i| fill_array.slice(i, 1).as_ref() == first.as_ref())
+                    })
+            }
+        };
+
+    // Fast path: at least one row needs to grow and all rows share
+    // the same fill value.
+    if is_uniform_fill {
+        let fill_scalar = match &default_element {
+            None => ScalarValue::try_from(&data_type)?,
+            Some(fill_array) if fill_array.logical_null_count() == fill_array.len() => {
+                ScalarValue::try_from(&data_type)?
+            }
+            Some(fill_array) => ScalarValue::try_from_array(fill_array.as_ref(), 0)?,
+        };
+        let default_element = fill_scalar.to_array_of_size(max_extra)?;
+        let default_value_data = default_element.to_data();
+
+        let capacity = Capacities::Array(original_data.len() + default_value_data.len());
+        let mut offsets = vec![O::usize_as(0)];
+        let mut mutable = MutableArrayData::with_capacities(
+            vec![&original_data, &default_value_data],
+            false,
+            capacity,
+        );
+
+        let mut null_builder = NullBufferBuilder::new(array.len());
+
+        for (row_index, offset_window) in array.offsets().windows(2).enumerate() {
+            if array.is_null(row_index) {
+                null_builder.append_null();
+                offsets.push(offsets[row_index]);
+                continue;
+            }
+            null_builder.append_non_null();
+
+            let count = count_array.value(row_index).to_usize().ok_or_else(|| {
+                internal_datafusion_err!("array_resize: failed to convert size to usize")
+            })?;
+            let count = O::usize_as(count);
+            let start = offset_window[0];
+            if start + count > offset_window[1] {
+                let extra_count = (start + count - offset_window[1]).to_usize().unwrap();
+                let end = offset_window[1];
+                mutable.extend(0, (start).to_usize().unwrap(), (end).to_usize().unwrap());

Review Comment:
   (Minor) Why `(start)`? Parens unnecessary, here and below.



-- 
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