[PATCH] do binary search for -r date:....

[Robert Widhopf-Fenk]

On Saturday, May 20, 2006 at 03:16:15, Olaf Conradi wrote:
> On Sat, May 20, 2006 at 12:58:54AM +0200, Robert Widhopf-Fenk wrote:
> Content-Description: message body text
> > 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.
> 
> +1 on binary searching
> 
> -1 on this implementation
> 
> These routines are very easy to make a mistake in.
[...]

In deed.

> This also demonstrates why I don't like while True loops ;)
> 
> I prefer the implementation of Guillaume Pinot, which uses python's
> bisect:

Attached is Guillaumes version against current bzr.dev with
added branch.lock_read() and branch.unlock() around the call
to bisect.

I was not aware of bisect and Guillaumes and your work on
this ... ;-/

Robert

-------------- next part --------------
=== modified file 'NEWS'
--- NEWS	
+++ NEWS	
@@ -1,6 +1,8 @@
 IN DEVELOPMENT
 
   IMPROVEMENTS:
+
+   * Speedup improvement for 'date:'-revision search. (Guillaume Pinot).
 
    * On Unix, detect terminal width using an ioctl not just $COLUMNS.
      Use terminal width for single-line logs from ``bzr log --line`` and

=== modified file 'bzrlib/revisionspec.py'
--- bzrlib/revisionspec.py	
+++ bzrlib/revisionspec.py	
@@ -17,6 +17,7 @@
 
 import datetime
 import re
+import bisect
 from bzrlib.errors import BzrError, NoSuchRevision, NoCommits
 
 _marker = []
@@ -248,6 +249,18 @@
 SPEC_TYPES.append(RevisionSpec_tag)
 
 
+class RevisionSpec_revs:
+    def __init__(self, revs, branch):
+        self.revs = revs
+        self.branch = branch
+    def __getitem__(self, index):
+        r = self.branch.repository.get_revision(self.revs[index])
+        # TODO: Handle timezone.
+        return datetime.datetime.fromtimestamp(r.timestamp)
+    def __len__(self):
+        return len(self.revs)
+
+
 class RevisionSpec_date(RevisionSpec):
     prefix = 'date:'
     _date_re = re.compile(
@@ -295,14 +308,14 @@
 
             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])
-            # TODO: Handle timezone.
-            dt = datetime.datetime.fromtimestamp(r.timestamp)
-            if first <= dt:
-                return RevisionInfo(branch, i+1)
-        return RevisionInfo(branch, None)
+
+        branch.lock_read()
+        rev = bisect.bisect(RevisionSpec_revs(revs, branch), dt)
+        branch.unlock()
+        if rev == len(revs):
+            return RevisionInfo(branch, None)
+        else:
+            return RevisionInfo(branch, rev + 1)
 
 SPEC_TYPES.append(RevisionSpec_date)
 

=== modified file 'bzrlib/tests/test_revisionnamespaces.py'
--- bzrlib/tests/test_revisionnamespaces.py	
+++ bzrlib/tests/test_revisionnamespaces.py	
@@ -50,6 +50,8 @@
 
         self.assertEquals(RevisionSpec('date:today').in_history(b),
                           (2, 'a at r-0-2'))
+        self.assertRaises(NoSuchRevision,
+                          RevisionSpec('date:tomorrow').in_history, b)
         self.assertEquals(RevisionSpec('date:yesterday').in_history(b),
                           (1, 'a at r-0-1'))
         self.assertEquals(RevisionSpec('before:date:today').in_history(b),