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

Proposed by John A Meinel on 2009-06-05
Status: Merged
Approved by: Ian Clatworthy on 2009-06-15
Approved revision: 4415
Merged at revision: not available
Proposed branch: lp:~jameinel/bzr/1.16-chkmap-updates
Merge into: lp:~bzr/bzr/trunk-old
Diff against target: 278 lines
To merge this branch: bzr merge lp:~jameinel/bzr/1.16-chkmap-updates
Reviewer Review Type Date Requested Status
Ian Clatworthy 2009-06-05 Approve on 2009-06-15
Review via email: mp+7113@code.launchpad.net
To post a comment you must log in.
John A Meinel (jameinel) wrote :

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.

lp:~jameinel/bzr/1.16-chkmap-updates updated on 2009-06-08
4416. By John A Meinel on 2009-06-05

Move the boolean check to the first part of the if statement

Ian Clatworthy (ian-clatworthy) wrote :

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) wrote :

> 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) wrote :

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
lp:~jameinel/bzr/1.16-chkmap-updates updated on 2009-06-15
4417. By John A Meinel on 2009-06-15

Fix some type() == tuple to be 'type() is tuple' or '.__class__ is tuple'

Preview Diff

[H/L] Next/Prev Comment, [J/K] Next/Prev File, [N/P] Next/Prev Hunk
1=== modified file 'bzrlib/chk_map.py'
2--- bzrlib/chk_map.py 2009-05-13 21:59:57 +0000
3+++ bzrlib/chk_map.py 2009-06-15 15:35:24 +0000
4@@ -121,7 +121,7 @@
5
6 def _ensure_root(self):
7 """Ensure that the root node is an object not a key."""
8- if type(self._root_node) == tuple:
9+ if type(self._root_node) is tuple:
10 # Demand-load the root
11 self._root_node = self._get_node(self._root_node)
12
13@@ -135,7 +135,7 @@
14 :param node: A tuple key or node object.
15 :return: A node object.
16 """
17- if type(node) == tuple:
18+ if type(node) is tuple:
19 bytes = self._read_bytes(node)
20 return _deserialise(bytes, node,
21 search_key_func=self._search_key_func)
22@@ -465,7 +465,7 @@
23
24 def _node_key(self, node):
25 """Get the key for a node whether it's a tuple or node."""
26- if type(node) == tuple:
27+ if type(node) is tuple:
28 return node
29 else:
30 return node._key
31@@ -491,7 +491,7 @@
32
33 :return: The key of the root node.
34 """
35- if type(self._root_node) == tuple:
36+ if type(self._root_node) is tuple:
37 # Already saved.
38 return self._root_node
39 keys = list(self._root_node.serialise(self._store))
40@@ -955,34 +955,99 @@
41 # prefix is the key in self._items to use, key_filter is the key_filter
42 # entries that would match this node
43 keys = {}
44+ shortcut = False
45 if key_filter is None:
46+ # yielding all nodes, yield whatever we have, and queue up a read
47+ # for whatever we are missing
48+ shortcut = True
49 for prefix, node in self._items.iteritems():
50- if type(node) == tuple:
51+ if node.__class__ is tuple:
52 keys[node] = (prefix, None)
53 else:
54 yield node, None
55- else:
56- # XXX defaultdict ?
57+ elif len(key_filter) == 1:
58+ # Technically, this path could also be handled by the first check
59+ # in 'self._node_width' in length_filters. However, we can handle
60+ # this case without spending any time building up the
61+ # prefix_to_keys, etc state.
62+
63+ # This is a bit ugly, but TIMEIT showed it to be by far the fastest
64+ # 0.626us list(key_filter)[0]
65+ # is a func() for list(), 2 mallocs, and a getitem
66+ # 0.489us [k for k in key_filter][0]
67+ # still has the mallocs, avoids the func() call
68+ # 0.350us iter(key_filter).next()
69+ # has a func() call, and mallocs an iterator
70+ # 0.125us for key in key_filter: pass
71+ # no func() overhead, might malloc an iterator
72+ # 0.105us for key in key_filter: break
73+ # no func() overhead, might malloc an iterator, probably
74+ # avoids checking an 'else' clause as part of the for
75+ for key in key_filter:
76+ break
77+ search_prefix = self._search_prefix_filter(key)
78+ if len(search_prefix) == self._node_width:
79+ # This item will match exactly, so just do a dict lookup, and
80+ # see what we can return
81+ shortcut = True
82+ try:
83+ node = self._items[search_prefix]
84+ except KeyError:
85+ # A given key can only match 1 child node, if it isn't
86+ # there, then we can just return nothing
87+ return
88+ if node.__class__ is tuple:
89+ keys[node] = (search_prefix, [key])
90+ else:
91+ # This is loaded, and the only thing that can match,
92+ # return
93+ yield node, [key]
94+ return
95+ if not shortcut:
96+ # First, convert all keys into a list of search prefixes
97+ # Aggregate common prefixes, and track the keys they come from
98 prefix_to_keys = {}
99 length_filters = {}
100 for key in key_filter:
101- search_key = self._search_prefix_filter(key)
102+ search_prefix = self._search_prefix_filter(key)
103 length_filter = length_filters.setdefault(
104- len(search_key), set())
105- length_filter.add(search_key)
106- prefix_to_keys.setdefault(search_key, []).append(key)
107- length_filters = length_filters.items()
108- for prefix, node in self._items.iteritems():
109- node_key_filter = []
110- for length, length_filter in length_filters:
111- sub_prefix = prefix[:length]
112- if sub_prefix in length_filter:
113- node_key_filter.extend(prefix_to_keys[sub_prefix])
114- if node_key_filter: # this key matched something, yield it
115- if type(node) == tuple:
116- keys[node] = (prefix, node_key_filter)
117+ len(search_prefix), set())
118+ length_filter.add(search_prefix)
119+ prefix_to_keys.setdefault(search_prefix, []).append(key)
120+
121+ if (self._node_width in length_filters
122+ and len(length_filters) == 1):
123+ # all of the search prefixes match exactly _node_width. This
124+ # means that everything is an exact match, and we can do a
125+ # lookup into self._items, rather than iterating over the items
126+ # dict.
127+ search_prefixes = length_filters[self._node_width]
128+ for search_prefix in search_prefixes:
129+ try:
130+ node = self._items[search_prefix]
131+ except KeyError:
132+ # We can ignore this one
133+ continue
134+ node_key_filter = prefix_to_keys[search_prefix]
135+ if node.__class__ is tuple:
136+ keys[node] = (search_prefix, node_key_filter)
137 else:
138 yield node, node_key_filter
139+ else:
140+ # The slow way. We walk every item in self._items, and check to
141+ # see if there are any matches
142+ length_filters = length_filters.items()
143+ for prefix, node in self._items.iteritems():
144+ node_key_filter = []
145+ for length, length_filter in length_filters:
146+ sub_prefix = prefix[:length]
147+ if sub_prefix in length_filter:
148+ node_key_filter.extend(prefix_to_keys[sub_prefix])
149+ if node_key_filter: # this key matched something, yield it
150+ if node.__class__ is tuple:
151+ keys[node] = (prefix, node_key_filter)
152+ else:
153+ yield node, node_key_filter
154 if keys:
155 # Look in the page cache for some more bytes
156 found_keys = set()
157@@ -1117,7 +1182,7 @@
158 :return: An iterable of the keys inserted by this operation.
159 """
160 for node in self._items.itervalues():
161- if type(node) == tuple:
162+ if type(node) is tuple:
163 # Never deserialised.
164 continue
165 if node._key is not None:
166@@ -1134,7 +1199,7 @@
167 lines.append('%s\n' % (self._search_prefix,))
168 prefix_len = len(self._search_prefix)
169 for prefix, node in sorted(self._items.items()):
170- if type(node) == tuple:
171+ if type(node) is tuple:
172 key = node[0]
173 else:
174 key = node._key[0]
175@@ -1179,7 +1244,7 @@
176 raise AssertionError("unserialised nodes have no refs.")
177 refs = []
178 for value in self._items.itervalues():
179- if type(value) == tuple:
180+ if type(value) is tuple:
181 refs.append(value)
182 else:
183 refs.append(value.key())
184
185=== modified file 'bzrlib/tests/test_chk_map.py'
186--- bzrlib/tests/test_chk_map.py 2009-05-13 21:59:57 +0000
187+++ bzrlib/tests/test_chk_map.py 2009-06-15 15:35:24 +0000
188@@ -1560,13 +1560,66 @@
189 child.map(None, ("baz",), "val")
190 node.add_node("b", child)
191
192- key_filter = (('foo',), ('fob',), ('bar',), ('baz',))
193+ # Note that 'ram' doesn't match anything, so it should be freely
194+ # ignored
195+ key_filter = (('foo',), ('fob',), ('bar',), ('baz',), ('ram',))
196 for child, node_key_filter in node._iter_nodes(None,
197 key_filter=key_filter):
198- # each child could matches two key filters, so make sure they were
199+ # each child could match two key filters, so make sure they were
200 # both included.
201 self.assertEqual(2, len(node_key_filter))
202
203+ def make_fo_fa_node(self):
204+ node = InternalNode('f')
205+ child = LeafNode()
206+ child.set_maximum_size(100)
207+ child.map(None, ("foo",), "val")
208+ child.map(None, ("fob",), "val")
209+ node.add_node('fo', child)
210+ child = LeafNode()
211+ child.set_maximum_size(100)
212+ child.map(None, ("far",), "val")
213+ child.map(None, ("faz",), "val")
214+ node.add_node("fa", child)
215+ return node
216+
217+ def test__iter_nodes_single_entry(self):
218+ node = self.make_fo_fa_node()
219+ key_filter = [('foo',)]
220+ nodes = list(node._iter_nodes(None, key_filter=key_filter))
221+ self.assertEqual(1, len(nodes))
222+ self.assertEqual(key_filter, nodes[0][1])
223+
224+ def test__iter_nodes_single_entry_misses(self):
225+ node = self.make_fo_fa_node()
226+ key_filter = [('bar',)]
227+ nodes = list(node._iter_nodes(None, key_filter=key_filter))
228+ self.assertEqual(0, len(nodes))
229+
230+ def test__iter_nodes_mixed_key_width(self):
231+ node = self.make_fo_fa_node()
232+ key_filter = [('foo', 'bar'), ('foo',), ('fo',), ('b',)]
233+ nodes = list(node._iter_nodes(None, key_filter=key_filter))
234+ self.assertEqual(1, len(nodes))
235+ matches = key_filter[:]
236+ matches.remove(('b',))
237+ self.assertEqual(sorted(matches), sorted(nodes[0][1]))
238+
239+ def test__iter_nodes_match_all(self):
240+ node = self.make_fo_fa_node()
241+ key_filter = [('foo', 'bar'), ('foo',), ('fo',), ('f',)]
242+ nodes = list(node._iter_nodes(None, key_filter=key_filter))
243+ self.assertEqual(2, len(nodes))
244+
245+ def test__iter_nodes_fixed_widths_and_misses(self):
246+ node = self.make_fo_fa_node()
247+ # foo and faa should both match one child, baz should miss
248+ key_filter = [('foo',), ('faa',), ('baz',)]
249+ nodes = list(node._iter_nodes(None, key_filter=key_filter))
250+ self.assertEqual(2, len(nodes))
251+ for node, matches in nodes:
252+ self.assertEqual(1, len(matches))
253+
254 def test_iteritems_empty_new(self):
255 node = InternalNode()
256 self.assertEqual([], sorted(node.iteritems(None)))
257
258=== modified file 'bzrlib/workingtree.py'
259--- bzrlib/workingtree.py 2009-06-10 03:56:49 +0000
260+++ bzrlib/workingtree.py 2009-06-15 15:35:24 +0000
261@@ -451,7 +451,7 @@
262 path = self.id2path(file_id)
263 file_obj = self.get_file_byname(path, filtered=False)
264 stat_value = _fstat(file_obj.fileno())
265- if self.supports_content_filtering() and filtered:
266+ if filtered and self.supports_content_filtering():
267 filters = self._content_filter_stack(path)
268 file_obj = filtered_input_file(file_obj, filters)
269 return (file_obj, stat_value)
270@@ -462,7 +462,7 @@
271 def get_file_byname(self, filename, filtered=True):
272 path = self.abspath(filename)
273 f = file(path, 'rb')
274- if self.supports_content_filtering() and filtered:
275+ if filtered and self.supports_content_filtering():
276 filters = self._content_filter_stack(filename)
277 return filtered_input_file(f, filters)
278 else: