Repository navigation
Use tagged ints for faster iteration #132554
Description
Iteration over tuples and short lists is quite inefficient as we need to create an iterator object, only to have to destroy it again moments later. Not only that, fetching values from iterators involves additional indirection compared to fetching them from sequences.
Instead we can push a pair of values to the stack. For common sequences, like tuple, list, strings, some ranges and a few others, we push the sequence and the integer index (initially 0) to the stack. For other iterables, we push the iterator and NULL.
GET_ITER will have the signature:
iterable -- iter, index_or_null
FOR_ITER now has the signature:
iter, index_or_null -- iter, index_or_null, next.
What makes this efficient is tagged integers. By using tagged integers, no objects need to be created.
Examples
GET_ITER
[ <tuple at ...> ] -> [ <tuple at ...>, 0 ]
[ <file at ...> ] -> [ <file iterator at ...>, NULL ]
FOR_ITER
[ <tuple at ...>, 0 ] -> [ <tuple at ...>, 1, item0 ]
[ <file iterator at ...>, NULL ] -> [ <file iterator at ...>, NULL, line ]
Activity
markshannon commentedon Apr 15, 2025
Faster CPython discussion
Tagged ints issue
mdboom commentedon Apr 21, 2025
As discussed in our meeting, I'm going to take a first crack at this.
mdboom commentedon Apr 21, 2025
Actually, realizing @markshannon already started that, I'm instead going to follow-on and do
GET_ITERspecializations.GH-132554: Add stats for GET_ITER (GH-132592)
GH-132554: "Virtual" iterators (GH-132555)
GH-132554: Fix tier2 `FOR_ITER` implementation and optimizations (GH-…
pythonGH-132554: "Virtual" iterators (pythonGH-132555)
pythonGH-132554: Fix tier2 `FOR_ITER` implementation and optimizations (
pythonGH-132554: "Virtual" iterators (pythonGH-132555)
pythonGH-132554: Fix tier2 `FOR_ITER` implementation and optimizations (
pythonGH-132554: Fix tier2 `FOR_ITER` implementation and optimizations (
pythonGH-132554: "Virtual" iterators (pythonGH-132555)