seq: Add a print_seq fast path function for integer and positive increments #7564
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
|
GNU testsuite comparison: |
|
GNU testsuite comparison: |
29bafc5 to
01816c7
Compare
|
GNU testsuite comparison: |
|
Scrapped a few more percents: |
|
GNU testsuite comparison: |
|
(Also added support for constant width printing, it's easy to add) |
|
GNU testsuite comparison: |
src/uu/seq/src/seq.rs
Outdated
| // Clippy wants to use `if let Some(...) = ...` to avoid is_some/unwrap combination, but that's | ||
| // not possible within an "if" test with multiple sub-expressions. | ||
| #[allow(clippy::unnecessary_unwrap)] | ||
| if fast_allowed && first_bui.is_some() && increment_u64.is_some() && last_bui.is_some() { |
There was a problem hiding this comment.
Maybe you could do
if fast_allowed {
// Test if we can use fast code path.
// First try to convert the range to BigUint (u64 for the increment).
let (first_bui, increment_u64, last_bui) = (
first.to_biguint(),
increment.to_biguint().and_then(|x| x.to_u64()),
last.to_biguint(),
);
if let (Some(first_bui), Some(increment_u64), Some(last_bui)) = (first_bui, increment_u64, last_bui) {
...
}
}There was a problem hiding this comment.
Oh! That's better indeed. Thanks!
src/uu/seq/src/seq.rs
Outdated
Comment on lines
257
to
260
| // Fast code path increment function. | ||
| // Add inc to the string val[start..end]. This operates on ASCII digits, assuming | ||
| // val and inc are well formed. | ||
| // Returns the new value for start. |
There was a problem hiding this comment.
You can make this a docstring, which makes it also show up in language servers and things like that.
Suggested change
| // Fast code path increment function. | |
| // Add inc to the string val[start..end]. This operates on ASCII digits, assuming | |
| // val and inc are well formed. | |
| // Returns the new value for start. | |
| /// Fast code path increment function. | |
| /// | |
| /// Add inc to the string val[start..end]. This operates on ASCII digits, assuming | |
| /// val and inc are well formed. | |
| /// Returns the new value for start. |
|
GNU testsuite comparison: |
…ements A lot of custom logic, we basically do arithmetic on character arrays, but this comes at with huge performance gains. Unlike coreutils `seq`, we do this for all positive increments (because why not), and we do not fall back to slow path if the last parameter is in scientific notation. Also, add some tests for empty separator, as that may catch some corner cases.
It is actually quite easy to implement, we just start with a padded number and increment as usual.
|
I feel a bit better about this, seeing that some of the extra code can be reused in #7782. We could directly merge that PR and drop this one, either way is fine. |
|
GNU testsuite comparison: |
|
Merged as part of #7782! |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
A lot of custom logic, we basically do arithmetic on character arrays, but this comes at with huge performance gains.
Unlike coreutils
seq, we do this for all positive increments (because why not), and we don't fall back to slow path if the last parameter is in scientific notation.Fixes #7482
I'm not too sure what I think about this ,-) This is a lot of added code, but this comes with huge performance gains, around 17x in some cases (and also, it was a fun puzzle, and I learnt quite a few new Rust things ,-P), and we are now competitive with GNU
seq:We're less conservative than
GNU, so this path also activates for ranges likes1 123 100000000(the GNU manual says they do something special below 200 increment, but I suspect that value is lower) and1e11, as long as the desired precision is still zero (a.k.a. integers).Still a draft, probably want to add something to
BENCHMARKING.md, a few more tests, and see if I can extract a bit more performance...