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

[Julien Fischer]

On Sat, 12 Sept 2026 at 23:58, Zoltan Somogyi <zoltan.somogyi at runbox.com> wrote:
>
>
>
> 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,/

Done.


> s/when/in situations where/

Done.


> > 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.

Done.

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

I have removed the parenthese and put an equals sign between them.

> > 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.

Done.

> > 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.

True.

...

> > --- 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 ..

Done.

...

> > @@ -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.

Done.

> > --- 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/

Fixed.

> The diff is otherwise fine.

Thanks for the review.

Julien.