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

Use BitChunks in equal_bits #2186

Closed
tustvold opened this issue Jul 27, 2022 · 0 comments · Fixed by #2194
Closed

Use BitChunks in equal_bits #2186

tustvold opened this issue Jul 27, 2022 · 0 comments · Fixed by #2194
Labels
arrow Changes to the arrow crate enhancement Any new improvement worthy of a entry in the changelog performance

Comments

@tustvold
Copy link
Contributor

Is your feature request related to a problem or challenge? Please describe what you are trying to do.

arrow::array::equal::utils::equal_bits currently is implemented as

(0..len).all(|i| {
        bit_util::get_bit(lhs_values, lhs_start + i)
            == bit_util::get_bit(rhs_values, rhs_start + i)
    })

This is likely extremely sub-optimal, performing a large number of operations for every bit

Describe the solution you'd like

Something like the below, not tested, should be significantly faster

let lhs = BitChunks::new(lhs_values, lhs_start, len);
let rhs = BitChunks::new(rhs_values, rhs_start, len);

for (a, b) in lhs.iter().zip(rhs.iter()) {
    if a != b {
        return false
    }
}

lhs.remainder_bits() == rhs.remainder_bits()

Describe alternatives you've considered

We could not do this

@tustvold tustvold added the enhancement Any new improvement worthy of a entry in the changelog label Jul 27, 2022
tustvold added a commit to tustvold/arrow-rs that referenced this issue Jul 27, 2022
tustvold added a commit to tustvold/arrow-rs that referenced this issue Jul 27, 2022
tustvold added a commit that referenced this issue Jul 28, 2022
* Use BitChunks in equal_bits (#2186)

* Further improvements (#2188)

* Use BitIndexIterator

* Cleanup

* Test contains_nulls

* fix: fmt

Co-authored-by: Andrew Lamb <andrew@nerdnetworks.org>
@alamb alamb added arrow Changes to the arrow crate performance labels Aug 4, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
arrow Changes to the arrow crate enhancement Any new improvement worthy of a entry in the changelog performance
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants