Skip to content

Speed up string to integer conversion tooΒ #87249

Open
@wooster0

Description

Now that #86761 is merged, it might be worth looking in other places too where potentially faster conversion algorithms can be used. This page has quite a lot of them:
https://johnnylee-sde.github.io/
One of them is this string to integer conversion algorithm: https://johnnylee-sde.github.io/Fast-numeric-string-to-int/
This algorithm is also used and mention in #86761 under Digit Parsing Improvements. It seems this approach allows parsing 8 digits at once instead of parsing one digit at a time which is what the algorithm in core currently does for integer to string conversion:
https://doc.rust-lang.org/src/core/num/mod.rs.html#843
Perhaps this new algorithm can then be reused in some form or another in the float parsing algorithm for more code reusage.

Here is a proof of concept program making use of the final algorithm at the bottom of the Fast numeric string to int article:

fn main() {
    let num = b"12345678";

    let mut sum = unsafe { *(num as *const u8 as *mut i64) };
    sum = (sum & 0xf0f0f0f0f0f0f0f).wrapping_mul(2561) >> 8;
    sum = (sum & 0xff00ff00ff00ff).wrapping_mul(6553601) >> 16;
    sum = (sum & 0xffff0000ffff).wrapping_mul(42949672960001) >> 32;

    dbg!(sum);
}
[src/main.rs:7] sum = 12345678

Metadata

Assignees

No one assigned

    Labels

    A-strArea: str and StringC-enhancementCategory: An issue proposing an enhancement or a PR with one.C-optimizationCategory: An issue highlighting optimization opportunities or PRs implementing suchE-help-wantedCall for participation: Help is requested to fix this issue.I-slowIssue: Problems and improvements with respect to performance of generated code.T-libsRelevant to the library team, which will review and decide on the PR/issue.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions