FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

gh-89189: More compact range iterator by serhiy-storchaka · Pull Request #27986 · python/cpython · GitHub

/ cpython Public

gh-89189: More compact range iterator #27986

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
serhiy-storchaka merged 12 commits into from
Nov 30, 2022
Conversation 14 Commits 12 Checks 0 Files changed
Merged

gh-89189: More compact range iterator #27986

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
12 commits
Select commit Hold shift + click to select a range
2fa0b0d
bpo-45026: More compact range iterator
serhiy-storchaka Aug 27, 2021
1cd0138
Fix sizeof test.
serhiy-storchaka Aug 27, 2021
214f204
Merge branch 'main' into range-iter
serhiy-storchaka Aug 29, 2021
3133f66
Add explicit tests for __setstate__.
serhiy-storchaka Aug 29, 2021
7a42474
Add a NEWS entry.
serhiy-storchaka Aug 29, 2021
175b0d3
Merge branch 'main' into range-iter
serhiy-storchaka Sep 5, 2021
22f76b8
Merge branch 'main' into range-iter
serhiy-storchaka Sep 15, 2021
20e3149
Merge branch 'main' into range-iter
serhiy-storchaka Sep 24, 2021
abf2971
Merge branch 'main' into range-iter
serhiy-storchaka Mar 28, 2022
0ca67c2
Merge branch 'main' into range-iter
serhiy-storchaka Nov 27, 2022
10822c0
Microoptimize small range iteration.
serhiy-storchaka Nov 27, 2022
050df74
Set start and len simultaneously in longrangeiter_setstate.
serhiy-storchaka Nov 30, 2022
File filter

Filter by extension

Filter by extension .c  (2) .h  (2) .py  (2) .rst  (1) All 4 file types selected
Viewed files
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Unified
Split
Hide whitespace
Diff view
Unified
Split
Hide whitespace
1 change: 0 additions & 1 deletion Include/internal/pycore_range.h
Show comments
View file
Open in desktop
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
Show hidden characters
Original file line number Diff line number Diff line change
Expand Up @@ -10,7 +10,6 @@ extern "C" {

typedef struct {
PyObject_HEAD
long index;
long start;
long step;
long len;
Expand Down
38 changes: 33 additions & 5 deletions Lib/test/test_range.py
Show comments
View file
Open in desktop
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
Show hidden characters
Original file line number Diff line number Diff line change
Expand Up @@ -407,11 +407,7 @@ def test_iterator_pickling_overflowing_index(self):
for proto in range(pickle.HIGHEST_PROTOCOL + 1):
with self.subTest(proto=proto):
it = iter(range(2**32 + 2))
_, _, idx = it.__reduce__()
self.assertEqual(idx, 0)
it.__setstate__(2**32 + 1) # undocumented way to set r->index
_, _, idx = it.__reduce__()
self.assertEqual(idx, 2**32 + 1)
it.__setstate__(2**32 + 1) # undocumented way to advance an iterator
d = pickle.dumps(it, proto)
it = pickle.loads(d)
self.assertEqual(next(it), 2**32 + 1)
Expand Down Expand Up @@ -442,6 +438,38 @@ def test_large_exhausted_iterator_pickling(self):
self.assertEqual(list(i), [])
self.assertEqual(list(i2), [])

def test_iterator_unpickle_compat(self):
testcases = [
b'c__builtin__\niter\n(c__builtin__\nxrange\n(I10\nI20\nI2\ntRtRI2\nb.',
b'c__builtin__\niter\n(c__builtin__\nxrange\n(K\nK\x14K\x02tRtRK\x02b.',
b'\x80\x02c__builtin__\niter\nc__builtin__\nxrange\nK\nK\x14K\x02\x87R\x85RK\x02b.',
b'\x80\x03cbuiltins\niter\ncbuiltins\nrange\nK\nK\x14K\x02\x87R\x85RK\x02b.',
b'\x80\x04\x951\x00\x00\x00\x00\x00\x00\x00\x8c\x08builtins\x8c\x04iter\x93\x8c\x08builtins\x8c\x05range\x93K\nK\x14K\x02\x87R\x85RK\x02b.',

b'c__builtin__\niter\n(c__builtin__\nxrange\n(L-36893488147419103232L\nI20\nI2\ntRtRL18446744073709551623L\nb.',
b'c__builtin__\niter\n(c__builtin__\nxrange\n(L-36893488147419103232L\nK\x14K\x02tRtRL18446744073709551623L\nb.',
b'\x80\x02c__builtin__\niter\nc__builtin__\nxrange\n\x8a\t\x00\x00\x00\x00\x00\x00\x00\x00\xfeK\x14K\x02\x87R\x85R\x8a\t\x07\x00\x00\x00\x00\x00\x00\x00\x01b.',
b'\x80\x03cbuiltins\niter\ncbuiltins\nrange\n\x8a\t\x00\x00\x00\x00\x00\x00\x00\x00\xfeK\x14K\x02\x87R\x85R\x8a\t\x07\x00\x00\x00\x00\x00\x00\x00\x01b.',
b'\x80\x04\x95C\x00\x00\x00\x00\x00\x00\x00\x8c\x08builtins\x8c\x04iter\x93\x8c\x08builtins\x8c\x05range\x93\x8a\t\x00\x00\x00\x00\x00\x00\x00\x00\xfeK\x14K\x02\x87R\x85R\x8a\t\x07\x00\x00\x00\x00\x00\x00\x00\x01b.',
]
for t in testcases:
it = pickle.loads(t)
self.assertEqual(list(it), [14, 16, 18])

def test_iterator_setstate(self):
it = iter(range(10, 20, 2))
it.__setstate__(2)
self.assertEqual(list(it), [14, 16, 18])
it = reversed(range(10, 20, 2))
it.__setstate__(3)
self.assertEqual(list(it), [12, 10])
it = iter(range(-2**65, 20, 2))
it.__setstate__(2**64 + 7)
self.assertEqual(list(it), [14, 16, 18])
it = reversed(range(10, 2**65, 2))
it.__setstate__(2**64 - 7)
self.assertEqual(list(it), [12, 10])

def test_odd_bug(self):
# This used to raise a "SystemError: NULL result without error"
# because the range validation step was eating the exception
Expand Down
3 changes: 2 additions & 1 deletion Lib/test/test_sys.py
Show comments
View file
Open in desktop
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
Show hidden characters
Original file line number Diff line number Diff line change
Expand Up @@ -1484,7 +1484,8 @@ def delx(self): del self.__x
# PyCapsule
# XXX
# rangeiterator
check(iter(range(1)), size('4l'))
check(iter(range(1)), size('3l'))
check(iter(range(2**65)), size('3P'))
# reverse
check(reversed(''), size('nP'))
# range
Expand Down
3 changes: 3 additions & 0 deletions Misc/NEWS.d/next/Core and Builtins/2021-08-29-15-55-19.bpo-45026.z7nTA3.rst
Show comments
View file
Open in desktop
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
Show hidden characters
Original file line number Diff line number Diff line change
@@ -0,0 +1,3 @@
Optimize the :class:`range` object iterator. It is now smaller, faster
iteration of ranges containing large numbers. Smaller pickles, faster
unpickling.
79 changes: 42 additions & 37 deletions Objects/rangeobject.c
Show comments
View file
Open in desktop
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
Show hidden characters
Original file line number Diff line number Diff line change
Expand Up @@ -756,18 +756,19 @@ PyTypeObject PyRange_Type = {
static PyObject *
rangeiter_next(_PyRangeIterObject *r)
{
if (r->index < r->len)
/* cast to unsigned to avoid possible signed overflow
in intermediate calculations. */
return PyLong_FromLong((long)(r->start +
(unsigned long)(r->index++) * r->step));
if (r->len > 0) {
long result = r->start;
r->start = result + r->step;
r->len--;
return PyLong_FromLong(result);
}
return NULL;
}

static PyObject *
rangeiter_len(_PyRangeIterObject *r, PyObject *Py_UNUSED(ignored))
{
return PyLong_FromLong(r->len - r->index);
return PyLong_FromLong(r->len);
}

PyDoc_STRVAR(length_hint_doc,
Expand All @@ -794,8 +795,8 @@ rangeiter_reduce(_PyRangeIterObject *r, PyObject *Py_UNUSED(ignored))
if (range == NULL)
goto err;
/* return the result */
return Py_BuildValue(
"N(N)l", _PyEval_GetBuiltin(&_Py_ID(iter)), range, r->index);
return Py_BuildValue("N(N)O", _PyEval_GetBuiltin(&_Py_ID(iter)),
range, Py_None);
Comment on lines +798 to +799

gvanrossum Nov 30, 2022

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

I'm not sure we care, but we might -- am I right that this writes pickles that can't be read by 3.11 or before?

serhiy-storchaka Nov 30, 2022

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

No, absolutely no. I would never propose such change.

Internals will be different, but the unpickled iterator wil produce the same values.
err:
Py_XDECREF(start);
Py_XDECREF(stop);
Expand All @@ -814,7 +815,8 @@ rangeiter_setstate(_PyRangeIterObject *r, PyObject *state)
index = 0;
else if (index > r->len)
index = r->len; /* exhausted iterator */
r->index = index;
r->start += index * r->step;
r->len -= index;
Py_RETURN_NONE;
}

Expand Down Expand Up @@ -904,13 +906,11 @@ fast_range_iter(long start, long stop, long step, long len)
it->start = start;
it->step = step;
it->len = len;
it->index = 0;
return (PyObject *)it;
}

typedef struct {
PyObject_HEAD
PyObject *index;
PyObject *start;
PyObject *step;
PyObject *len;
Expand All @@ -919,7 +919,8 @@ typedef struct {
static PyObject *
longrangeiter_len(longrangeiterobject *r, PyObject *no_args)
{
return PyNumber_Subtract(r->len, r->index);
Py_INCREF(r->len);
return r->len;
}

static PyObject *
Expand All @@ -946,8 +947,8 @@ longrangeiter_reduce(longrangeiterobject *r, PyObject *Py_UNUSED(ignored))
}

/* return the result */
return Py_BuildValue(
"N(N)O", _PyEval_GetBuiltin(&_Py_ID(iter)), range, r->index);
return Py_BuildValue("N(N)O", _PyEval_GetBuiltin(&_Py_ID(iter)),
range, Py_None);
}

static PyObject *
Expand All @@ -970,7 +971,22 @@ longrangeiter_setstate(longrangeiterobject *r, PyObject *state)
if (cmp > 0)
state = r->len;
}
Py_XSETREF(r->index, Py_NewRef(state));
PyObject *product = PyNumber_Multiply(state, r->step);
if (product == NULL)
return NULL;
PyObject *new_start = PyNumber_Add(r->start, product);
Py_DECREF(product);
if (new_start == NULL)
return NULL;
PyObject *new_len = PyNumber_Subtract(r->len, state);
if (new_len == NULL) {
Py_DECREF(new_start);
return NULL;
}
PyObject *tmp = r->start;
r->start = new_start;
Py_SETREF(r->len, new_len);
Py_DECREF(tmp);
Comment on lines +986 to +989

gvanrossum Nov 30, 2022

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

I don't see a scenario where we can't just use

Py_SETREF(r->len, new_len);
Py_SETREF(r->start, new_start);

(which would be a little easier to follow).

Both new_len and new_start are definitely new references we own, so even if state was a borrowed reference to r->len everything would be all right.

I'll leave it up to you though.

serhiy-storchaka Nov 30, 2022

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

Py_SETREF can only help when you assign a single object attribute, or if the attributes are independent. Two sequential Py_SETREFs can be a sign of a bug.

We do not check the type of state. It can be an arbitrary Python object with methods __lt__, __gt__, __mul__ and __rsub__. Therefore we do not control the types of new_len and new_start. Therefore we do not control the types of r->len and r->start. They can have __del__ methods which release the GIL after assignment in Py_SETREF. When the GIL is released, the iterator object can be used in other thread when it is in inconsistent state -- new r->len and old r->start.

It never occurs in normal code (state is always an exact int), but if you try hard, you perhaps can reproduce this.

gvanrossum Nov 30, 2022

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

Aha, that's a scenario I hadn't considered. Maybe the next time I am asked in some kind of Q&A or interview "do you have any regrets" I should mention __del__ methods.
Py_RETURN_NONE;
}

Expand All @@ -987,7 +1003,6 @@ static PyMethodDef longrangeiter_methods[] = {
static void
longrangeiter_dealloc(longrangeiterobject *r)
{
Py_XDECREF(r->index);
Py_XDECREF(r->start);
Py_XDECREF(r->step);
Py_XDECREF(r->len);
Expand All @@ -997,29 +1012,21 @@ longrangeiter_dealloc(longrangeiterobject *r)
static PyObject *
longrangeiter_next(longrangeiterobject *r)
{
PyObject *product, *new_index, *result;
if (PyObject_RichCompareBool(r->index, r->len, Py_LT) != 1)
if (PyObject_RichCompareBool(r->len, _PyLong_GetZero(), Py_GT) != 1)
return NULL;

new_index = PyNumber_Add(r->index, _PyLong_GetOne());
if (!new_index)
PyObject *new_start = PyNumber_Add(r->start, r->step);
if (new_start == NULL) {
return NULL;

product = PyNumber_Multiply(r->index, r->step);
if (!product) {
Py_DECREF(new_index);
return NULL;
}

result = PyNumber_Add(r->start, product);
Py_DECREF(product);
if (result) {
Py_SETREF(r->index, new_index);
}
else {
Py_DECREF(new_index);
PyObject *new_len = PyNumber_Subtract(r->len, _PyLong_GetOne());
if (new_len == NULL) {
Py_DECREF(new_start);
return NULL;
}

PyObject *result = r->start;
r->start = new_start;
Py_SETREF(r->len, new_len);
return result;
}

Expand Down Expand Up @@ -1108,7 +1115,6 @@ range_iter(PyObject *seq)
it->start = Py_NewRef(r->start);
it->step = Py_NewRef(r->step);
it->len = Py_NewRef(r->length);
it->index = Py_NewRef(_PyLong_GetZero());
return (PyObject *)it;
}

Expand Down Expand Up @@ -1186,7 +1192,7 @@ range_reverse(PyObject *seq, PyObject *Py_UNUSED(ignored))
it = PyObject_New(longrangeiterobject, &PyLongRangeIter_Type);
if (it == NULL)
return NULL;
it->index = it->start = it->step = NULL;
it->start = it->step = NULL;

/* start + (len - 1) * step */
it->len = Py_NewRef(range->length);
Expand All @@ -1210,7 +1216,6 @@ range_reverse(PyObject *seq, PyObject *Py_UNUSED(ignored))
if (!it->step)
goto create_failure;

it->index = Py_NewRef(_PyLong_GetZero());
return (PyObject *)it;

create_failure:
Expand Down
7 changes: 4 additions & 3 deletions Python/bytecodes.c
Show comments
View file
Open in desktop
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
Show hidden characters
Original file line number Diff line number Diff line change
Expand Up @@ -2620,14 +2620,15 @@ dummy_func(
STAT_INC(FOR_ITER, hit);
_Py_CODEUNIT next = next_instr[INLINE_CACHE_ENTRIES_FOR_ITER];
assert(_PyOpcode_Deopt[_Py_OPCODE(next)] == STORE_FAST);
if (r->index >= r->len) {
if (r->len <= 0) {
STACK_SHRINK(1);
Py_DECREF(r);
JUMPBY(INLINE_CACHE_ENTRIES_FOR_ITER + oparg + 1);
}
else {
long value = (long)(r->start +
(unsigned long)(r->index++) * r->step);
long value = r->start;
r->start = value + r->step;
r->len--;
if (_PyLong_AssignValue(&GETLOCAL(_Py_OPARG(next)), value) < 0) {
goto error;
}
Expand Down
7 changes: 4 additions & 3 deletions Python/generated_cases.c.h
Show comments
View file
Open in desktop

Some generated files are not rendered by default. Learn more about how customized files appear on GitHub.

Back | FazBrowse Home | New Git URL