[m-rev.] for review: speed up string to int and string to uint conversion

[Zoltan Somogyi]

On Sun, 9 Aug 2026 13:58:31 +1000, Julien Fischer <jfischer at opturion.com> wrote:

> Some smaller inefficiencies are present as well, such as computing the length
> of the input string twice instead of just once, or using a checked int to uint
> conversion where a cast would be safe.
> 
> This diff addresses issue (1) by avoiding the use of higher-order code
> completely. This is much faster and not any more verbose than the existing
> code (which was quite verbose for reasons of its own).
> 
> Issue (2) is resolved using a technique from strtol() implementations in
> various C libraries.

I would reword this in the active voice.

> It arranges the overflow test in such a way that the
> division is invariant and can be hoisted out of the loop.

LOOP invariant.

> 
> I benchmarked string.to_int/2 using the benchmarking module on one million
> randomly generated strings of between 1 and 31 digits. At the default
> optimization level in asm_fast.gc on my machine, the results are as follows:
> 
>     rotd-2026-05-03: 3170 ms (higher-order, old broken overflow check)
>     rotd-2026-08-04: 4150 ms (higher-order, one div per loop overflow check)
>     this diff: 1740 ms
> 
> (This is far from a systematic benchmark, but the results speak for
> themselves.)

Yes, they do!

>      % preceded by a plus or minus sign. For bases > 10, digits 10 to 35
>      % are represented by the letters A-Z or a-z. If the string does not match
>      % this syntax or the number is not in the range [min_int, max_int],
> -    % the predicate fails.
> +    % the predicate fails. An exception is thrown if the specified base is
> +    % not in [2, 36].

Throws an exception if ...

>  :- pred base_string_to_int(int::in, string::in, int::out) is semidet.
> 
>      % Convert a signed base N string to an int. Throws an exception
>      % if the string argument is not precisely an optional sign followed by
>      % a non-empty string of base N digits, or if the number is not in
> -    % the range [min_int, max_int].
> +    % the range [min_int, max_int], or if the specified base is not in [2, 36].
>      %
>  :- func det_base_string_to_int(int, string) = int.

Put a line break before "Throws", and start each condition on a new line
with a minus sign, as if in an itemize scope.

> @@ -1597,13 +1598,15 @@
>      % must contain one or more digits in the specified base. For bases > 10,
>      % digits 10 to 35 are represented by the letters A-Z or a-z. If the string
>      % does not match this syntax or the number is not in the range
> -    % [0, max_uint], the predicate fails.
> +    % [0, max_uint], the predicate fails. An exception is thrown if the
> +    % specified base is not in [2, 36].
>      %
>  :- pred base_string_to_uint(int::in, string::in, uint::out) is semidet.

Throws an exception if ...

>      % Convert an unsigned base N string to a uint. Throws an exception
>      % if the string argument is not precisely a non-empty string of base N
> -    % digits, or if the number is not in the range [0, max_uint].
> +    % digits, or if the number is not in the range [0, max_uint], or if
> +    % the specified base is not in [2, 36].
>      %
>  :- func det_base_string_to_uint(int, string) = uint.

Again, use itemize-like layout.

> +do_base_string_to_int(Base, String, Int) :-
> +    string.index(String, 0, Char),
> +    End = string.count_code_units(String),
> +    ( if
> +        ( Char = ('-'), Sign0 = negative
> +        ; Char = ('+'), Sign0 = positive
> +        )
> +    then
> +        Sign = Sign0,
> +        % Start at the first digit, which *should* be just after the sign.
> +        End > 1,
> +        Start = 1
> +    else
> +        Sign = positive,
> +        Start = 0
> +    ),
> +    % The divisions below are all safe since our callers set Base
> +    % to be in 2..36.
> +    (
> +        Sign = positive,
> +        CutOff = max_int `unchecked_quotient` Base,
> +        CutLimit = max_int `unchecked_rem` Base,

If you are looking for further speedups, this could be done here.
Realistically, there are two possible values of max_int, and therefore
we could do a lookup in one of two 36-element precomputed arrays,
at least when targeting C. (Arranging access to such an array may be
slower than two divisions in Java/C#.)

> +    % Convert the base Base digits of String between I and End into an int,
> +    % accumulating the result in !Int. Fail if the value being accumulated
> +    % would exceed max_int.

To make that sentence make sense, you need to duplicate the clause head
at the start of the comment. Without it, the reader does not know what I is.
In any case, I would rename it as "CurOffset", and rename J as "NextOffset".
Likewise, End->EndOffset.

> +    % We must detect the overflow *before* it happens. Computing
> +    % (Base * !.Int) + M and then testing the result does not work,

... or !.Int.

> +    % because the multiplication may overflow by more than the range of
> +    % an int. In that case the wrapped-around result is again greater

Add comma after "case".

> +    % than !.Int, and so is indistinguishable from a result that did not
> +    % overflow.
> +    %
> +    % Requiring that !.Int =< (max_int - M) // Base be true at each iteration
> +    % of the loop does detect overflow, but at the cost of having a division in
> +    % each iteration.
> +    %
> +    % Instead, we can hoist the division out of the loop body observing that
> +    % the above check depends on the digit M only through a comparison that
> +    % can be split into cases. Specifically, we can write max_int as:
> +    %
> +    %   max_int = (Base * CutOff) + CutLimit
> +    %
> +    % CutOff and CutLimit are invariant and our caller can compute them as:

*will* compute them as

> +    %   CutOff   = max_int // Base
> +    %   CutLimit = max_int rem Base  (0 =< CutLimit < Base)

I would add "implying" before "0".

> +    % Given these, (Base * !.Int) + M does not exceed max_int if and only
> +    % if either:

To make this make sense, you have to first tell the reader what M is,
and that it is less than Base.

> +    % - !.Int < CutOff, in which case, since M < Base,
> +    %
> +    %       (Base * !.Int) + M =< (Base * (CutOff - 1)) + (Base - 1)
> +    %                           = (Base * CutOff) - 1
> +    %                          =< max_int
> +    %

At first, I didn't see where the first line's inequality comes from.
Say explicitly it comes from !.Int < CutOff. or just replace "since M < Base"
with "therefore".

> +    %   whatever the digit is; or

the digit M is

> +    % - !.Int = CutOff and M =< CutLimit, in which case
> +    %
> +    %       (Base * !.Int) + M =< (Base * CutOff) + CutLimit = max_int.
> +    %
> +    % If !.Int > CutOff, then (Base * !.Int) >= (Base * CutOff) + Base,
> +    % which exceeds max_int whatever the digit is.

Add a line break and an indent after "then", to make this case look like
the first two.

I don't think CutOff and CutLimit are good names for these roles,
because in a sense they are BOTH limits.

A good name for CutOff would tell readers that this is the maximum
that !.Int can be before the addition of a digit, and the CutLimit
is the max value of that digit *if* !.Int = CutOff. However, right now
I also cannot think of any *short* names that do that. Maybe
something like MaxSoFar/MaxBeforeNextDigit and MaxNextDigit?

> +    % As for do_base_string_to_positive_int_loop above, but accumulate a
> +    % negative value, and fail if it would be less than min_int.
> +    % Here our caller gives us

s/As for/This predicate is similar to/, and then adjust the verbs.
And the comments above apply here as well.

> +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.
> +    CutOff = max_uint `unchecked_quotient` UBase,
> +    CutLimit = max_uint `unchecked_rem` UBase,
> +    do_base_string_to_uint_loop(UBase, Base, CutOff, CutLimit, String,
> +        0, End, 0u, UInt).

And here.

> +    % The overflow check here is the one described in the comment on
> +    % do_base_string_to_positive_int_loop above.
> +    %
> +:- pred do_base_string_to_uint_loop(uint::in, int::in, uint::in, uint::in,
> +    string::in, int::in, int::in, uint::in, uint::out) is semidet.
> +
> +do_base_string_to_uint_loop(UBase, Base, CutOff, CutLimit, String,
> +        I, End, !UInt) :-
> +    ( if I < End then
> +        unsafe_index_next(String, I, J, Char),
> +        char.unsafe_base_digit_to_int(Base, Char, M),
> +        MU = uint.cast_from_int(M),

I don't think this cast is a builtin. You can eliminate its runtime cost
by adding a uint version of unsafe_base_digit_to_int. Since bases are
inherently positive, arguably *that* should be the main version anyway.

Despite the quantity of comments above, an excellent diff!

Zoltan.