BUILD_SLICE (BINARY|STORE)_SUBSCR superinstructions.

[markshannon]

These pairs are relatively rare, but it might be worth combining them for a couple reasons:

• They allow BINARY_SUBSCR and STORE_SUBSCR to be better specialized as we don't need to worry about slices
• The whole effort of creating a slice, and pushing to the stack, only to pop it and free it can be avoided.

If we do add these superinstructions, then the compiler will need to changed for augmented assignment.

def f(x,i,j,v):
    x[i:j] += v

compiles to:

  1           0 RESUME                   0

  2           2 LOAD_FAST                0 (x)
              4 LOAD_FAST                1 (i)
              6 LOAD_FAST                2 (j)
              8 BUILD_SLICE              2
             10 COPY                     2
             12 COPY                     2
             14 BINARY_SUBSCR
             24 LOAD_FAST                3 (v)
             26 BINARY_OP               13 (+=)
             30 SWAP                     3
             32 SWAP                     2
             34 STORE_SUBSCR
             38 LOAD_CONST               0 (None)
             40 RETURN_VALUE

We will want to replace the
BUILD_SLICE; COPY 2; COPY 2; BINARY_SUBSCR
with COPY 3; COPY 3; COPY 3; BUILD_SLICE; BINARY_SUBSCR
and the subsequent SWAP 3; SWAP 2; STORE_SUBSCR
with SWAP 4; SWAP 3; SWAP 2; BUILD_SLICE; STORE_SUBSCR
allowing both BUILD_SLICEs to be combined.

[brandtbucher]

I gave this a go late last year (albeit without the instruction reordering proposed here for augmented subscription), and wasn't able to get a speedup, even after specializing for many different flavors of list[:]/list[lo:]/list[:hi]/list[lo:hi]/tuple[:]/tuple[lo:]/tuple[:hi]/tuple[lo:hi]. I think I even dabbled in the 3-argument form for handling reverse slices at one point.

The main "issues" I ran into are that:

• Creating a slice isn't very expensive at all: we keep one cached on the current interpreter, so most slice creations don't even involve an allocation.
• Our benchmarks tend to slice array.array and bytearray, which are dubious at best and very, very difficult at worst (in the case of array, where the entire module is heap-allocated and has no useful C API).

[markshannon]

I'd like to resurrect this in light of the latest stats.

Creating a slice might not be that expensive, but it isn't free and it obscures the underlying operation.
For example, when slicing a list, we are doing the following:

• Create slice
• Unpack slice
• Unbox ints
• Perform the actual operation

Super instructions won't help with the unboxing, but keeps the ints on the stack where other optimizations might be able to.

While it might be tricky to handle array.array, we are going to want to handle numpy arrays and similar, as well. So we are going to have to come with a method of doing so.

[markshannon]

I think it might be worthwhile to store a pointer to a function for extracting slices. Something like the old sq_slice and sq_ass_slice tp_slots.

The VM can handle bounds correction, provided we only specialize for simple sequences where Py_SIZE() is the same as len().
This won't work for numpy arrays in general, but could work for simple 1D arrays.

Example:
x[:4]
compiles to:

    evaluate x
    LOAD_CONST None
    LOAD_CONST 4
    SUBSCR_SLICE

We want to specialize for the shape of the slice, not the class of the sequence. We might also want to specialize for const indexes, as they are quite common.
Once specialized this looks like:

    evaluate x
    LOAD_CONST None
    LOAD_CONST 4
    SUBSCR_SLICE_NONE_INT  

SUBSCR_SLICE_NONE_INT checks on x's class's flags that it supports fast slice subscripting, it then unboxes 4 and replaces the None with Py_SIZE(x) before calling x->...->sq_slice`.

[markshannon]

python/cpython#94163