[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