Speed up string to integer conversion too

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

[huangjj27]

How to do this in the condition of String with non-numeric characters? for example, we have to consider things like "x1234" or "0x234"

I don't think from_str_radix or parse (which uses from_str_radix internally) consider such prefixes. Neither u8::from_str_radix("xFF", 16) nor u8::from_str_radix("0xFF", 16) work (but u8::from_str_radix("FF", 16) does).
Prefixes that it does consider are + and -: https://doc.rust-lang.org/src/core/num/mod.rs.html#865 (or no prefix).
It will check for those and otherwise move on with the algorithm.

---

In this regard, I was wondering if it wouldn't be better if an alternative method is added that doesn't parse any prefixes. This could further speed up parsing for cases where the user knows that the inputs won't contain any prefixes, basically a more raw version that would specifically only focus on parsing digits. Such a method would then also be easier to integrate into the string to float algorithm for code reusage.
The goal could be to take this digit parsing algorithm currently used in the algorithm introduced in #86761 and extract it into a public method, possibly called raw_from_str_radix, from_no_prefix_str_radix or maybe positive_from_str_radix because the input takes no prefixes and the numbers will always be positive? (Although the user can always negate the resulting number later if they feel like it).

---

However, instead of that, maybe it is even better to generalize it and go a different route and make it even more configurable where you have this method and you can pass some kind of bitflags to it to tell it what kind of prefixed numbers it will receive:

bitflags! {
    /// Used to tell `specific_from_str_radix` what kind of numbers it will get.
    struct Number: u32 {
        /// A number such as `+2` and `+64`.
        const PrefixedPositive = 0b00000001;
        /// A number such as `-2` and `-64`.
        const Negative = 0b00000010;
        /// A number such as `2` and `64`.
        const NonPrefixedPositive = 0b00000100;
        /// All kinds of numbers, such as `+2, `-64` and `2`.
        const All = Self::PrefixedPositive.bits | Self::Negative.bits | Self::NonPrefixedPositive.bits;
    }
}

Something like that maybe? That method could be called maybe specific_from_str_radix or something? With a signature of pub fn specific_from_str_radix(src: &str, radix: u32, number: Number) -> Result<i32, ParseIntError>.
This would allow for maximum configurability and speed.

[Alexhuszagh]

How to do this in the condition of String with non-numeric characters? for example, we have to consider things like "x1234" or "0x234"

None of the existing functions use that, and this approach works for any radix <= 10 (there might be tricks for digits above radix 10 that could work, but it cannot merely use a bitmask to determine if all the characters are valid digits, nor to convert them into the range [0x0, b), where b is the radix).

[Alexhuszagh]

So in general, there's 2 different approaches to finding out if N digits are all valid digits, and then afterwards you can use a trick to convert them to the base numbers to process them like above (it's obviously radix-dependent, but it's not that complicated):

1. Use a wrapping add of 0x46 and wrapping sub of 0x30 for each byte, take the bitwise or, and ensure that the MSB is 0.

So, for example, with 8 digits, we have:

#[inline]
pub fn is_8digitsv: u64) -> bool {
    let a = v.wrapping_add(0x4646_4646_4646_4646);
    let b = v.wrapping_sub(0x3030_3030_3030_3030);
    (a | b) & 0x8080_8080_8080_8080 == 0
}

This works because all digits are in the range [0x30, 0x39], and 0x39 + 0x46 == 0x7F, and 0x30 - 0x30 == 0x0. So, if we have digits below, we have wrapping underflow, leading to the MSB being set, if any digits are above, the same is true.

This can be adopted for radixes <= 10, since we can just adjust 0x46 accordingly (radix 5, for example, would be 0x41).

2. We can also do a similar check, with a slightly slower optimization:

#[inline]
pub fn is_8digitsv: u64) -> bool {
    let a = v & 0xF0F0F0F0F0F0F0F0);
    let b = v.wrapping_add(0x0606060606060606) & 0xF0F0F0F0F0F0F0F0;
    (a | (b >> 4)) & 0x3333333333333333 == 0
}

Essentially, this works the same way: a just checks all of the most significant 4-bits are in the range [0x30, 0x3F], and b checks that all the least significant 4-bits are in the range [0x0, 0xF].

For radixes above 10, things get a bit more complicated.

[GollyTicker]

I'm new to rust and want to find a place to contribute. So I'm looking into this issue and attempting it myself on my fork.

I already got sokme help and pointers from the docs and the chat.

First task IMO is to have some benchmarks for the current implementation before, I can run and test variations of the optimised impl. 🤞

[purepani]

I have some code testing a more generic version of the algorithm that works for any base between 2-36. The ascii to int conversion is:

const fn ascii_to_int(src: u64) -> u64 {
    //normalizes uppercase and lowercase letters
    let val = (src & 0x4040404040404040);
    //shifts letters so that they are above the ascii numbers and then shifts them down.
    ((val >> 6) | (val >> 3) | (val >> 2)).wrapping_add(src & 0x1f1f1f1f1f1f1f1f).wrapping_sub(0x1010101010101010)
}

However, I'm finding that this isn't really speeding up anything above base 10 anyway on my computer(since the max length of a decimal is only 13, the speedup can't kick in since some values need to be dynamically calculated), so perhaps there only needs to be the fast path for anything base 10 or lower.

[Alexhuszagh]

I have some code testing a more generic version of the algorithm that works for any base between 2-36. The ascii to int conversion is:

const fn ascii_to_int(src: u64) -> u64 {
    //normalizes uppercase and lowercase letters
    let val = (src & 0x4040404040404040);
    //shifts letters so that they are above the ascii numbers and then shifts them down.
    ((val >> 6) | (val >> 3) | (val >> 2)).wrapping_add(src & 0x1f1f1f1f1f1f1f1f).wrapping_sub(0x1010101010101010)
}

However, I'm finding that this isn't really speeding up anything above base 10 anyway on my computer(since the max length of a decimal is only 13, the speedup can't kick in since some values need to be dynamically calculated), so perhaps there only needs to be the fast path for anything base 10 or lower.

This is consistent with all the benchmarking I've done internally as well. I just used this optimization for radix 10 since it's by far the most common, can almost always be optimized out since it's known at compile time, and doesn't need any generic code, however, a generic solution from 2-10 could definitely work well.