src/sorting/scaling.py

   1 #!/usr/bin/env python
   2
   3 """Measure how a sorting executable scales with N.
   4
   5 The executable should support one of the following:
   6   executable path/to/data/file
   7   cat path/to/data/file | executable
   8 Where the data file is of the format output by data.py.
   9 """
  10
  11 from __future__ import with_statement
  12
  13 import subprocess
  14 import time
  15 import sys
  16
  17 import numpy
  18 import matplotlib
  19 matplotlib.use('Agg')  # select backend that doesn't require X Windows
  20 import pylab
  21
  22
  23 def generate_data(generator, stream, N, ordered=False):
  24     print >> sys.stderr, 'generate %d data points (ordered? %s)' % (
  25         N, ordered)
  26     stream.seek(0)
  27     stream.truncate()
  28     args = [generator, str(N)]
  29     if ordered:
  30         args.insert(1, '--ordered')
  31     q = subprocess.Popen(args, stdout=stream)
  32     status = q.wait()
  33     assert status == 0, status
  34     stream.flush()
  35
  36 def run_test(executable, stdin=True, data_filename=None):
  37     print >> sys.stderr, 'run %s' % executable
  38     if stdin:
  39         with open(data_filename, 'r') as f:
  40             contents = f.read()
  41     start = time.time()
  42     if stdin:
  43         p = subprocess.Popen([executable], stdin=subprocess.PIPE,
  44                              stdout=open('/dev/null', 'w'))
  45         p.communicate(contents)
  46     else:
  47         p = subprocess.Popen([executable, data_filename],
  48                              stdout=open('/dev/null', 'w'))
  49     status = p.wait()
  50     stop = time.time()
  51     assert status == 0, status
  52     return stop - start
  53
  54 def run_tests(executable, stdin=True, generator='./data.py', data_file=None,
  55               ordered=False, repeats=10, max_time=1e2):
  56     times = {}
  57     prev_time = 0
  58     N = 2
  59     while prev_time < max_time:
  60         print
  61         ts = numpy.zeros((repeats,), dtype=numpy.double)
  62         for i in range(repeats):
  63             generate_data(generator, data_file, N, ordered=ordered)
  64             ts[i] = run_test(executable, stdin, data_file.name)
  65         times[N] = ts
  66         prev_time = ts.mean()
  67         N *= 2
  68     return times
  69
  70 def main(argv=None):
  71     import optparse
  72     import tempfile
  73
  74     if argv == None:
  75         argv = sys.argv[1:]
  76
  77     p = optparse.OptionParser(
  78         usage='%prog [options] executable', epilog=__doc__)
  79     p.format_epilog = lambda formatter: __doc__
  80     p.add_option('-s', '--stdin', dest='stdin', default=False,
  81                  action='store_true', help='Use the stdin executable syntax.')
  82     p.add_option('-g', '--generator', dest='generator', default='./data.py',
  83                  help='Executable generating the random source (%default).')
  84     p.add_option('-r', '--repeats', dest='repeats', default=10, type='int',
  85                  help='Number of repeats to run at each N (%default).')
  86     p.add_option('-m', '--max-time', dest='max_time', default=1e2,type='float',
  87                  help='Number of repeats to run at each N (%default).')
  88     p.add_option('-p', '--plot', dest='plot', default=None,
  89                  help='Filename for a scaling plot (no plot is generated if this option is not set).')
  90
  91     options,args = p.parse_args(argv)
  92
  93     executable = args[0]
  94
  95     data_file = tempfile.NamedTemporaryFile()
  96     kwargs = {
  97         'executable': executable,
  98         'stdin': options.stdin,
  99         'generator': options.generator,
 100         'data_file': data_file,
 101         'repeats': options.repeats,
 102         'max_time': options.max_time,
 103         }
 104     try:
 105         times = run_tests(ordered=False, **kwargs)
 106         ordered_times = run_tests(ordered=True, **kwargs)
 107     except:
 108         data_file.close()
 109         raise
 110
 111     columns = ['N',
 112                'ordered mean (s)', 'ordered std. dev. (s)',
 113                'random mean (s)', 'random std. dev. (s)']
 114     plots = dict([(c, []) for c in columns])
 115
 116     print '# sort times for %s' % executable
 117     print '# %d repeats' % options.repeats
 118     print '#%s' % '\t'.join(columns)
 119     invalid = numpy.array(numpy.inf)
 120     for key in sorted(set(times.keys() + ordered_times.keys())):
 121         om = ordered_times.get(key, invalid).mean()
 122         os = ordered_times.get(key, invalid).std()
 123         m = times.get(key, invalid).mean()
 124         s = times.get(key, invalid).std()
 125         print '\t'.join([str(x) for x in [key, om, os, m, s]])
 126         for c,x in zip(columns, [key, om, os, m, s]):
 127             plots[c].append(x)
 128
 129     if options.plot:
 130         f = pylab.figure()
 131         a = pylab.axes()
 132         a.hold(True)
 133         for c,color in zip(['ordered', 'random'], 'br'):
 134             a.errorbar(
 135                 x=plots['N'],
 136                 y=plots['%s mean (s)' % c],
 137                 yerr=plots['%s std. dev. (s)' % c],
 138                 fmt='%so-' % color, label=c)
 139         a.set_title('sort times for %s' % executable)
 140         a.set_xscale('log')
 141         a.set_yscale('log')
 142         a.set_xlabel('N')
 143         a.set_ylabel('t (s)')
 144         a.legend(loc='best')
 145         f.savefig(options.plot)
 146
 147 if __name__ == '__main__':
 148     main()