[PATCH] do binary search for -r date:....
Robert Widhopf-Fenk
hack at robf.de
Fri May 19 23:58:54 BST 2006
The current implementation does a linear search to find
the specified date, which is dead slow for a tree with
may revisions.
The attached patch does a binary search to find it.
Actually "branch.repository.get_revision" is responsible for
the slowness. I really wonder why it is that slow to get
a revision from a local storage ... is it really reading the
knit index for each call to "branch.repository.get_revision"?
-------------- next part --------------
=== modified file 'bzrlib/revisionspec.py'
--- bzrlib/revisionspec.py
+++ bzrlib/revisionspec.py
@@ -296,13 +296,29 @@
dt = datetime.datetime(year=year, month=month, day=day,
hour=hour, minute=minute, second=second)
first = dt
- for i in range(len(revs)):
- r = branch.repository.get_revision(revs[i])
+ left = 1
+ right = len(revs)
+ while True:
+ middle = (left + right) / 2
+ # indexes for revs start with 0
+ r = branch.repository.get_revision(revs[middle - 1])
# TODO: Handle timezone.
dt = datetime.datetime.fromtimestamp(r.timestamp)
- if first <= dt:
- return RevisionInfo(branch, i+1)
- return RevisionInfo(branch, None)
+ if left == right:
+ break
+ if first < dt:
+ right = middle - 1
+ elif first > dt:
+ left = middle + 1
+ else:
+ break
+ # take next element as we want revisions after the given date
+ if dt < first:
+ middle = middle + 1
+ if middle <= len(revs):
+ return RevisionInfo(branch, middle)
+ else:
+ return RevisionInfo(branch, None)
SPEC_TYPES.append(RevisionSpec_date)
More information about the bazaar
mailing list