M
Mark Dickinson
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)
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)
