More compact range iterator

[serhiy-storchaka]

BPO	45026
Nosy	@gvanrossum, @rhettinger, @ambv, @serhiy-storchaka, @sweeneyde
PRs	gh-89189: More compact range iterator #27986 bpo-45026: More compact range iterator (alt) #28176
Files	three-way-comparison.log

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = None
created_at = <Date 2021-08-27.03:03:33.269>
labels = ['interpreter-core', '3.11', 'performance']
title = 'More compact range iterator'
updated_at = <Date 2021-09-27.14:46:46.491>
user = 'https://github.com/serhiy-storchaka'

bugs.python.org fields:

activity = <Date 2021-09-27.14:46:46.491>
actor = 'lukasz.langa'
assignee = 'none'
closed = False
closed_date = None
closer = None
components = ['Interpreter Core']
creation = <Date 2021-08-27.03:03:33.269>
creator = 'serhiy.storchaka'
dependencies = []
files = ['50306']
hgrepos = []
issue_num = 45026
keywords = ['patch']
message_count = 22.0
messages = ['400390', '400392', '400396', '400399', '400528', '401085', '401411', '401419', '402139', '402335', '402347', '402349', '402452', '402477', '402534', '402543', '402555', '402639', '402649', '402708', '402712', '402724']
nosy_count = 5.0
nosy_names = ['gvanrossum', 'rhettinger', 'lukasz.langa', 'serhiy.storchaka', 'Dennis Sweeney']
pr_nums = ['27986', '28176']
priority = 'normal'
resolution = None
stage = 'patch review'
status = 'open'
superseder = None
type = 'resource usage'
url = 'https://bugs.python.org/issue45026'
versions = ['Python 3.11']

[serhiy-storchaka]

The proposed PR provides more compact implementation of the range iterator. It consumes less memory and produces smaller pickles. It is presumably faster because it performs simpler arithmetic operations on iteration (no multiplications).

[serhiy-storchaka]

Currently the range iterator contains four integers: index, start, step and len. On iteration index is increased until achieve len, the result is calculated as start+index*step.

In the proposed PR the range iterator contains only three integers: index was removed. Instead len counts the number of iterations that left, and start is increased by step on every iteration. Less memory, simpler calculation.

Pickle no longer contains index, but __setstate__ is kept for compatibility.

The only incompatible change is that calling __setstate__ repeatedly will have different effect. Currently __setstate__ with the same values does not have effect, with this PR it will advance iterator. But Python only calls __setstate__ once for just created object when unpickle or copy.

[sweeneyde]

Is it worth removing the len field as well and lazily using get_len_of_range() as needed?

Then the hot function can look something like:

static PyObject *
rangeiter_next(rangeiterobject *r)
{
    long result = r->start
    if (result < r->stop) {
        r->start += r->step;
        return PyLong_FromLong(result);
    }
    return NULL;
}

[serhiy-storchaka]

step can be negative. So the condition should be more complex: ((r->stop > 0) ? (result < r->stop) : (result > r->stop)). And it would look much more complex for longrangeiterobject.

[serhiy-storchaka]

Microbenchmarks show some speed up:

Iterating large range:

$ ./python -m timeit -s 'r = range(0, 10**20, 3**35)' 'list(r)'
Before: 2000 loops, best of 5: 199 usec per loop
After:  2000 loops, best of 5: 113 usec per loop

Unpickling:

$ ./python -m timeit -s 'from pickle import dumps, loads; p = dumps([iter(range(i)) for i in range(1000)])' 'loads(p)'
Before: 500 loops, best of 5: 476 usec per loop
After:  500 loops, best of 5: 363 usec per loop

I did not observe any difference in iterating small ranges and pickling.

Smaller size in memory, smaller pickles.

[serhiy-storchaka]

PR 28176 implements idea proposed by Dennis in msg400396. It keeps the current and stop values instead of the initial start, index and initial length. I do not have data yet, but it is expected that it's iteration may be faster (for large integers), but __lenght_hint__ should be slower.

[ambv]

I like Dennis' idea and Serhiy's implementation in #72363. It's a bit of a larger change compared to #72173 but I think it's worth it: I expect iteration speed is more important than len() speed for range objects.

[serhiy-storchaka]

I have not benchmarked PR 28176 yet and do not know whether it have advantages over PR 27986 and how large. Slower __lenght_hint__ can make list(range(...)) slower for small ranges, but I do not know how small.

[serhiy-storchaka]

Iterating large integers:

$ ./python -m pyperf timeit -s 'r = range(0, 10**20, 3**35)' 'for i in r: pass'

baseline: Mean +- std dev: 223 us +- 10 us
PR 27986: Mean +- std dev: 128 us +- 4 us
PR 28176: Mean +- std dev: 99.0 us +- 3.7 us

$ ./python -m pyperf timeit -s 'r = range(0, 10**20, 3**35)' 'list(r)'
baseline: Mean +- std dev: 191 us +- 13 us
PR 27986: Mean +- std dev: 107 us +- 7 us
PR 28176: Mean +- std dev: 91.3 us +- 2.4 us

Unpickling:

$ ./python -m pyperf timeit -s 'from pickle import dumps, loads; p = dumps([iter(range(i)) for i in range(1000)])' 'loads(p)'
baseline: Mean +- std dev: 535 us +- 29 us
PR 27986: Mean +- std dev: 420 us +- 15 us
PR 28176: Mean +- std dev: 418 us +- 17 us

$ ./python -m pyperf timeit -s 'from pickle import dumps, loads; p = dumps([iter(range(i*10**10)) for i in range(1000)])' 'loads(p)'
baseline: Mean +- std dev: 652 us +- 37 us
PR 27986: Mean +- std dev: 530 us +- 43 us
PR 28176: Mean +- std dev: 523 us +- 17 us

Seems PR 28176 is slightly faster than PR 27986 in iterating long integers.