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