Merge lp:~jameinel/bzr/1.16-chkmap-updates into lp:~bzr/bzr/trunk-old

[John A Meinel]

[John A Meinel (jameinel)]

This is a slight rework of InternalNode._iter_nodes() to provide some shortcuts to finding nodes to return.

This changes the "initial commit" time for a mysql tree (7.8k files, 140MB) from 15.2s down to 13.7s on my machine (about 10% improvement.)

The big win here is that "CHKMap.apply_delta()" is adding all of the keys by calling .map() one at a time. For each of these, we have to look up what page it fits in, and possibly create the page. The lookup *was* being done by iterating all of the children of this InternalNode, and seeing if each child matched the search key.

This changes the search in 2 ways.

1) If we are searching for a single key, and that results in a _node_width search key, then we can do a single dict lookup for that item, and know if we have it or not, without building up *any* other structures.

2) If we are looking for multiple keys, we can aggregate their search keys. If at that point, all search keys are "_node_width", then again, we can do simple dict lookups for each key.

The main win here, is that root nodes are going to be 255-entries wide. So we avoid iterating across 255 items and doing a comparison, in exchange for doing a dict lookup for each item.

Part (1) is probably what makes the biggest improvement for 'bzr commit' time, but I think both are still useful improvments. (I'm guessing the latter will help stuff like 'bzr ls' more.)

Note that this, coupled with my fulltext commit changes bring initial commit time down to 12.7s, though --1.9 format commit is still around 11.7s. (But that is down from ~15s without those changes.)
So there are still bits of work to be done, but it is getting closer.

[Ian Clatworthy (ian-clatworthy)]

This looks pretty good. I want to take another look when I'm a bit more awake though before approving it.

One small thing: you changed one instance of "type(node) == tuple" to "type(node) is tuple" but you missed 2 other spots in that routine. I'll finish reviewing it tomorrow.

[John A Meinel (jameinel)]

> One small thing: you changed one instance of "type(node) == tuple" to
> "type(node) is tuple" but you missed 2 other spots in that routine. I'll
> finish reviewing it tomorrow.

Sure, I wasn't on a crusade against "== tuple", I just happened to see one and fixed it. I'm happy to do the others.

[Ian Clatworthy (ian-clatworthy)]

I'm awake now and it all still looks ok. :-) If you get a moment, tweaking the ''== tuple' to 'is tuple' would be nice as you're merging but it's not a big deal either way IIUIC.

review: Approve

=== modified file 'bzrlib/chk_map.py'
--- bzrlib/chk_map.py	2009-05-13 21:59:57 +0000
+++ bzrlib/chk_map.py	2009-06-15 15:35:24 +0000
@@ -121,7 +121,7 @@
 
     def _ensure_root(self):
         """Ensure that the root node is an object not a key."""
-        if type(self._root_node) == tuple:
+        if type(self._root_node) is tuple:
             # Demand-load the root
             self._root_node = self._get_node(self._root_node)
 
@@ -135,7 +135,7 @@
         :param node: A tuple key or node object.
         :return: A node object.
         """
-        if type(node) == tuple:
+        if type(node) is tuple:
             bytes = self._read_bytes(node)
             return _deserialise(bytes, node,
                 search_key_func=self._search_key_func)
@@ -465,7 +465,7 @@
 
     def _node_key(self, node):
         """Get the key for a node whether it's a tuple or node."""
-        if type(node) == tuple:
+        if type(node) is tuple:
             return node
         else:
             return node._key
@@ -491,7 +491,7 @@
 
         :return: The key of the root node.
         """
-        if type(self._root_node) == tuple:
+        if type(self._root_node) is tuple:
             # Already saved.
             return self._root_node
         keys = list(self._root_node.serialise(self._store))
@@ -955,34 +955,99 @@
         # 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 node.__class__ is tuple:
                     keys[node] = (prefix, None)
                 else:
                     yield node, None
-        else:
-            # XXX defaultdict ?
+        elif len(key_filter) == 1:
+            # Technically, this path could also be handled by the first check
+            # in 'self._node_width' in length_filters. However, we can handle
+            # this case without spending any time building up the
+            # prefix_to_keys, etc state.
+
+            # This is a bit ugly, but TIMEIT showed it to be by far the fastest
+            # 0.626us   list(key_filter)[0]
+            #       is a func() for list(), 2 mallocs, and a getitem
+            # 0.489us   [k for k in key_filter][0]
+            #       still has the mallocs, avoids the func() call
+            # 0.350us   iter(key_filter).next()
+            #       has a func() call, and mallocs an iterator
+            # 0.125us   for key in key_filter: pass
+            #       no func() overhead, might malloc an iterator
+            # 0.105us   for key in key_filter: break
+            #       no func() overhead, might malloc an iterator, probably
+            #       avoids checking an 'else' clause as part of the for
+            for key in key_filter:
+                break
+            search_prefix = self._search_prefix_filter(key)
+            if len(search_prefix) == 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_prefix]
+                except KeyError:
+                    # A given key can only match 1 child node, if it isn't
+                    # there, then we can just return nothing
+                    return
+                if node.__class__ is tuple:
+                    keys[node] = (search_prefix, [key])
+                else:
+                    # This is loaded, and the only thing that can match,
+                    # return
+                    yield node, [key]
+                    return
+        if not shortcut:
+            # First, convert all keys into a list of search prefixes
+            # Aggregate common prefixes, and track the keys they come from
             prefix_to_keys = {}
             length_filters = {}
             for key in key_filter:
-                search_key = self._search_prefix_filter(key)
+                search_prefix = self._search_prefix_filter(key)
                 length_filter = length_filters.setdefault(
-                                    len(search_key), set())
-                length_filter.add(search_key)
-                prefix_to_keys.setdefault(search_key, []).append(key)
-            length_filters = length_filters.items()
-            for prefix, node in self._items.iteritems():
-                node_key_filter = []
-                for length, length_filter in length_filters:
-                    sub_prefix = prefix[:length]
-                    if sub_prefix in length_filter:
-                        node_key_filter.extend(prefix_to_keys[sub_prefix])
-                if node_key_filter: # this key matched something, yield it
-                    if type(node) == tuple:
-                        keys[node] = (prefix, node_key_filter)
+                                    len(search_prefix), set())
+                length_filter.add(search_prefix)
+                prefix_to_keys.setdefault(search_prefix, []).append(key)
+
+            if (self._node_width in length_filters
+                and len(length_filters) == 1):
+                # all of the search prefixes match exactly _node_width. This
+                # means that everything is an exact match, and we can do a
+                # lookup into self._items, rather than iterating over the items
+                # dict.
+                search_prefixes = length_filters[self._node_width]
+                for search_prefix in search_prefixes:
+                    try:
+                        node = self._items[search_prefix]
+                    except KeyError:
+                        # We can ignore this one
+                        continue
+                    node_key_filter = prefix_to_keys[search_prefix]
+                    if node.__class__ is tuple:
+                        keys[node] = (search_prefix, node_key_filter)
                     else:
                         yield node, node_key_filter
+            else:
+                # The slow way. We walk every item in self._items, and check to
+                # see if there are any matches
+                length_filters = length_filters.items()
+                for prefix, node in self._items.iteritems():
+                    node_key_filter = []
+                    for length, length_filter in length_filters:
+                        sub_prefix = prefix[:length]
+                        if sub_prefix in length_filter:
+                            node_key_filter.extend(prefix_to_keys[sub_prefix])
+                    if node_key_filter: # this key matched something, yield it
+                        if node.__class__ is tuple:
+                            keys[node] = (prefix, node_key_filter)
+                        else:
+                            yield node, node_key_filter
         if keys:
             # Look in the page cache for some more bytes
             found_keys = set()
@@ -1117,7 +1182,7 @@
         :return: An iterable of the keys inserted by this operation.
         """
         for node in self._items.itervalues():
-            if type(node) == tuple:
+            if type(node) is tuple:
                 # Never deserialised.
                 continue
             if node._key is not None:
@@ -1134,7 +1199,7 @@
         lines.append('%s\n' % (self._search_prefix,))
         prefix_len = len(self._search_prefix)
         for prefix, node in sorted(self._items.items()):
-            if type(node) == tuple:
+            if type(node) is tuple:
                 key = node[0]
             else:
                 key = node._key[0]
@@ -1179,7 +1244,7 @@
             raise AssertionError("unserialised nodes have no refs.")
         refs = []
         for value in self._items.itervalues():
-            if type(value) == tuple:
+            if type(value) is tuple:
                 refs.append(value)
             else:
                 refs.append(value.key())

=== modified file 'bzrlib/tests/test_chk_map.py'
--- bzrlib/tests/test_chk_map.py	2009-05-13 21:59:57 +0000
+++ bzrlib/tests/test_chk_map.py	2009-06-15 15:35:24 +0000
@@ -1560,13 +1560,66 @@
         child.map(None, ("baz",), "val")
         node.add_node("b", child)
 
-        key_filter = (('foo',), ('fob',), ('bar',), ('baz',))
+        # Note that 'ram' doesn't match anything, so it should be freely
+        # ignored
+        key_filter = (('foo',), ('fob',), ('bar',), ('baz',), ('ram',))
         for child, node_key_filter in node._iter_nodes(None,
                                                        key_filter=key_filter):
-            # each child could matches two key filters, so make sure they were
+            # each child could match two key filters, so make sure they were
             # both included.
             self.assertEqual(2, len(node_key_filter))
 
+    def make_fo_fa_node(self):
+        node = InternalNode('f')
+        child = LeafNode()
+        child.set_maximum_size(100)
+        child.map(None, ("foo",), "val")
+        child.map(None, ("fob",), "val")
+        node.add_node('fo', child)
+        child = LeafNode()
+        child.set_maximum_size(100)
+        child.map(None, ("far",), "val")
+        child.map(None, ("faz",), "val")
+        node.add_node("fa", child)
+        return node
+
+    def test__iter_nodes_single_entry(self):
+        node = self.make_fo_fa_node()
+        key_filter = [('foo',)]
+        nodes = list(node._iter_nodes(None, key_filter=key_filter))
+        self.assertEqual(1, len(nodes))
+        self.assertEqual(key_filter, nodes[0][1])
+
+    def test__iter_nodes_single_entry_misses(self):
+        node = self.make_fo_fa_node()
+        key_filter = [('bar',)]
+        nodes = list(node._iter_nodes(None, key_filter=key_filter))
+        self.assertEqual(0, len(nodes))
+
+    def test__iter_nodes_mixed_key_width(self):
+        node = self.make_fo_fa_node()
+        key_filter = [('foo', 'bar'), ('foo',), ('fo',), ('b',)]
+        nodes = list(node._iter_nodes(None, key_filter=key_filter))
+        self.assertEqual(1, len(nodes))
+        matches = key_filter[:]
+        matches.remove(('b',))
+        self.assertEqual(sorted(matches), sorted(nodes[0][1]))
+
+    def test__iter_nodes_match_all(self):
+        node = self.make_fo_fa_node()
+        key_filter = [('foo', 'bar'), ('foo',), ('fo',), ('f',)]
+        nodes = list(node._iter_nodes(None, key_filter=key_filter))
+        self.assertEqual(2, len(nodes))
+
+    def test__iter_nodes_fixed_widths_and_misses(self):
+        node = self.make_fo_fa_node()
+        # foo and faa should both match one child, baz should miss
+        key_filter = [('foo',), ('faa',), ('baz',)]
+        nodes = list(node._iter_nodes(None, key_filter=key_filter))
+        self.assertEqual(2, len(nodes))
+        for node, matches in nodes:
+            self.assertEqual(1, len(matches))
+
     def test_iteritems_empty_new(self):
         node = InternalNode()
         self.assertEqual([], sorted(node.iteritems(None)))

=== modified file 'bzrlib/workingtree.py'
--- bzrlib/workingtree.py	2009-06-10 03:56:49 +0000
+++ bzrlib/workingtree.py	2009-06-15 15:35:24 +0000
@@ -451,7 +451,7 @@
             path = self.id2path(file_id)
         file_obj = self.get_file_byname(path, filtered=False)
         stat_value = _fstat(file_obj.fileno())
-        if self.supports_content_filtering() and filtered:
+        if filtered and self.supports_content_filtering():
             filters = self._content_filter_stack(path)
             file_obj = filtered_input_file(file_obj, filters)
         return (file_obj, stat_value)
@@ -462,7 +462,7 @@
     def get_file_byname(self, filename, filtered=True):
         path = self.abspath(filename)
         f = file(path, 'rb')
-        if self.supports_content_filtering() and filtered:
+        if filtered and self.supports_content_filtering():
             filters = self._content_filter_stack(filename)
             return filtered_input_file(f, filters)
         else: