/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/treebuilder.py

  • Committer: John Arbash Meinel
  • Date: 2010-08-04 07:14:54 UTC
  • mto: This revision was merged to the branch mainline in revision 5390.
  • Revision ID: john@arbash-meinel.com-20100804071454-bfhbwrqes7sabvay
Populate the offsets array.

This cuts down the number of bisections dramatically, basically by pre-caching
the first step. On real-world data it drops the steps from 587 to 156.
Or from 4.9/key to 1.3/key.
This drops the time to lookup from 23.7us to 20.3us.
Note that (k in dict) is 12.2us. I do wish we were just a bit closer to that.
However, with _LeafNode inherited from dict, I get 26us, so
maybe there is something in the interpreter that does a PyDict_CheckExact
call, and there isn't much we can do about it.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/treebuilder.py
1
 
# Copyright (C) 2006 Canonical Ltd
 
1
# Copyright (C) 2006, 2008, 2009, 2010 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
16
16
 
17
17
"""TreeBuilder helper class.
18
18
 
19
 
TreeBuilders are used to build trees of various shapres or properties. This
 
19
TreeBuilders are used to build trees of various shapes or properties. This
20
20
can be extremely useful in testing for instance.
21
21
"""
22
22