benchbase.py 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528
  1. import sys, re, string, time, copy, gc
  2. from itertools import *
  3. from StringIO import StringIO
  4. import time
  5. TREE_FACTOR = 1 # increase tree size with '-l / '-L' cmd option
  6. _TEXT = "some ASCII text" * TREE_FACTOR
  7. _UTEXT = u"some klingon: \F8D2" * TREE_FACTOR
  8. _ATTRIBUTES = {
  9. '{attr}test1' : _TEXT,
  10. '{attr}test2' : _TEXT,
  11. 'bla1' : _TEXT,
  12. 'bla2' : _TEXT,
  13. 'bla3' : _TEXT
  14. }
  15. def initArgs(argv):
  16. global TREE_FACTOR
  17. try:
  18. argv.remove('-l')
  19. # use large trees
  20. TREE_FACTOR *= 2
  21. except ValueError:
  22. pass
  23. try:
  24. argv.remove('-L')
  25. # use LARGE trees
  26. TREE_FACTOR *= 2
  27. except ValueError:
  28. pass
  29. ############################################################
  30. # benchmark decorators
  31. ############################################################
  32. def with_attributes(*use_attributes):
  33. "Decorator for benchmarks that use attributes"
  34. vmap = {False : 0, True : 1}
  35. values = [ vmap[bool(v)] for v in use_attributes ]
  36. def set_value(function):
  37. try:
  38. function.ATTRIBUTES.update(values)
  39. except AttributeError:
  40. function.ATTRIBUTES = set(values)
  41. return function
  42. return set_value
  43. def with_text(no_text=False, text=False, utext=False):
  44. "Decorator for benchmarks that use text"
  45. values = []
  46. if no_text:
  47. values.append(0)
  48. if text:
  49. values.append(1)
  50. if utext:
  51. values.append(2)
  52. def set_value(function):
  53. try:
  54. function.TEXT.add(values)
  55. except AttributeError:
  56. function.TEXT = set(values)
  57. return function
  58. return set_value
  59. def onlylib(*libs):
  60. "Decorator to restrict benchmarks to specific libraries"
  61. def set_libs(function):
  62. if libs:
  63. function.LIBS = libs
  64. return function
  65. return set_libs
  66. def serialized(function):
  67. "Decorator for benchmarks that require serialized XML data"
  68. function.STRING = True
  69. return function
  70. def children(function):
  71. "Decorator for benchmarks that require a list of root children"
  72. function.CHILDREN = True
  73. return function
  74. def nochange(function):
  75. "Decorator for benchmarks that do not change the XML tree"
  76. function.NO_CHANGE = True
  77. return function
  78. ############################################################
  79. # benchmark baseclass
  80. ############################################################
  81. class SkippedTest(Exception):
  82. pass
  83. class TreeBenchMark(object):
  84. atoz = string.ascii_lowercase
  85. repeat100 = range(100)
  86. repeat500 = range(500)
  87. repeat1000 = range(1000)
  88. _LIB_NAME_MAP = {
  89. 'etree' : 'lxe',
  90. 'ElementTree' : 'ET',
  91. 'cElementTree' : 'cET'
  92. }
  93. SEARCH_TAG = "{cdefg}a00001"
  94. def __init__(self, etree, etree_parser=None):
  95. self.etree = etree
  96. libname = etree.__name__.split('.')[-1]
  97. self.lib_name = self._LIB_NAME_MAP.get(libname, libname)
  98. if libname == 'etree':
  99. deepcopy = copy.deepcopy
  100. def set_property(root, fname):
  101. xml = self._serialize_tree(root)
  102. if etree_parser is not None:
  103. setattr(self, fname, lambda : etree.XML(xml, etree_parser))
  104. else:
  105. setattr(self, fname, lambda : deepcopy(root))
  106. setattr(self, fname + '_xml', lambda : xml)
  107. setattr(self, fname + '_children', lambda : root[:])
  108. else:
  109. def set_property(root, fname):
  110. setattr(self, fname, self.et_make_clone_factory(root))
  111. xml = self._serialize_tree(root)
  112. setattr(self, fname + '_xml', lambda : xml)
  113. setattr(self, fname + '_children', lambda : root[:])
  114. attribute_list = list(enumerate( [{}, _ATTRIBUTES] ))
  115. text_list = list(enumerate( [None, _TEXT, _UTEXT] ))
  116. build_name = self._tree_builder_name
  117. self.setup_times = []
  118. for tree in self._all_trees():
  119. times = []
  120. self.setup_times.append(times)
  121. setup = getattr(self, '_setup_tree%d' % tree)
  122. for an, attributes in attribute_list:
  123. for tn, text in text_list:
  124. root, t = setup(text, attributes)
  125. times.append(t)
  126. set_property(root, build_name(tree, tn, an))
  127. def _tree_builder_name(self, tree, tn, an):
  128. return '_root%d_T%d_A%d' % (tree, tn, an)
  129. def tree_builder(self, tree, tn, an, serial, children):
  130. name = self._tree_builder_name(tree, tn, an)
  131. if serial:
  132. name += '_xml'
  133. elif children:
  134. name += '_children'
  135. return getattr(self, name)
  136. def _serialize_tree(self, root):
  137. return self.etree.tostring(root, encoding='UTF-8')
  138. def et_make_clone_factory(self, elem):
  139. def generate_elem(append, elem, level):
  140. var = "e" + str(level)
  141. arg = repr(elem.tag)
  142. if elem.attrib:
  143. arg += ", **%r" % elem.attrib
  144. if level == 1:
  145. append(" e1 = Element(%s)" % arg)
  146. else:
  147. append(" %s = SubElement(e%d, %s)" % (var, level-1, arg))
  148. if elem.text:
  149. append(" %s.text = %r" % (var, elem.text))
  150. if elem.tail:
  151. append(" %s.tail = %r" % (var, elem.tail))
  152. for e in elem:
  153. generate_elem(append, e, level+1)
  154. # generate code for a function that creates a tree
  155. output = ["def element_factory():"]
  156. generate_elem(output.append, elem, 1)
  157. output.append(" return e1")
  158. # setup global function namespace
  159. namespace = {
  160. "Element" : self.etree.Element,
  161. "SubElement" : self.etree.SubElement
  162. }
  163. # create function object
  164. exec "\n".join(output) in namespace
  165. return namespace["element_factory"]
  166. def _all_trees(self):
  167. all_trees = []
  168. for name in dir(self):
  169. if name.startswith('_setup_tree'):
  170. all_trees.append(int(name[11:]))
  171. return all_trees
  172. def _setup_tree1(self, text, attributes):
  173. "tree with 26 2nd level and 520 * TREE_FACTOR 3rd level children"
  174. atoz = self.atoz
  175. SubElement = self.etree.SubElement
  176. current_time = time.time
  177. t = current_time()
  178. root = self.etree.Element('{abc}rootnode')
  179. for ch1 in atoz:
  180. el = SubElement(root, "{abc}"+ch1*5, attributes)
  181. el.text = text
  182. for ch2 in atoz:
  183. tag = "{cdefg}%s00001" % ch2
  184. for i in range(20 * TREE_FACTOR):
  185. SubElement(el, tag).tail = text
  186. t = current_time() - t
  187. return (root, t)
  188. def _setup_tree2(self, text, attributes):
  189. "tree with 520 * TREE_FACTOR 2nd level and 26 3rd level children"
  190. atoz = self.atoz
  191. SubElement = self.etree.SubElement
  192. current_time = time.time
  193. t = current_time()
  194. root = self.etree.Element('{abc}rootnode')
  195. for ch1 in atoz:
  196. for i in range(20 * TREE_FACTOR):
  197. el = SubElement(root, "{abc}"+ch1*5, attributes)
  198. el.text = text
  199. for ch2 in atoz:
  200. SubElement(el, "{cdefg}%s00001" % ch2).tail = text
  201. t = current_time() - t
  202. return (root, t)
  203. def _setup_tree3(self, text, attributes):
  204. "tree of depth 8 + TREE_FACTOR with 3 children per node"
  205. SubElement = self.etree.SubElement
  206. current_time = time.time
  207. t = current_time()
  208. root = self.etree.Element('{abc}rootnode')
  209. children = [root]
  210. for i in range(6 + TREE_FACTOR):
  211. tag_no = count().next
  212. children = [ SubElement(c, "{cdefg}a%05d" % (i%8), attributes)
  213. for i,c in enumerate(chain(children, children, children)) ]
  214. for child in children:
  215. child.text = text
  216. child.tail = text
  217. t = current_time() - t
  218. return (root, t)
  219. def _setup_tree4(self, text, attributes):
  220. "small tree with 26 2nd level and 2 3rd level children"
  221. SubElement = self.etree.SubElement
  222. current_time = time.time
  223. t = current_time()
  224. root = self.etree.Element('{abc}rootnode')
  225. children = [root]
  226. for ch1 in self.atoz:
  227. el = SubElement(root, "{abc}"+ch1*5, attributes)
  228. el.text = text
  229. SubElement(el, "{cdefg}a00001", attributes).tail = text
  230. SubElement(el, "{cdefg}z00000", attributes).tail = text
  231. t = current_time() - t
  232. return (root, t)
  233. def benchmarks(self):
  234. """Returns a list of all benchmarks.
  235. A benchmark is a tuple containing a method name and a list of tree
  236. numbers. Trees are prepared by the setup function.
  237. """
  238. all_trees = self._all_trees()
  239. benchmarks = []
  240. for name in dir(self):
  241. if not name.startswith('bench_'):
  242. continue
  243. method = getattr(self, name)
  244. if hasattr(method, 'LIBS') and self.lib_name not in method.LIBS:
  245. method_call = None
  246. else:
  247. method_call = method
  248. if method.__doc__:
  249. tree_sets = method.__doc__.split()
  250. else:
  251. tree_sets = ()
  252. if tree_sets:
  253. tree_tuples = [ map(int, tree_set.split(','))
  254. for tree_set in tree_sets ]
  255. else:
  256. try:
  257. function = getattr(method, 'im_func', method)
  258. arg_count = method.func_code.co_argcount - 1
  259. except AttributeError:
  260. arg_count = 1
  261. tree_tuples = self._permutations(all_trees, arg_count)
  262. serialized = getattr(method, 'STRING', False)
  263. children = getattr(method, 'CHILDREN', False)
  264. no_change = getattr(method, 'NO_CHANGE', False)
  265. for tree_tuple in tree_tuples:
  266. for tn in sorted(getattr(method, 'TEXT', (0,))):
  267. for an in sorted(getattr(method, 'ATTRIBUTES', (0,))):
  268. benchmarks.append((name, method_call, tree_tuple,
  269. tn, an, serialized, children,
  270. no_change))
  271. return benchmarks
  272. def _permutations(self, seq, count):
  273. def _permutations(prefix, remainder, count):
  274. if count == 0:
  275. return [ prefix[:] ]
  276. count -= 1
  277. perms = []
  278. prefix.append(None)
  279. for pos, el in enumerate(remainder):
  280. new_remainder = remainder[:pos] + remainder[pos+1:]
  281. prefix[-1] = el
  282. perms.extend( _permutations(prefix, new_remainder, count) )
  283. prefix.pop()
  284. return perms
  285. return _permutations([], seq, count)
  286. ############################################################
  287. # Prepare and run benchmark suites
  288. ############################################################
  289. def buildSuites(benchmark_class, etrees, selected):
  290. benchmark_suites = map(benchmark_class, etrees)
  291. # sorted by name and tree tuple
  292. benchmarks = [ sorted(b.benchmarks()) for b in benchmark_suites ]
  293. selected = [ re.compile(r).search for r in selected ]
  294. if selected:
  295. benchmarks = [ [ b for b in bs
  296. if [ match for match in selected
  297. if match(b[0]) ] ]
  298. for bs in benchmarks ]
  299. return (benchmark_suites, benchmarks)
  300. def build_treeset_name(trees, tn, an, serialized, children):
  301. text = {0:'-', 1:'S', 2:'U'}[tn]
  302. attr = {0:'-', 1:'A'}[an]
  303. ser = {True:'X', False:'T'}[serialized]
  304. chd = {True:'C', False:'R'}[children]
  305. return "%s%s%s%s T%s" % (text, attr, ser, chd, ',T'.join(imap(str, trees))[:6])
  306. def printSetupTimes(benchmark_suites):
  307. print "Setup times for trees in seconds:"
  308. for b in benchmark_suites:
  309. print "%-3s: " % b.lib_name,
  310. for an in (0,1):
  311. for tn in (0,1,2):
  312. print ' %s ' % build_treeset_name((), tn, an, False, False)[:2],
  313. print
  314. for i, tree_times in enumerate(b.setup_times):
  315. print " T%d:" % (i+1), ' '.join("%6.4f" % t for t in tree_times)
  316. print
  317. def runBench(suite, method_name, method_call, tree_set, tn, an,
  318. serial, children, no_change):
  319. if method_call is None:
  320. raise SkippedTest
  321. current_time = time.time
  322. call_repeat = range(10)
  323. tree_builders = [ suite.tree_builder(tree, tn, an, serial, children)
  324. for tree in tree_set ]
  325. rebuild_trees = not no_change and not serial
  326. args = tuple([ build() for build in tree_builders ])
  327. method_call(*args) # run once to skip setup overhead
  328. times = []
  329. for i in range(3):
  330. gc.collect()
  331. gc.disable()
  332. t = -1
  333. for i in call_repeat:
  334. if rebuild_trees:
  335. args = [ build() for build in tree_builders ]
  336. t_one_call = current_time()
  337. method_call(*args)
  338. t_one_call = current_time() - t_one_call
  339. if t < 0:
  340. t = t_one_call
  341. else:
  342. t = min(t, t_one_call)
  343. times.append(1000.0 * t)
  344. gc.enable()
  345. if rebuild_trees:
  346. args = ()
  347. args = ()
  348. gc.collect()
  349. return times
  350. def runBenchmarks(benchmark_suites, benchmarks):
  351. for bench_calls in izip(*benchmarks):
  352. for lib, (bench, benchmark_setup) in enumerate(izip(benchmark_suites, bench_calls)):
  353. bench_name = benchmark_setup[0]
  354. tree_set_name = build_treeset_name(*benchmark_setup[-6:-1])
  355. print "%-3s: %-28s" % (bench.lib_name, bench_name[6:34]),
  356. print "(%-10s)" % tree_set_name,
  357. sys.stdout.flush()
  358. try:
  359. result = runBench(bench, *benchmark_setup)
  360. except SkippedTest:
  361. print "skipped"
  362. except KeyboardInterrupt:
  363. print "interrupted by user"
  364. sys.exit(1)
  365. except Exception, e:
  366. print "failed: %s: %s" % (e.__class__.__name__, e)
  367. else:
  368. print "%9.4f msec/pass, best of (" % min(result),
  369. for t in result:
  370. print "%9.4f" % t,
  371. print ")"
  372. if len(benchmark_suites) > 1:
  373. print # empty line between different benchmarks
  374. ############################################################
  375. # Main program
  376. ############################################################
  377. def main(benchmark_class):
  378. import_lxml = True
  379. callgrind_zero = False
  380. if len(sys.argv) > 1:
  381. try:
  382. sys.argv.remove('-i')
  383. # run benchmark 'inplace'
  384. sys.path.insert(0, 'src')
  385. except ValueError:
  386. pass
  387. try:
  388. sys.argv.remove('-nolxml')
  389. # run without lxml
  390. import_lxml = False
  391. except ValueError:
  392. pass
  393. try:
  394. sys.argv.remove('-z')
  395. # reset callgrind after tree setup
  396. callgrind_zero = True
  397. except ValueError:
  398. pass
  399. initArgs(sys.argv)
  400. _etrees = []
  401. if import_lxml:
  402. from lxml import etree
  403. _etrees.append(etree)
  404. try:
  405. sys.argv.remove('-fel')
  406. except ValueError:
  407. pass
  408. else:
  409. # use fast element creation in lxml.etree
  410. etree.set_element_class_lookup(
  411. etree.ElementDefaultClassLookup())
  412. if len(sys.argv) > 1:
  413. if '-a' in sys.argv or '-c' in sys.argv:
  414. # 'all' or 'C-implementations' ?
  415. try:
  416. sys.argv.remove('-c')
  417. except ValueError:
  418. pass
  419. try:
  420. import cElementTree as cET
  421. _etrees.append(cET)
  422. except ImportError:
  423. try:
  424. import xml.etree.cElementTree as cET
  425. _etrees.append(cET)
  426. except ImportError:
  427. pass
  428. try:
  429. # 'all' ?
  430. sys.argv.remove('-a')
  431. except ValueError:
  432. pass
  433. else:
  434. try:
  435. from elementtree import ElementTree as ET
  436. _etrees.append(ET)
  437. except ImportError:
  438. try:
  439. from xml.etree import ElementTree as ET
  440. _etrees.append(ET)
  441. except ImportError:
  442. pass
  443. if not _etrees:
  444. print "No library to test. Exiting."
  445. sys.exit(1)
  446. print "Preparing test suites and trees ..."
  447. selected = set( sys.argv[1:] )
  448. benchmark_suites, benchmarks = \
  449. buildSuites(benchmark_class, _etrees, selected)
  450. print "Running benchmark on", ', '.join(b.lib_name
  451. for b in benchmark_suites)
  452. print
  453. printSetupTimes(benchmark_suites)
  454. if callgrind_zero:
  455. cmd = open("callgrind.cmd", 'w')
  456. cmd.write('+Instrumentation\n')
  457. cmd.write('Zero\n')
  458. cmd.close()
  459. runBenchmarks(benchmark_suites, benchmarks)