ab.py 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407
  1. #!/usr/bin/python
  2. # encoding: utf-8
  3. # Copyright 2017 Google Inc.
  4. #
  5. # Use of this source code is governed by a BSD-style license that can be found
  6. # in the LICENSE file.
  7. #
  8. # This is an A/B test utility script used by calmbench.py
  9. #
  10. # For each bench, we get a distribution of min_ms measurements from nanobench.
  11. # From that, we try to recover the 1/3 and 2/3 quantiles of the distribution.
  12. # If range (1/3 quantile, 2/3 quantile) is completely disjoint between A and B,
  13. # we report that as a regression.
  14. #
  15. # The more measurements we have for a bench, the more accurate our quantiles
  16. # are. However, taking more measurements is time consuming. Hence we'll prune
  17. # out benches and only take more measurements for benches whose current quantile
  18. # ranges are disjoint.
  19. #
  20. # P.S. The current script is brute forcely translated from a ruby script. So it
  21. # may be ugly...
  22. import re
  23. import os
  24. import sys
  25. import time
  26. import json
  27. import subprocess
  28. import shlex
  29. import multiprocessing
  30. import traceback
  31. from argparse import ArgumentParser
  32. from multiprocessing import Process
  33. from threading import Thread
  34. from threading import Lock
  35. from pdb import set_trace
  36. HELP = """
  37. \033[31mPlease call calmbench.py to drive this script if you're not doing so.
  38. This script is not supposed to be used by itself. (At least, it's not easy to
  39. use by itself. The calmbench bots may use this script directly.)
  40. \033[0m
  41. """
  42. FACTOR = 3 # lower/upper quantile factor
  43. DIFF_T = 0.99 # different enough threshold
  44. TERM = 10 # terminate after this no. of iterations without suspect changes
  45. MAXTRY = 30 # max number of nanobench tries to narrow down suspects
  46. UNITS = "ns µs ms s".split()
  47. timesLock = Lock()
  48. timesA = {}
  49. timesB = {}
  50. def parse_args():
  51. parser = ArgumentParser(description=HELP)
  52. parser.add_argument('outdir', type=str, help="output directory")
  53. parser.add_argument('a', type=str, help="name of A")
  54. parser.add_argument('b', type=str, help="name of B")
  55. parser.add_argument('nano_a', type=str, help="path to A's nanobench binary")
  56. parser.add_argument('nano_b', type=str, help="path to B's nanobench binary")
  57. parser.add_argument('arg_a', type=str, help="args for A's nanobench run")
  58. parser.add_argument('arg_b', type=str, help="args for B's nanobench run")
  59. parser.add_argument('repeat', type=int, help="number of initial runs")
  60. parser.add_argument('skip_b', type=str, help=("whether to skip running B"
  61. " ('true' or 'false')"))
  62. parser.add_argument('config', type=str, help="nanobenh config")
  63. parser.add_argument('threads', type=int, help="number of threads to run")
  64. parser.add_argument('noinit', type=str, help=("whether to skip running B"
  65. " ('true' or 'false')"))
  66. parser.add_argument('--concise', dest='concise', action="store_true",
  67. help="If set, no verbose thread info will be printed.")
  68. parser.set_defaults(concise=False)
  69. # Additional args for bots
  70. BHELP = "bot specific options"
  71. parser.add_argument('--githash', type=str, default="", help=BHELP)
  72. parser.add_argument('--keys', type=str, default=[], nargs='+', help=BHELP)
  73. args = parser.parse_args()
  74. args.skip_b = args.skip_b == "true"
  75. args.noinit = args.noinit == "true"
  76. if args.threads == -1:
  77. args.threads = 1
  78. if args.config in ["8888", "565"]: # multi-thread for CPU only
  79. args.threads = max(1, multiprocessing.cpu_count() / 2)
  80. return args
  81. def append_dict_sorted_array(dict_array, key, value):
  82. if key not in dict_array:
  83. dict_array[key] = []
  84. dict_array[key].append(value)
  85. dict_array[key].sort()
  86. def add_time(args, name, bench, t, unit):
  87. normalized_t = t * 1000 ** UNITS.index(unit);
  88. if name.startswith(args.a):
  89. append_dict_sorted_array(timesA, bench, normalized_t)
  90. else:
  91. append_dict_sorted_array(timesB, bench, normalized_t)
  92. def append_times_from_file(args, name, filename):
  93. with open(filename) as f:
  94. lines = f.readlines()
  95. for line in lines:
  96. items = line.split()
  97. if len(items) > 10:
  98. bench = items[10]
  99. matches = re.search("([+-]?\d*.?\d+)(s|ms|µs|ns)", items[3])
  100. if (not matches or items[9] != args.config):
  101. continue
  102. time_num = matches.group(1)
  103. time_unit = matches.group(2)
  104. add_time(args, name, bench, float(time_num), time_unit)
  105. class ThreadWithException(Thread):
  106. def __init__(self, target):
  107. super(ThreadWithException, self).__init__(target = target)
  108. self.exception = None
  109. def run(self):
  110. try:
  111. self._Thread__target(*self._Thread__args, **self._Thread__kwargs)
  112. except BaseException as e:
  113. self.exception = e
  114. def join(self, timeout=None):
  115. super(ThreadWithException, self).join(timeout)
  116. class ThreadRunner:
  117. """Simplest and stupidiest threaded executer."""
  118. def __init__(self, args):
  119. self.concise = args.concise
  120. self.threads = []
  121. def add(self, args, fn):
  122. if len(self.threads) >= args.threads:
  123. self.wait()
  124. t = ThreadWithException(target = fn)
  125. t.daemon = True
  126. self.threads.append(t)
  127. t.start()
  128. def wait(self):
  129. def spin():
  130. i = 0
  131. spinners = [". ", ".. ", "..."]
  132. while len(self.threads) > 0:
  133. timesLock.acquire()
  134. sys.stderr.write(
  135. "\r" + spinners[i % len(spinners)] +
  136. " (%d threads running)" % len(self.threads) +
  137. " \r" # spaces for erasing characters
  138. )
  139. timesLock.release()
  140. time.sleep(0.5)
  141. i += 1
  142. if not self.concise:
  143. ts = Thread(target = spin);
  144. ts.start()
  145. for t in self.threads:
  146. t.join()
  147. exceptions = []
  148. for t in self.threads:
  149. if t.exception:
  150. exceptions.append(t.exception)
  151. self.threads = []
  152. if not self.concise:
  153. ts.join()
  154. if len(exceptions):
  155. for exc in exceptions:
  156. print exc
  157. raise exceptions[0]
  158. def split_arg(arg):
  159. raw = shlex.split(arg)
  160. result = []
  161. for r in raw:
  162. if '~' in r:
  163. result.append(os.path.expanduser(r))
  164. else:
  165. result.append(r)
  166. return result
  167. def run(args, threadRunner, name, nano, arg, i):
  168. def task():
  169. file_i = "%s/%s.out%d" % (args.outdir, name, i)
  170. should_run = not args.noinit and not (name == args.b and args.skip_b)
  171. if i <= 0:
  172. should_run = True # always run for suspects
  173. if should_run:
  174. if i > 0:
  175. timesLock.acquire()
  176. print "Init run %d for %s..." % (i, name)
  177. timesLock.release()
  178. subprocess.check_call(["touch", file_i])
  179. with open(file_i, 'w') as f:
  180. subprocess.check_call([nano] + split_arg(arg) +
  181. ["--config", args.config], stderr=f, stdout=f)
  182. timesLock.acquire()
  183. append_times_from_file(args, name, file_i)
  184. timesLock.release()
  185. threadRunner.add(args, task)
  186. def init_run(args):
  187. threadRunner = ThreadRunner(args)
  188. for i in range(1, max(args.repeat, args.threads / 2) + 1):
  189. run(args, threadRunner, args.a, args.nano_a, args.arg_a, i)
  190. run(args, threadRunner, args.b, args.nano_b, args.arg_b, i)
  191. threadRunner.wait()
  192. def get_lower_upper(values):
  193. i = max(0, (len(values) - 1) / FACTOR)
  194. return values[i], values[-i - 1]
  195. def different_enough(lower1, upper2):
  196. return upper2 < DIFF_T * lower1
  197. # TODO(liyuqian): we used this hacky criteria mainly because that I didn't have
  198. # time to study more rigorous statistical tests. We should adopt a more rigorous
  199. # test in the future.
  200. def get_suspects():
  201. suspects = []
  202. for bench in timesA.keys():
  203. if bench not in timesB:
  204. continue
  205. lowerA, upperA = get_lower_upper(timesA[bench])
  206. lowerB, upperB = get_lower_upper(timesB[bench])
  207. if different_enough(lowerA, upperB) or different_enough(lowerB, upperA):
  208. suspects.append(bench)
  209. return suspects
  210. def process_bench_pattern(s):
  211. if ".skp" in s: # skp bench won't match their exact names...
  212. return "^\"" + s[0:(s.index(".skp") + 3)] + "\""
  213. else:
  214. return "^\"" + s + "\"$"
  215. def suspects_arg(suspects):
  216. patterns = map(process_bench_pattern, suspects)
  217. return " --match " + (" ".join(patterns))
  218. def median(array):
  219. return array[len(array) / 2]
  220. def regression(bench):
  221. a = median(timesA[bench])
  222. b = median(timesB[bench])
  223. if (a == 0): # bad bench, just return no regression
  224. return 1
  225. return b / a
  226. def percentage(x):
  227. return (x - 1) * 100
  228. def format_r(r):
  229. return ('%6.2f' % percentage(r)) + "%"
  230. def normalize_r(r):
  231. if r > 1.0:
  232. return r - 1.0
  233. else:
  234. return 1.0 - 1/r
  235. def test():
  236. args = parse_args()
  237. init_run(args)
  238. last_unchanged_iter = 0
  239. last_suspect_number = -1
  240. tryCnt = 0
  241. it = 0
  242. while tryCnt < MAXTRY:
  243. it += 1
  244. suspects = get_suspects()
  245. if len(suspects) != last_suspect_number:
  246. last_suspect_number = len(suspects)
  247. last_unchanged_iter = it
  248. if (len(suspects) == 0 or it - last_unchanged_iter >= TERM):
  249. break
  250. print "Number of suspects at iteration %d: %d" % (it, len(suspects))
  251. threadRunner = ThreadRunner(args)
  252. for j in range(1, max(1, args.threads / 2) + 1):
  253. run(args, threadRunner, args.a, args.nano_a,
  254. args.arg_a + suspects_arg(suspects), -j)
  255. run(args, threadRunner, args.b, args.nano_b,
  256. args.arg_b + suspects_arg(suspects), -j)
  257. tryCnt += 1
  258. threadRunner.wait()
  259. suspects = get_suspects()
  260. if len(suspects) == 0:
  261. print ("%s and %s does not seem to have significant " + \
  262. "performance differences.") % (args.a, args.b)
  263. else:
  264. suspects.sort(key = regression)
  265. print "%s (compared to %s) is likely" % (args.a, args.b)
  266. for suspect in suspects:
  267. r = regression(suspect)
  268. if r < 1:
  269. print "\033[31m %s slower in %s\033[0m" % \
  270. (format_r(1/r), suspect)
  271. else:
  272. print "\033[32m %s faster in %s\033[0m" % \
  273. (format_r(r), suspect)
  274. with open("%s/bench_%s_%s.json" % (args.outdir, args.a, args.b), 'w') as f:
  275. results = {}
  276. for bench in timesA:
  277. r = regression(bench) if bench in suspects else 1.0
  278. results[bench] = {
  279. args.config: {
  280. "signed_regression": normalize_r(r),
  281. "lower_quantile_ms": get_lower_upper(timesA[bench])[0] * 1e-6,
  282. "upper_quantile_ms": get_lower_upper(timesA[bench])[1] * 1e-6,
  283. "options": {
  284. # TODO(liyuqian): let ab.py call nanobench with --outResultsFile so
  285. # nanobench could generate the json for us that's exactly the same
  286. # as that being used by perf bots. Currently, we cannot guarantee
  287. # that bench is the name (e.g., bench may have additional resolution
  288. # information appended after name).
  289. "name": bench
  290. }
  291. }
  292. }
  293. output = {"results": results}
  294. if args.githash:
  295. output["gitHash"] = args.githash
  296. if args.keys:
  297. keys = {}
  298. for i in range(len(args.keys) / 2):
  299. keys[args.keys[i * 2]] = args.keys[i * 2 + 1]
  300. output["key"] = keys
  301. f.write(json.dumps(output, indent=4))
  302. print ("\033[36mJSON results available in %s\033[0m" % f.name)
  303. with open("%s/bench_%s_%s.csv" % (args.outdir, args.a, args.b), 'w') as out:
  304. out.write(("bench, significant?, raw regresion, " +
  305. "%(A)s quantile (ns), %(B)s quantile (ns), " +
  306. "%(A)s (ns), %(B)s (ns)\n") % {'A': args.a, 'B': args.b})
  307. for bench in suspects + timesA.keys():
  308. if (bench not in timesA or bench not in timesB):
  309. continue
  310. ta = timesA[bench]
  311. tb = timesB[bench]
  312. out.write(
  313. "%s, %s, %f, " % (bench, bench in suspects, regression(bench)) +
  314. ' '.join(map(str, get_lower_upper(ta))) + ", " +
  315. ' '.join(map(str, get_lower_upper(tb))) + ", " +
  316. ("%s, %s\n" % (' '.join(map(str, ta)), ' '.join(map(str, tb))))
  317. )
  318. print (("\033[36m" +
  319. "Compared %d benches. " +
  320. "%d of them seem to be significantly differrent." +
  321. "\033[0m") %
  322. (len([x for x in timesA if x in timesB]), len(suspects)))
  323. print ("\033[36mPlease see detailed bench results in %s\033[0m" %
  324. out.name)
  325. if __name__ == "__main__":
  326. try:
  327. test()
  328. except Exception as e:
  329. print e
  330. print HELP
  331. traceback.print_exc()
  332. raise e