Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Optimize performance of the substr_index function #9890

Closed
Tracked by #10171
alamb opened this issue Mar 31, 2024 · 6 comments · Fixed by #9973
Closed
Tracked by #10171

Optimize performance of the substr_index function #9890

alamb opened this issue Mar 31, 2024 · 6 comments · Fixed by #9973
Assignees
Labels
enhancement New feature or request

Comments

@alamb
Copy link
Contributor

alamb commented Mar 31, 2024

Is your feature request related to a problem or challenge?

As noted in #9864 (comment) there might be some optimization available for the substr_index function so to facilitate that add a benchmark for that function.

A new benchmark testing the substr_index function was added in #9878 and available for use to test the performance of that function and any changes.

Describe the solution you'd like

Make the substr_index benchmark faster

To run:

cargo bench --bench substr_index

Describe alternatives you've considered

No response

Additional context

No response

@alamb alamb added the enhancement New feature or request label Mar 31, 2024
@kevinmingtarja
Copy link
Contributor

Hi, I was curious about this and decided to test it out myself.

I first generated a flamegraph using flamegraph-rs (CARGO_PROFILE_BENCH_DEBUG=true cargo flamegraph --root --bench substr_index -- --bench).

It seems like quite a lot of time is spent on malloc, free, and memmove, as you noted in #9864 (comment).

A snippet of flamegraph.svg:
Screen Shot 2024-04-05 at 03 11 53

I then tested out a quick change to avoid the Box::new() (at the expense of code duplication :D), and managed to get around -28% improvement!

% cargo bench --bench substr_index -- --baseline main
   Compiling datafusion-functions v37.0.0 (/Users/kevin/git/arrow-datafusion/datafusion/functions)
    Finished bench [optimized] target(s) in 56.31s
     Running benches/substr_index.rs (target/release/deps/substr_index-bcc13e06371405f5)
substr_index_array_array_1000
                        time:   [87.912 µs 88.197 µs 88.515 µs]
                        change: [-29.549% -28.257% -27.292%] (p = 0.00 < 0.05)
                        Performance has improved.

diff:

-                let splitted: Box<dyn Iterator<Item = _>> = if n > 0 {
-                    Box::new(string.split(delimiter))
-                } else {
-                    Box::new(string.rsplit(delimiter))
-                };
                 let occurrences = usize::try_from(n.unsigned_abs()).unwrap_or(usize::MAX);
-                // The length of the substring covered by substr_index.
-                let length = splitted
-                    .take(occurrences) // at least 1 element, since n != 0
-                    .map(|s| s.len() + delimiter.len())
-                    .sum::<usize>()
-                    - delimiter.len();
+                let length;
+                if n > 0 {
+                    let splitted = string.split(delimiter);
+                    length = splitted
+                        .take(occurrences)
+                        .map(|s| s.len() + delimiter.len())
+                        .sum::<usize>()
+                        - delimiter.len();
+                } else {
+                    let splitted = string.rsplit(delimiter);
+                    length = splitted
+                        .take(occurrences)
+                        .map(|s| s.len() + delimiter.len())
+                        .sum::<usize>()
+                        - delimiter.len();
+                }

@alamb
Copy link
Contributor Author

alamb commented Apr 4, 2024

🚀

@alamb
Copy link
Contributor Author

alamb commented Apr 4, 2024

FYI @Omega359

@Omega359
Copy link
Contributor

Omega359 commented Apr 4, 2024

The 25-30% improvement is in line with what I expected for the box removal - very nice work!

@kevinmingtarja
Copy link
Contributor

I'll make a PR some time today or tmr!

@kevinmingtarja
Copy link
Contributor

take

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants