Rev 4414: Add a shortcut for the case when we are searching for a single full-width key. in http://bazaar.launchpad.net/~jameinel/bzr/1.16-chkmap-updates

[John Arbash Meinel]

At http://bazaar.launchpad.net/~jameinel/bzr/1.16-chkmap-updates

------------------------------------------------------------
revno: 4414
revision-id: john at arbash-meinel.com-20090605150139-osvqaqcv0bk55cuc
parent: pqm at pqm.ubuntu.com-20090605081039-abvojdsxjbg5i4ff
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-chkmap-updates
timestamp: Fri 2009-06-05 10:01:39 -0500
message:
  Add a shortcut for the case when we are searching for a single full-width key.
  This saves approx 14.0s => 12.5s for 'initial commit' of a MySQL tree.
  Mostly it is about improving 'InternalNode.map()' performance for a very large 'apply_delta'.
  Needs further testing to ensure it handles edge cases.
  Also, we could probably tweak the generic code path a bit as well.
  We could probably split the lookups into full-width matches versus sub-matches,
  and then combine keys based on the search prefixes being identical, etc.
-------------- next part --------------
=== modified file 'bzrlib/chk_map.py'
--- a/bzrlib/chk_map.py	2009-05-13 21:59:57 +0000
+++ b/bzrlib/chk_map.py	2009-06-05 15:01:39 +0000
@@ -955,13 +955,40 @@
         # prefix is the key in self._items to use, key_filter is the key_filter
         # entries that would match this node
         keys = {}
+        shortcut = False
         if key_filter is None:
+            # yielding all nodes, yield whatever we have, and queue up a read
+            # for whatever we are missing
+            shortcut = True
             for prefix, node in self._items.iteritems():
-                if type(node) == tuple:
+                if type(node) is tuple:
                     keys[node] = (prefix, None)
                 else:
                     yield node, None
-        else:
+        elif len(key_filter) == 1:
+            # We are looking for a single item
+            # Sometimes it is a set, sometimes it is a list
+            key = list(key_filter)[0]
+            search_key = self._search_prefix_filter(key)
+            if len(search_key) == self._node_width:
+                # This item will match exactly, so just do a dict lookup, and
+                # see what we can return
+                shortcut = True
+                try:
+                    node = self._items[search_key]
+                except KeyError:
+                    # A given key can only match 1 child node, if it isn't
+                    # there, then we can just return nothing
+                    return
+                else:
+                    if type(node) is tuple:
+                        keys[node] = (search_key, [key])
+                    else:
+                        # This is loaded, and the only thing that can match,
+                        # return
+                        yield node, [key]
+                        return
+        if not shortcut:
             # XXX defaultdict ?
             prefix_to_keys = {}
             length_filters = {}
@@ -971,6 +998,8 @@
                                     len(search_key), set())
                 length_filter.add(search_key)
                 prefix_to_keys.setdefault(search_key, []).append(key)
+            if len(length_filters) > 1:
+                import pdb; pdb.set_trace()
             length_filters = length_filters.items()
             for prefix, node in self._items.iteritems():
                 node_key_filter = []