← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

  • Committer: John Arbash Meinel
  • Date: 2008-08-25 19:02:16 UTC
  • mto: This revision was merged to the branch mainline in revision 3688.
  • Revision ID: john@arbash-meinel.com-20080825190216-vdkyinz5p5e5s8kq
Two quick tweaks.
Change _iter_mem_nodes to use sorted order.
That way we can sort purely on the 'key' which
we know is the sort key anyway. This shaves off
a *lot* of time spent in 'sorted()'.
Also, if 'references' is in our output nodes,
we know we've already checked that it is a valid
key, so we don't need to check it again.
This shaves another 600ms or so for a bzr.dev tree.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/btree_index.py
169
169
        node_refs = []
170
170
        for reference_list in references:
171
171
            for reference in reference_list:
172
 
                self._check_key(reference)
 
172
                # If reference is in self._nodes, then we have already checked
 
173
                # it
 
174
                if reference not in self._nodes:
 
175
                    self._check_key(reference)
173
176
            node_refs.append(tuple(reference_list))
174
177
        if key in self._nodes:
175
178
            raise errors.BadIndexDuplicateKey(key, self)
190
193
            key_dict[key[-1]] = key_value
191
194
        if len(self._keys) < self._spill_at:
192
195
            return
193
 
        iterators_to_combine = [iter(sorted(self._iter_mem_nodes()))]
 
196
        iterators_to_combine = [self._iter_mem_nodes()]
194
197
        pos = -1
195
198
        for pos, backing in enumerate(self._backing_indices):
196
199
            if backing is None:
228
231
 
229
232
    def _iter_mem_nodes(self):
230
233
        """Iterate over the nodes held in memory."""
 
234
        nodes = self._nodes
231
235
        if self.reference_lists:
232
 
            return ((self, key, value, references)
233
 
                    for key, (references, value) in self._nodes.iteritems())
 
236
            for key in sorted(nodes):
 
237
                references, value = nodes[key]
 
238
                yield self, key, value, references
234
239
        else:
235
 
            return ((self, key, value)
236
 
                    for key, (references, value) in self._nodes.iteritems())
 
240
            for key in sorted(nodes):
 
241
                references, value = nodes[key]
 
242
                yield self, key, value
237
243
 
238
244
    def _iter_smallest(self, iterators_to_combine):
239
245
        if len(iterators_to_combine) == 1:
422
428
                "iter_all_entries scales with size of history.")
423
429
        # Doing serial rather than ordered would be faster; but this shouldn't
424
430
        # be getting called routinely anyway.
425
 
        iterators = [iter(sorted(self._iter_mem_nodes()))]
 
431
        iterators = [self._iter_mem_nodes()]
426
432
        for backing in self._backing_indices:
427
433
            if backing is not None:
428
434
                iterators.append(backing.iter_all_entries())