Super-instructions

[gvanrossum]

Literature: look for work by Anton Ertl (Forth)

Basic idea: suppose in a runtime (!) execution profile we see that the sequence LOAD_FAST, LOAD_FAST occurs frequently. We can introduce a new opcode, LOAD_FAST_LOAD_FAST (LFLF), and blindly replace the first of every pair of LOAD_FAST opcodes with the super-instruction LFLF. The code then changes from e.g.

    LOAD_FAST 0 (x)
    LOAD_FAST 1 (y)
    BINARY_ADD

to

    LOAD_FAST_LOAD_FAST 0 (x)
    LOAD_FAST 1 (y)
    BINARY_ADD

The opcode case for LFLF would do the following:

• load the first variable (x)
• decode the argument for the second opcode
• adjust the program counter to consume the second opcode
• load the second variable(y)
• DISPATCH()

This saves all the other stuff that's done for each opcode (tracing etc.), and it doesn't even read the second opcode. (If the second LOAD_FAST is preceded by an EXTENDED_ARG opcode we should not do the substitution, so that getting the argument for the second opcode is a single byte access and the p-counter update is a fixed add.)

The beauty is that if there's a jump to the second LOAD_FAST instruction, things just work, so this form of code rewriting can be very fast.

[ericsnowcurrently]

Yeah, taking advantage of common bytecode sequences is something that I've thought would be worth exploring.

If we did this, it would be helpful to have basic tooling to identify common patterns (e.g. from running the test suite or even an arbitrary given workload). It would also be important for such tooling to validate that any super-instructions we add are still worth having, since changes in the compiler can create or eliminate those patterns. Likewise it would be important to identify the more important workloads to target (just like with #10), or even just show that the specific workload isn't so critical.

[ericsnowcurrently]

Here's a derivative idea that may be worth exploring later: a dynamic flavor of super-instructions, where we recognize common patterns at runtime and build/run the collapsed case accordingly (sort of like a JIT). This introduces extra overhead so, to be worth it, it would have to be used frequently enough and, of course, more than offset that overhead.

[gvanrossum]

Note that there's something in ceval.c that can dump out dynamic instruction pair occurrences. Search for dxpairs IIRC.

[gvanrossum]

I've attempted something a little different: in the compiler itself, collapse

LOAD_FAST x
BINARY_ADD

into a new opcode

FAST_ADD x

which duplicates the code of LOAD_FAST and BINARY_ADD. Many other opcodes can get this treatment if it works out, e.g. LOAD_CONST and other binary and unary operations (I also did BINARY_SUBSCR).

Here's the branch: https://github.com/gvanrossum/cpython/tree/add-opcodes

UPDATE: This makes the bytecode more compact and saves dispatch time, at the cost of more cases in the switch. (I could reduce the code size by using more gotos. :-) On a microbenchmark I see 5-10% speedup.

[ericsnowcurrently]

UPDATE: This makes the bytecode more compact and saves dispatch time, at the cost of more cases in the switch. (I could reduce the code size by using more gotos. :-) On a microbenchmark I see 5-10% speedup.

That definitely sounds like something worth exploring.

[ericsnowcurrently]

I like how straight-forward the change is. 🙂

[ericsnowcurrently]

Here are the results of running the benchmarks on the add-opcodes branch right now: results-add-opcodes.tar.gz

(Note that the actual benchmark run took about 20 minutes.)

[gvanrossum]

Hm, that shows small improvements for some number-heavy opcodes, but significant slowdowns on the pickle benchmarks. That's kind of weird, and why we need a separate machine (#19).

[gvanrossum]

Some other pairs that could be combined easily using the same technique:

• LOAD_CONST + RETURN_VALUE = RETURN_CONST
• LOAD_CONST (None) + RETURN_VALUE = RETURN_NONE
• CALL_METHOD + POP_TOP = POP_METHOD
• POP_TOP + LOAD_FAST = POP_TOP_AND_LOAD_FAST
• CALL_METHOD + RETURN_VALUE = RETURN_METHOD
• GET_ITER + FOR_ITER = GET_ITER_AND_FOR_ITER
• LOAD_FAST + RETURN_VALUE = RETURN_FAST

Of these, RETURN_CONST and RETURN_NONE show the most promise IMO (in my sample of 1 they are the most prominent).

Note that there are other common combinations, but they require a different approach to dispatch, because both instructions in the pair have an operand. (Top 9 in my sample: LOAD_FAST + LOAD_ATTR, LOAD_FAST + LOAD_FAST, LOAD_FAST + STORE_ATTR, LOAD_GLOBAL + LOAD_FAST, LOAD_FAST + LOAD_METHOD, STORE_FAST + LOAD_FAST, LOAD_METHOD + LOAD_FAST, LOAD_GLOBAL + CALL_FUNCTION, STORE_ATTR + LOAD_FAST.) This is the approach (according to Mark) taken by Ertl.

[markshannon]

See faster-cpython/cpython#2 (comment) for restrictions on super-instruction formation.

I don't think there is much room for super-instructions implemented in the compiler, because:

• They shouldn't include a bytecode that we will want to specialize, because specialization gains much more than removing the dispatch.
• They can't cross line boundaries.
• They can't include more than one instruction that has an operand.

Unfortunately, FAST_ADD, FAST_SUBSCR, CONST_ADD, CONST_SUBSCR all break rule 1.

INT_ADD is good because it is already specialized, and will rarely cross a line boundary.

Various combinations of LOAD_CONST, IS_OP and POP_JUMP_IF_XXX are also promising.

[gvanrossum]

Things that can be done then include:

• INT_ADD

• LOAD_CONST(None), IS_OP, POP_JUMP_IF_XXX

• RETURN_NONE, RETURN_CONST

• Maybe add checks to skip these optimizations if they span lines, e.g.

    return (
      None
    )
  ``
  
  

Some of these could be separate PRs to test the waters.

[gvanrossum]

(Actually, code like that return broken across lines already executes like it's all on the second line, so I think I needn't worry about that.)