[issue45026] More compact range iterator

Łukasz Langa added the comment: Well, this is kind of disappointing on my end. I attach the full result of a three-way comparison between `main` at the time of Serhiy's last merge (3f8b23f8ddab75d9b77a3997d54e663187e12cc8) with GH-27986 (20e3149c175a24466c7d1c352f8ff2c11effc489) and GH-28176

[issue45026] More compact range iterator

Łukasz Langa added the comment: Benchmarks for PGO builds on macOS 10.15 Catalina, Intel MBP 2018. Like in Dennis' case, 20e3149c175a24466c7d1c352f8ff2c11effc489 is GH-27986 and cffa90a8b0057d7e7456571045f2fb7b9ceb426f is GH-28176. The difference is that `it_` benchmarks create the iterator o

[issue45026] More compact range iterator

Łukasz Langa added the comment: Dennis, run your benchmarks with --rigorous to avoid "Benchmark hidden because not significant". I note that the second and third benchmarks aren't useful as written because the iterators are exhausted after first repetition. I could see this in my results, no

[issue45026] More compact range iterator

Dennis Sweeney added the comment: I did more benchmarks on my Windows laptop, and it seems the difference goes away after using PGO. The benchmarking program: # from pyperf import Runner runner = Runner() for n in [10, 100, 1000, 10_000, 100_000]: runne

[issue45026] More compact range iterator

Serhiy Storchaka added the comment: There is nothing in code that could explain a measureable difference in creating the range objects or the range object iterators. And indeed, it is in the range of the standard deviation, so it is non-existent. -- _

[issue45026] More compact range iterator

Łukasz Langa added the comment: Serhiy, right: looks like the difference stems from recreating the range objects, not from iteration. But Dennis' observation still stands: using `for i in range(...):` is a very popular idiom. If that becomes slower than the status quo, we will be making exist

[issue45026] More compact range iterator

Serhiy Storchaka added the comment: I do not see any difference in iterating small integers: $ ./python -m pyperf timeit -s 'r = range(1)' 'for i in r: pass' PR 27986: Mean +- std dev: 174 us +- 9 us PR 28176: Mean +- std dev: 172 us +- 10 us -- __

[issue45026] More compact range iterator

Łukasz Langa added the comment: Good point benchmarking small iterations too, Dennis. I missed that. Agreed then, GH-27986 looks like a winner. -- ___ Python tracker ___

[issue45026] More compact range iterator

Dennis Sweeney added the comment: I benchmarked GH-27986 and GH-28176 on "for i in range(1): pass" and found that GH-27986 was faster for this (likely most common) case of relatively small integers. Mean +- std dev: [main] 204 us +- 5 us -> [GH-27986] 194 us +- 4 us: 1.05x faster Mean +

[issue45026] More compact range iterator

Łukasz Langa added the comment: Since len timings for ranges of 100 items are negligible anyway, I personally still favor GH-28176 which is clearly faster during iteration. -- ___ Python tracker

[issue45026] More compact range iterator

Guido van Rossum added the comment: May the best PR win. :-) -- ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscrib

[issue45026] More compact range iterator

Serhiy Storchaka added the comment: length_hint(), not len(). Its cost is included in microbenchmark for list(), where it is followed by iterating 2000 items. Calling operator.length_hint() in Python: $ ./python -m pyperf timeit -s 'it = iter(range(1000)); from operator import length_hint'

[issue45026] More compact range iterator

Łukasz Langa added the comment: Looks like GH-28176 is faster across the board. One missing benchmark here is comparing `len()` speed as this was where the results will be reversed. It would be interesting to see to what extent. -- ___ Python track

[issue45026] More compact range iterator

Change by Guido van Rossum : -- nosy: +gvanrossum ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https://mai

[issue45026] More compact range iterator

Serhiy Storchaka added the comment: 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

[issue45026] More compact range iterator

Serhiy Storchaka added the comment: 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. -- _

[issue45026] More compact range iterator

Łukasz Langa added the comment: I like Dennis' idea and Serhiy's implementation in GH-28176. It's a bit of a larger change compared to GH-27986 but I think it's worth it: I expect iteration speed is more important than `len()` speed for range objects. -- _

[issue45026] More compact range iterator

Serhiy Storchaka added the comment: 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 __

[issue45026] More compact range iterator

Change by Serhiy Storchaka : -- pull_requests: +26603 pull_request: https://github.com/python/cpython/pull/28176 ___ Python tracker ___

[issue45026] More compact range iterator

Serhiy Storchaka added the comment: 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 -

[issue45026] More compact range iterator

Serhiy Storchaka added the comment: 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. -- ___ Python tracker

[issue45026] More compact range iterator

Dennis Sweeney added the comment: 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->

[issue45026] More compact range iterator

Serhiy Storchaka added the comment: 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

[issue45026] More compact range iterator

Change by Serhiy Storchaka : -- keywords: +patch pull_requests: +26433 stage: -> patch review pull_request: https://github.com/python/cpython/pull/27986 ___ Python tracker ___

[issue45026] More compact range iterator

New submission from 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). -- com