[lang]

Present Perfect

Personal
Projects
Packages
Patches
Presents
Linux

Picture Gallery
Present Perfect

Python disassembly

Filed under: Hacking,Python — Thomas @ 18:19

2009-06-27
18:19

As part of this weekend's yakshave, I'm trying to implement a handler for STORE_MAP in pychecker. STORE_MAP is a new opcode in Python 2.6, which speeds up dict building.

So, for the first time I went under the hood of Python and figured out just enough to understand this problem. It was a lot less scary than I thought it was going to be!

It seems that using dis.dis(), one can easily dissassemble any python function into its opcodes. This shows clearly where the behaviour is different between python 2.5 and python 2.6.

Given the following function:

f = lambda: {'a': 1, 'b': 2}

Python 2.6 gives:

1 0 BUILD_MAP 2
3 LOAD_CONST 0 (1)
6 LOAD_CONST 1 ('a')
9 STORE_MAP
10 LOAD_CONST 2 (2)
13 LOAD_CONST 3 ('b')
16 STORE_MAP
17 RETURN_VALUE

I couldn't find a good description of the output of dis.dis, but in my naiveness I am guessing the following:

  • The first 1 maps to the line number in the code object where the function is found.
  • The second column is the offset of the opcode and its arguments
  • The third column is the opcode name
  • The next column is the arguments for the opcode; in the case of CONST, it shows the index as well as the const object indexed

I am assuming each opcode takes one address location, and each argument takes two; that maps with the address pointers in front of the opcodes.

The opcodes are all documented.

So, in human terms:

  • we start with BUILD_MAP, saying that we'll create a new dictionary on the stack, with 2 entries.
  • we load the constant with index 0 onto the stack (which happens to be the integer object '1', the value of the 'a' key)
  • we load the constant with index 1 onto the stack (which happens to be the string object 'a', the key for the '1' value)
  • STORE_MAP pops the key and the value off the stack, storing them in the dict. Note that the key was indeed loaded on the stack after the value. Now only the dictionary is left on the stack.
  • Repeat LOAD_CONST, LOAD_CONST and STORE_MAP for the next set
  • RETURN_VALUE returns the current value on the stack to the caller

Pretty simple, when you look at it twice.

For the same code, python 2.5 gives:

>>> dis.dis(f)
1 0 BUILD_MAP 0
3 DUP_TOP
4 LOAD_CONST 1 ('a')
7 LOAD_CONST 2 (1)
10 ROT_THREE
11 STORE_SUBSCR
12 DUP_TOP
13 LOAD_CONST 3 ('b')
16 LOAD_CONST 4 (2)
19 ROT_THREE
20 STORE_SUBSCR
21 RETURN_VALUE

This code is slightly longer and more complicated. Basically, LOAD_CONST, LOAD_CONST, STORE_MAP was implemented with DUP_TOP, LOAD_CONST, LOAD_CONST, ROT_THREE, STORE_SUBSCR

It looks like DUP_TOP was needed because STORE_SUBSCR consumes the dictionary off the stack, and ROT_THREE is needed because the arguments are pushed on the stack in the wrong order.

Seems like a nice and obvious improvement once you understand it. An exercise for the reader is to profile whether this change actually makes things faster in practice.

So, where does this leave me for pychecker ? It now looks deceptively simple. STORE_MAP simply pops off two items of the stack. There is nothing to check for, since we're in a dictionary context. So all my implementation needs to do is to pop 2 items off the stack, and that's it.

And thus it was commited to pychecker CVS. Popping one item off the yak stack!

2 Comments »

  1. You’re missing a closing quote on the href of your first link in this post, so the first half of your post doesn’t show in a browser.

    Comment by Robert Brewer — 2009-06-27 @ 20:39

  2. Thanks Robert for spotting ! Corrected.

    Comment by Thomas — 2009-06-27 @ 20:44

RSS feed for comments on this post. TrackBack URL

Leave a comment

picture