Rev 3855: (jam) Make BTreeBuilder.iter_entries faster by using a smaller set in file:///home/pqm/archives/thelove/bzr/%2Btrunk/

[Canonical.com Patch Queue Manager]

At file:///home/pqm/archives/thelove/bzr/%2Btrunk/

------------------------------------------------------------
revno: 3855
revision-id: pqm at pqm.ubuntu.com-20081126060051-cwcyil3w3ek8llsh
parent: pqm at pqm.ubuntu.com-20081125203528-0vccybk8fasrh3fn
parent: john at arbash-meinel.com-20081125185538-7lj7din373541s0r
committer: Canonical.com Patch Queue Manager <pqm at pqm.ubuntu.com>
branch nick: +trunk
timestamp: Wed 2008-11-26 06:00:51 +0000
message:
  (jam) Make BTreeBuilder.iter_entries faster by using a smaller set
  	for difference_update.
modified:
  bzrlib/btree_index.py          index.py-20080624222253-p0x5f92uyh5hw734-7
    ------------------------------------------------------------
    revno: 3847.2.3
    revision-id: john at arbash-meinel.com-20081125185538-7lj7din373541s0r
    parent: john at arbash-meinel.com-20081125182954-1d0u8uli0jphejy9
    committer: John Arbash Meinel <john at arbash-meinel.com>
    branch nick: builder_iter_entries
    timestamp: Tue 2008-11-25 12:55:38 -0600
    message:
      Bring back the shortcut
    modified:
      bzrlib/btree_index.py          index.py-20080624222253-p0x5f92uyh5hw734-7
    ------------------------------------------------------------
    revno: 3847.2.2
    revision-id: john at arbash-meinel.com-20081125182954-1d0u8uli0jphejy9
    parent: john at arbash-meinel.com-20081124212832-6j0b39iecfiip8nn
    committer: John Arbash Meinel <john at arbash-meinel.com>
    branch nick: builder_iter_entries
    timestamp: Tue 2008-11-25 12:29:54 -0600
    message:
      Rather than skipping the difference_update entirely, just restrict it to the intersection keys.
    modified:
      bzrlib/btree_index.py          index.py-20080624222253-p0x5f92uyh5hw734-7
    ------------------------------------------------------------
    revno: 3847.2.1
    revision-id: john at arbash-meinel.com-20081124212832-6j0b39iecfiip8nn
    parent: pqm at pqm.ubuntu.com-20081121221932-44m8c85k5ri8h5hg
    committer: John Arbash Meinel <john at arbash-meinel.com>
    branch nick: builder_iter_entries
    timestamp: Mon 2008-11-24 15:28:32 -0600
    message:
      Shortcut BTreeBuilder.iter_entries when there are no backing indices.
      It turns out that the keys.difference_update was taking a significant amount of time.
      When branching bzr.dev from a stacked into a standalone, 84/180 seconds was spent
      just in that difference_update.
      My guess is that difference_update always scales with the number of entries in the
      target set, even when the source set is small.
    modified:
      bzrlib/btree_index.py          index.py-20080624222253-p0x5f92uyh5hw734-7
=== modified file 'bzrlib/btree_index.py'
--- a/bzrlib/btree_index.py	2008-11-09 18:40:17 +0000
+++ b/bzrlib/btree_index.py	2008-11-25 18:55:38 +0000
@@ -431,15 +431,21 @@
             efficient order for the index (keys iteration order in this case).
         """
         keys = set(keys)
+        local_keys = keys.intersection(self._keys)
         if self.reference_lists:
-            for key in keys.intersection(self._keys):
+            for key in local_keys:
                 node = self._nodes[key]
                 yield self, key, node[1], node[0]
         else:
-            for key in keys.intersection(self._keys):
+            for key in local_keys:
                 node = self._nodes[key]
                 yield self, key, node[1]
-        keys.difference_update(self._keys)
+        # Find things that are in backing indices that have not been handled
+        # yet.
+        if not self._backing_indices:
+            return # We won't find anything there either
+        # Remove all of the keys that we found locally
+        keys.difference_update(local_keys)
         for backing in self._backing_indices:
             if backing is None:
                 continue