Speed up `int.__round__` for large negative `ndigits`

[devdanzin]

Feature or enhancement

Proposal:

Rounding an int by a large positive ndigits is instantaneous, while a by a large negative number takes ages, only to return zero:

>>> large_number = 2**31
>>> large_negative_number = -2**31
>>> d = 17000
>>> d.__round__(large_number)  # Instant result, returns d
17000
>>> d.__round__(large_negative_number)  # Takes forever, calculating divmod(d, int(pow(10, large_negative_number)))

It could be almost as fast as the positive ndigits case by checking:

int(math.log10(d)) < abs(large_negative_number)

And returning zero if it's True.

A similar optimization is possible for Fraction: #132472

I realize there may not be a real use case for these enhancements.

cc @JelleZijlstra

Has this already been discussed elsewhere?

This is a minor feature, which does not need previous discussion elsewhere

Links to previous discussion of this feature:

It was very briefly discussed on Discord.

Linked PRs

• gh-132474: optimize rounding of int's for large negative ndigits #132579

[ZeroIntensity]

cc @skirpichev

[skirpichev]

Yes, that does make sense for me, the gmpy2 has similar optimization:
https://github.com/aleaxit/gmpy/blob/ea6cdf16064e8f5bd575c0c1b02df0ea0fa70fc4/src/gmpy2_mpz_misc.c#L269-L272
Though, this must be benchmarked.

But you should be slightly more careful. It's easy to find a counterexample for your inequality:

>>> import math
>>> d = 501
>>> n = -3
>>> round(d, n)
1000
>>> int(math.log10(d)) < abs(n)
True

calculating divmod(d, int(pow(10, large_negative_number)))

It's actually divmod_near(). You can see it's pure-Python equivalent in commentary.

[devdanzin]

But you should be slightly more careful. It's easy to find a counterexample for your inequality:

Unfortunately that's as far as my math can take me, I have no idea about how to start fixing this (other than brute forcing values to see where errors happen, trying to figure out a pattern and a convoluted way to avoid them).

[skirpichev]

Here my tests (0 coming for ndigits <= -5). As expected, slowdown for small abs(ndigits) is noticeable (patch 1).

Benchmark	ref	patch	patch2
round(17000, -1)	508 ns	647 ns: 1.27x slower	481 ns: 1.06x faster
round(17000, -2)	484 ns	618 ns: 1.28x slower	471 ns: 1.03x faster
round(17000, -3)	587 ns	672 ns: 1.14x slower	549 ns: 1.07x faster
round(17000, -4)	682 ns	784 ns: 1.15x slower	673 ns: 1.01x faster
round(17000, -5)	561 ns	696 ns: 1.24x slower	549 ns: 1.02x faster
round(17000, -6)	577 ns	312 ns: 1.85x faster	555 ns: 1.04x faster
round(17000, -7)	613 ns	313 ns: 1.96x faster	584 ns: 1.05x faster
round(17000, -8)	562 ns	312 ns: 1.80x faster	not significant
round(17000, -9)	612 ns	312 ns: 1.96x faster	595 ns: 1.03x faster
round(17000, -10)	653 ns	311 ns: 2.10x faster	658 ns: 1.01x slower
round(17000, -20)	958 ns	311 ns: 3.08x faster	197 ns: 4.87x faster
round(17000, -50)	1.45 us	311 ns: 4.66x faster	197 ns: 7.37x faster
round(17000, -100)	1.97 us	311 ns: 6.33x faster	197 ns: 9.99x faster
Geometric mean	(ref)	1.69x faster	1.61x faster

We try different cutoff tests. First version - close to the original proposal (almost literally it's math.log10(self), which we can simplify further - _PyLong_Frexp() is an important part here), second - seems cheaper, but will be successful only for much bigger abs(ndigits). I appreciate if someone repeat tests on less noisy system.

Patch and benchmark code.

Patch 1:

diff --git a/Objects/longobject.c b/Objects/longobject.c
index 692312c1ad..36f9d95b9c 100644
--- a/Objects/longobject.c
+++ b/Objects/longobject.c
@@ -6212,6 +6212,21 @@ int___round___impl(PyObject *self, PyObject *o_ndigits)
         return long_long(self);
     }
 
+    int64_t n, e;
+
+    if (PyLong_AsInt64(ndigits, &n) < 0) {
+        Py_DECREF(ndigits);
+        return NULL;
+    }
+    n = -n;
+
+    double x = _PyLong_Frexp((PyLongObject *)self, &e);
+
+    if ((int64_t)(log10(x) + 0.3010299956639812*e) < n - 1) {
+        Py_DECREF(ndigits);
+        return _PyLong_GetZero();
+    }
+
     /* result = self - divmod_near(self, 10 ** -ndigits)[1] */
     PyObject *temp = (PyObject*)long_neg((PyLongObject*)ndigits);
     Py_SETREF(ndigits, temp);

Patch 2:

diff --git a/Objects/longobject.c b/Objects/longobject.c
index 692312c1ad..6ca54cbb55 100644
--- a/Objects/longobject.c
+++ b/Objects/longobject.c
@@ -6212,6 +6212,21 @@ int___round___impl(PyObject *self, PyObject *o_ndigits)
         return long_long(self);
     }
 
+    int64_t n;
+
+    if (PyLong_AsInt64(ndigits, &n) < 0) {
+        Py_DECREF(ndigits);
+        return NULL;
+    }
+    n = -n;
+
+    int64_t nbits = _PyLong_NumBits(self) + 1;
+
+    if (nbits + 1 < n) {
+        Py_DECREF(ndigits);
+        return _PyLong_GetZero();
+    }
+
     /* result = self - divmod_near(self, 10 ** -ndigits)[1] */
     PyObject *temp = (PyObject*)long_neg((PyLongObject*)ndigits);
     Py_SETREF(ndigits, temp);

# bench.py
import pyperf
runner = pyperf.Runner()
d = 17000
for n in list(range(1, 11)) + [20, 50, 100]:
    n = -n
    s = f"round({d}, {n})"
    runner.bench_func(s, round, d, n)

CC @tim-one

[picnixz]

Can you tests when round(d, n) does not give 0 instead? namely, what happens when d is very large (possibly much larger than $10^n$)? having benchmarks there would be interesting as well.

[skirpichev]

Can you tests when round(d, n) does not give 0 instead?

In fact, above tests have such case (n > -5).

namely, what happens when d is very large (possibly much larger than 10**n)?

divmod() cost will be eventually dominate in running time, I think.

Benchmark	ref	patch	patch2	patch3
round(2**5, -5)	525 ns	297 ns: 1.77x faster	532 ns: 1.01x slower	233 ns: 2.26x faster
round(2**7, -5)	528 ns	301 ns: 1.76x faster	536 ns: 1.01x slower	234 ns: 2.26x faster
round(2**10, -5)	554 ns	298 ns: 1.86x faster	581 ns: 1.05x slower	619 ns: 1.12x slower
round(2**15, -5)	555 ns	675 ns: 1.22x slower	586 ns: 1.06x slower	620 ns: 1.12x slower
round(2**20, -5)	667 ns	803 ns: 1.20x slower	668 ns: 1.00x slower	730 ns: 1.10x slower
round(2**25, -5)	751 ns	877 ns: 1.17x slower	761 ns: 1.01x slower	783 ns: 1.04x slower
round(2**30, -5)	808 ns	896 ns: 1.11x slower	784 ns: 1.03x faster	840 ns: 1.04x slower
round(2**50, -5)	793 ns	898 ns: 1.13x slower	784 ns: 1.01x faster	830 ns: 1.05x slower
round(2**100, -5)	864 ns	996 ns: 1.15x slower	not significant	908 ns: 1.05x slower
Geometric mean	(ref)	1.10x faster	1.01x slower	1.14x faster

(Here round(2**d, -5) != 0 for d>=20.)

Benchmark code and patch3.

# bench.py
import math
import pyperf
runner = pyperf.Runner()
n = -5
for d in [5, 7, 10, 15, 20, 25, 30, 50, 100]:
    x = 1<<d
    s = f"round(2**{d}, {n})"
    runner.bench_func(s, round, x, n)

Patch 3:

diff --git a/Objects/longobject.c b/Objects/longobject.c
index 692312c1ad..856bbf3c0b 100644
--- a/Objects/longobject.c
+++ b/Objects/longobject.c
@@ -6212,6 +6212,21 @@ int___round___impl(PyObject *self, PyObject *o_ndigits)
         return long_long(self);
     }
 
+    int64_t n, e;
+
+    if (PyLong_AsInt64(ndigits, &n) < 0) {
+        Py_DECREF(ndigits);
+        return NULL;
+    }
+    n = -n;
+
+    (void)_PyLong_Frexp((PyLongObject *)self, &e);
+
+    if (e/3 + 2 < n) {
+        Py_DECREF(ndigits);
+        return _PyLong_GetZero();
+    }
+
     /* result = self - divmod_near(self, 10 ** -ndigits)[1] */
     PyObject *temp = (PyObject*)long_neg((PyLongObject*)ndigits);
     Py_SETREF(ndigits, temp);

[skirpichev]

Ok, I'm not sure that it worth, but here is a pr: #132579