Recipe20.16.Binding Constants at Compile Time

Recipe 20.16. Binding Constants at Compile Time

Credit: Raymond Hettinger, Skip Montanaro

Problem

Runtime lookup of global and built-in names is slower than lookup of local names. So, you would like to bind constant global and built-in names into local constant names at compile time.

Solution

To perform this task, we must examine and rewrite bytecodes in the function's code object. First, we get three names from the standard library module opcode, so we can operate symbolically on bytecodes, and define two auxiliary functions for bytecode operations:

from opcode import opmap, HAVE_ARGUMENT, EXTENDED_ARG globals( ).update(opmap) def _insert_constant(value, i, code, constants):     ''' insert LOAD_CONST for value at code[i:i+3].  Reuse an existing         constant if values coincide, otherwise append new value to the         list of constants; return index of the value in constants. '''     for pos, v in enumerate(constants):         if v is value: break     else:         pos = len(constants)         constants.append(value)     code[i] = LOAD_CONST     code[i+1] = pos & 0xFF     code[i+2] = pos >> 8     return pos def _arg_at(i, code):     ''' return argument number of the opcode at code[i] '''     return code[i+1] | (code[i+2] << 8)

Next comes the workhorse, the internal function that does all the binding and folding work:

def _make_constants(f, builtin_only=False, stoplist=( ), verbose=False):     # bail out at once, innocuously, if we're in Jython, IronPython, etc     try: co = f.func_code     except AttributeError: return f     # we'll modify the bytecodes and consts, so make lists of them     newcode = map(ord, co.co_code)     codelen = len(newcode)     newconsts = list(co.co_consts)     names = co.co_names     # Depending on whether we're binding only builtins, or ordinary globals     # too, we build dictionary 'env' to look up name->value mappings, and we     # build set 'stoplist' to selectively override and cancel such lookups     import _ _builtin_ _     env = vars(_ _builtin_ _).copy( )     if builtin_only:         stoplist = set(stoplist)         stoplist.update(f.func_globals)     else:         env.update(f.func_globals)     # First pass converts global lookups into lookups of constants     i = 0     while i < codelen:         opcode = newcode[i]         # bail out in difficult cases: optimize common cases only         if opcode in (EXTENDED_ARG, STORE_GLOBAL):             return f         if opcode == LOAD_GLOBAL:             oparg = _arg_at(i, newcode)             name = names[oparg]             if name in env and name not in stoplist:                 # get the constant index to use instead                 pos = _insert_constant(env[name], i, newcode, newconsts)                 if verbose: print '%r -> %r[%d]' % (name, newconsts[pos], pos)         # move accurately to the next bytecode, skipping arg if any         i += 1         if opcode >= HAVE_ARGUMENT:             i += 2     # Second pass folds tuples of constants and constant attribute lookups     i = 0     while i < codelen:         newtuple = [  ]         while newcode[i] == LOAD_CONST:             oparg = _arg_at(i, newcode)             newtuple.append(newconsts[oparg])             i += 3         opcode = newcode[i]         if not newtuple:             i += 1             if opcode >= HAVE_ARGUMENT:                 i += 2             continue         if opcode == LOAD_ATTR:             obj = newtuple[-1]             oparg = _arg_at(i, newcode)             name = names[oparg]             try:                 value = getattr(obj, name)             except AttributeError:                 continue             deletions = 1         elif opcode == BUILD_TUPLE:             oparg = _arg_at(i, newcode)             if oparg != len(newtuple):                 continue             deletions = len(newtuple)             value = tuple(newtuple)         else:             continue         reljump = deletions * 3         newcode[i-reljump] = JUMP_FORWARD         newcode[i-reljump+1] = (reljump-3) & 0xFF         newcode[i-reljump+2] = (reljump-3) >> 8         pos = _insert_constant(value, i, newcode, newconsts)         if verbose: print "new folded constant: %r[%d]" % (value, pos)         i += 3     codestr = ''.join(map(chr, newcode))     codeobj = type(co)(co.co_argcount, co.co_nlocals, co.co_stacksize,                     co.co_flags, codestr, tuple(newconsts), co.co_names,                     co.co_varnames, co.co_filename, co.co_name,                     co.co_firstlineno, co.co_lnotab, co.co_freevars,                     co.co_cellvars)     return type(f)(codeobj, f.func_globals, f.func_name, f.func_defaults,                     f.func_closure)

Finally, we use _make_constants to optimize itself and its auxiliary function, and define the functions that are meant to be called from outside this module to perform the optimizations that this module supplies:

# optimize thyself! _insert_constant = _make_constants(_insert_constant) _make_constants = _make_constants(_make_constants) import types @_make_constants def bind_all(mc, builtin_only=False, stoplist=( ), verbose=False):     """ Recursively apply constant binding to functions in a module or class.     """     try:         d = vars(mc)     except TypeError:         return     for k, v in d.items( ):         if type(v) is types.FunctionType:             newv = _make_constants(v, builtin_only, stoplist,  verbose)             setattr(mc, k, newv)         elif type(v) in (type, types.ClassType):             bind_all(v, builtin_only, stoplist, verbose) @_make_constants def make_constants(builtin_only=False, stoplist=[  ], verbose=False):     """ Call this metadecorator to obtain a decorator which optimizes         global references by constant binding on a specific function.     """     if type(builtin_only) == type(types.FunctionType):         raise ValueError, 'must CALL, not just MENTION, make_constants'     return lambda f: _make_constants(f, builtin_only, stoplist, verbose)

Discussion

Assuming you have saved the code in this recipe's Solution as module optimize.py somewhere on your Python sys.path, the following example demonstrates how to use the make_constants decorator with arguments (i.e., metadecorator) to optimize a functionin this case, a reimplementation of random.sample:

import random import optimize @optimize.make_constants(verbose=True) def sample(population, k):     " Choose `k' unique random elements from a `population' sequence. "     if not isinstance(population, (list, tuple, str)):         raise TypeError('Cannot handle type', type(population))     n = len(population)     if not 0 <= k <= n:         raise ValueError, "sample larger than population"     result = [None] * k     pool = list(population)     for i in xrange(k):         # invariant:  non-selected at [0,n-i)         j = int(random.random( ) * (n-i))         result[i] = pool[j]         pool[j] = pool[n-i-1]   # move non-selected item into vacancy     return result

Importing this module emits the following output. (Some details, such as the addresses and paths, will, of course, vary.)

'isinstance' -> <built-in function isinstance>[6] 'list' -> <type 'list'>[7] 'tuple' -> <type 'tuple'>[8] 'str' -> <type 'str'>[9] 'TypeError' -> <class exceptions.TypeError at 0x402952cc>[10] 'type' -> <type 'type'>[11] 'len' -> <built-in function len>[12] 'ValueError' -> <class exceptions.ValueError at 0x40295adc>[13] 'list' -> <type 'list'>[7] 'xrange' -> <type 'xrange'>[14] 'int' -> <type 'int'>[15] 'random' -> <module 'random' from '/usr/local/lib/python2.4/random.pyc'>[16] new folded constant: (<type 'list'>, <type 'tuple'>, <type 'str'>)[17] new folded constant: <built-in method random of Random object at 0x819853c>[18]

On my machine, with the decorator optimize.make_constants as shown in this snippet, sample(range(1000), 100) takes 287 microseconds; without the decorator (and thus with the usual bytecode that the Python 2.4 compiler produces), the same operation takes 333 microseconds. Thus, using the decorator improves performance by approximately 14% in this exampleand it does so while allowing your own functions' source code to remain pristine, without any optimization-induced obfuscation. On functions making use of more constant names within loops, the performance benefit of using this recipe's decorator can be correspondingly greater.

A common and important technique for manual optimization of a Python function, once that function is shown by profiling to be a bottleneck of program performance, is to ensure that all global and built-in name lookups are turned into lookups of local names. In the source of functions that have been thus optimized, you see strange arguments with default values, such as _len=len, and the body of the function uses this local name _len to refer to the built-in function len. This kind of optimization is worthwhile because lookup of local names is much faster than lookup of global and built-in names. However, functions thus optimized can become cluttered and less readable. Moreover, optimizing by hand can be tedious and error prone.

This recipe automates this important optimization technique: by just mentioning a decorator before the def statement, you get all the constant bindings and foldings, while leaving the function source uncluttered, readable, and maintainable. After binding globals to constants, the decorator makes a second pass and folds constant attribute lookups and tuples of constants. Constant attribute lookups often occur when you use a function or other attribute from an imported module, such as the use of random.random in the sample function in the example snippet. Tuples of constants commonly occur in for loops and conditionals using the in operator, such as for x in ('a', 'b', 'c'). The best way to appreciate the bytecode transformations performed by the decorator in this recipe is to run "dis.dis(sample)" and view the disassembly into bytecodes, both with and without the decorator.

If you want to optimize every function and method in a module, you can call optimize.bind_all(sys.modules[_ _name_ _]) as the last instruction in the module's body, before the tests. To optimize every method in a class, you can call optimize.bind_all(theclass) just after the end of the body of the class theclass statement. Such wholesale optimization is handy (it does not require you to deal with any details) but generally not the best approach. It's best to bind, selectively, only functions whose speed is important. Functions that particularly benefit from constant-binding optimizations are those that refer to many global and built-in names, particularly with references in loops.

To ensure that the constant-binding optimizations do not alter the behavior of your code, apply them only where dynamic updates of globals are not desired (i.e., the globals do not change). In more dynamic environments, a more conservative approach is to pass argument builtin_only as true, so that only the built-ins get optimized (built-ins include functions such as len, exceptions such as IndexError, and such constants as true or False). Alternatively, you can pass a sequence of names as the stoplist argument, to tell the binding optimization functions to leave unchanged any reference to those names.

While this recipe is meant for use with Python 2.4, you can also use this approach in Python 2.3, with a few obvious caveats. In particular, in version 2.3, you cannot use the new 2.4 @decorator syntax. Therefore, to use in Python 2.3, you'll have to tweak the recipe's code a little, to expose _make_constants directly, without a leading underscore, and use f=make_constants(f) in your code, right after the end of the body of the def f statement. However, if you are interested in optimization, you should consider moving to Python 2.4 anyway: Python 2.4 is very compatible with Python 2.3, with just a few useful additions, and version 2.4 is generally measurably faster than Python 2.3.

Recipe20.16.Binding Constants at Compile Time