Tagged values on the evaluation stack.

[markshannon]

CPython does a lot of boxing. Tagged values (#138) is the (very) long goal to fix this, that is probably a long way off.

Allowing tagged values on the stack might be a useful intermediate step.
Tagged values can provide a way to:

• Avoid boxing of ints produced when iterating over range and enumerate
• Avoid boxing of intermediate numbers in arithmetic expressions.
• Avoid boxing of indexes.

Consider iterating over range.
python/cpython#91713 avoids boxing by forming a superinstruction of the specialize FOR_ITER and the following STORE_FAST. This only works in a for loop, not a comprehension. Allowing tagged values on the stack would allow efficient specialization of any iterator or indexing operation that produces a number (potentially including numpy iterators), without needing a superinstruction for each specialization.

The compiler can track which operations consume values from the stack, so we can mark at compile time which operations can produce a tagged value, so only some instructions would need to handle tagged values:

• STORE_FAST
• BINARY_OP
• BINARY_SUBSCR (index only)
• STORE_SUBSCR (index only)
• Conditional branches.

And only some instructions would be able to produced tagged values:

• FOR_ITER
• BINARY_OP
• BINARY_SUBSCR

Specialization of LOAD_FAST for integers, or floats, is a possibility as well.

This won't work with #393, but as it potentially saves boxing, as well reference counts, this might be the more profitable approach.

Avoiding N * M specializations

We already specialize moving values to/from the stack depending on where the value is.
If we add specializations for what a value is, then the combination can blow up.
For example, we already have 10 specializations of LOAD_ATTR. If we were to have the same for unboxed ints and floats, we would need 30 specializations, which is excessive.

Implementation

Interpreter

By changing the (C) type of values on the stack from PyObject * to a struct, we can prevent casts, so that all conversions need to go through a function/macro.
It is then a relatively simple, is laborious, process of converting all uses of stack values to one of:

• TO_OBJECT(val, error_label) -- No-op for object pointers, boxes tagged values
• ASSERT_OBJECT(val) -- No-op for object pointers, assertion failure if boxed.
  For example, the implementation of BINARY_SUBSCR includes:

    PyObject *sub = POP();
    PyObject *container = TOP();

which would need to become:

    PyObject *sub = TO_OBJECT(POP(), error);
    PyObject *container = ASSERT_OBJECT(TOP());

Compiler

The compiler will need to do some backward flow analysis from use to determine which stack values can be unboxed.
One possibility is to have two versions of instructions, one that can produce tagged values, one that cannot.
Another option is to have an explicit BOX instruction that would box tagged values.
E.g.

    BINARY_OP '+'
    CALL 1

Since CALL cannot handle tagged values, and BINARY_OP can produce them, we need to fix this.
Option 1

    BINARY_OP_BOXED '+'
    CALL 1

Option 2

    BINARY_OP '+'
    BOX
    CALL 1

Neither option is ideal. Option 1 needs a lot more specializations of BINARY_OP. Option 2 adds a fair bit of dispatching overhead.

[sweeneyde]

This only works in a for loop, not a comprehension.

Doesn't it work on comprehensions? With that PR, I get this:

>>> f = lambda: [x for x in range(10)]
>>> f()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> __lltrace__ = 1
>>> f()

(...)
6: FOR_ITER_RANGE
    stack=[[], <range_iterator object at 0x000002ADC3D5DE80>]
12: LOAD_FAST 1
    stack=[[], <range_iterator object at 0x000002ADC3D5DE80>, 0]
14: LIST_APPEND 2
    stack=[[0], <range_iterator object at 0x000002ADC3D5DE80>]
(...)

[markshannon]

Doesn't it work on comprehensions?

It works for most list and set comprehensions, yes, but not for dict comprehensions, or generator expressions, which are sort of comprehensions.

The point is that this the specializations of FOR_ITER aren't as generally useful as we would like, as it relies on the FOR_ITER being followed by STORE_FAST. Anything else, like UNPACK_SEQUENCE as we would see in for i, obj in enumerate(seq):, doesn't get handled as efficiently.

The ideal is that we need fewer specializations and get the benefits of the complex specializations that handle objects with refcount == 1.

This isn't to say that should continue to add specializations, just that we want to think about alternative and complementary approaches.

[sweeneyde]

It works for most list and set comprehensions, yes, but not for dict comprehensions, or generator expressions, which are sort of comprehensions.

Dict comprehensions and generator expressions over ranges should still use the current FOR_ITER_RANGE, since they still use STORE_FAST. The situations where ranges wouldn't specialize now are only if the loop variable is a global or something strange like for foo.bar in range(10):.