Merge lp:~jameinel/bzr/2.2-move-to-front-if-changed-562429 into lp:bzr

[John A Meinel]

I haven't actually confirmed that this fixes bug #562429, but it fits the symptoms, and it does fix a problem that *I* encountered.

Basically, spiv's new 'reorder indexes' code works well, but it tries to re-order even when the indexes are already at the beginning.

This is a pretty trivial change, but in my case:
  branch.revision_history()

drops from 1.4s down to 0.62s.

[Andrew Bennetts (spiv)]

Makes sense, and thanks for improving my code!

I wonder if it would be faster again to teach iter_entries not to call _move_to_front at all if len(hit_indices) == num. of times it looped through 'for index in self._indices'? Probably not much.

review: Approve

[lp:~jameinel/bzr/2.2-move-to-front-if-changed-562429]

5153. By John A Meinel on 2010-04-14

Avoid packing and unpacking the indices, and shortcut once you've found all
the interesting indices.

5154. By John A Meinel on 2010-04-14

Restore the indices_info variable.

Code is clearer, and isn't broken under -Dindex. :)

5155. By John A Meinel on 2010-04-14

Minor tweak

=== modified file 'NEWS'
--- NEWS	2010-04-14 04:35:47 +0000
+++ NEWS	2010-04-14 05:26:34 +0000
@@ -67,6 +67,10 @@
   read calls.  An incremental pull via plain HTTP takes half the time and
   bytes for a moderately large repository.  (Andrew Bennetts)
 
+* Index lookups only re-order the indexes when the hit files aren't
+  already first. Reduces the cost of reordering
+  (John Arbash Meinel, #562429)
+
 * Less code is loaded at startup.  (Cold-cache start time is about 10-20%
   less.)
   (Martin Pool, #553017)

=== modified file 'bzrlib/index.py'
--- bzrlib/index.py	2010-04-08 07:01:10 +0000
+++ bzrlib/index.py	2010-04-14 05:26:34 +0000
@@ -1418,6 +1418,10 @@
         _move_to_front propagates to all objects in self._sibling_indices by
         calling _move_to_front_by_name.
         """
+        if self._indices[:len(hit_indices)] == hit_indices:
+            # The 'hit_indices' are already at the front (and in the same
+            # order), no need to re-order
+            return
         hit_names = self._move_to_front_by_index(hit_indices)
         for sibling_idx in self._sibling_indices:
             sibling_idx._move_to_front_by_name(hit_names)
@@ -1431,19 +1435,27 @@
         if 'index' in debug.debug_flags:
             mutter('CombinedGraphIndex reordering: currently %r, promoting %r',
                    indices_info, hit_indices)
-        hit_indices_info = []
         hit_names = []
-        unhit_indices_info = []
-        for name, idx in indices_info:
+        unhit_names = []
+        new_hit_indices = []
+        unhit_indices = []
+
+        for offset, (name, idx) in enumerate(indices_info):
             if idx in hit_indices:
-                info = hit_indices_info
                 hit_names.append(name)
+                new_hit_indices.append(idx)
+                if len(new_hit_indices) == len(hit_indices):
+                    # We've found all of the hit entries, everything else is
+                    # unhit
+                    unhit_names.extend(self._index_names[offset+1:])
+                    unhit_indices.extend(self._indices[offset+1:])
+                    break
             else:
-                info = unhit_indices_info
-            info.append((name, idx))
-        final_info = hit_indices_info + unhit_indices_info
-        self._indices = [idx for (name, idx) in final_info]
-        self._index_names = [name for (name, idx) in final_info]
+                unhit_names.append(name)
+                unhit_indices.append(idx)
+
+        self._indices = new_hit_indices + unhit_indices
+        self._index_names = hit_names + unhit_names
         if 'index' in debug.debug_flags:
             mutter('CombinedGraphIndex reordered: %r', self._indices)
         return hit_names