[m-rev.] for review: speed up string to int and string to uint conversion
Julien Fischer
jfischer at opturion.com
Sun Aug 9 13:58:31 AEST 2026
For review by anyone.
* There is no test case for the issue with base_string_to_uint because
the test suit does not contain a test for that predicate (beyond the overflow
tests I added recently). The test of base_string_to_int, while
present, is also
quite sparse. I will add more extensive tests of both in a separate change.
* I will add the the benchmark program to the benchmarks suite after
generalising it a bit.
----------------------------------------------------------------------------
Speed up string to int and string to uint conversion.
Fix a bug in string to uint conversion.
String to int or uint conversion has a number of performance problems.
The two main ones are:
1. The code uses the higher-order predicate string.foldl_between/6.
As the closure passed to this predicate has multiple possible values
(due to specializtion for common bases), this code is not readily
amenable to higher-order specialization.
2. The recent fix to the overflow checks (commit cac042281) introduced a
division operation in the body of the loop that processes the digits.
Furthermore, because the divisor was not a constant value, strength
reduction optimizations that the target language compilers apply to division
by a constant do *not* apply here.
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. It arranges the overflow test in such a way that the
division is invariant and can be hoisted out of the loop. The full details
are given in the comment attached to the code.
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.)
While working on this, I encountered a bug in string to uint conversion:
string.base_string_to_uint(Base, "", 0u) succeeds instead of failing.
This is due to a missing emptiness check on the input string. (In the signed
case, we read the first character to test for a sign, and that read checks for
non-emptiness).
library/string.m:
Replace the use of higher-order code in string to int and string to
uint conversions.
Use the cheaper test for overflow.
Add a missing check for an empty string in base_string_to_uint/3.
Document that base_string_to_{int,uint} and friends will throw
an exception if the given base is not in 2..36.
Julien.
diff --git a/library/string.m b/library/string.m
index 846fa8eb9..37022f27d 100644
--- a/library/string.m
+++ b/library/string.m
@@ -1568,14 +1568,15 @@
% 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].
%
:- 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.
@@ -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.
% 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.
@@ -5976,24 +5979,17 @@ string_to_doc(S) = pretty_printer.string_to_doc(S).
%
to_int(String, Int) :-
- base_string_to_int(10, String, Int).
+ do_base_string_to_int(10, String, Int).
det_to_int(S) = det_base_string_to_int(10, S).
base_string_to_int(Base, String, Int) :-
- string.index(String, 0, Char),
- End = string.count_code_units(String),
- ( if
- ( Char = ('-'), FoldPred = base_negative_int_accumulator(Base)
- ; Char = ('+'), FoldPred = base_positive_int_accumulator(Base)
- )
- then
- % Start at the first digit, which *should* be just after the sign.
- End > 1,
- foldl_between(FoldPred, String, 1, End, 0, Int)
+ ( if 2 =< Base, Base =< 36 then
+ do_base_string_to_int(Base, String, Int)
else
- FoldPred = base_positive_int_accumulator(Base),
- foldl_between(FoldPred, String, 0, End, 0, Int)
+ string.format("the base must be between 2 and 36; %d is not",
+ [i(Base)], Msg),
+ unexpected($pred, Msg)
).
det_base_string_to_int(Base, S) = N :-
@@ -6005,87 +6001,166 @@ det_base_string_to_int(Base, S) = N :-
%---------------------%
-:- func base_positive_int_accumulator(int) = pred(char, int, int).
-:- mode base_positive_int_accumulator(in) =
- out(pred(in, in, out) is semidet) is det.
-
-base_positive_int_accumulator(Base) = Pred :-
- % Avoid allocating a closure for the common bases. A more general, but
- % finicky, way to avoid the allocation is to inline foldl_between so that
- % the higher-order calls in base_string_to_int can be specialised.
- % The redundant closures will also need to be deleted by unused argument
- % elimination.
- ( if Base = 10 then
- Pred = accumulate_positive_int(10)
- else if Base = 16 then
- Pred = accumulate_positive_int(16)
- else if Base = 8 then
- Pred = accumulate_positive_int(8)
- else if Base = 2 then
- Pred = accumulate_positive_int(2)
- else if 2 =< Base, Base =< 36 then
- Pred = accumulate_positive_int(Base)
- else
- string.format("the base must be between 2 and 36; %d is not",
- [i(Base)], Msg),
- unexpected($pred, Msg)
- ).
+:- type int_sign
+ ---> positive
+ ; negative.
-:- pred accumulate_positive_int(int::in, char::in, int::in, int::out)
is semidet.
+:- pred do_base_string_to_int(int::in, string::in, int::out) is semidet.
-accumulate_positive_int(Base, Char, N0, N) :-
- char.unsafe_base_digit_to_int(Base, Char, M),
- % Fail if Base * N0 + M would exceed max_int.
- % The division is safe since our caller sets Base to be in 2..36.
- N0 =< (max_int - M) `unchecked_quotient` Base,
- N = (Base * N0) + M.
+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,
+ 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)
+ ).
-:- func base_negative_int_accumulator(int) = pred(char, int, int).
-:- mode base_negative_int_accumulator(in) = out(pred(in, in, out) is semidet)
- is det.
+ % 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.
+ %
+ % We must detect the overflow *before* it happens. Computing
+ % (Base * !.Int) + M and then testing the result does not work,
+ % because the multiplication may overflow by more than the range of
+ % an int. In that case the wrapped-around result is again greater
+ % 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:
+ %
+ % CutOff = max_int // Base
+ % CutLimit = max_int rem Base (0 =< CutLimit < Base)
+ %
+ % Given these, (Base * !.Int) + M does not exceed max_int if and only
+ % if either:
+ %
+ % - !.Int < CutOff, in which case, since M < Base,
+ %
+ % (Base * !.Int) + M =< (Base * (CutOff - 1)) + (Base - 1)
+ % = (Base * CutOff) - 1
+ % =< max_int
+ %
+ % whatever the digit is; or
+ %
+ % - !.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.
+ %
+:- pred do_base_string_to_positive_int_loop(int::in, int::in, int::in,
+ string::in, int::in, int::in, int::in, int::out) is semidet.
-base_negative_int_accumulator(Base) = Pred :-
- % Avoid allocating a closure for the common bases.
- ( if Base = 10 then
- Pred = accumulate_negative_int(10)
- else if Base = 16 then
- Pred = accumulate_negative_int(16)
- else if Base = 8 then
- Pred = accumulate_negative_int(8)
- else if Base = 2 then
- Pred = accumulate_negative_int(2)
- else if 2 =< Base, Base =< 36 then
- Pred = accumulate_negative_int(Base)
+do_base_string_to_positive_int_loop(Base, CutOff, CutLimit, String,
+ I, End, !Int) :-
+ ( if I < End then
+ unsafe_index_next(String, I, J, Char),
+ char.unsafe_base_digit_to_int(Base, Char, M),
+ % Fail if (Base * !.Int) + M would exceed max_int.
+ ( !.Int < CutOff
+ ; !.Int = CutOff, M =< CutLimit
+ ),
+ !:Int = (Base * !.Int) + M,
+ do_base_string_to_positive_int_loop(Base, CutOff, CutLimit, String,
+ J, End, !Int)
else
- string.format("the base must be between 2 and 36; %d is not",
- [i(Base)], Msg),
- unexpected($pred, Msg)
+ true
).
-:- pred accumulate_negative_int(int::in, char::in,
- int::in, int::out) is semidet.
-
-accumulate_negative_int(Base, Char, N0, N) :-
- char.unsafe_base_digit_to_int(Base, Char, M),
- % Fail if Base * N0 - M would be less than min_int.
- % We must use truncating division in the following check.
- % Flooring division (i.e. div) causes the test to succeed
- % for values of N0 for which the multiplication overflows.
- % The division is safe since our caller sets Base to be in 2..36.
- N0 >= (min_int + M) `unchecked_quotient` Base,
- N = (Base * N0) - M.
+ % 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
+ %
+ % CutOff = min_int // Base
+ % CutLimit = -(min_int rem Base)
+ %
+ % so that min_int = (Base * CutOff) - CutLimit, where CutLimit is
+ % again in 0 .. Base-1. The test mirrors the positive case: the step
+ % is safe if !.Int > CutOff, whatever the digit is, or if
+ % !.Int = CutOff and M =< CutLimit.
+ %
+ % Note that these must be the truncating quotient and remainder,
+ % For a negative dividend, truncation rounds towards zero, which makes
+ % CutOff the ceiling of the exact quotient min_int / Base; that is the
+ % tight bound on !.Int. Flooring division yields a CutOff one lower
+ % whenever Base does not divide min_int exactly, and the test
+ % !.Int > CutOff would then accept an accumulator value whose next step
+ % overflows. With 32-bit ints and Base = 10, for example, it would
+ % convert "-2147483649" to 2147483647 instead of failing.
+ %
+ % Note also that we cannot avoid the issue by accumulating a
+ % positive value and negating it at the end, since the magnitude of
+ % min_int is not representable as a positive int.
+ %
+:- pred do_base_string_to_negative_int_loop(int::in, int::in, int::in,
+ string::in, int::in, int::in, int::in, int::out) is semidet.
+
+do_base_string_to_negative_int_loop(Base, CutOff, CutLimit, String,
+ I, End, !Int) :-
+ ( if I < End then
+ unsafe_index_next(String, I, J, Char),
+ char.unsafe_base_digit_to_int(Base, Char, M),
+ % Fail if (Base * !.Int) - M would be less than min_int.
+ ( !.Int > CutOff
+ ; !.Int = CutOff, M =< CutLimit
+ ),
+ !:Int = (Base * !.Int) - M,
+ do_base_string_to_negative_int_loop(Base, CutOff, CutLimit, String,
+ J, End, !Int)
+ else
+ true
+ ).
%---------------------%
to_uint(String, UInt) :-
- base_string_to_uint(10, String, UInt).
+ do_base_string_to_uint(10, String, UInt).
det_to_uint(S) = det_base_string_to_uint(10, S).
base_string_to_uint(Base, String, UInt) :-
- End = string.count_code_units(String),
- foldl_between(base_uint_accumulator(Base), String,
- 0, End, 0u, UInt).
+ ( if 2 =< Base, Base =< 36 then
+ do_base_string_to_uint(Base, String, UInt)
+ else
+ string.format("the base must be between 2 and 36; %d is not",
+ [i(Base)], Msg),
+ unexpected($pred, Msg)
+ ).
det_base_string_to_uint(Base, S) = N :-
( if base_string_to_uint(Base, S, N0) then
@@ -6096,42 +6171,41 @@ det_base_string_to_uint(Base, S) = N :-
%---------------------%
-:- func base_uint_accumulator(int) = pred(char, uint, uint).
-:- mode base_uint_accumulator(in) =
- out(pred(in, in, out) is semidet) is det.
-
-base_uint_accumulator(Base) = Pred :-
- % Avoid allocating a closure for the common bases. A more general, but
- % finicky, way to avoid the allocation is to inline foldl_between so that
- % the higher-order calls in base_string_to_int can be specialised.
- % The redundant closures will also need to be deleted by unused argument
- % elimination.
- ( if Base = 10 then
- Pred = accumulate_uint(10u, 10)
- else if Base = 16 then
- Pred = accumulate_uint(16u, 16)
- else if Base = 8 then
- Pred = accumulate_uint(8u, 8)
- else if Base = 2 then
- Pred = accumulate_uint(2u, 2)
- else if 2 =< Base, Base =< 36 then
- Pred = accumulate_uint(uint.det_from_int(Base), Base)
- else
- string.format("the base must be between 2 and 36; %d is not",
- [i(Base)], Msg),
- unexpected($pred, Msg)
- ).
+:- pred do_base_string_to_uint(int::in, string::in, uint::out) is semidet.
-:- pred accumulate_uint(uint::in, int::in, char::in, uint::in, uint::out)
- is semidet.
+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).
-accumulate_uint(Base, BaseInt, Char, N0, N) :-
- char.unsafe_base_digit_to_int(BaseInt, Char, M),
- MU = uint.det_from_int(M),
- % Fail if Base * N0 + MU would exceed max_uint.
- % The division is safe since our caller sets Base to be in 2..36.
- N0 =< (max_uint - MU) `unchecked_quotient` Base,
- N = (Base * N0) + MU.
+ % 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),
+ % Fail if (UBase * !.UInt) + MU would exceed max_uint.
+ ( !.UInt < CutOff
+ ; !.UInt = CutOff, MU =< CutLimit
+ ),
+ !:UInt = (UBase * !.UInt) + MU,
+ do_base_string_to_uint_loop(UBase, Base, CutOff, CutLimit, String,
+ J, End, !UInt)
+ else
+ true
+ ).
%---------------------%
More information about the reviews
mailing list