Replace ROT_xxx bytecodes with a single SWAP bytecode.

[markshannon]

In general a swap is quicker than a rotate. A swap needs no loop and only two reads and writes:

            PyObject *top = TOP();
            PyObject *other = PEEK(oparg);
            SET_TOP(other);
            PEEK(oparg) = top;

I propose adding a SWAP bytecode which swaps the TOS with the nth item on the stack, and removing ROT_TWO, ROT_THREE, and ROT_N.

Replacing the simple rotates instructions with SWAPs is simple:
ROT_TWO = SWAP 2
ROT_THREE = SWAP 3; SWAP 2. Given ROT_THREE is mostly used in combination with another instruction, this shouldn't cause an increase in code size:

• DUP_TOP; ROT_THREE -> DUP_TOP; SWAP 3
• ROT_THREE; ROT_TWO -> SWAP 3

Removing ROT_N is a bit more complex, but using ROT_N is already a last resort in the pattern matching compiler.
A sequence of SWAPs is likely to be faster, even if it needs a few more instructions.

Combined with COPY and POP_TOP, this provides the ability to perform arbitrary stack transformations at a cost that is linear in the number of instructions.

In theory we could replace NOP with SWAP 1, but given NOPs are already unwanted overhead, we don't want them any slower.

[ericsnowcurrently]

Anyone know if a SWAP opcode was considered when the ROT_xxx opcodes were originally added? If so, why did we go with ROT_xxx? I'd expect there was good reason.

[gvanrossum]

There was no good reason. It was just what I knew from other interpreters (lost in the mist of times).

[brandtbucher]

Replacing the simple rotates instructions with SWAPs is simple: ROT_TWO = SWAP 2 ROT_THREE = SWAP 3; SWAP 2. Given ROT_THREE is mostly used in combination with another instruction, this shouldn't cause an increase in code size:

• DUP_TOP; ROT_THREE -> DUP_TOP; SWAP 3

Hm, wouldn't this become DUP_TOP; SWAP 3; SWAP 2? Or maybe SWAP 2; COPY 2?

Removing ROT_N is a bit more complex, but using ROT_N is already a last resort in the pattern matching compiler. A sequence of SWAPs is likely to be faster, even if it needs a few more instructions.

Cool! Not sure what you mean by "last resort", though. Rotations are currently pretty fundamental to how name captures work, so it would be nice to see some actual numbers before finally ditching ROT_N.

[markshannon]

By "last resort", I mean if ROT_TWO or ROT_THREE are insufficient.

Are rotations fundamental to how name capture works?
I may be mistaken, but don't you just need a means of getting a value buried in the stack to the top.
E.g. suppose you are matching list(range(4)) to [a, b, 2, d]. You start with 0 1 2 3 on the stack (TOS on right).
First you need the second item on the top to validate it, which can be done with SWAP 2.
Assuming a match, you now have 0 1 3 2 on the stack to be stored into a, b, d, c respectively.

SWAP 4 # c b d a 
STORE a # c b d 
SWAP 2 #  c d b
STORE b # c d
SWAP 2 # d c
STORE c 
STORE d

Assuming stores need to be in correct order. For fast locals, it should be OK to shuffle the store and remove all the swaps, but that's a job for the peephole optimizer.

[brandtbucher]

Do you plan to replace DUP_TOP and DUP_TOP_TWO with COPY 1 and COPY 2; COPY 2? It seems like the same reasoning applies.

That (in combination with replacing ROT_* with SWAP) would simplify our stack manipulations pretty dramatically. I imagine it could help with dataflow analysis and more effective peepholing, for example.

[markshannon]

We might as well.

[markshannon]

Ok. Here's a plan.

1. Remove DUP_TOP and DUP_TOP_TWO
2. Add SWAP and remove ROT_TWO and ROT_THREE.
3. Remove ROT_N. For @brandtbucher, as he knows the pattern matching compiler best.
4. Implement a more sophisticated peephole optimizer that can handle stack manipulations interleaved with LOAD_FAST and STORE_FAST. Because of observable side effects, LOAD_FASTs cannot be reordered with other LOAD_FASTs or STORE_FASTs, but (provided they are on the same line) STORE_FASTs can be reordered with each other. Stack manipulations can be freely reordered.

Steps 1 and 2 are independent and can be done in either order.

[brandtbucher]

Sounds good. One question:

(provided they are on the same line) STORE_FASTs can be reordered with each other.

We're definitely in a grey area here, but this seems illegal to me. The order of stores is user-visible:

>>> class C:
...     def __del__(self):
...         import sys
...         frame = sys._getframe(1)
...         print(f"a = {frame.f_locals.get('a', 'NULL')}")
...         print(f"b = {frame.f_locals.get('b', 'NULL')}")
... 
>>> a = C()
>>> a, b = None, None
a = None
b = NULL

I doubt this would break any code in practice, but I'm pretty sure reordering these breaks language guarantees about evaluation order.

[markshannon]

I think it is OK. There are no guarantees about when or where __del__ is called, so no ordering guarantees.

As an aside, we should probably ban most introspection and VM state changes in __del__ functions.

[brandtbucher]

I think it is OK. There are no guarantees about when or where __del__ is called, so no ordering guarantees.

But that's beside the point, right? It would certainly be surprising to see the effect of binding b, but not a, regardless of when __del__ was called.

And __del__ was just a simple, reproducible example I came up with on the spot. Opcode tracing or a well-placed KeyboardInterrupt could make the same effects visible in the frame's locals.

(Again, I doubt this is an issue in practice, but we should probably be aware of the fact that we're probably bending the language a bit when we do this.)

[markshannon]

Keyboard interrupts can only occur at known points, so peephole optimizer knows about them. Likewise for line events.
Opcode tracing is not part of the language spec, since the bytecode is explicitly not part of the spec.

Take the multiple assignment, a, b, = t.

The language specifies an order of events, so that in

(a,
 b) = t

there is a "line" event after the assignment to a and before the assignment to b, so you can observe the VM after a has been assigned, and before b has been assigned.

For

a, b = t

There is no point at which you can observe that a has been assigned to, but not b.

[brandtbucher]

Keyboard interrupts can only occur at known points, so peephole optimizer knows about them.

Ah, I forgot that we don't check eval breakers between arbitrary opcodes. Thanks for reminding me!

[brandtbucher]

FYI, I'm working on a patch for all of this. Should be up later today.

[markshannon]

python/cpython#30902

[brandtbucher]

More aggressive swap folding: python/cpython#30970