10000 bpo-45026: More compact range iterator (alt) by serhiy-storchaka · Pull Request #28176 · python/cpython · GitHub
[go: up one dir, main page]
Skip to content

bpo-45026: More compact range iterator (alt) #28176

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

Closed
wants to merge 15 commits into from
Closed

bpo-45026: More compact range iterator (alt) #28176

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
15 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
177da8c
Keep stop instead of len.
serhiy-storchaka Sep 5, 2021
155cb3c
Merge branch 'main' into range-iter2
serhiy-storchaka Sep 10, 2021
dced0e6
Fix refleaks.
serhiy-storchaka Sep 10, 2021
3219849
Merge branch 'main' into range-iter2
serhiy-storchaka Sep 15, 2021
cffa90a
Merge branch 'main' into range-iter2
serhiy-storchaka Sep 24, 2021
dbdb0cc
Merge branch 'main' into range-iter2
serhiy-storchaka Mar 28, 2022
109445f
Merge branch 'main' into range-iter2
serhiy-storchaka Nov 27, 2022
189ca23
Unify code with range-iter.
serhiy-storchaka Nov 27, 2022
d315911
Microoptimize small range iteration.
serhiy-storchaka Nov 29, 2022
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Next Next commit
bpo-45026: More compact range iterator
  • Loading branch information
@serhiy-storchaka
serhiy-storchaka committed Aug 27, 2021
commit 2fa0b0d756ec0ad5bd66be48dcf6411e879ffb73
18 changes: 18 additions & 0 deletions Lib/test/test_range.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -421,6 +421,24 @@ 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_odd_bug(self):
# This used to raise a "SystemError: NULL result without error"
# because the range validation step was eating the exception
Expand Down
77 changes: 37 additions & 40 deletions Objects/rangeobject.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -766,7 +766,6 @@ PyTypeObject PyRange_Type = {

typedef struct {
PyObject_HEAD
long index;
long start;
long step;
long len;
Expand All @@ -775,18 +774,19 @@ typedef struct {
static PyObject *
rangeiter_next(rangeiterobject *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 += r->step;
r->len--;
return PyLong_FromLong(result);
}
return NULL;
}

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

PyDoc_STRVAR(length_hint_doc,
Expand All @@ -813,8 +813,8 @@ rangeiter_reduce(rangeiterobject *r, PyObject *Py_UNUSED(ignored))
if (range == NULL)
goto err;
/* return the result */
return Py_BuildValue("N(N)i", _PyEval_GetBuiltinId(&PyId_iter),
range, r->index);
return Py_BuildValue("N(N)O", _PyEval_GetBuiltinId(&PyId_iter),
range, Py_None);
err:
Py_XDECREF(start);
Py_XDECREF(stop);
Expand All @@ -833,7 +833,8 @@ rangeiter_setstate(rangeiterobject *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 @@ -931,13 +932,11 @@ fast_range_iter(long start, long stop, long step)
return NULL;
}
it->len = (long)ulen;
it->index = 0;
return (PyObject *)it;
}

typedef struct {
PyObject_HEAD
PyObject *index;
PyObject *start;
PyObject *step;
PyObject *len;
Expand All @@ -946,7 +945,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 Down Expand Up @@ -976,7 +976,7 @@ longrangeiter_reduce(longrangeiterobject *r, PyObject *Py_UNUSED(ignored))

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

static PyObject *
Expand All @@ -999,8 +999,18 @@ longrangeiter_setstate(longrangeiterobject *r, PyObject *state)
if (cmp > 0)
state = r->len;
}
Py_INCREF(state);
Py_XSETREF(r->index, state);
PyObject *new_len = PyNumber_Subtract(r->len, state);
if (new_len == NULL)
return NULL;
Py_SETREF(r->len, new_len);
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;
Py_SETREF(r->start, new_start);
Py_RETURN_NONE;
}

Expand All @@ -1017,7 +1027,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 @@ -1027,29 +1036,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 @@ -1128,11 +1129,9 @@ range_iter(PyObject *seq)
it->start = r->start;
it->step = r->step;
it->len = r->length;
it->index = _PyLong_GetZero();
Py_INCREF(it->start);
Py_INCREF(it->step);
Py_INCREF(it->len);
Py_INCREF(it->index);
return (PyObject *)it;
}

Expand Down Expand Up @@ -1210,7 +1209,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 = range->length;
Expand All @@ -1235,8 +1234,6 @@ range_reverse(PyObject *seq, PyObject *Py_UNUSED(ignored))
if (!it->step)
goto create_failure;

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

create_failure:
Expand Down
0