Extend `FOR_ITER` specializations to cover other indexable sequences

[markshannon]

Currently, we specialize FOR_ITER for both tuple and list. We also handle tuple and lists specially in GET_ITER to support this specialization.

We should extend this specialization of iteration over sequences, using virtual iterators to bytes, str, bytesarray and others.
To do this, we should:

• Add a tp_getiteritem slots to PyTypeObject for sequences that can be efficiently indexed and cannot raise except for out-of-bounds access.
• Add a specialization of FOR_ITER for these classes.
• Specialize GET_ITER for:
  • iterators
  • indexable sequences (those classes with a tp_getiteritem slot)
• Specialize SEND for indexable sequences which should also improve JIT coverage, as unspecialized _SEND is currently a major cause of jit optimization failures.

Combined with #145667 this will allow effective specialization of a wider range of iterables and allow that specialization not only for for loops, but also for yield from loops.
It will add 3 instructions (4 new, 1 removed) which a reasonable

Linked PRs

• gh-145668: Optimize FOR_ITER virtual iterators for bytes, bytearray, … #145670
• GH-145668: Add FOR_ITER specialization for virtual iterators. Specialize GET_ITER. #147967

[MrEx3cut0r]

@markshannon hi! I`d like to work on it

[markshannon]

Here is a more detailed, and slightly changed design.

The tp_getiteritem function pointer slot

It is probably too limiting to only allow contiguous sequences that cannot raise. It would prevents iteration over strings (can raise if cannot allocate new string) and others that might occasionally raise.
We additionally specialize for lists and tuples, so it makes sense to broaden virtual iteration as it won't negatively impact the performance of lists and tuples.

The signature is PyObject *tp_getiteritem(PyObject *iterable, intptr_t *index). The VM will initialize the index to 0 at the start of iteration, thereafter the index is under the control of tp_getiteritem. The returned value is the next item in the iteration. If NULL is returned, iteration is complete if *index >= 0 and an error has occurred if *index < 0. If iteration is complete, no exception should be set. StopIteration should never be raised.

tp_getiteritem cannot handle dicts, or sets, as we won't be able to spot concurrent modification, but it will be able to handle frozendicts and frozensets.

Specialization of GET_ITER

GET_ITER should gain specializations for:

• Iterators: Py_TYPE(obj)->tp_iter == PyObject_SelfIter
• Virtual iterators: Py_TYPE(obj)->tp_iteritem != NULL

Specialization of SEND

SEND should gain a specializations for virtual iterators: Py_TYPE(obj)->tp_iteritem != NULL

[brijkapadia]

@MrEx3cut0r Are you still working on this or could I try to take a stab at this.

[MrEx3cut0r]

@bkap123 you can take it, i have no time for it