Skip to content

Speed up i256 division and remainder operations#4303

Merged
tustvold merged 11 commits intoapache:masterfrom
viirya:i256_div
May 31, 2023
Merged

Speed up i256 division and remainder operations#4303
tustvold merged 11 commits intoapache:masterfrom
viirya:i256_div

Conversation

@viirya
Copy link
Member

@viirya viirya commented May 28, 2023

Which issue does this PR close?

Closes #4302.

Rationale for this change

What changes are included in this PR?

Are there any user-facing changes?

@github-actions github-actions bot added the arrow Changes to the arrow crate label May 28, 2023
@viirya
Copy link
Member Author

viirya commented May 28, 2023 

i256_div                time:   [6.3815 µs 6.3855 µs 6.3904 µs]                                                    
                        change: [-75.246% -75.211% -75.178%] (p = 0.00 < 0.05)      
                        Performance has improved.                                                                                                                                                                                      
Found 10 outliers among 100 measurements (10.00%)                                                                  
  5 (5.00%) high mild                                                                                              
  5 (5.00%) high severe                                                                                                                                                                                                                
                                                                                                                   
i256_rem                time:   [6.3864 µs 6.3933 µs 6.4011 µs]                                             
                        change: [-75.315% -75.275% -75.234%] (p = 0.00 < 0.05)         
                        Performance has improved.                                                                  
Found 8 outliers among 100 measurements (8.00%)                                                                    
  4 (4.00%) high mild
  4 (4.00%) high severe

@viirya viirya mentioned this pull request May 28, 2023
Merged
tustvold
tustvold reviewed May 30, 2023
View reviewed changes
Copy link
Contributor

@tustvold tustvold left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thank you for this, left some comments

arrow-buffer/src/bigint.rs
/// [`i256`] operations return this error type.
#[derive(Debug)]
pub struct ParseI256Error {}
pub enum I256Error {
Copy link
Contributor

@tustvold tustvold May 30, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This is a breaking change (which is fine)

Copy link
Contributor

@tustvold tustvold May 31, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I've filed #4318 to remove this breaking change, PTAL

arrow-buffer/src/bigint.rs
if me < you {
return Ok((Self::from_le_bytes(ret), self));
}

Copy link
Contributor

@tustvold tustvold May 30, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I wonder if at this point we could fallback to 128-bit division if both the high components are zero?

Copy link
Member Author

@viirya viirya May 31, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The low component is u128. If the high component is zero, it might be possibly over i128 range, no?

Copy link
Contributor

@tustvold tustvold May 31, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Is that a problem, we have already taken the absolute value, so it is an unsigned division operation?

Copy link
Member Author

@viirya viirya May 31, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Oh, got your idea. You meant to do it in u128.

@tustvold tustvold added the api-change Changes to the arrow API label May 30, 2023
@tustvold tustvold merged commit 0783cf9 into apache:master May 31, 2023
tustvold added a commit to tustvold/arrow-rs that referenced this pull request May 31, 2023
@tustvold
Revert error handling changes from apache#4303
0631769
@tustvold tustvold mentioned this pull request May 31, 2023
Merged
tustvold added a commit that referenced this pull request May 31, 2023
@tustvold
Revert error handling changes from #4303 (#4318)
30196d8
@tustvold tustvold removed the api-change Changes to the arrow API label May 31, 2023
@tustvold tustvold mentioned this pull request Jun 2, 2023
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@tustvold tustvold tustvold approved these changes

Assignees

No one assigned

Labels

arrow Changes to the arrow crate

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Speed up i256 division and remainder operations

2 participants

@viirya @tustvold