[Python-checkins] gh-100726: Optimize construction of range object for medium sized integers (#100810)
mdickinson
webhook-mailer at python.org
Sat Jan 21 14:33:15 EST 2023
https://github.com/python/cpython/commit/f63f525e161204970418ebc132efc542daaa24ed
commit: f63f525e161204970418ebc132efc542daaa24ed
branch: main
author: Pieter Eendebak <pieter.eendebak at gmail.com>
committer: mdickinson <dickinsm at gmail.com>
date: 2023-01-21T19:33:08Z
summary:
gh-100726: Optimize construction of range object for medium sized integers (#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 <dickinsm at gmail.com>
files:
A Misc/NEWS.d/next/Core and Builtins/2023-01-03-20-59-20.gh-issue-100726.W9huFl.rst
M Lib/test/test_range.py
M Objects/rangeobject.c
diff --git a/Lib/test/test_range.py b/Lib/test/test_range.py
index 7be76b32ac29..3870b153688b 100644
--- 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
new file mode 100644
index 000000000000..2c93098b347a
--- /dev/null
+++ 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
index 992e7c079ded..b4d0bbf32c84 100644
--- 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;
More information about the Python-checkins
mailing list