local_-mode functions compare ~localize, equal ~localize, and globalize derivationsinfinity and neg_infinity to Bignumround, iround, round_as_bigint, iround_exn, round_as_bigint_exn, and round_decimal functions now support Bankers rounding directionChanges to Stable and Unstable modules:
equal derivation from Stable.t and Unstable.tequal functions to Stable and Unstable modules that adhere to IEEE float semantics, treating nan as not equal to nanBig_int
stable_witness derivation to both the BigInt.Stable.V1 and BigInt.Stable.V2 modules. This facilitates compatibility checks between different versions of serialized dataBig_num
Add deriving attributes:
Bignum.t, Bignum.Stable.t, and Bignum.Unstable.t derive sexp_grammarAdd new functions to Bignum:
truncate: Rounds the input towards zero to an integeris_infinite: Returns true if the number is either positive or negative infinityis_positive_infinity: Returns true if the number is positive infinityis_negative_infinity: Returns true if the number is negative infinityarg_type to Bignum, for ease of use in Command.t based parsers'_' followed by a concat, which allocated a bunch of intermediate strings.Zarith.Q's compare, in a few locations. Fixed this.Bignum.of_string needs to handle different formats for its input. The previous version of the code was trying to parse the common format (floats), and in case of failure, was attempting to use a different format (based on the error). This resulted in the string being parsed twice in some cases.
This version is a complete rewriting of of_string to do the parsing in one step. The new code for to_string encode an automaton and remembers the positions of the various elements of the string (depending on the format).
This feature uses a function which has been upstreamed in the new version of ZArith (1.4) which is a variant of the Zarith.of_string function to work with substrings. This variant alone is responsible for a big part of the performance improvement.
The new version of the code performs better than the original one in all cases. The performance improvement are variable depending on the micro benchmark. See below.
We also tried to implement the lexing engine using OCamllex. This makes for a much more concise description, but the performance are significantly lower. OCamllex produces code which allocates some table and some state, which is avoided in the hand written code. Also, it will allocate the sub strings matched.
New version (patch for ZArith + of_substring, reimplementation of of_string)
┌─────────────────────────────────────────────────────────────────────┬──────────────┬───────────┬──────────┬──────────┬────────────┐ │ Name │ Time/Run │ mWd/Run │ mjWd/Run │ Prom/Run │ Percentage │ ├─────────────────────────────────────────────────────────────────────┼──────────────┼───────────┼──────────┼──────────┼────────────┤ │ bigint\_bench.ml random │ 48_381.13ns │ 7_166.00w │ 1.24w │ 1.24w │ 45.12% │ │ bigint\_bench.ml:vs. Big\_int plus_self │ 293.96ns │ 72.00w │ │ │ 0.27% │ │ bigint\_bench.ml:vs. Big\_int plus_other │ 807.62ns │ 124.00w │ │ │ 0.75% │ │ bigint\_bench.ml:vs. Big\_int mult_self │ 353.98ns │ 91.00w │ │ │ 0.33% │ │ bigint\_bench.ml:vs. Big\_int mult_other │ 783.78ns │ 128.00w │ │ │ 0.73% │ │ bignum\_bench.ml:Bignum of\_string/to\_string of_string (decimal) │ 14_415.44ns │ 475.00w │ │ │ 13.44% │ │ bignum\_bench.ml:Bignum of\_string/to\_string of_string (scientific) │ 61_363.80ns │ 3_929.00w │ │ │ 57.23% │ │ bignum\_bench.ml:Bignum of\_string/to\_string of_string (fraction) │ 24_957.02ns │ 303.00w │ │ │ 23.28% │ │ bignum\_bench.ml:Bignum of\_string/to\_string to_string (decimal) │ 15_867.52ns │ 1_523.00w │ │ │ 14.80% │ │ bignum\_bench.ml:Bignum of\_string/to\_string to_string (scientific) │ 33_345.31ns │ 4_206.00w │ │ │ 31.10% │ │ bignum\_bench.ml:Bignum of\_string/to\_string to_string (fraction) │ 31_770.26ns │ 3_779.00w │ │ │ 29.63% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp of_sexp (decimal) │ 9_726.82ns │ 380.00w │ │ │ 9.07% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp of_sexp (scientific) │ 28_141.40ns │ 2_059.00w │ │ │ 26.25% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp of_sexp (fraction) │ 70_436.16ns │ 5_541.00w │ │ │ 65.69% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp to_sexp (decimal) │ 27_000.73ns │ 1_994.00w │ │ │ 25.18% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp to_sexp (scientific) │ 66_057.63ns │ 6_217.00w │ │ │ 61.61% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp to_sexp (fraction) │ 107_219.89ns │ 8_097.00w │ │ │ 100.00% │ │ bignum\_bench.ml:Bignum binprot roundtrip compact │ 5_997.81ns │ 581.00w │ │ │ 5.59% │ │ bignum\_bench.ml:Bignum binprot roundtrip classic │ 18_522.20ns │ 779.00w │ │ │ 17.27% │ │ bignum\_bench.ml:round round_decimal:0 │ 8_479.49ns │ 463.00w │ │ │ 7.91% │ │ bignum\_bench.ml:round round_decimal:3 │ 24_621.71ns │ 2_115.00w │ │ │ 22.96% │ │ bignum\_bench.ml:round round_decimal:6 │ 26_896.35ns │ 2_437.00w │ │ │ 25.09% │ │ bignum\_bench.ml:round round_decimal:9 │ 29_428.19ns │ 2_730.00w │ │ │ 27.45% │ │ bignum\_bench.ml:round round │ 8_452.31ns │ 459.00w │ │ │ 7.88% │ └─────────────────────────────────────────────────────────────────────┴──────────────┴───────────┴──────────┴──────────┴────────────┘
Original version
┌─────────────────────────────────────────────────────────────────────┬──────────────┬───────────┬──────────┬──────────┬────────────┐ │ Name │ Time/Run │ mWd/Run │ mjWd/Run │ Prom/Run │ Percentage │ ├─────────────────────────────────────────────────────────────────────┼──────────────┼───────────┼──────────┼──────────┼────────────┤ │ bigint\_bench.ml random │ 51_218.04ns │ 7_166.00w │ 1.25w │ 1.25w │ 43.26% │ │ bigint\_bench.ml:vs. Big\_int plus_self │ 336.84ns │ 72.00w │ │ │ 0.28% │ │ bigint\_bench.ml:vs. Big\_int plus_other │ 837.73ns │ 124.00w │ │ │ 0.71% │ │ bigint\_bench.ml:vs. Big\_int mult_self │ 411.03ns │ 91.00w │ │ │ 0.35% │ │ bigint\_bench.ml:vs. Big\_int mult_other │ 808.03ns │ 128.00w │ │ │ 0.68% │ │ bignum\_bench.ml:Bignum of\_string/to\_string of_string (decimal) │ 29_650.60ns │ 2_415.00w │ │ │ 25.04% │ │ bignum\_bench.ml:Bignum of\_string/to\_string of_string (scientific) │ 92_495.93ns │ 6_465.00w │ │ │ 78.12% │ │ bignum\_bench.ml:Bignum of\_string/to\_string of_string (fraction) │ 39_482.77ns │ 2_060.00w │ │ │ 33.35% │ │ bignum\_bench.ml:Bignum of\_string/to\_string to_string (decimal) │ 16_195.93ns │ 1_523.00w │ │ │ 13.68% │ │ bignum\_bench.ml:Bignum of\_string/to\_string to_string (scientific) │ 34_227.78ns │ 4_059.00w │ │ │ 28.91% │ │ bignum\_bench.ml:Bignum of\_string/to\_string to_string (fraction) │ 32_856.17ns │ 3_779.00w │ │ │ 27.75% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp of_sexp (decimal) │ 19_745.71ns │ 2_149.00w │ │ │ 16.68% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp of_sexp (scientific) │ 51_024.99ns │ 3_853.00w │ │ │ 43.09% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp of_sexp (fraction) │ 88_884.15ns │ 7_819.00w │ │ │ 75.07% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp to_sexp (decimal) │ 32_812.27ns │ 2_498.00w │ │ │ 27.71% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp to_sexp (scientific) │ 77_518.77ns │ 6_369.00w │ │ │ 65.47% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp to_sexp (fraction) │ 118_402.78ns │ 8_907.00w │ │ │ 100.00% │ │ bignum\_bench.ml:Bignum binprot roundtrip compact │ 8_947.02ns │ 371.00w │ │ │ 7.56% │ │ bignum\_bench.ml:Bignum binprot roundtrip classic │ 22_799.74ns │ 1_039.00w │ │ │ 19.26% │ │ bignum\_bench.ml:round round_decimal:0 │ 8_176.74ns │ 463.00w │ │ │ 6.91% │ │ bignum\_bench.ml:round round_decimal:3 │ 25_798.77ns │ 2_115.00w │ │ │ 21.79% │ │ bignum\_bench.ml:round round_decimal:6 │ 28_561.23ns │ 2_437.00w │ │ │ 24.12% │ │ bignum\_bench.ml:round round_decimal:9 │ 30_861.38ns │ 2_730.00w │ │ │ 26.06% │ │ bignum\_bench.ml:round round │ 8_237.26ns │ 459.00w │ │ │ 6.96% │ └─────────────────────────────────────────────────────────────────────┴──────────────┴───────────┴──────────┴──────────┴────────────┘
Tentative version using OCamllex
┌─────────────────────────────────────────────────────────────────────┬──────────────┬────────────┬──────────┬──────────┬────────────┐ │ Name │ Time/Run │ mWd/Run │ mjWd/Run │ Prom/Run │ Percentage │ ├─────────────────────────────────────────────────────────────────────┼──────────────┼────────────┼──────────┼──────────┼────────────┤ │ bigint\_bench.ml random │ 48_164.21ns │ 7_166.00w │ 1.25w │ 1.25w │ 39.99% │ │ bigint\_bench.ml:vs. Big\_int plus_self │ 285.84ns │ 72.00w │ │ │ 0.24% │ │ bigint\_bench.ml:vs. Big\_int plus_other │ 768.12ns │ 124.00w │ │ │ 0.64% │ │ bigint\_bench.ml:vs. Big\_int mult_self │ 343.14ns │ 91.00w │ │ │ 0.28% │ │ bigint\_bench.ml:vs. Big\_int mult_other │ 780.00ns │ 128.00w │ │ │ 0.65% │ │ bignum\_bench.ml:Bignum of\_string/to\_string of_string (decimal) │ 26_931.12ns │ 3_108.00w │ │ │ 22.36% │ │ bignum\_bench.ml:Bignum of\_string/to\_string of_string (scientific) │ 79_750.28ns │ 6_599.00w │ 0.11w │ 0.11w │ 66.21% │ │ bignum\_bench.ml:Bignum of\_string/to\_string of_string (fraction) │ 34_988.94ns │ 4_300.00w │ │ │ 29.05% │ │ bignum\_bench.ml:Bignum of\_string/to\_string to_string (decimal) │ 15_958.17ns │ 1_523.00w │ │ │ 13.25% │ │ bignum\_bench.ml:Bignum of\_string/to\_string to_string (scientific) │ 32_495.25ns │ 4_059.00w │ │ │ 26.98% │ │ bignum\_bench.ml:Bignum of\_string/to\_string to_string (fraction) │ 31_802.75ns │ 3_779.00w │ │ │ 26.40% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp of_sexp (decimal) │ 18_742.81ns │ 2_924.00w │ │ │ 15.56% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp of_sexp (scientific) │ 45_282.09ns │ 4_622.00w │ │ │ 37.60% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp of_sexp (fraction) │ 86_907.83ns │ 8_777.00w │ 0.15w │ 0.15w │ 72.16% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp to_sexp (decimal) │ 35_727.73ns │ 4_493.00w │ │ │ 29.66% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp to_sexp (scientific) │ 82_247.61ns │ 8_273.00w │ 0.13w │ 0.13w │ 68.29% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp to_sexp (fraction) │ 120_445.25ns │ 10_688.00w │ 0.12w │ 0.12w │ 100.00% │ │ bignum\_bench.ml:Bignum binprot roundtrip compact │ 6_734.49ns │ 371.00w │ │ │ 5.59% │ │ bignum\_bench.ml:Bignum binprot roundtrip classic │ 21_773.79ns │ 1_890.00w │ │ │ 18.08% │ │ bignum\_bench.ml:round round_decimal:0 │ 8_306.45ns │ 463.00w │ │ │ 6.90% │ │ bignum\_bench.ml:round round_decimal:3 │ 24_714.96ns │ 2_115.00w │ │ │ 20.52% │ │ bignum\_bench.ml:round round_decimal:6 │ 26_894.27ns │ 2_437.00w │ │ │ 22.33% │ │ bignum\_bench.ml:round round_decimal:9 │ 29_343.81ns │ 2_730.00w │ │ │ 24.36% │ │ bignum\_bench.ml:round round │ 8_296.05ns │ 459.00w │ │ │ 6.89% │ └─────────────────────────────────────────────────────────────────────┴──────────────┴────────────┴──────────┴──────────┴────────────┘
Fixed a bug in the =Zarith= library's to_float function.
These fixes first introduce tests from the base distribution, and then backport a bugfix to the handling of to_float.
Big_int.Bignum.sexp_of_t when the denominator is zero.Bigint.random function, which produces a uniformly distributed value.Bignum.t to Bigint.t, and to convert Bigint.t into Bignum.t.Bignum.Bigint module, with arbitrary-precision integers based on Zarith, which is significantly faster than the Num.Big_int library.Bignum on Re2, and reduced dependence from Core to Core_kernel.Improved the performance of Bignum's binprot.
Bignum's binprot had been to just binprot the decimal string representation. This is both slow to do and unnecessarily big in the majority of cases. Did something better in the majority of cases and fell back to this representation in the exceptional case.
$ ./inline_benchmarks_runner
Estimated testing time 20s (2 benchmarks x 10s). Change using -quota SECS.Name | Time/Run | mWd/Run | Percentage |
|---|---|---|---|
bignum0.ml:Stable:Bignum binprot roundtrip compact | 7.87us | 490.00w | 32.88% |
bignum0.ml:Stable:Bignum binprot roundtrip classic | 23.94us | 1_079.00w | 100.00% |