Python Performance Tips

This page is devoted to various tips and tricks that help improve the performance of your Python programs. Wherever the information comes from someone else, I've tried to identify the source.

If you have any light to shed on this subject, let me know.

Contents

  • Profiling Code
    • Profile Module
    • Trace Module
  • Sorting
  • String concatenation
  • Loops
  • Avoiding dots...
  • Local Variables
  • Initializing Dictionary Elements
  • Import Statement Overhead
  • Using map with Dictionaries
  • Data Aggregation
  • Doing Stuff Less Often

Profiling Code

The first step to speeding up your program is learning where the bottlenecks lie. It hardly makes sense to optimize code that is never executed or that already runs fast. I use two modules to help locate the hotspots in my code, profile and trace.

Profile Module

The profile module is included as a standard module in the Python distribution. Using it to profile the execution of a set of functions is quite easy. Suppose your main function is called main, takes no arguments and you want to execute it under the control of the profile module. In its simplest form you just execute

import profile
profile.run('main()')
When main() returns, the profile module will print a table of function calls and execution times. The output can be tweeked using the Stats class included with the module. For more details, check out the profile module's documentation (Lib/profile.doc).

Trace Module

The trace module is a spin-off of the profile module I wrote originally to perform some crude statement level test coverage. As of Python 2.0 you should find trace.py in the Tools/scripts directory of the Python distribution. Thanks to Andrew Dalke it's very easy to run from the command line to trace execution of whole scripts:

% trace.py -t spam.py eggs
There's no separate documentation, but there are some pretty complete docstrings at the top of the module.

Sorting

From Guido van Rossum

Sorting lists of basic Python objects is generally pretty efficient. The sort method for lists takes an optional comparison function as an argument that can be used to change the sorting behavior. This is quite convenient, though it can really slow down your sorts.

An alternative way to speed up sorts is to construct a list of tuples whose first element is a sort key that will sort properly using the default comparison, and whose second element is the original list element.

Suppose, for example, you have a list of tuples that you want to sort by the n-th field of each tuple. The following function will do that.

def sortby(list, n):
    nlist = map(lambda x, n=n: (x[n], x), list)
    nlist.sort()
    return map(lambda (key, x): x, nlist)
Here's an example use:
>>> list = [(1, 2, 'def'), (2, -4, 'ghi'), (3, 6, 'abc')]
>>> list.sort()
>>> list
[(1, 2, 'def'), (2, -4, 'ghi'), (3, 6, 'abc')]
>>> sortby(list, 2)
[(3, 6, 'abc'), (1, 2, 'def'), (2, -4, 'ghi')]
>>> sortby(list, 1)
[(2, -4, 'ghi'), (1, 2, 'def'), (3, 6, 'abc')]

String Concatenation

Strings in Python are immutable. This fact frequently sneaks up and bites novice Python programmers on the rump. Immutability confers some advantages and disadvantages. In the plus column, strings can be used a keys in dictionaries and individual copies can be shared among multiple variable bindings. (Python automatically shares one- and two-character strings.) In the minus column, you can't say something like, "change all the 'a's to 'b's" in any given string. Instead, you have to create a new string with the desired properties. This continual copying can lead to significant inefficiencies in Python programs.

The following is adapted from inputs by Aaron Watters:

Avoid this:

   str = ""
   for substring in list:
       str = str + substring

Use "".join(list) instead. The former is a very common and catastrophic mistake when building large strings. Similarly, if you are generating bits of a string sequentially instead of

   str = ""
   for x list:
       str = str + some_function(x)
use
   str = [None]*len(list):
   for i in range(len(list):
       str[i] = some_function(list[i])
   str = "".join(str)

Avoid:

   out = "" + head + prologue + query + tail + "
Instead, use
   out = "%s%s%s%s" % (head, prologue, query, tail)

This is a lot faster, and easier to modify also. In addition, the slow way of doing things got slower in Python 2.0 with the addition of rich comparisons to the language. It now takes the Python virtual machine a lot longer to figure out how to concatenate to strings. (Don't forget that Python does all method lookup at runtime.)

Loops

Python supports a couple of looping constructs. The for statement is most commonly used. It loops over the elements of a sequence, assigning each to the loop variable. If the body of your loop is simple, the interpreter overhead of the for loop itself can be a substantial amount of the overhead. This is where the map function is handy. You can think of map as a for moved into C code. The only restriction is that the "loop body" of map must be a function call.

Here's a straightforward example. Instead of looping over a list of words and converting them to upper case:

newlist = []
for word in list:
    newlist.append(word.upper())
you can use map to push the loop from the interpreter into compiled C code:
import string
newlist = map(string.upper, list)

List comprehensions were added to Python in version 2.0 as well. They provide a syntactically more compact way of writing the above for loop:

newlist = [s.upper() for s in list]
It's not really any faster than the for loop version, however.

Guido van Rossum wrote a much more detailed examination of loop optimization that is definitely worth reading.

Avoiding dots...

Suppose you can't use map? The example above of converting words in a list to upper case has another inefficiency. Both newlist.append and string.upper are function references that are recalculated each time through the loop. The original loop can be replaced with:
import string
upper = string.upper
newlist = []
append = newlist.append
for word in list:
    append(upper(word))

Local Variables

The final speedup available to us for the non-map version of the for loop is to use local variables wherever possible. If the above loop is cast as a function, append and upper become local variables.

def func():
    upper = string.upper
    newlist = []
    append = newlist.append
    for word in words:
    append(upper(word))
    return newlist
An extra performance boost is received because local variables are accessed more efficiently than variables at module scope. On my machine (100MHz Pentium running BSDI), I got the following times for converting the list of words in /usr/share/dict/words (38,470 words) to upper case:

Version | Time (seconds)
Basic loop | 3.47
Eliminate dots | 2.45
Local variable & no dots | 1.79
Using map function | 0.54

Eliminating the loop overhead by using map is often going to be the most efficient option. When the complexity of your loop precludes its use other techniques are available to speed up your loops, however.

Initializing Dictionary Elements

Suppose you are building a dictionary of word frequencies and you've already broken your words up into a list. You might execute something like:

wdict = {}
for word in words:
    if not wdict.has_key(word): wdict[word] = 0
    wdict[word] = wdict[word] + 1

Except for the first time, each time a word is seen the if statement's test fails. If you are counting a large number of words, many will probably occur multiple times. In a situation where the initialization of a value is only going to occur once and the augmentation of that value will occur many times it is cheaper to use a try statement:

wdict = {}
for word in words:
    try:
        wdict[word] = wdict[word] + 1
    except KeyError:
        wdict[word] = 1

It's important to catch the expected exception, and not have a default except clause to avoid trying to recover from an exception you really can't handle by the statement(s) in the try clause.

Note that if the try clause generates an exception most of the time, it will often be more efficient to test for the exceptional condition than to generate it and recover from it.

Import Statement Overhead

import statements can be executed just about anywhere. It's often useful to place them inside functions to restrict their visibility and/or reduce initial startup time. Although Python's interpreter is optimized to not import the same module multiple times, repeatedly executing an import statement can seriously affect performance in some circumstances.

Consider the following two snippets of code (originally from Greg McFarlane, I believe - I found it unattributed in a comp.lang.python/python-list@python.org posting and later attributed to him in another source):

def doit():
    import string             ###### import statement inside function
    string.lower('Python')

for num in range(100000):
    doit()
or:
import string             ###### import statement outside function
def doit():
    string.lower('Python')

for num in range(100000):
    doit()
The second version will run substantially faster than the first, even though the reference to the string module is global in the second example. String methods were introduced to the language in Python 2.0. These provide a version that avoids import completely:
def doit():
    'Python'.lower()

for num in range(100000):
    doit()

The above example is obviously a bit contrived, but the general principle holds.

Using map with Dictionaries

I found it frustrating that to use map to eliminate simple for loops like:

dict = {}
nil = []
for s in list:
    dict[s] = nil
I had to use a lambda form or define a named function that would probably negate any speedup I was getting by using map in the first place. I decided I needed some functions to allow me to set, get or delete dictionary keys and values en masse. I proposed a change to Python's dictionary object and used it for awhile. However, a more general solution appears in the form of the operator module in Python 1.4. Suppose you have a list and you want to eliminate its duplicates. Instead of the code above, you can execute:
dict = {}
map(operator.setitem, [dict]*len(list), list, [])
list = statedict.keys()
This moves the for loop into C where it executes much faster.

Data Aggregation

(Paraphrased from a note by Aaron Watters)

Function call overhead in Python is relatively high, especially compared with the execution speed of a builtin function. This strongly suggests that extension module functions should handle aggregates of data where possible. Here's a contrived example written in Python. (Just pretend the function was written in C. :-)

x = 0
def doit(i):
    global x
    x = x + i

list = range(10000)
for i in list:
    doit(i)
vs.
x = 0
def doit(list):
    global x
    for i in list:
    x = x + i

list = range(10000)
doit(list)
Even written in Python, the second example runs about four times faster than the first. Had doit been written in C the difference would likely have been even greater (exchanging a Python for loop for a C for loop as well as removing most of the function calls).

Doing Stuff Less Often

The Python interpreter performs some periodic checks. In particular, it decides whether or not to let another thread run and whether or not to run a pending call (typically a call established by a signal handler). Most of the time there's nothing to do, so performing these checks each pass around the interpreter loop can slow things down. There is a function in the sys module, setcheckinterval, which you can call to tell the interpreter how often to perform these periodic checks. In Python 1.4 it defaults to 10. If you aren't running with threads and you don't expect to be catching lots of signals, setting this to a larger value can improve the interpreter's performance, sometimes substantially.

Skip Montanaro
(skip@pobox.com)

Last modified: Thu Jul 12 12:02:02 CDT 2001


Skip's Python Bits

Python is an interpreted object-oriented programming language that has gained an enthusiastic following. You can read all about it at the Python Software Association's web site.

I've written or collected little bits and pieces of quasi-useful Python stuff. What I've announced to the public is available here.

Buying this book helps keep Mojam and Musi-Cal running.

More or Less Current Stuff

Alarms for asyncore.
I recently had a reason to start using asyncore. It's a marvelous package for doing I/O with several network sockets. One of the first things I wanted to do after getting it working was implement alarms. Signal.alarm is ugly and may not work everywhere anyway, so I took advantage of the fact that asyncore uses the timeout feature of select() and poll().
Weekend Edition Sunday Puzzle.
I listen on occasion to NPR's Sunday Weekend Edition. Perhaps the best segment of the show is the Puzzle run by Will Shortz. On October 7th, 2001, this challenge was posted:
Draw a 4 by 3 box. The object is to fill it with letters spelling 3 four-letter words across and 4 three-letter words reading down. The conditions: your box can not repeat any letters, and it must use all six vowels (a, e, i, o, u, y) once. All words must be uncapitalized, common English words.
The code in nprpuzzle.py solves this problem using a straightforward O(N**3) algorithm. I don't claim it's the best way to approach the problem, but it was a fun diversion for a Sunday. It uses my little progress module to track progress.
Locate Division Operators.
With the coming change to the semantics of integer division you'll probably want to run something like finddiv.py over your code to identify potential trouble spots. It does nothing more than identify lines containing a "/" operator. It doesn't perform any analysis to try and prune the possible list of lines it displays. It does display lines in a format that Emacs's next-error command understands.
Editor Support for Python.
This is no longer maintained by me. You will be redirected to the new editors page on the main Python website.
ConstantMap.py - map numeric constants to their names.
The ConstantMap.ConstantMap class can be instantiated from modules of constants to map "magic numbers" back to their names. This is useful when debugging code that returns such numbers. For example, the numeric constant modules generated by the h2py script all map semi-meaningful names to mostly meaningless numbers. ConstantMap allows you to map them back.
Watch - keyboard/mouse monitor.
This Python script (hosted at SourceForge) monitors keyboard and mouse activity and enforces work and rest times. It currently only runs on Linux, but it has run on Windows in the past (only directly monitoring mouse activity) and could probably run on the Mac without a lot of effort.
Soundex module.
This module is a Python replacement for the now defunct soundex.c. This module is a merging of separate ones written by Tim Peters and Fred Drake.
SYLK file reader.
This module reads SYLK files and generates CSV files. Note that it currently has only been tested with files generated from AppleWorks 5.0 on a Mac.
Rough Size Calculator.
There are three general sources of memory leaks in long-running Python programs: cyclical objects that reference counting can't reclaim, botches at the low-level malloc interface, and growth of container objects that are reachable, but whose growth you're unaware of. Neil Schemenauer's garbage collector in Python 2.0 does a good job identifying cyclical garbage. This module attacks the third case. The test case uses the Cache module below.
Simple Caching Dictionary.
Sometimes you need to cache results of long computations or database queries, but don't want your memory consumption to grow without bound. The Cache class subclasses UserDict.UserDict to provide a cache that discards values based on access time.
Python Code Coverage.
This is a summary of C and Python code coverage when running the regression tests that are part of the standard distribution.
XML-RPC validation suite.
This server passes the XML-RPC validation suite as implemented at validator.xmlrpc.com as of June 5th, 2000.
Adding gzip encoding capability to XML-RPC clients and servers.
The instructions in gzip-xmlrpc.txt describe simple mods to XML-RPC servers and clients to allow responses to be encoded using gzip when possible. This can help performance significantly when using XML-RPC over wide area networks. You can also download the version of xmlrpclib.py that I use which includes one or two other mods. It is based on version 0.9.8 of Fredrik Lundh's xmlrpclib package.
Getting interactive help about objects
I include the two functions in help.py in my .pythonrc file. During interactive sessions I can then execute help(foo) for an arbitrary object foo. If it's a Python function or method, it will display its declaration. If it has a doc string it will display that as well.
Warning about return statement usage
This patch to Python/dist/src/compile.c causes the Python byte code compiler to print warnings if it encounters inconsistent use of the return statement within a function. This is experimental code. Use at your own risk! (last updated 1999-09-10)
Warning about hiding builtin names
This script takes a list of module names and tells you which top-level functions have local variables that hide builtin objects with the same name. (last updated 1999-09-30)
Manipulating recurring dates
Recurring dates occur frequently in my business, e.g., "The Bill Baldwin Trio appears every Thursday at 10pm". recur.py is a crack at the problem. It allows you to intersect two recurring dates or generate a finite subset of dates that fit the recurrence pattern. There's a long comment at the start that's not much more than me thinking out loud, followed by a fairly small amount of code. Feedback is much appreciated. Experimental (last updated 1999-08-09)
Paper for SPAM-7
This paper describes some initial work I did with a peephole optimizer for Python byte code. (last updated 1998-11-22)
Faster stack manipulation
This patch against the 1.5.1 source distribution reduces the number of temporary variables and PUSH/POP operations performed by the Python interpreter. It also cleans up a few other miscellaneous nits. See README.stack file for a summary of the changes. Experimental (last updated 1998-07-05)
Peephole optimizer for Python byte code
This patch against the 1.5.1 source distribution adds a peephole optimizer to Python. See README.peep file for an introduction. Experimental (last updated 1998-07-02)
Validation of CGI script parameters
The cgi module that comes with Python eliminates the tedium of marshalling script parameters from the HTTP input stream. This module enhances that with type checking. You can indicate which parameters are required, which are optional and what their types must be. Type information can be given in the input form, in an auxiliary file on the server or in the CGI script itself. The latest version also handles multi-valued parameters such as would be encountered with <select> tags having the multiple attribute. (last updated 1999-09-30)
Finite State Machine
I recently added the ability for the states to be regex objects. This makes it easier to match some inputs in a case-insensitive manner. I'm sure creative folks will find other weird uses for the capability. (Note that when testing for re matches, it simply loops through the possible inputs for that state. The first re that matches the input is considered to match. If you have multiple re's that match a particular input, which one gets picked is non-deterministic.) (last updated 1999-09-30)
DOS-ification of file names
I wrote this short script to map long filenames to DOS 8.3 names. I imagine there are some errors in the assumptions about what can go in a DOS filename. Feedback is welcome. (last updated 1996-12-19)
Date-parsing module
I wrote this module to recognize dates in many different formats on-the-fly. The most useful bits are the parse_date function and the Time class. (last updated 1996-10-31)
Browsable Python sources
I find it convenient to use this to refer to individual files from web pages. I used to tar it all up and use a Python CGI script called tgzextr.py to pull out individual files, but I now have enough disk space to keep the sources laying about... :-) This directory is just a snapshot of the CVS repository. (last updated 1999-09-30)
Test coverage tool
This little knock-off of the profile module provides test coverage of Python scripts in the spirit of Sun's now ancient (and probably defunct) tcov tool. (last updated 1999-08-21)
Speeding up Python programs
We all want our Python programs to run fast. I'm slowing working on some notes and references collected from my experience and that of other people. Contributions and comments are most welcome. (last updated 1999-01-25)
Simple-minded TCP client and server
I wrote a small client and server to test TCP connection and transmission speeds using either AF_INET or AF_UNIX sockets. Some implementations of AF_INET sockets degrade as you perform more and more connections in a short period of time. This is presumably due to linear search for an available port and the fact that TCP requires sockets to hang around for awhile after closing to catch late-arriving packets. (last updated 1996-06-07)
Parser for robots.txt files
Writing a Web wanderer in Python? Here's a little piece of code to help you along. Delivered with the Python distribution now.

Demo Scripts

The same questions seem to pop up from time-to-time. Here are some short scripts that demostrate various Python modules or features

Submitting URLs through a proxy
The Mapblast script takes two arguments, a city and a state or Canadian Province, and tries to extract the city's lat/long information from the Mapblast web server. If it succeeds, it displays a line with the city, state, latitude and longitude separated by colons. If the city name is slightly misspelled (e.g. Pittsburg instead of Pittsburgh), the Mapblast server does a fair job of correcting your spelling. This script displays what Mapblast said, not what your wrote... (last updated 1998-05-12)
Submitting a web form using the POST method
The sony.py script accepts a key representing a single Sony Music artist on stdin and submits it to Sony's artist search engine by mimicking the POST method submission that a user would trigger by searching for their favorite artist. It's one stage in a pipeline that looks something like:
      httpget http://www2.music.sony.com/musicdb/TourInfo | \
          egrep -i 'DJ HONDA' | \
          sed -e 's:
(last updated 1998-05-17)

More or Less Obsolete Stuff

Experimental threaded web server
This server avoids forking by mapping URLs to modules and then calls the appropriate function in the handler thread. This was an interesting exercise, but you should probably use Medusa instead.
Quick Index of Python Library Reference
I got tired of trying to find the names of modules in the Python Library Reference table of contents, so I wrote a little script to create an alphabetically organized table that makes it easier (for me at least) to find what I'm looking for.
Python support for VTK 2.0
The above gzip'd diffs for VTK 2.0 support integration of VTK with Python (85839 bytes). It was obsoleted by a rewrite of the VTK wrapper code generator, so if you are running a more recent version of VTK than what was released in mid-May 1998, this won't work.
Enhanced urllib module
CGI scripts tend to do lots of quoting and unquoting. I wrote a small enhancement to Python's urllib module that migrates urllib.quote and urllib.unquote into the urlop C module. The test1 function at the bottom of the urllib module runs 50-70 times faster using the urlop module on my P100/BSDI system.
Improved (?) allocation of short strings (Feedback welcome)
I wrote a special-purpose allocator for short string objects (short being <= 128 bytes, including the object header). A modified version of stringobject.c contains the whole thing. A modified version of stropmodule.c defines a "counts" function that can be called to retrieve a list of counters that track creation and deletion of, respectively, large, <=32-byte, <=64-byte, <=128-byte strings. Note that this is not yet ready for prime time! This is just experimental code at this point. It is not well enough packaged yet.
Partial C implementation of the regsub module
This is another not-quite-ready-for-prime-time module. It only implements regsub.sub and regsub.gsub at this point. I just checked my version of regsub.py and noticed I'm not even using it... I suspect there's a bug lurking in there but punted on trying to find it. Whoever wants to take on the challenge, here it is.
SPAM-1 presentation on Python/C++
Ages and ages ago (1994! That's fourteen Internet years as I write this in September 1996) it seems I was doing some Python/C++ integration. It's been superceded by lots of other work. Still, some may find the concepts presented useful.
python ring
Previous 5 Sites | Skip Previous | Previous | Next | Skip Next | Next 5 Sites | Random Site | List Sites
Skip Montanaro
skip@mojam.com
Last modified: Wed Jan 23 11:16:59 CST 2002


 There is now a web page at python.org about editors. You should be sent there momentarily.


Adding gzip encoding to Python-based XML-RPC clients is pretty simple.  My
approach is based upon the observation that (in my code anyway - database
queries) the request is usually much smaller than the response.  The
client's request is never gzip'd.  It only tells the server if it will
accept a gzip'd response.

To add gzip-awareness to xmlrpclib.py take the following steps:

1. Near the top of the file add the following lines:

    try:
    import zlib
    except ImportError:
    zlib = None

2. In Transport.request, add an Accept-Encoding header if zlib was imported
   okay:

    if zlib is not None:
    h.putheader("Accept-Encoding", "gzip")

3. Replace the "return self.parse_response..." with

    try:
    content_encoding = headers["content-encoding"]
    if content_encoding and content_encoding == "x-gzip":
        return self.parse_response_gzip(h.getfile())
    elif content_encoding:
        raise ProtocolError(host + handler,
                500,
                "Unknown encoding type: %s" %
                content_encoding,
                headers)
    else:
        return self.parse_response(h.getfile())
    except KeyError:
    return self.parse_response(h.getfile())

4. Add a parse_response_gzip method to the Transport class:

    def parse_response_gzip(self, f):
    # read response from input file, and parse it

        #t = time.time()
        dc = zlib.decompressobj()
    p, u = getparser()
        resp = []

        append = resp.append
        read = f.read

    while 1:
        response = read(8192)
        if not response: break
            append(response)

        response = dc.decompress(string.join(resp, ""))
        #print "decompress time: %.2f" % (time.time()-t)
        #t = time.time()
        p.feed(response)
        rest = dc.flush()
        if rest: p.feed(rest)

    f.close()
    p.close()

        #print "parse time: %.2f" % (time.time()-t)
    return u.close()

To modify an XML-RPC server to handle gzip encoding the steps are similar.

1. Try and import zlib:

    try:
    import zlib
    except ImportError:
    zlib = None

2. In do_POST, check to see if gzip was sent as an encoding:

    try:
    accept_encoding = self.headers["accept-encoding"]
    if accept_encoding:
        accept_encoding = map(string.strip,
                  string.split(accept_encoding, ","))
    else:
        accept_encoding = []
    except KeyError:
    accept_encoding = []

3. Add appropriate tests later in do_POST to make sure you can and should
   send a gzip'd response.  The requirements are that zlib was imported and
   gzip was one of the encodings sent by the client.  I also avoid gzip'ing
   short responses.

    if (zlib is not None and
    "gzip" in accept_encoding and
    len(response) > 1000):
    self.send_header("Content-encoding", "x-gzip")
    response = zlib.compress(response)
    self.send_header("Content-length", "%d" % len(response))


Python Library Module Quick Reference

Python v1.5 Library Module Quick Reference

Extracted from the Python Library Reference Manual.

Updated: Wed, 13 Jan 1999 05:00:03 GMT

_
__builtin__ __main__
M
multifile | mailcap | marshal
mimetools | mimetypes | mailbox
mimify | math | md5
mpz
A
AL | audioop | array
al | anydbm | aifc
N
nntplib netrc
B
binascii | binhex | BaseHTTPServer
base64 | bisect | Bastion
O
os operator
C
cmath | crypt | cd
compileall | code | cStringIO
cmd | cPickle | copy_reg
calendar | copy | cgi
commands
P
pwd | pickle | popen2
parser | posixfile | posix
pprint | py_compile | posixpath
poplib
D
dis dbm dumbdbm
DEVICE
Q
quopri Queue
E
errno
R
rgbimg | random | rotor
regsub | rexec | resource
regex | re | rfc822
F
fileinput | fnmatch | fl
fcntl | FL | flp
fm | ftplib | formatter
S
sndhdr | signal | sunaudiodev
shutil | shlex | StringIO
struct | string | site
symbol | shelve | socket
select | sys | smtplib
sgmllib | syslog | stat
SocketServer
G
gzip | gdbm | gopherlib
glob | grp | getopt
gl | GL
T
time | types | token
tempfile | TERMIOS | termios
thread | threading | traceback
H
htmllib httplib
U
urllib | uu | user
urlparse | UserList | UserDict
I
imghdr | imp | imaplib
imageop | imgfile
W
whrandom whichdb
J
jpeg
X
xdrlib xmllib
K
keyword
Z
zlib
L
locale

Last Modified: Wed, 13 Jan 1999 05:00:03 GMT


Branch Execution Summary

Version: 2.1a1 (#227, Jan 21 2001, 22:47:48) [GCC egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)]
Date: Wed Jan 31 22:45:31 PST 2001

File % Coverage # Branches
Top
Modules
Objects
Parser
Python


Python Statement Coverage Testing

This directory contains a mirror of the Python CVS repository at SourceForge that is updated nightly. Each night the interpreter is recompiled using GCC with flags that enable C statement coverage and the standard regression test is run. The individual tests are then executed again using pytrace.

Summaries of both the C statement coverage and Python statement coverage are then generated and exposed as HTML source for convenient browsing:

  • C statement coverage summary
  • C branch execution summary
  • Python statement coverage summary
Skip Montanaro


Line Execution Summary

Date: Wed Jan 31 22:45:32 PST 2001

File % Coverage # Lines
Top
Modules
Objects
Parser
Python


Python Module Code Coverage

% coverage | file
16.00% | ./Lib/xml/sax/expatreader.py
28.07% | ./Lib/stat.py
32.47% | ./Lib/pprint.py
36.63% | ./Lib/urllib.py
36.92% | ./Lib/socket.py
36.97% | ./Lib/mimetools.py
40.26% | ./Lib/xml/dom/xml.dom.py
41.27% | ./Lib/random.py
41.63% | ./Lib/xml/dom/xml.dom.pulldom.py
43.28% | ./Lib/py_compile.py
44.93% | ./Lib/test/test.test_support.py
45.64% | ./Lib/ntpath.py
46.15% | ./Lib/os.py
47.80% | ./Lib/tempfile.py
49.09% | ./Lib/copy.py
50.00% | ./Lib/base64.py
50.00% | ./Lib/test/test_thread.py
52.97% | ./Lib/calendar.py
53.05% | ./Lib/pickle.py
54.09% | ./Lib/xml/sax/xml.sax.xmlreader.py
54.10% | ./Lib/xml/dom/xml.dom.minidom.py
54.51% | ./Lib/dospath.py
55.28% | ./Lib/UserString.py
55.46% | ./Lib/token.py
57.40% | ./Lib/zipfile.py
59.49% | ./Lib/linecache.py
60.39% | ./Lib/test/test_minidom.py
62.50% | ./Lib/test/test_pty.py
62.96% | ./Lib/copy_reg.py
63.19% | ./Lib/popen2.py
63.33% | ./Lib/xml/xml.py
63.64% | ./Lib/xml/sax/xml.sax.py
65.47% | ./Lib/binhex.py
65.52% | ./Lib/posixpath.py
65.95% | ./Lib/rfc822.py
66.91% | ./Lib/ConfigParser.py
67.43% | ./Lib/traceback.py
67.54% | ./Lib/codecs.py
68.04% | ./Lib/xml/sax/xml.sax._exceptions.py
68.09% | ./Lib/atexit.py
68.34% | ./Lib/StringIO.py
68.35% | ./Lib/xml/sax/sax.py
69.17% | ./Lib/cgi.py
69.57% | ./Lib/encodings/encodings.py
70.03% | ./Lib/locale.py
71.07% | ./Lib/xmllib.py
71.13% | ./Lib/xml/sax/sax._exceptions.py
71.84% | ./Lib/whrandom.py
72.09% | ./Lib/UserDict.py
73.93% | ./Lib/tokenize.py
76.81% | ./Lib/test/test_threadedtempfile.py
76.92% | ./Lib/sre_constants.py
78.05% | ./Lib/test/test_import.py
78.95% | ./Lib/gzip.py
79.03% | ./Lib/test/test_pwd.py
80.00% | ./Lib/re.py
80.66% | ./Lib/sre.py
81.25% | ./Lib/test/test_openpty.py
81.58% | ./Lib/test/test_dospath.py
82.03% | ./Lib/test/test_funcattrs.py
82.35% | ./Lib/test/test_sha.py
83.33% | ./Lib/test/test_compile.py
83.33% | ./Lib/test/test_userstring.py
83.61% | ./Lib/getopt.py
84.21% | ./Lib/test/test_mailbox.py
84.88% | ./Lib/UserList.py
85.00% | ./Lib/test/test_imageop.py
86.03% | ./Lib/test/test_audioop.py
86.24% | ./Lib/test/test_strftime.py
86.84% | ./Lib/test/test_bufio.py
86.96% | ./Lib/test/test_socket.py
87.37% | ./Lib/xml/sax/sax.handler.py
87.37% | ./Lib/xml/sax/xml.sax.handler.py
87.50% | ./Lib/test/test_rgbimg.py
87.50% | ./Lib/test/test_time.py
87.67% | ./Lib/test/test_support.py
87.75% | ./Lib/gettext.py
87.88% | ./Lib/test/test_xreadline.py
88.24% | ./Lib/test/test_mimetools.py
88.62% | ./Lib/test/test_contains.py
88.68% | ./Lib/test/test_select.py
88.89% | ./Lib/test/test_string.py
89.29% | ./Lib/test/test_copy_reg.py
89.47% | ./Lib/test/test_rfc822.py
89.74% | ./Lib/test/test_gdbm.py
90.00% | ./Lib/test/test_grp.py
90.00% | ./Lib/test/test_hash.py
90.10% | ./Lib/MimeWriter.py
90.18% | ./Lib/string.py
90.91% | ./Lib/test/test_rotor.py
91.26% | ./Lib/test/test_struct.py
91.58% | ./Lib/test/test_long.py
91.60% | ./Lib/test/test_unpack.py
91.71% | ./Lib/sre_compile.py
92.06% | ./Lib/test/test_operator.py
92.20% | ./Lib/test/test_b2.py
92.23% | ./Lib/test/test_richcmp.py
92.31% | ./Lib/test/test_binhex.py
92.75% | ./Lib/test/test_fork1.py
93.10% | ./Lib/test/test_fcntl.py
93.62% | ./Lib/test/test_file.py
93.65% | ./Lib/test/test_popen2.py
93.75% | ./Lib/test/test_charmapcodec.py
93.87% | ./Lib/sre_parse.py
94.12% | ./Lib/test/test_operations.py
94.23% | ./Lib/test/test_urlparse.py
94.34% | ./Lib/test/test_signal.py
94.49% | ./Lib/test/test_zlib.py
94.55% | ./Lib/test/test_regex.py
94.59% | ./Lib/test/test_opcodes.py
94.67% | ./Lib/test/test_array.py
94.69% | ./Lib/test/test_pow.py
95.24% | ./Lib/test/test_xmllib.py
95.41% | ./Lib/test/test_ucn.py
95.51% | ./Lib/test/test_binascii.py
95.52% | ./Lib/test/test_types.py
95.65% | ./Lib/test/test_md5.py
95.73% | ./Lib/test/test_bisect.py
95.83% | ./Lib/test/test_strop.py
96.02% | ./Lib/test/test_format.py
96.20% | ./Lib/test/test_cfgparser.py
96.43% | ./Lib/test/test_wave.py
96.95% | ./Lib/test/test_poll.py
97.37% | ./Lib/test/test_userdict.py
97.44% | ./Lib/test/test_compare.py
97.47% | ./Lib/test/test_math.py
97.96% | ./Lib/test/test_ntpath.py
98.28% | ./Lib/encodings/encodings.iso8859_3.py
98.30% | ./Lib/test/test_pkg.py
98.38% | ./Lib/test/test_sre.py
98.82% | ./Lib/test/test_coercion.py
98.88% | ./Lib/test/test_userlist.py
98.89% | ./Lib/test/test_urllib.py
98.90% | ./Lib/encodings/encodings.iso8859_8.py
98.90% | ./Lib/test/test_cgi.py
98.90% | ./Lib/test/test_getopt.py
99.00% | ./Lib/test/test_parser.py
99.03% | ./Lib/encodings/encodings.iso8859_7.py
99.14% | ./Lib/encodings/encodings.iso8859_6.py
99.15% | ./Lib/test/test_mmap.py
99.24% | ./Lib/test/test_unicode.py
99.28% | ./Lib/test/test_exceptions.py
100.00% | ./Lib/encodings/encodings.aliases.py
100.00% | ./Lib/encodings/encodings.ascii.py
100.00% | ./Lib/encodings/encodings.cp037.py
100.00% | ./Lib/encodings/encodings.cp1006.py
100.00% | ./Lib/encodings/encodings.cp1026.py
100.00% | ./Lib/encodings/encodings.cp1250.py
100.00% | ./Lib/encodings/encodings.cp1251.py
100.00% | ./Lib/encodings/encodings.cp1252.py
100.00% | ./Lib/encodings/encodings.cp1253.py
100.00% | ./Lib/encodings/encodings.cp1254.py
100.00% | ./Lib/encodings/encodings.cp1255.py
100.00% | ./Lib/encodings/encodings.cp1256.py
100.00% | ./Lib/encodings/encodings.cp1257.py
100.00% | ./Lib/encodings/encodings.cp1258.py
100.00% | ./Lib/encodings/encodings.cp437.py
100.00% | ./Lib/encodings/encodings.cp500.py
100.00% | ./Lib/encodings/encodings.cp737.py
100.00% | ./Lib/encodings/encodings.cp775.py
100.00% | ./Lib/encodings/encodings.cp850.py
100.00% | ./Lib/encodings/encodings.cp852.py
100.00% | ./Lib/encodings/encodings.cp855.py
100.00% | ./Lib/encodings/encodings.cp856.py
100.00% | ./Lib/encodings/encodings.cp857.py
100.00% | ./Lib/encodings/encodings.cp860.py
100.00% | ./Lib/encodings/encodings.cp861.py
100.00% | ./Lib/encodings/encodings.cp862.py
100.00% | ./Lib/encodings/encodings.cp863.py
100.00% | ./Lib/encodings/encodings.cp864.py
100.00% | ./Lib/encodings/encodings.cp865.py
100.00% | ./Lib/encodings/encodings.cp866.py
100.00% | ./Lib/encodings/encodings.cp869.py
100.00% | ./Lib/encodings/encodings.cp874.py
100.00% | ./Lib/encodings/encodings.cp875.py
100.00% | ./Lib/encodings/encodings.iso8859_10.py
100.00% | ./Lib/encodings/encodings.iso8859_13.py
100.00% | ./Lib/encodings/encodings.iso8859_14.py
100.00% | ./Lib/encodings/encodings.iso8859_15.py
100.00% | ./Lib/encodings/encodings.iso8859_2.py
100.00% | ./Lib/encodings/encodings.iso8859_4.py
100.00% | ./Lib/encodings/encodings.iso8859_5.py
100.00% | ./Lib/encodings/encodings.iso8859_9.py
100.00% | ./Lib/encodings/encodings.koi8_r.py
100.00% | ./Lib/encodings/encodings.latin_1.py
100.00% | ./Lib/encodings/encodings.mac_cyrillic.py
100.00% | ./Lib/encodings/encodings.mac_greek.py
100.00% | ./Lib/encodings/encodings.mac_iceland.py
100.00% | ./Lib/encodings/encodings.mac_latin2.py
100.00% | ./Lib/encodings/encodings.mac_roman.py
100.00% | ./Lib/encodings/encodings.mac_turkish.py
100.00% | ./Lib/encodings/encodings.raw_unicode_escape.py
100.00% | ./Lib/encodings/encodings.unicode_escape.py
100.00% | ./Lib/encodings/encodings.unicode_internal.py
100.00% | ./Lib/encodings/encodings.utf_16.py
100.00% | ./Lib/encodings/encodings.utf_16_be.py
100.00% | ./Lib/encodings/encodings.utf_16_le.py
100.00% | ./Lib/encodings/encodings.utf_8.py
100.00% | ./Lib/plat-linux2/FCNTL.py
100.00% | ./Lib/regex_syntax.py
100.00% | ./Lib/test/regex_tests.py
100.00% | ./Lib/test/string_tests.py
100.00% | ./Lib/test/test.py
100.00% | ./Lib/test/test_MimeWriter.py
100.00% | ./Lib/test/test_StringIO.py
100.00% | ./Lib/test/test_atexit.py
100.00% | ./Lib/test/test_augassign.py
100.00% | ./Lib/test/test_bastion.py
100.00% | ./Lib/test/test_cmath.py
100.00% | ./Lib/test/test_crypt.py
100.00% | ./Lib/test/test_dumbdbm.py
100.00% | ./Lib/test/test_errno.py
100.00% | ./Lib/test/test_extcall.py
100.00% | ./Lib/test/test_gettext.py
100.00% | ./Lib/test/test_gzip.py
100.00% | ./Lib/test/test_longexp.py
100.00% | ./Lib/test/test_posixpath.py
100.00% | ./Lib/test/test_timing.py
100.00% | ./Lib/test/test_tokenize.py
100.00% | ./Lib/test/test_unicodedata.py
100.00% | ./Lib/test/test_zipfile.py
100.00% | ./Lib/test/testcodec.py
100.00% | ./Lib/xml/parsers/xml.parsers.expat.py
100.00% | ./Lib/xml/parsers/xml.parsers.py

The following Python files were not exercised at all by the tests:

Lib: BaseHTTPServer.py, Bastion.py, CGIHTTPServer.py, ConfigParser.py, Cookie.py, MimeWriter.py, Queue.py, SimpleHTTPServer.py, SocketServer.py, StringIO.py, UserDict.py, UserList.py, UserString.py, aifc.py, anydbm.py, asynchat.py, asyncore.py, atexit.py, audiodev.py, base64.py, bdb.py, binhex.py, bisect.py, calendar.py, cgi.py, chunk.py, cmd.py, code.py, codecs.py, codeop.py, colorsys.py, commands.py, compileall.py, copy.py, copy_reg.py, dbhash.py, dircache.py, dis.py, doctest.py, dospath.py, dumbdbm.py, filecmp.py, fileinput.py, fnmatch.py, formatter.py, fpformat.py, ftplib.py, getopt.py, getpass.py, gettext.py, glob.py, gopherlib.py, gzip.py, htmlentitydefs.py, htmllib.py, httplib.py, ihooks.py, imaplib.py, imghdr.py, imputil.py, keyword.py, knee.py, linecache.py, locale.py, macpath.py, macurl2path.py, mailbox.py, mailcap.py, mhlib.py, mimetools.py, mimetypes.py, mimify.py, multifile.py, mutex.py, netrc.py, nntplib.py, ntpath.py, nturl2path.py, os.py, pdb.py, pickle.py, pipes.py, popen2.py, poplib.py, posixfile.py, posixpath.py, pprint.py, pre.py, profile.py, pstats.py, pty.py, py_compile.py, pyclbr.py, quopri.py, random.py, re.py, reconvert.py, regex_syntax.py, regsub.py, repr.py, rexec.py, rfc822.py, rlcompleter.py, robotparser.py, sched.py, sgmllib.py, shelve.py, shlex.py, shutil.py, site.py, smtpd.py, smtplib.py, sndhdr.py, socket.py, sre.py, sre_compile.py, sre_constants.py, sre_parse.py, stat.py, statcache.py, statvfs.py, string.py, stringold.py, sunau.py, sunaudio.py, symbol.py, tabnanny.py, telnetlib.py, tempfile.py, threading.py, toaiff.py, token.py, tokenize.py, traceback.py, tty.py, types.py, tzparse.py, urllib.py, urllib2.py, urlparse.py, user.py, uu.py, warnings.py, wave.py, weakref.py, webbrowser.py, whichdb.py, whrandom.py, xdrlib.py, xmllib.py, zipfile.py
Lib/curses: ascii.py, has_key.py, panel.py, textpad.py, wrapper.py
Lib/xml/dom: minidom.py, pulldom.py
Lib/xml/parsers: expat.py
Lib/xml/sax: _exceptions.py, expatreader.py, handler.py, saxutils.py, xmlreader.py


Branch Execution Summary

Date: Wed Jan 31 22:45:32 PST 2001

File % Coverage # Branches
Modules


Line Execution Summary

Date: Wed Jan 31 22:45:32 PST 2001

File % Coverage # Lines
Modules


Branch Execution Summary

Date: Wed Jan 31 22:45:32 PST 2001

File % Coverage # Branches
Objects


Line Execution Summary

Date: Wed Jan 31 22:45:32 PST 2001

File % Coverage # Lines
Objects


Branch Execution Summary

Date: Wed Jan 31 22:45:32 PST 2001

File % Coverage # Branches
Parser


Line Execution Summary

Date: Wed Jan 31 22:45:32 PST 2001

File % Coverage # Lines
Parser


Branch Execution Summary

Date: Wed Jan 31 22:45:32 PST 2001

File % Coverage # Branches
Python


Line Execution Summary

Date: Wed Jan 31 22:45:32 PST 2001

File % Coverage # Lines
Python


Integrating Python and C++

 I've been around a couple times (well, maybe one and a half times) when it comes to integrating C++ with an interpreted very high-level language (VHLL). In here I discuss some of the experiences I've had and the problems I've encountered in hopes that it will stimulate discussion during the Interfacing to C++ and inheriting built-in types session at the Python workshop.

Background

While at GE's R&D Center, I worked on a VHLL called LYMB. Python and LYMB have very similar architectures: a high-level interpreted language used for application development, with much of the underlying system implemented in C. The major differences between LYMB and Python are the language syntax and where most classes are implemented (in C versus the VHLL).

Several significant applications were developed in LYMB, including a scientific visualization tool called VISAGE (VISualization And Graphics Environment)[1]. The ability to easily modify the application (even on-the-fly), create new combinations of visualization operators and new user interface subsystems convinced us that this was the way to go.

Customers asked about C++ again and again (even though most of them weren't using it and many had no immediate plans - it was just "the next thing"). They worried about our mechanisms for creating classes in C (which aren't all that different from what C++ does, but simpler). We finally got a customer who said, "We use C++, and we'll fund some development".

We did some C++ integration work at GE CRD that convinced me this was a fruitful path, especially after I saw how cumbersome programming in C++ could be at times. Getting LYMB away from GE was like rescuing Jonah from the whale, however, so I let the whale have Jonah and submitted an SBIR proposal to the NSF to look at the problem.

The original plan was to write a new VHLL to front C++ that would be well-integrated with it, but a better application development language. Quite frankly, I was a bit worried about designing and implementing a new language and trying to get it accepted by the community. Then I discovered Python.

Evaluating Python

I fiddled around with Python for a little bit. Classes were written in Python, not C like in LYMB. This is better from an application development perspective, since you'd like to be able to use the same organizational approach for the application as a whole as you use for the application's underpinnings. (LYMB does have a metaclass class, which allows classes to be developed in the LYMB scripting language, but it's implementation is not as clean as Python's class mechanism.) Namespaces are no problem in Python. LYMB has no construct similar to Python's module. Internally, it looked pretty similar to LYMB, with which I was quite familiar. It even had multiple inheritance. (One of the LYMB/C++ problems was mapping C++'s multiple inheritance model onto LYMB's single inheritance model.) "By George!", I thought. "This might actually work!"

First Steps

Once I chose Python as my VHLL (conceptually creating Python++), I had to actually implement something. The goal of the research is to see how much of the conversion we can do automatically, where we can't, and how we can get over those places. My first task was to generate an interface manually to a couple of simple classes. I chose the RNG and MLCG classes in the Free Software Foundation's libg++ class library. They had a number of interesting traits:
  • Both classes were small, so manual coding wouldn't take forever.
  • All visible parameter and return value types were simple (int, float, double).
  • Inheritance had to be dealt with (RNG is the base class for MLCG).
After converting RNG and MLCG manually and seeing that the Python versions behaved as expected, I decided it was time to try automating the process. So I started hacking some Python. I first wrote a tokenizer class (nominally written in Python, but mostly sed and cpp). Next came a simple class parser. Finally, an interface generator.

For the prototype, the basic approach was to implement a C module for each class, and worry about proper subclassing in a later phase. The code for the MLCG module shows the result. Each module keeps a pointer to the C++ object as a private variable, a pointer to its type (for type checking), and a flag indicating if this module is the "owner" of the pointer.

    typedef struct _CPPobject {
        OB_HEAD
        void *__cpp_inst__;
        typeobject *__type__;
        int __iown__;
    } CPPobject;

Learning to Walk

At this stage, I knew I could convert simple classes, but there were several tasks I hadn't yet approached and would have to get some experience with. I chose a significantly more complex set of classes for my next experiment and began refining my hacked together module generator. I chose the a set of about 200 classes written by some friends as demo software for a book they are working on. I took one of their simpler demo programs and tried wrapping just the classes used in the application. That worked okay, expect for two problems. First, there were some constructs my generator couldn't handle, which I expected to find. Second, there were some classes behind the scenes (base classes and such) that my software assumed were wrapped. The first wasn't so bad, because for the prototype I was resolved to to some manual fix-up. The second problem was bigger. I added the half dozen or so unwrapped classes to the list of classes to interface and turned the crank again. Hmmm, there are some more undefined modules. One more time... By the time I grew tired of this exercise, I needed to generate interfaces to a very large part of the entire library. That manual fix-up problem suddenly got a whole lot bigger.

Any sane person would have gone back to square one and figured out a way to not wrap that first set of "indirect" classes. Instead, I decided to tackle the interface problems that could not be handled by my existing interface generator. Here are some of the problems I faced.

Compound arguments
Passing a pointer and a count as two separate arguments often serves as a poor man's vector in C. In mapping Python arguments into C++ and back, I encountered this several times.
Pointers in general
Pointers raise several problems:
  • Who allocated them?
  • Who should delete them?
  • What do they point to, and how much of that has to be mapped between Python & C++)?
  • What about function pointers?
  • What about pointers masquerading as vectors?
Overloaded operators
It's difficult to see how more than a few operators will map into Python. Somewhere along the way, I think C++ programmers will have to realize that their code might get used outside a C++ environment and make sure full class functionality is implemented without operators. Punt.
Templates
A primary motivation for templates in C++ is to implement type-safe container classes[2]. To paraphrase Humphrey Bogart, "We don't need no steenking collections." Besides, since templates are a compile-time mechanism, it's difficult to see how they could be integrated cleanly into a run-time facility. Eventually something will probably have to be done, but for now we punt.
Saving information
Somehow, you have to tell the interface generator how to handle constructs for which it has incomplete information. You'd like to only have to give that information once. For the first prototype I used Emacs and the Patch program, but that won't work forever.
True Subclassing
I think this can be handled with two small changes to Python's internals. One, the mechanism for implementing classes by the interpreter needs to be formally exposed to the C programmer. Two, we need to create a C++ analogue of Python's classobject which, coupled with the external C++ class of interest, serves as a foundation for a class the interface generator generates. Because of the properties inherited from its parents, it should be possible to derive new classes from it in Python.
Code Length
The current method of repeated inline calls to getarg() and err_clear() was straightforward to implement, but if there are many versions of an overloaded function, the code necessary to implement it gets rather large (and potentially slow if calling getarg() is expensive). It would be nice if there was some sort of table-driven mechanism available to identify exactly which version of the function should be called.

When Do We Get to Run?

For my work there is still the minor problem of securing follow-on funding, but presuming that is successful, I have a number of ideas about how to solve the above problems. Presuming they prove tractable (and I think they will), there are more problems I haven't yet considered, some technical and some more marketing:
  • How do we get Python++ accepted in the programming community at large?
  • How about programming support?
  • Can you create a debugger that seamlessly crosses the boundary between Python and C++?
I'm sure there are others. My hope is we can unearth the major ones during the workshop and perhaps establish strategies for addressing them.

Slides

There are PostScript versions of the couple of slides I will toss on the projector at the workshop available as well. They are:
  • I'm Working on C++/Python Integration
  • Motivating C++/Python Integration
  • What are some hurdles to integration?

References

1. W. J. Schroeder, W. E. Lorensen, G. D. Montanaro, and C. Volpe. VISAGE: An Object-Oriented Scientific Visualization System. In Proceedings of the Visualization '92 Conference, pp. 219-225, 1992.

2. Bjarne Stroustrup. The C++ Programming Language. Addison-Wesley, 1991.

Skip Montanaro
Email: skip@automatrix.com


% ./python
Python 1.0.2 (May  9 1994)
Copyright 1991-1994 Stichting Mathematisch Centrum, Amsterdam
>>> from mlcg import MLCG           ## import "new" method into local scope
>>> ran = MLCG()                    ## create a random number generator
>>> i = ran.asLong() % 100          ## use it
>>> i
72
>>> i = ran.asLong() % 100          ## use it again
>>> i
14
>>> ran.reseed(45, 99)              ## set its seeds to known values
>>> ran.asLong()                    ## play around a little bit more
967208681
>>> ran.asLong()
1103973908
>>>


A Peephole Optimizer for Python

Skip Montanaro
Automatrix, Inc.
Rexford, NY

Abstract

This paper describes the implementation of a peephole optimizer for Python byte codes. Python's byte code compiler currently generates code that can easily be improved. The peephole optimizer implemented presented here implements a number of common optimizations, including jump chaining, constant expression evaluation and elimination of unecessary loads. Some optimizations rely on specific properties of Python or its virtual machine. Some optimizations common to statically typed languages, such as algebraic simplification and expression rearrangement, are prevented by Python's dynamic typing. Preliminary results obtained using pybench [Lemb] suggest that the optimizer has a positive benefit for specific operations. With the current measurement tools available however, it is difficult to quantify benefits that can be derived by using the optimizer. Situations in which the benchmarks may not yield reliable results are considered. The limitations Python places on the optimizer are discussed, especially restrictions caused by the dynamic nature of the language. Other performance improvements to the Python interpreter are discussed briefly.

Introduction

Python code is compiled to a high-level virtual machine in a straightforward fashion. We should be able to apply a peephole optimizer to the code to improve performance. This paper investigates an experimental peephole optimizer written in Python which is integrated with the existing byte compiler.

In general, a peephole optimizer searches for patterns of opcodes that can be replaced by more efficient ones. Peephole optimization works because it can "see" more of the instruction stream at once than the compiler can during code generation. For instance, the simple

x = hairy_calc()
y = x + 15
would generate a store into x followed by an immediate load from x. The compiler wouldn't know to make a copy of the function value on the stack before storing it in x because it hasn't yet seen the statement after the one it is compiling. A peephole optimizer will see a very simple pattern:
STORE x
LOAD x
which it can replace with:
DUP_TOP
STORE x
(A notation similar to that generated by the Python disassembler is used in this paper. Labels and statement addresses are omitted and variable references are simplified.)

Two obvious optimizations are implemented by the byte code compiler itself. When Python is run with the -O flag, SET_LINENO opcodes and code to implement assert statements are not generated. There is much more that can be done, however. Some common constructs such as tuple assignments, while convenient for the programmer

a,b,c = 1,2,3
yield inefficient code which can easily be improved.

Peephole optimization of Python byte code is performed by the xfreeze module [Tutt], a contributed enhancement of the freeze module available from the Python Software Association's web site [PSA]. Several of the optimizations implemented here were derived from those found in xfreeze. Unfortunately, xfreeze is a specialized program mixing two purposes: optimizing byte code and binding a Python interpreter and a set of associated modules into a single monolithic executable. The relative rarity of the latter task means the optimizations it performs get little use.

Byte Code Interpreter

Python code is compiled into virtual machine code, that is, code that defines a computer that is not realized in hardware, but is executed at run-time by a byte code interpreter. Python's virtual machine is stack-oriented. With one exception, all instructions operate on the top one to three Python objects on the stack or transfer objects between the stack and fixed locations (representing local or global variables).

The main portion of the interpreter is implemented in the eval_code2 function in ceval.c. A large switch statement is used to decode and execute individual instructions:

switch (opcode) {
    case POP_TOP:
        ...
        continue;

    case ROT_TWO:
        ...
        continue;
    ...
    case BINARY_MULTIPLY:
        ...
        break;
    ...
}

There are several different ways to improve the performance of Python programs. Some of the most obvious ones are:

Optimize the Python code.
Straightforward reorganization of Python code, replacing less efficient algorithms with more efficient ones, reimplimenting some critical code in extension modules or rearchitecting the application altogether can have dramatic effects on the program's performance. In this regard Python is no different than most other programming languages.
Improve the efficiency of the interpreter itself.
The C code that implements the interpreter has been improved dramatically, and it can be made still more efficient. If the interpreter can make assumptions about the properties of some objects, some of the underlying functions the interpreter relies on can also be improved, or replaced altogether with versions that avoid needless error checks and thus streamline their execution.
Improve the sequence of instructions executed.
The peephole optimizer described here is one example of this. It works by matching fairly straightforward patterns of instructions and replacing them with faster, though equivalent, sequences. Much more sophisticated optimizations are possible as well, as has been demonstrated by Chambers for Self [Cham].
Change the architecture of the virtual machine.
Identifying special case instructions, such as integer loads or instructions that resolve dotted names (e.g., string.join) in one instruction instead of two can improve the performance of the system. Changing the underlying architecture - by adding registers to the architecture, for instance - can improve performance. For instance, adding registers to the virtual machine and implementing a decent register allocation scheme has the potential to reduce data movement within the virtual machine significantly.
Replace the interpreter altogether.
JPython replaces the Python virtual machine with the Java virtual machine. While this was not done necessarily for performance reasons, increased performance may result as JVM technology continues to improve. Python-to-C converters also fall into this category.

Architecture

The peephole optimizer [Mon1] is organized as a set of Python classes. Each class is a subclass of the OptimizeFilter base class, specialized for applying a single optimization. An entire optimizer is built by chaining several optimizers together in a pipeline. OptimizeFilter instances accept either a code object or another OptimizeFilter instance as input, as well as optional lists of local variable names, values, and constants. The optimize method breaks up the code into basic blocks, then calls optimize_block for each basic block, replacing it with the return value of the call.

def optimize(self):
    blocks = self.input
    self.output = [None]*len(blocks)
    for i in range(len(blocks)):
        self.output[i] = self.optimize_block(blocks[i])
For the purposes of this work, a basic block is a straight section of code whose only entry point is the first instruction in the block. This differs slight from that used by Aho, et. al. [Aho], who further constrain basic blocks to have only one exit point. While the current definition isn't strictly incorrect, it may not expose as many opportunities for optimizations as Aho's does.

In most cases, OptimizeFilter subclasses need only implement an optimize_block method. One optimizer class (JumpNextEliminator) overrides the optimize method however, because it looks across basic block boundaries.

The optimizer is invoked by the byte code compiler if run-time optimization has been selected with the -O flag and the optimize module can be located and imported. An alternative implementation would be to post-process .pyc files, emitting .pyo files as a result. This was not considered because it would require reliance of the optimizer on the new module to generate new code objects which is not built into the Python executable by default.

Chaining individual optimizer instances into a pipeline allows large optimizers to be constructed easily. It is easy to plug new optimizer instances into the pipeline at the appropriate point(s). The main optimization function is:

def optimize5(code, v=None, n=None, c=None):
    lsc = LoadStoreCompressor(code, v, n, c)
    sle = StoreLoadEliminator(lsc, v, n, c)
    lnr = LineNumberRemover(sle, v, n, c)
    ...
    jne2 = JumpNextEliminator(dcr2, v, n, c)
    jpo2 = JumpOptimizer(jne2, v, n, c)
    return jpo2.code()
Note that each optimizer instance except the first takes another optimizer instance as input. The first optimizer step, the LoadStoreCompressor instance, takes the byte code string as input.

Several new instructions were added to the Python virtual machine. The LOADI instruction uses the small_ints cache maintained in intobject.c to speed up loading of small positive integers. LOAD_TWO_FAST and STORE_TWO_FAST encode two arguments to load in their 16-bit arguments. LOAD_ATTR_FAST and STORE_ATTR_FAST encode a local argument reference and an attribute name reference in their 16-bit arguments.

In the paragraphs that follow, each of the optimization classes currently implemented is described briefly, with examples, where appropriate, of the specific optimizations they perform.

TupleRearranger

This class optimizes Python code like

a,b,c = 1,2,3
into the byte code equivalent of
c = 3
b = 2
a = 1
avoiding the overhead of building and unpacking a tuple. This is an obvious pattern likely to appear in Python byte code, but less likely to occur in languages without similar operations. The execution order of the right-hand side of the statement is not affected. The assignment to the variables on the left-hand side is optimized, however. The above assignment statement generates a sequence of instructions that look like
LOAD_CONST   1
LOAD_CONST   2
LOAD_CONST   3
BUILD_TUPLE  3
UNPACK_TUPLE 3
STORE_FAST   a
STORE_FAST   b
STORE_FAST   c

The net effect of the BUILD_TUPLE/UNPACK_TUPLE pair is simply to reverse the order of the three values on the top of the stack. Instead of reversing the order of the operands, it's simpler to reverse the order of the assignments:

LOAD_CONST   1
LOAD_CONST   2
LOAD_CONST   3
STORE_FAST   c
STORE_FAST   b
STORE_FAST   a
and avoid tuple creation and deletion altogether.

This optimization is not applied in all cases. If the UNPACK_TUPLE instruction is not followed immediately by at lest the same number of simple stores (stores to individual global or local variables) to unique variables, the optimization is not performed. Transforming

LOAD_CONST   1
LOAD_CONST   2
LOAD_CONST   3
BUILD_TUPLE  3
UNPACK_TUPLE 3
STORE_FAST   a
STORE_FAST   b
STORE_FAST   b
into
LOAD_CONST   1
LOAD_CONST   2
LOAD_CONST   3
STORE_FAST   b
STORE_FAST   b
STORE_FAST   a
is incorrect, because b has the value 3 after executing the first sequence, but 2 after executing the second sequence.

ConstantExpressionEvaluator

This class precomputes a number of constant expressions and stores them in the function's constants list, including obvious binary and unary operations and tuples consisting of just constants. Of particular note is the fact that complex literals are not represented by the compiler as constants but as expressions, so 2+3j appears as

LOAD_CONST n (2)
LOAD_CONST m (3j)
BINARY_ADD

This class converts those to

LOAD_CONST q (2+3j)
which can result in a fairly large performance boost for code that uses complex constants. In general Python code this optimizations is probably not as useful as in languages like C that make heavy use of macro processors to define manifest constants.

UnreachableCodeRemover

This class deletes all instructions in a basic block that follow an unconditional transfer. It does not improve the performance of the program directly, though by eliminating unused code it can sometimes clear the way for further optimizations.

LoadStoreCompressor

This class performs two similar optimizations. It replaces pairs of LOAD_FAST or STORE_FAST instructions with single LOAD_TWO_FAST or STORE_TWO_FAST instructions, respectively. It also replaces the sequences LOAD_FAST/LOAD_ATTR or LOAD_FAST/STORE_ATTR with LOAD_FAST_ATTR or STORE_FAST_ATTR opcodes, respectively. The LOAD_FAST_ATTR and STORE_FAST_ATTR instructions seem to speed up attribute lookup, but it's not clear that the LOAD_TWO_FAST and STORE_TWO_FAST opcodes result in much of a performance improvement (they do save a trip around the interpreter loop), and they further complicate downstream optimizations by increasing the number of different types of load or store instructions that must be considered by later optimization classes. For this reason this optimizer is currently executed late in the pipeline. It should probably be split into two separate classes.

MultiLoadEliminator

This class converts n consecutive loads of the same object to a single load and n-1 DUP_TOP opcodes.

StoreLoadEliminator

This class converts a store to an object then a load of the same object into a DUP_TOP followed by a store. This construct occurs frequently in code that saves an expensive-to-compute quantity then reuses it:

foo = spam = some_hairy_function(...)
bar = foo * math.sin(math.pi/3)
baz = aunt_mabel * foo
This class currently eliminates the first load of foo but not the second.

JumpNextEliminator

This class eliminates an unconditional jump to the following basic block if it is the last opcode in its basic block.

JumpOptimizer

This class traverses a chain of n jumps, short-circuiting the second through n-th jumps if they are unconditional.

ConstantShortcut

This class converts LOAD_CONST instructions for None or small positive integers to LOAD_NONE or LOADI instructions, respectively. LOAD_NONE short-circuits the constant lookup of Py_None. LOADI uses the small_ints cache in intobject.c to avoid looking up small positive integer constants. Both optimizations are useful because they reduce a series of memory references of the form

(PyTupleObject *)(f->f_code->co_consts)->ob_item[i]

where f is the current frame, to either small_ints[i] or Py_None.

Generation of LOADI instructions is a bit fragile, since it relies on the size of the small_ints cache in intobject.c being the same when the optimizer is run as when the actual byte codes are executed later. A more general approach to efficient access of a function's constants would be to create a fastconstants variable in eval_code2, similar to the fastlocals variable already used to speed up access to local variables.

Branches Not Taken

At first glance, a number of other code transformations seem possible. It would be nice to rearrange expressions using the algebraic properties of numbers, but this can't be done because although an object implements a particular operation, it's not required to implement the usual semantics associated with the operation on numbers, and with no side-effects. For instance, consider the expression

l + a + l
This compiles to
LOAD l
LOAD a
BINARY_ADD
LOAD l
BINARY_ADD
If l and a are numbers the expression can be rearranged to avoid a load
LOAD l
DUP_TOP
BINARY_ADD
LOAD a
BINARY_ADD
but not if l and a are strings.

This problem applies to strength reduction as well. If we know we are dealing with integers or floating point numbers the following statement

a = a ** 2
can be sped up by recasting it as
a = a * a

since multiplication is faster than exponentiation. The optimizer doesn't know that a is a number, however. (There may be some situations where it can be inferred a is an int or float object, though this is currently not possible in the general case.)

If the view of the code being optimized is expanded beyond the realm of basic blocks, other optimizations are possible. Dead code elimination identifies variables that are set but not used and eliminates them. Cross jumping merges the code common to the tail end of two basic blocks whose sole successor is the same block. The following code segments demonstrate cross jumping:

if type(a) == types.ComplexType:
    x = cmath.sin(a)
    foo(x)
else:
    x = math.sin(a)
    foo(x)

if type(a) == types.ComplexType:
    x = cmath.sin(a)
else:
    x = math.sin(a)
foo(x)

Stack pollution (deferred stack cleanup) could be performed if we added a POP n instruction to the virtual machine. Stack pollution saves stack cleanup until it's required. For instance, the following code

f(10)
g(20)
compiles to
LOADI 10
LOAD f
CALL_FUNCTION 1
POP_TOP
LOADI 20
LOAD g
CALL_FUNCTION 1
POP_TOP
The first POP could be deferred:
LOADI 10
LOAD f
CALL_FUNCTION 1
LOADI 20
LOAD g
CALL_FUNCTION 1
POP 2

This requires analysis to determine that elements on the stack below the return value of f(10) are not needed before the call to g(20) returns.

Results

All performance tests were run on a machine with the following configuration:

100MHz Pentium, 64MB main memory
RedHat Linux 5.0
EGCS 1.0.3 compiler
Python 1.5.1
pybench 0.6

Python was configured using "--with-threads". The interpreter was compiled using the -O2 flag of EGCS. While this does not represent the maximum optimization possible, it is perhaps the most common optimization level used. The benchmark was run four times, twice with the peephole optimizer disabled, and twice with it enabled. Between pairs of runs all .pyo and .pyc files were deleted. Only the results of the second run of each pair were used to minimize the effect of executing the optimizer (which is itself rather slow) on the benchmark results. Python was run with the -S and -O flags and the PYTHONPATH and PYTHONSTARTUP environment variables were not set.

Table 1 shows the results of the benchmark tests. The numbers represent the per cent reduction (negative values) or increase (positive values) in execution time for the optimized versus unoptimized runs.

Table 1. The effect of applying the peephole optimizer
Test | % diff | Test | % diff
Builtin Function Calls | -2.51% | Second Import | +1.37%
Builtin Method Lookup | -11.95% | Second Package Import | +1.63%
Comparisons | +2.06% | Second Submodule Import | +0.50%
Concat Strings | -7.34% | Simple Complex Arithmetic | -14.68%
Create Instances | -0.01% | Simple Dict Manipulation | -4.24%
Create Strings With Concat | -12.30% | Simple Float Arithmetic | +3.85%
Dict Creation | -5.01% | Simple Int Float Arithmetic | +1.55%
For Loops | -5.46% | Simple Integer Arithmetic | -0.74%
If Then Else | -3.52% | Simple List Manipulation | -8.07%
List Slicing | -0.34% | Simple Long Arithmetic | -7.83%
Nested For Loops | -0.97% | Small Lists | -7.11%
Normal Class Attribute | -20.64% | Small Tuples | -3.74%
Normal Instance Attribute | +3.84% | Special Class Attribute | -23.11%
PPrint | -1.88% | Special Instance Attribute | +1.65%
Pickler | +0.31% | String Slicing | -9.55%
Python Function Calls | +0.81% | Try Except | +0.67%
Python Method Calls | -2.72% | Try Raise Except | -2.33%
Random | +4.32% | Tuple Slicing | -6.39%
Recursion | +7.30%

The most obvious result is that there are a few tests that show very large improvements, a few that show moderate improvements, but none that apparently suffer much from the changes. Why this might be the case is discussed in the discussion below.

Discussion

Interpreting the Benchmark Results

This work shows that under the right circumstances, peephole optimization can yield significant performance gains. Measuring those gains is currently rather difficult, however, partly because they are generally small, but also because the tools available to measure them are either crude (simple timings), they aren't yet well characterized (pybench) or they demonstrate an unrealistic mix of operations that makes extrapolation to real programs difficult (pystone and pybench). In addition, differences between compilers, optimization levels and the processors they target can mask improvements. The range of optimizations applied here is limited to patterns the author saw while scanning byte code or those suggested by others. It is likely that over time more optimizations will be suggested and that some of the current optimizations will be improved.

Tim Peters cautions against too great a reliance on measurements of individual optimizations [Pete]:

A good change should be made even if timing shows it slowing down on some combo; if the operation count has been reduced, the timing result is a fluke due to bad compiler or load-map luck that's probably specific to every detail of the combo in use, and that will go away by magic anyway.

This advice is particularly germane if the optimization has not been tested on multiple architectures, it is still in an early stage of development or the tools used to measure the change are not yet well understood. Performance will be affected by many factors, including processor architecture, the compiler, optimization level and cache size. It's best to make a full range of measurements before deciding whether or not to use the output of the optimizer.

Pybench contains a series of tests which each try to exercise a single operation. It is useful as an objective gauge for measuring changes to the Python interpreter where the byte code generated by the compiler is not modified and suggesting the general direction of those changes, however it must be understood that the code in the tests doesn't resemble typical code. Since the same operation is executed repeatedly, the peephole optimizer will tend to show no effect (when it couldn't improve the particular operation being tested) or a very dramatic positive effect (when it was able to optimize a particular sequence). As an example, consider the SpecialClassAttribute test in Lookups.py. It repeatedly executes statements like:

c.__a = 2
x = c.__a

where c is a class defined in the local scope and x is a local variable. The peephole optimizer make significant improvements in the code generated for these statements. First, constants will be loaded using the more efficient LOADI instruction instead of LOAD_CONST. Second, attribute stores and loads will be performed by either STORE_FAST_ATTR or LOAD_FAST_ATTR. Assignment to c.__a looks like

LOADI               2
STORE_ATTR_FAST     c, _SpecialClassAttribute__a
while assignment to x looks like
LOAD_ATTR_FAST      c, _SpecialClassAttribute__a
STORE_FAST          x
Contrast this with the unoptimized code
LOAD_CONST          3
LOAD_FAST           c
STORE_ATTR          _SpecialClassAttribute__b
and
LOAD_FAST           c
LOAD_ATTR           _SpecialClassAttribute__c
STORE_FAST          x

Only two-thirds as many instructions are executed per assignment, so even if they are individually no more efficient, the code speeds up significantly. The SimpleComplexArithmetic test falls prey to the same magnified result, but for a different reason. Complex constants are not stored as constants in the unoptimized case, but as a pair of loads followed by an add or a subtract. The optimizer precomputes these constant expressions and saves the constants for later reuse. While both tests demonstrate the positive effect of one or more of the optimizations, their magnitude has little direct bearing on what one could expect if the optimizer was applied to production code. Also, Python code optimizers improve they will probably progress to the point where much of the repeated code in pybench's tests is deleted, making them much less useful as tests of either the optimizer or improvements to the Python virtual machine.

Pybench might or might not test most commonly occurring operations, or may test them out of context. If so, the optimizer won't get the opportunity to strut its stuff. For instance, it doesn't currently test the TupleRearranger optimization at all

The only test that seemed to run significantly slower was the Recursion test. It's not clear why that was the case. The optimizer made only a couple transformations to the recursive function that traded a couple LOAD_CONSTs for LOADIs and removed some unreachable code. Studying the C code that implements LOAD_CONST and LOADI, it's difficult to see how the former would be faster than the latter. Executing the following simple function with and without peephole optimization enabled suggests that LOADI is much faster than LOAD_CONST.

def f():
    import time

    t = time.clock()
    for j in xrange(10000):
    for i in xrange(100):
        pass
    ohd = time.clock()-t

    t = time.clock()
    for j in xrange(10000):
    for i in xrange(100):
        a = 2; a = 2; a = 2; a = 2
    print time.clock()-t-ohd

With the optimzer disabled, executing the above function displayed 6.88 on my 100 MHz Pentium. With it enabled, it displayed 3.38. Inspection of the disassembled byte code showed that the substitution of LOADI for LOAD_CONST instructions was the only change to the code of the inner loop.

Over the long-run, a series of benchmarks should be developed that use a mix of actual Python application code. A small attempt was made to move in that direction by adding two benchmarks to pybench (PPrint and Pickler) which are based on test code in two standard Python modules. More complex "real-life" tests should be developed, however. (Who wants to implement HSPICE in Python?)

Optimizer Speed

The speed of the optimizer itself needs to be improved, probably by recoding parts of it in C. In its current state it is a hindrance to startup of programs with short runtimes or that execute most of their code in the __main__ module whose byte code is never saved to a .pyo file for later reuse. In the absence of an actual Python-to-C compiler, it may be possible to rely on the fairly regular structure of the optimizer classes to aid in manual conversion. Perhaps some sort of template matching "compiler" such as Strout's Python2C [Stro] specially tailored to this application can be written to automate much of the conversion. This would make it easy for people to test new optimizations without resorting to coding them directly in C, but once they are tested to fairly painlessly migrate them to C.

Miscellaneous Improvements

The technique of speeding up constant loads should be investigated further. While this appears to improve performance, it could probably be generalized to speed up access to all of a function's constants without relying on coupling between the interpreter and Python's integer object.

In theory, it is possible to generate both conservative and aggressive code based upon presumed knowledge of object types, though it may be difficult to realize much of a performance gain from it unless the aggressive optimizations are fairly significant. It seems unlikely that it would yield much better performance than the current inlining of integer adds and subtracts unless a large block of heavily optimized code could be selected with a single test.

Do We Need Type/Protocol Declarations?

To allow the prospect of efficient module compilation to C or machine code, at various times people have discussed adding some form of (optional) static type declarations to Python. At issue are what the syntax of such declarations might look like, what needs to be specified and how much type inference can be done by the compiler without them (which would lessen the need for static type declarations). Recently the topic of protocols was raised in the Python newsgroup. John Skaller implemented a basic protocol module [Skal]. The current module may not be sufficient for the needs of an optimizer without enhancement, however, since it allows one to state what operations a module implements, but not their semantics. Also, protocols are implemented by executing Python code. It's unclear how their properties could affect the compiler or optimizer without actually executing the code.

Chambers [Cham] demonstrated that a significant amount of optimization can be performed in highly dynamic object-oriented languages. Many of the techniques applied to Self should be applicable to Python as well.

Are We Even Headed in the Right Direction?

Peephole optimization is better than nothing, but doesn't look like it will yield major improvements in performance, probably not more than 10-20 per cent. More sophisticated optimization strategies can be tried, but while they've been demonstrated in other environments, they are not trivial to implement. Python's dynamic typing makes it challenging to infer types and compile-time, though Chambers [Cham] clearly shows this is possible.

Chambers showed that code generation for multiple cases can be used to generate code for common, fast cases (and allow function inlining in some cases) while still preserving the full generality of the language.

Instead of applying effort trying to work with incomplete type information, it might be worthwhile to look at more radical changes to the run-time system. For instance, adding registers to the Python virtual machine in the form of a set of register variables local to eval_code2 and using well-understood register allocation schemes might significantly improve the data movement characteristics of the interpreter for both global and local variables, especially in inner loops. Suppose the following Python code is executed:

from math import sin
for x in range(100):
    plot(x, sin(x))
The body of the loop compiles to something like:
LOAD_FAST plot
LOAD_FAST x
LOAD_FAST x
LOAD_FAST sin
CALL_FUNCTION 1
CALL_FUNCTION 2
POP_TOP

Each LOAD_FAST instruction copies a local variable reference to the stack from the fastlocals array -- two array accesses and a reference count increment per local variable on each iteration. If register variables were available to store references to x, sin and plot, setup code for the loop would load them into registers once where they could be accessed directly by register-oriented instructions, and with much smaller penalties. Loop finalization code would copy x back to its slot in the fastlocals array. Assuming references to sin, x and plot are in R1, R2 and R4, respectively, this yields a loop body something like

CALLR1 R1, R2		; R3 = sin(x)
POPR R3			; pop top of stack into R3
CALLR2 R4, R2, R3	; plot(x, R3)
POP_TOP

which would reduce or eliminate much of the movement of data between variables and the stack. The tradeoff would be the increased cost of decoding register arguments. That might be nothing more than an array index operation, but wouldn't be free.

Implementation of such a system would require substantial changes to the Python virtual machine and a reasonably sophisticated optimizer. The potential payoff seems significant, however. LOAD and STORE opcodes are the most frequently executed instructions in the Python virtual machine.

Another possible approach to consider is run-time native code generation and optimization. Kistler [Kist] describes a code generator and optimizer that targets its efforts as it profiles the running system. Chambers [Cham] also implemented on-the-fly translation to machine code for Self. Such a system would appear to integrate well with Python, since it is easy to replace function and method definitions at run-time. One attraction of on-the-fly native code generation is that it can be restricted to just the code that will actually be executed, thus allowing more effort to be put into optimizing the code that is generated.

Optimization of Python programs is still in its infancy. Peephole optimization is probably the easiest way to improve performance, though it is limited in how much can be achieved. By adding more techniques common to modern native code compilers [Cham], it should be possible to continue to improve the efficiency of Python byte code. Further out, more radical changes to the underlying system (which can be thought of as different implementations of the same architecture) may yield much larger performance improvements.

Peephole optimization appears to be just the tip of the optimization iceberg. In its current state, it appears to improve performance by several per cent as suggested by pybench results. The performance of the optimizer itself can be a hindrance and suggests reimplementation of parts of the optimizer itself in C. More aggressive optimizations, such as code inlining and customization, and architectural changes to the Python virtual machine, such as the addition of registers, suggest that there is plenty of room for further significant improvements in performance of Python applications.

Appendix: Other Changes

During the course of studying the main Python interpreter function eval_code2, several simple changes to the Python interpreter were tried [Mon2]. They included:

Optimization of stack access
By minimizing the movement of the stack pointer the number of memory references can be reduced, resulting in small performance gains for opcodes that make heavy use of the stack such as DUP_TOP, ROT_TWO and ROT_THREE.

Caching the top element of the stack in a register
This improves the memory access patterns of the interpreter a bit more.

Short-circuiting interpreter error checks
The error checking code at the bottom of the interpreter loop tests the values of three variables: err, x and why. With few exceptions, each virtual machine instruction sets at most one of those variables, so it's almost always faster to check for the one error condition an instruction can set directly the code that implements that instruction, avoiding the general set of checks at the bottom of the loop. This improvement was begun in Python 1.5, but was still incomplete as of the release of 1.5.1.

These optimizations yielded moderate performance improvements for some pybench tests, but also degraded performance in other tests. Further work is needed to identify and correct those problems, but these changes show promise.

References

[Aho] Aho, Alfred V., Ravi Sethi, Jeffrey D. Ullman. "Compilers: Principles, Techniques, and Tools". Addison Wesley, 1986.

[Cham] Chambers, Craig. "The Design and Implementation of the Self Compiler, an Optimizing Compiler for Object-Oriented Programming Languages". Ph. D. dissertation, Computer Science Department, Stanford University, March 1992.

[Kist] Kistler, Thomas. "Dynamic Runtime Optimization", UC Irvine Technical Report 96-54, November 1996. http://www.ics.uci.edu/~kistler/ics-tr-96-54.ps

[Lemb] Lemburg, Marc-Andre. "Pybench". http://www.lemburg.com/files/python/pybench-0.9.zip.

[Mon1] Montanaro, Skip. "Peephole Optimizer Patch" http://musi-cal.mojam.com/~skip/python/optimizer.patch.

[Mon2] Montanaro, Skip. "Stack Manipulation Patch" http://musi-cal.mojam.com/~skip/python/stack-diffs.out

[PSA] Python Software Association. http://www.python.org/.

[Pete] Peters, Tim. Post to the comp.lang.python newsgroup. July 8, 1998. http://www.dejanews.com/getdoc.xp?AN=369547398.

  • [Skal] Skaller, John. Post to the comp.lang.python newsgroup. July 9, 1998. http://www.dejanews.com/getdoc.xp?AN=369976995.

    [Stro] Strout, Joseph. "Python2C". http://www.strout.net/python/ai/python2c.py.

    [Tutt] Tutt, Bill. "Xfreeze". http://www.python.org/ftp/python/contrib/System/xfreeze.README