Fetching contributors…
Cannot retrieve contributors at this time
executable file 341 lines (302 sloc) 10.2 KB
#!/usr/bin/python
from __future__ import print_function
import os, sys, subprocess
from math import *
# The tests to run are near the bottom
MIN_REPS = 3
NUM_POINTS = 9
MIN_TIME = 0.1
MAX_TIME = 1.0
MAX_X = 100000
def makedir(x):
try:
os.mkdir(x)
except OSError:
pass
def rm(x):
try:
os.unlink(x)
except OSError:
pass
makedir('fig')
makedir('fig/relative')
makedir('fig/absolute')
makedir('.cache')
makedir('dat')
makedir('gnuplot')
limits = (128,)
current_limit = None
def make(limit):
global current_limit
current_limit = limit
setup = 'from blist import blist'
ns = []
for i in range(50+1):
ns.append(int(floor(10**(i*0.1))))
ns = list(i for i in sorted(set(ns)) if i <= MAX_X)
def smart_timeit(stmt, setup, hint):
n = hint
while 1:
v = timeit(stmt, setup, n)
if v[0]*n > MIN_TIME:
return v, n
n <<= 1
import timeit
timeit_path = timeit.__file__
timeit_cache = {}
def timeit(stmt, setup, rep):
assert rep >= MIN_REPS
key = (stmt, setup, rep, current_limit)
if key in timeit_cache:
return timeit_cache[key]
try:
n = NUM_POINTS
args =[sys.executable, timeit_path,
'-r', str(n), '-v', '-n', str(rep), '-s', setup, '--', stmt]
p = subprocess.Popen(args,
stdout=subprocess.PIPE, stderr=subprocess.PIPE)
so, se = p.communicate()
try:
lines = so.split(b'\n')
raw = lines[0]
number = int(lines[1].split()[0])
times = [float(x) / number for x in raw.split()[2:]]
times.sort()
# median, lower quartile, upper quartile
v = (times[n//2], times[n//4], times[3*n//4])
timeit_cache[key] = v
return v
except:
print(so)
print(se)
raise
except:
print(stmt)
print(setup)
raise
values = {}
def get_timing1(limit, label, setup_n, template, typename, use_rep_map):
f = open('dat/%s-%s.dat' % (str(limit), label), 'w')
print('#', label, file=f)
print('#', template.replace('\n', '\\n'), file=f)
if setup_n is None:
setup_n = "x = TypeToTest(range(n))"
else:
setup_n = setup_n
ftimeit = open('fig/%s.txt' % label, 'w')
print('<div class="blist_inner">Setup: <code>%s</code><br/>' % setup_n.replace('\n', '<br/>'),
file=ftimeit)
print('Timed: <code>%s</code></div>' % template.replace('\n', '<br/>'),
file=ftimeit)
ftimeit.close()
for i in reversed(list(range(len(ns)))):
n = ns[i]
key = (limit, label, setup_n, n, template, typename)
print(n, end=' ')
sys.stdout.flush()
setup2 = '\nTypeToTest = %s\nn = %d\n' % (typename, n)
setup3 = setup + '\n' + setup2 + setup_n
stmt = template
if not use_rep_map:
if i < len(ns)-1:
rep_map[n] = max(rep_map[n], rep_map[ns[i+1]])
v, rep = smart_timeit(stmt, setup3, rep_map[n])
if rep_map[n] < rep:
rep_map[n] = rep
else:
k = rep_map[n]
if k * values[key] > MAX_TIME:
k = max(MIN_REPS, int(ceil(MAX_TIME / values[key])))
v = timeit(stmt, setup3, k)
values[key] = v[0]
v = [x*1000 for x in v]
if typename == 'list':
list_values[n] = v[0]
print(n, file=f, end=' ')
for x in v:
print(x, file=f, end=' ')
for x in v:
print(x/list_values[n], file=f, end=' ')
print(file=f)
print()
f.close()
def get_timing(label, setup_n, template):
global rep_map, list_values
rep_map = {}
list_values = {}
for n in ns:
rep_map[n] = MIN_REPS
make('list')
get_timing1('list', label, setup_n, template, 'list', False)
for limit in limits:
print('Timing', label, limit, ':', end=' ')
sys.stdout.flush()
make(limit)
get_timing1(limit, label, setup_n, template, 'blist', False)
make('list')
get_timing1('list', label, setup_n, template, 'list', True)
for limit in limits:
print('Timing', label, limit, ':', end=' ')
sys.stdout.flush()
make(limit)
get_timing1(limit, label, setup_n, template, 'blist', True)
plot(label, True)
plot(label, False)
html(label)
def html(label):
fname = 'fig/%s.html' % label
f = open(fname, 'w')
if timing_d[label][0] is None:
setup = 'x = TypeToTest(range(n))'
else:
setup = timing_d[label][0]
print('''
<html>
<head>
<title>BList vs Python list timing results: %s</title>
<script src="svg.js"></script>
</head>
<body>
<div style="width: 100%%; background-color: #ccc;">
<a href="/">Home</a>
| <a href="/blist/">BList</a>
| <a href="http://pokersleuth.com/">Poker Sleuth</a>
| <a href="http://pokersleuth.com/poker-crunch.shtml">Poker Calculator</a>
| <a href="http://pokersleuth.com/hand-converter.shtml">Hand Converter</a>
</div>
<object data="absolute/%s.svg" width="480" height="360"
type="image/svg+xml"></object>
<object data="relative/%s.svg" width="480" height="360"
type="image/svg+xml"></object>
<p>
Setup:
<pre>
%s
</pre>
Timed:
<pre>
%s
</pre>
</body>
</html>
''' % (label, label, label, setup, timing_d[label][1]), file=f)
f.close()
def plot(label, relative):
safe_label = label.replace('_', '\\\\_')
fname = 'gnuplot/%s.gnuplot' % label
f = open(fname, 'w')
if relative:
d = 'fig/relative/'
else:
d = 'fig/absolute/'
print("""
set output "%s/%s.svg"
set xlabel "List Size (n)"
set title "%s"
set terminal svg size 480,360 dynamic enhanced
set size noratio 1,1
set key top left
set bars 0.2
set pointsize 0.5
set xtics ("1" 1, "10" 10, "100" 100, "1k" 1000, "10k" 10000, "100k" 100000, "1M" 1000000)
""" % (d, label, safe_label), file=f)
if relative:
print('set title "Normalized Execution Times, log-linear scale"', file=f)
print('set logscale x', file=f)
print('set yrange [0:*]', file=f)
print('set yrange [0:200]', file=f)
print('set ylabel "Execution Time (%)"', file=f)
k = 3
m = 100.0
else:
print('set title "Raw Execution Times, log-log scale"', file=f)
print('set logscale xy', file=f)
print('set yrange [0.00001:10]', file=f)
print('set ylabel "Execution Time"', file=f)
print('set ytics ("1 ns" 0.000001, "10 ns" 0.00001, "100 ns" 0.0001, "1 us" 0.001, "10 us" 0.01, "100 us" 0.1, "1 ms" 1.0, "10 ms" 10.0, "100 ms" 100.0)', file=f)
k = 0
m = 1.0
print (('plot "dat/list-%s.dat" using 1:(%f*$%d):(%f*$%d):(%f*$%d) title "list()" with yerr pt 1, \\' % (label, m, k+2, m, k+3, m, k+4)), file=f)
for limit in limits:
print ((' "dat/%d-%s.dat" using 1:(%f*$%d):(%f*$%d):(%f*$%d) title "blist()" with yerr pt 1 '% (limit, label, m, k+2, m, k+3, m, k+4)), file=f)
print(file=f)
f.flush()
f.close()
if os.system('gnuplot "%s"' % fname):
raise RuntimeError('Gnuplot failure')
timing_d = {}
def add_timing(name, auto, stmt):
timing_d[name] = (auto, stmt)
def run_timing(name):
auto, stmt = timing_d[name]
get_timing(name, auto, stmt)
def run_all():
for k in sorted(timing_d):
run_timing(k)
########################################################################
# Tests to run are below here.
# The arguments to add_timing are as follows:
# 1) name of the test
# 2) setup code to run once. "None" means x = TypeToTest(range(n))
# 3) code to execute repeatedly in a loop
#
# The following symbols will autoamtically be defined:
# - blist
# - TypeToTest
# - n
add_timing('eq list', 'x = TypeToTest(range(n))\ny=range(n)', 'x==y')
#add_timing('eq recursive', 'x = TypeToTest()\nx.append(x)\ny = TypeToTest()\ny.append(y)', 'try:\n x==y\nexcept RuntimeError:\n pass')
add_timing('FIFO', None, """\
x.insert(0, 0)
x.pop(0)
""")
add_timing('LIFO', None, """\
x.append(0)
x.pop(-1)
""")
add_timing('add', None, "x + x")
add_timing('contains', None, "-1 in x")
#add_timing('getitem1', None, "x[0]")
#add_timing('getitem2', None, "x.__getitem__(0)")
add_timing('getitem3', 'x = TypeToTest(range(n))\nm = n//2', "x[m]")
add_timing('getslice', None, "x[1:-1]")
add_timing('forloop', None, "for i in x:\n pass")
add_timing('len', None, "len(x)")
add_timing('eq', None, "x == x")
add_timing('mul10', None, "x * 10")
#add_timing('setitem1', None, 'x[0] = 1')
add_timing('setitem3', 'x = TypeToTest(range(n))\nm = n//2', 'x[m] = 1')
add_timing('count', None, 'x.count(5)')
add_timing('reverse', None, 'x.reverse()')
add_timing('delslice', None, 'del x[len(x)//4:3*len(x)//4]\nx *= 2')
add_timing('setslice', None, 'x[:] = x')
add_timing('sort random', 'import random\nx = [random.randrange(n*4) for i in range(n)]', 'y = TypeToTest(x)\ny.sort()')
add_timing('sort random key', 'import random\nx = [random.randrange(n*4) for i in range(n)]', 'y = TypeToTest(x)\ny.sort(key=float)')
add_timing('sort sorted', None, 'x.sort()')
add_timing('sort sorted key', None, 'x.sort(key=int)')
add_timing('sort reversed', 'x = list(range(n))\nx.reverse()', 'y = TypeToTest(x)\ny.sort()')
add_timing('sort reversed key', 'x = list(range(n))\nx.reverse()', 'y = TypeToTest(x)\ny.sort(key=int)')
add_timing('sort random tuples', 'import random\nx = [(random.random(), random.random()) for i in range(n)]', 'y = TypeToTest(x)\ny.sort()')
ob_def = '''
import random
class ob:
def __init__(self, v):
self.v = v
def __lt__(self, other):
return self.v < other.v
x = [ob(random.randrange(n*4)) for i in range(n)]
'''
add_timing('sort random objects', ob_def, 'y = TypeToTest(x)\ny.sort()')
add_timing('sort sorted objects', ob_def + 'x.sort()', 'x.sort()')
add_timing('init from list', 'x = list(range(n))', 'y = TypeToTest(x)')
add_timing('init from tuple', 'x = tuple(range(n))', 'y = TypeToTest(x)')
add_timing('init from iterable', 'x = range(n)', 'y = TypeToTest(x)')
add_timing('init from same type', None, 'y = TypeToTest(x)')
add_timing('shuffle', 'from random import shuffle\nx = TypeToTest(range(n))', 'shuffle(x)')
if __name__ == '__main__':
make(128)
if len(sys.argv) == 1:
run_all()
else:
for name in sys.argv[1:]:
run_timing(name)