Exploring Python Bytecode

For the past month or so, I’ve been trying to understand what appears to be a black art mostly because of lacking documentation – Python bytecode generation and peephole optimization. Some notes from the study for the benefit of IRC-mate ‘jstatm’ and anyone else living on similar planes of insanity.

Although bytecode applies to objects other than functions such as tracebacks, dictionaries and strings, I am only interested in optimization and flow analysis of class methods, functions and lambdas. Lets get to the action straight away with an example. Here is a small python program to disassemble and display the bytecode of a function in human readable form.

#!/usr/bin/python

import sys
import opcode

# A simple function to disassemble and ponder over
# Sum of even numbers from 0 - 100
def foo_simple():
  sum = 0
  # For the heck of creating a closure in the byte-code
  # use (n+sum) instead of n. Even + Even = Even in any case
  for i in filter(lambda n: ( (n+sum) % 2 == 0), range(101)):
    sum += i
  if 1 > 0:
    print 'Nobody Expects The Spanish Inquisition !'
  return sum

# The Byte-Code decompiler. Returns a list of tuples that
# represent the opcode and arguments in the code object
# Reference: The python dis module
def decompile(code_object):
  code = code_object.co_code
  variables = code_object.co_cellvars + code_object.co_freevars
  instructions = []
  n = len(code)
  i = 0
  e = 0
  while i < n:
    i_offset = i
    i_opcode = ord(code[i])
    i = i + 1
    if i_opcode >= opcode.HAVE_ARGUMENT:
      # WTF: I can't type 8 in wordpress
      # It gets converted to a frigging smiley !
      i_argument = ord(code[i]) + (ord(code[i+1]) << (4*2)) + e
      i = i +2
      if i_opcode == opcode.EXTENDED_ARG:
        e = iarg << 16
      else:
        e = 0
      if i_opcode in opcode.hasconst:
        i_arg_value = repr(code_object.co_consts[i_argument])
        i_arg_type = 'CONSTANT'
      elif i_opcode in opcode.hasname:
        i_arg_value = code_object.co_names[i_argument]
        i_arg_type = 'GLOBAL VARIABLE'
      elif i_opcode in opcode.hasjrel:
        i_arg_value = repr(i + i_argument)
        i_arg_type = 'RELATIVE JUMP'
      elif i_opcode in opcode.haslocal:
        i_arg_value = code_object.co_varnames[i_argument]
        i_arg_type = 'LOCAL VARIABLE'
      elif i_opcode in opcode.hascompare:
        i_arg_value = opcode.cmp_op[i_argument]
        i_arg_type = 'COMPARE OPERATOR'
      elif i_opcode in opcode.hasfree:
        i_arg_value = variables[i_argument]
        i_arg_type = 'FREE VARIABLE'
      else:
        i_arg_value = i_argument
        i_arg_type = 'OTHER'
    else:
      i_argument = None
      i_arg_value = None
      i_arg_type = None
    instructions.append( (i_offset, i_opcode, opcode.opname[i_opcode],\
                          i_argument, i_arg_type, i_arg_value) )
  return instructions

# Print the byte code in homo-sapien compatible format
def pretty_print(instructions):
  print '%5s %-20s %3s  %5s  %-20s  %s' % \
    ('OFFSET', 'INSTRUCTION', 'OPCODE', 'ARG', 'TYPE', 'VALUE')
  for (offset, op, name, argument, argtype, argvalue) in instructions:
    print '%5d  %-20s (%3d)  ' % (offset, name, op),
    if argument != None:
      print '%5d  %-20s  (%s)' % (argument, argtype, argvalue),
    print 

def main():
  pretty_print(decompile(foo_simple.func_code))
#  print foo_simple()

if __name__ == '__main__':
  main()

#:~

If you look at the generated code carefully, you will notice that the CPython virtual machine is heavily stack based. The bytecode of

def foo_stupid():
    i = 0
    i = i + 1
    return i

would look something like this

OFFSET INSTRUCTION   OPCODE    ARG  TYPE             VALUE
0      LOAD_CONST    (100)       1  CONSTANT         (0)
3      STORE_FAST    (125)       0  LOCAL VARIABLE   (i)
6      LOAD_FAST     (124)       0  LOCAL VARIABLE   (i)
9      LOAD_CONST    (100)       2  CONSTANT         (1)
12     BINARY_ADD    ( 23)
13     STORE_FAST    (125)       0  LOCAL VARIABLE   (i)
16     LOAD_FAST     (124)       0  LOCAL VARIABLE   (i)
19     RETURN_VALUE  ( 83)

Some of you would have noticed that the instruction sequence looks senile. (STORE, LOAD) sequences on the same variable such as (3,6) and (13,16) are totally pointless. These are clear candidates for optimization. In fact if we keep building intelligence into the byte-code optimizer, it could eventually output something like

OFFSET INSTRUCTION   OPCODE    ARG  TYPE             VALUE
0      LOAD_CONST    (100)       1  CONSTANT         (1)
3      RETURN_VALUE  ( 83)

(For comparison, try writing a C program equivalent to the foo_stupid() function and compile it with gcc -O3 -S and look at the generated assembly. It would simply be a mov $1, %eax followed by a ret for the 32 bit x86 ABI. No frame pointer thank you !)

Quite astonishingly, running the program with python -O (byte code optimization enabled) did nothing to change the emitted byte code for foo_stupid(). Running through optimize_code(), the peephole optimizer in Python/compile.c confirms that foo_stupid() was a bad example to choose !

And lastly, I should mention a couple of projects that relate to Python and Bytecode Optimization in loosely coupled ways:

Psyco:

Psyco’s Just in time specialization is a good example of the kind of optimization that can make a serious difference. psyco emits native machine code during the JIT phase. It uses runtime profiling to find out type information about objects and starts dynamically patching machine code at runtime based on the profiler’s feedback. In simple terms if you have a function like

def f(a, b):
  return (2*a + 3*b)

Duck typing prevents a lot of optimization because a,b can be integers, long integers, strings, lists, tuples, floats or even complex numbers. If a function dispatch occurs with integer arguments for a and b, pysco creates a version of f that is optimized for integer values of a and b. Further calls with integer arguments jump to this version. Later if you call the same function with floating point arguments, another optimized version of the function is emitted. It hogs memory but runs way too faster than the CPython VM instructions. My only pet-peeve is that the machine code is patched in memory and there is no way to store it to the disk.

PyPy:

The most interesting python project in this area currently is PyPy. PyPy is a self-hosting python implementation that translates Python to lower level languages. PyPy is written in python itself or rather a restricted subset called RPython (Which omits some of the dynamic aspects of python). The best part about PyPy is that the translation into low-level languages is “pluggable”. PyPy can produce CPython or Jython or IronPython or any arbitrary Intermediate code format. Very slick !

I am particularly interested in the LLVM code generation capabilites of PyPy. The Low-Level Virtual Machine (LLVM) project itself is very mature and does some serious optimization of its intermediate code. And when coupled with the fact that it has backends for x86/64, SPARC, Power, Alpha and ARM, this gives us the enviable prospect of translating python code into native machine code.

A very good tool to experiment with the CPython bytecode is the aptly named byteplay project: http://code.google.com/p/byteplay/
Not to forget the excellent peak.util.Assembler

Filed under: Open Source, Programming, Python