gh-100726: Optimize construction of range object for medium sized int…

…egers (#100810) Use C long arithmetic instead of PyLong arithmetic to compute the range length, where possible. Co-authored-by: blurb-it[bot] <43283697+blurb-it[bot]@users.noreply.github.com> Co-authored-by: Mark Dickinson <[email protected]>
python · Jan 21, 2023 · f63f525 · f63f525
1 parent b4e11a7
commit f63f525
Show file tree

Hide file tree

Showing 3 changed files with 60 additions and 0 deletions.
diff --git a/Lib/test/test_range.py b/Lib/test/test_range.py
@@ -542,6 +542,7 @@ def test_range_iterators(self):
                        for start in limits
                        for end in limits
                        for step in (-2**63, -2**31, -2, -1, 1, 2)]
+        test_ranges += [(-2**63, 2**63-2, 1)] # regression test for gh-100810
 
         for start, end, step in test_ranges:
             iter1 = range(start, end, step)

diff --git a/Misc/NEWS.d/next/Core and Builtins/2023-01-03-20-59-20.gh-issue-100726.W9huFl.rst b/Misc/NEWS.d/next/Core and Builtins/2023-01-03-20-59-20.gh-issue-100726.W9huFl.rst
@@ -0,0 +1 @@
+Optimize construction of ``range`` object for medium size integers.
diff --git a/Objects/rangeobject.c b/Objects/rangeobject.c
@@ -171,6 +171,49 @@ range_dealloc(rangeobject *r)
     PyObject_Free(r);
 }
 
+static unsigned long
+get_len_of_range(long lo, long hi, long step);
+
+/* Return the length as a long, -2 for an overflow and -1 for any other type of error
+ *
+ * In case of an overflow no error is set
+ */
+static long compute_range_length_long(PyObject *start,
+                PyObject *stop, PyObject *step) {
+    int overflow = 0;
+
+    long long_start = PyLong_AsLongAndOverflow(start, &overflow);
+    if (overflow) {
+        return -2;
+    }
+    if (long_start == -1 && PyErr_Occurred()) {
+        return -1;
+    }
+    long long_stop = PyLong_AsLongAndOverflow(stop, &overflow);
+    if (overflow) {
+        return -2;
+    }
+    if (long_stop == -1 && PyErr_Occurred()) {
+        return -1;
+    }
+    long long_step = PyLong_AsLongAndOverflow(step, &overflow);
+    if (overflow) {
+        return -2;
+    }
+    if (long_step == -1 && PyErr_Occurred()) {
+        return -1;
+    }
+
+    unsigned long ulen = get_len_of_range(long_start, long_stop, long_step);
+    if (ulen > (unsigned long)LONG_MAX) {
+        /* length too large for a long */
+        return -2;
+    }
+    else {
+        return (long)ulen;
+    }
+}
+
 /* Return number of items in range (lo, hi, step) as a PyLong object,
  * when arguments are PyLong objects.  Arguments MUST return 1 with
  * PyLong_Check().  Return NULL when there is an error.
@@ -191,6 +234,21 @@ compute_range_length(PyObject *start, PyObject *stop, PyObject *step)
     PyObject *zero = _PyLong_GetZero();  // borrowed reference
     PyObject *one = _PyLong_GetOne();  // borrowed reference
 
+    assert(PyLong_Check(start));
+    assert(PyLong_Check(stop));
+    assert(PyLong_Check(step));
+
+    /* fast path when all arguments fit into a long integer */
+    long len = compute_range_length_long(start, stop, step);
+    if (len >= 0) {
+        return PyLong_FromLong(len);
+    }
+    else if (len == -1) {
+        /* unexpected error from compute_range_length_long, we propagate to the caller */
+        return NULL;
+    }
+    assert(len == -2);
+
     cmp_result = PyObject_RichCompareBool(step, zero, Py_GT);
     if (cmp_result == -1)
         return NULL;
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1 @@
		Optimize construction of ``range`` object for medium size integers.