[m-rev.] for review: implement fast path string to int and uint conversion

[Zoltan Somogyi]

On Sat, 12 Sep 2026 22:27:44 +1000, Julien Fischer <jfischer at opturion.com> wrote:

> For review by anyone.
> 
> ----------------------------------------
> 
> Implement fast path string to int and uint conversion.
> 
> When converting strings to ints we can omit the overflow check when we know

s/ints/ints,/

s/when/in situations where/

> that the number of digits in the string is small enough that overflow cannot
> occur. Since conversion begins by computing the length of the string, we have
> a bound on the number of digits ready to hand. Change base_string_to_int/3 to
> check whether the number of digits is below the safe limit, and if it is, to
> use a conversion that omits the overflow check.
> 
> The safe digit limit depends on both the base and the word size. For a base
> B and word size W, it is the largest number of digits D such that every
> string of D base B digits denotes a value that is representable, i.e. the
> largest D such that B^D - 1 =< 2^(W-1) - 1 (max_int). 

The -1 after W is for the signed case. It may be different for unsigned, so
give that limit separately.

LATER ZS: I see you do. I was misled by the quiet change from both ints and uints
being mentioned in the top line, to just ints in the paragraph above. Please make
the switch clearer.

The "(max_int)" looks like a multiplier; change it so it does not do so.

> We provide two tables
> of safe digit limits, one for each word size.

We provide separate tables of safe digit limits for each possible platform word size.

> We use the limit derived from max_int for negative values as well. The bound
> that applies there is the magnitude of min_int, i.e. max_int + 1, which is
> larger, so the limit derived from it can only be the same or larger than the
> one we use. Borrowing the max_int limit is therefore never unsafe: at worst
> it would send a string to the checked path that the fast path could have
> handled. As it happens it does not even do that, since the two limits are the
> same for every base from 2 to 36 at both word sizes.
> 
> Implement the same fast path approach for string to uint conversion. The safe
> digit limit tables, likewise one per word size, are not the same as for int,
> since the bound is max_uint rather than max_int: in base 10 with 64-bit words,
> for example, 19 digits are safe for a uint but only 18 are safe for an int.

But of course, the int limits would be SAFE for uints, and there would be
very few cases in practice where this would matter. The justification for using
larger limits for uints is therefore simply that it is easy to do.

> Using the benchmark program added by this change, in asm_fast.gc, shows a speed
> up of ~11% over the existing implementation for converting 1 million randomly
> generated decimal strings of between 1 and 31 digits.

Where does that speedup come from? Wouldn't ALMOST ALL of those decimal strings
have a digit beyond the 19th, leading to the fast path being unusable?

LATER ZS: I see that the decimal strings are random but not uniform over the range,
but have a uniform distribution over the number of digits. This makes half the speedup
for roughly half of "random" larger ints falling into the fast path size range not
really surprising.

>  For 1 million randomly
> generated decimal strings of between 1 and 6 digits (i.e. where all the strings
> are below the safe limit), the speed up is ~25%.

That's impressive.

> --- a/library/string.m
> +++ b/library/string.m
> @@ -6027,22 +6027,150 @@ do_base_string_to_int(Base, String, Int) :-
>          Sign = positive,
>          Start = 0
>      ),
> -    % The divisions below are all safe since our callers set Base
> -    % to be in 2..36.

I would keep that here, because ..

> +            % These divisions (and the ones in the negative case) are all safe
> +            % since our callers set Base to be in 2..36.

... the text in parentheses here ...

> +            CutOff = max_int `unchecked_quotient` Base,
> +            CutLimit = max_int `unchecked_rem` Base,
> +            do_base_string_to_positive_int_loop(Base, CutOff, CutLimit, String,
> +                Start, End, 0, Int)
> +        )
>      ;
>          Sign = negative,
> -        CutOff = min_int `unchecked_quotient` Base,
> -        CutLimit = -(min_int `unchecked_rem` Base),
> -        do_base_string_to_negative_int_loop(Base, CutOff, CutLimit, String,
> -            Start, End, 0, Int)
> +        ( if can_use_to_int_fast_path(Base, NumStringDigits) then
> +            do_unsafe_base_string_to_negative_int_loop(Base, String,
> +                Start, End, 0, Int)
> +        else
> +            CutOff = min_int `unchecked_quotient` Base,
> +            CutLimit = -(min_int `unchecked_rem` Base),

... is harder to see from here.

> @@ -6191,12 +6357,128 @@ do_base_string_to_uint(Base, String, UInt) :-
>      End = string.count_code_units(String),
>      End > 0, % Fail if we have the empty string.
>      UBase = uint.cast_from_int(Base),
> -    % Both of these divisions are safe since our callers set Base
> -    % to be in 2..36.

Same comment as above.

> --- a/tests/general/test_string_to_int_overflow.m
> +++ b/tests/general/test_string_to_int_overflow.m
> @@ -120,6 +120,88 @@ main(!IO) :-
>      test(base_string_to_int(10, "+9223372036854775807"), !IO),
>      test(base_string_to_int(10, "+9223372036854775808"), !IO),
> 
> +    % The base_string_to_int/3 fast path skips the overflow check entirely for
> +    % strings that are short enough no string of that many digits can overflow.
> +    % The number of digits for which this holds depends on the base and the
> +    % word size; see safe_int_digits_for_word{32,64}_and_base in string.m.
> +    %
> +    % The following paired tests check that the overflow behaviour is correct
> +    % at boundary between the fast and checked paths.

s/at/at the/

The diff is otherwise fine.

Zoltan.