Skip to content

GH-132554: Specialize GET_ITER and FOR_ITER for range #135063

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

Jump to bottom
Draft
wants to merge 16 commits into
base: main
Choose a base branch
from
Draft

GH-132554: Specialize GET_ITER and FOR_ITER for range #135063

wants to merge 16 commits into from
+1,065 −578

Conversation

markshannon
Copy link
Member

@markshannon markshannon commented Jun 3, 2025 •
edited
Loading

Extends the idea of "virtual iterators" to ranges as well. Most ranges have a step of one. For these ranges we can treat them much like a C for loop, using tagged integers for the current value and the limit.

The stack during iteration now looks like this:

Original iterable 2nd on stack top of stack
range (step=1) limit (tagged) current (tagged)
list or tuple iterable index (tagged)
other iterator NULL

GET_ITER is specialized for the above cases plus any iterable with Py_TYPE(self)->tp_iter == PyObject_SelfIter which avoids the call to PyObject_GetIter; simply pushing NULL instead.

Also fixes stats for FOR_ITER and GET_ITER.

@markshannon markshannon changed the title Specialize GET_ITER and FOR_ITER for range GH-132554: Specialize GET_ITER and FOR_ITER for range Jun 3, 2025
@bedevere-app bedevere-app bot mentioned this pull request Jun 3, 2025
Open
eendebakpt
eendebakpt reviewed Jun 3, 2025
View reviewed changes
Python/bytecodes.c Outdated
}
else {
PyObject *iter_o = PyStackRef_AsPyObjectBorrow(iter);
next = _PyForIter_NextWithIndex(iter_o, null_or_index);
Copy link
Contributor

Choose a reason for hiding this comment

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

The _PyForIter_NextWithIndex handles the exact lists and exact tuples.

In this PR we have the code to handle range iteration by pushing the index and limit to the stack. Could we simplify _PyForIter_NextWithIndex to only deal with lists and for tuples push the index and length of the tuple to the stack (e.g. use the same approach as range)?

(if this is possible maybe in a followup PR)

Copy link
Member Author

Choose a reason for hiding this comment

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

Are you proposing pushing a third value to the stack during iteration?
I doubt that would be worth it.

Copy link
Contributor

Choose a reason for hiding this comment

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

Yes. Might not be worth it indeed, but I will check once this pr has settled.

@eendebakpt
Copy link
Contributor

Micro benchmarks look good:

for loop length 1: Mean +- std dev: [mainx] 152 ns +- 1 ns -> [prx] 124 ns +- 1 ns: 1.23x faster
repeat loop length 1: Mean +- std dev: [mainx] 234 ns +- 1 ns -> [prx] 227 ns +- 2 ns: 1.03x faster
for loop length 2: Mean +- std dev: [mainx] 169 ns +- 1 ns -> [prx] 142 ns +- 3 ns: 1.19x faster
repeat loop length 2: Mean +- std dev: [mainx] 252 ns +- 2 ns -> [prx] 245 ns +- 4 ns: 1.03x faster
for loop length 8: Mean +- std dev: [mainx] 291 ns +- 4 ns -> [prx] 256 ns +- 4 ns: 1.14x faster
repeat loop length 8: Mean +- std dev: [mainx] 367 ns +- 6 ns -> [prx] 359 ns +- 3 ns: 1.02x faster
for loop length 10000: Mean +- std dev: [mainx] 341 us +- 6 us -> [prx] 330 us +- 3 us: 1.03x faster
repeat loop length 10000: Mean +- std dev: [mainx] 254 us +- 3 us -> [prx] 258 us +- 2 us: 1.02x slower

Geometric mean: 1.08x faster
Script 
import pyperf

runner = pyperf.Runner()

loop = """
import itertools

def g(n):
    x=0
    for ii in range(n):
        x += 1
def repeat(n):
    x = 0
    r = itertools.repeat(None, n)
    for ii in r:
        x += 1
"""

for s in [1, 2, 8, 10_000]:
    time = runner.timeit(name=f"for loop length {s}", stmt=f"g({s})", setup=loop)
    time = runner.timeit(name=f"repeat loop length {s}", stmt=f"repeat({s})", setup=loop)

The repeat loop length x is a control benchmark: it does not involve a for loop, but is slightly faster because pyperf itself includes a for loop in the timing. That effect is relatively small though.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@eendebakpt eendebakpt eendebakpt left review comments

@ericsnowcurrently ericsnowcurrently Awaiting requested review from ericsnowcurrently ericsnowcurrently will be requested when the pull request is marked ready for review ericsnowcurrently is a code owner

@Fidget-Spinner Fidget-Spinner Awaiting requested review from Fidget-Spinner Fidget-Spinner will be requested when the pull request is marked ready for review Fidget-Spinner is a code owner

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
2 participants
@markshannon @eendebakpt