Speed quirk: redundant line gives six-fold speedup

Thu Aug 25 12:44:24 EDT 2005

I have a simple 192-line Python script that begins with the line:

dummy0 = 47

The script runs in less than 2.5 seconds.  The variable dummy0 is never
referenced again, directly or indirectly, by the rest of the script.

Here's the surprise: if I remove or comment out this first line, the
script takes more than 15 seconds to run.  So it appears that adding a
redundant line produces a spectacular six-fold increase in speed!

(Actually, I had to add 29 dummy lines at the beginning of the code to
get the speed increase; if any one of these lines is removed the
running time reverts to around 15 seconds again.)

Questions:

(1) Can anyone else reproduce this behaviour, or is it just some quirk
    of my setup?
(2) Any possible explanations?  Is there some optimization that kicks
    in at a certain number of lines, or at a certain length of
    bytecode?
(3) If (2), is there some way to force the optimization, so that I can
    get the speed increase without having to add the extra lines?

I'm running Python 2.4.1 on a 1.2Ghz iBook G4:

Python 2.4.1 (#1, May 21 2005, 19:56:42) 
[GCC 3.3 20030304 (Apple Computer, Inc. build 1495)] on darwin

I've posted the code below, with some trepidation, since it's not a
work of art and wasn't really intended to be seen by other human
beings.  It's necessarily quite long: any attempt to shorten it
significantly seems to cancel the speed gain.  Any clues as to what
might be going on would be greatly appreciated!

Mark

# code starts here
dummy0 = 47
dummy1 = 47
dummy2 = 47
dummy3 = 47
dummy4 = 47
dummy5 = 47
dummy6 = 47
dummy7 = 47
dummy8 = 47
dummy9 = 47
dummy10 = 47
dummy11 = 47
dummy12 = 47
dummy13 = 47
dummy14 = 47
dummy15 = 47
dummy16 = 47
dummy17 = 47
dummy18 = 47
dummy19 = 47
dummy20 = 47
dummy21 = 47
dummy22 = 47
dummy23 = 47
dummy24 = 47
dummy25 = 47
dummy26 = 47
dummy27 = 47
dummy28 = 47

# Sudoku puzzle solver via Knuth's method of `dancing links'.

# Initial data: list of constraints, list of moves, and map from moves to lists of constraints

template = ("  | %s %s %s | %s %s %s | %s %s %s |\n" * 3).join(["  +-------+-------+-------+\n"] * 4)
div_nums = range(9)
symbols = "123456789"

constraints = ["position %d, %d" % (i, j) for i in div_nums for j in div_nums] + \
              ["%s in %s %d" % (i, j, k) for i in symbols for j in ["row", "column", "block"] for k in div_nums]

satisfies = dict(((s, i, j),
                  ["position %d, %d" % (i, j),
                   "%s in row %d" % (s, i),
                   "%s in column %d" % (s, j),
                   "%s in block %d" % (s, i-i%3+j//3)]) for s in symbols for i in div_nums for j in div_nums)

moves = satisfies.keys()

class LLentry(object): pass

# First set up the data objects and column objects

def rowhead(obj):
    obj.L = obj.R = obj.M = obj

def colhead(obj):
    obj.U = obj.D = obj.C = obj
    obj.S = 0

def rowinsert(obj, pos):
    # insert into doubly-linked list with header pos
    posL = pos.L
    obj.R = pos
    pos.L = obj
    obj.L = posL
    posL.R = obj
    obj.M = pos

def colinsert(obj, pos):
    # as above
    posU = pos.U
    obj.D = pos
    pos.U = obj
    obj.U = posU
    posU.D = obj
    obj.C = pos
    pos.S += 1

def rowitems(pos):
    c = pos.R
    while c is not pos:
        yield c
        c = c.R

def move(m):
    cc = m.R
    while cc is not m:
        c = cc.C
        c.R.L = c.L; c.L.R = c.R
        r = c.D
        while r is not c:
            j = r.R
            while j is not r:
                j.D.U = j.U
                j.U.D = j.D
                j.C.S -= 1
                j = j.R
            r = r.D
        cc = cc.R
    moves_so_far.append(m)

h = LLentry()
rowhead(h); colhead(h)

constraint_from_name = {}
for name in constraints:
    obj = LLentry()
    obj.N = name; constraint_from_name[name] = obj
    rowinsert(obj, h); colhead(obj)
    obj.S = 0

move_from_name = {}
for m in satisfies.keys():
    # we must assume that each move satisfies at least one constraint
    obj = LLentry()
    obj.N = m; move_from_name[m] = obj
    colinsert(obj, h); rowhead(obj)

ones = [(move_from_name[m], constraint_from_name[c]) for m, cc in satisfies.items() for c in cc]
for m, c in ones:
    obj = LLentry()
    rowinsert(obj, m)
    colinsert(obj, c)

moves_so_far = []
# everything's now set up to start the search

def search():
    if h.L is h:
        data = dict(((i, j), s) for s, i, j in (m.N for m in moves_so_far))
        yield template % tuple(data[i, j] for i in div_nums for j in div_nums)
    else:
        mm = min((c.S, c) for c in rowitems(h))[1].D
        while mm is not mm.C:
            m = mm.M
            cc = m.R
            while cc is not m:
                c = cc.C
                c.R.L = c.L
                c.L.R = c.R
                r = c.D
                while r is not c:
                    j = r.R
                    while j is not r:
                        j.D.U = j.U
                        j.U.D = j.D
                        j.C.S -= 1
                        j = j.R
                    r = r.D
                cc = cc.R
            moves_so_far.append(m)
            for solution in search():
                yield solution
            m = moves_so_far.pop()
            cc = m.L
            while cc is not m:
                c = cc.C
                r = c.U
                while r is not c:
                    j = r.L
                    while j is not r:
                        j.D.U = j.U.D = j
                        j.C.S += 1
                        j = j.L
                    r = r.U
                c.R.L = c.L.R = c
                cc = cc.L
            mm = mm.D

rows = [
    "7......19",
    "46.19....",
    "...6827.4",
    ".9......7",
    "...3..4.5",
    "..67.....",
    "..1......",
    "2...74...",
    "...2..3.."]

for r, row in enumerate(rows):
    for c, entry in enumerate(row):
        if entry != '.':
            move(move_from_name[(entry, r, c)])

import time
t = time.time()
for i in range(10):
    for solution in search():
        print solution
print "Total time taken: %s seconds" % (time.time() - t)