← 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: 2009-11-07 01:58:11 UTC
  • mto: This revision was merged to the branch mainline in revision 4842.
  • Revision ID: john@arbash-meinel.com-20091107015811-apybkqd40koa4b98
Get rid of the GraphIndexBuilder/BTreeBuilder._keys attribute.

This removes a set that grows O(N). We used it for some performance
stuff, because set.intersection is not efficient if other is not
a set. But we can work around that differently. It saves about 2MB
for a set with 100k items in it.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/btree_index.py
160
160
        :param value: The value to associate with the key. It may be any
161
161
            bytes as long as it does not contain \0 or \n.
162
162
        """
 
163
        # Ensure that 'key' is a StaticTuple
 
164
        key = static_tuple.StaticTuple.from_sequence(key).intern()
163
165
        # we don't care about absent_references
164
166
        node_refs, _ = self._check_key_ref_value(key, references, value)
165
167
        if key in self._nodes:
166
168
            raise errors.BadIndexDuplicateKey(key, self)
167
169
        self._nodes[key] = static_tuple.StaticTuple(node_refs, value)
168
 
        self._keys.add(key)
169
170
        if self._nodes_by_key is not None and self._key_length > 1:
170
171
            self._update_nodes_by_key(key, value, node_refs)
171
 
        if len(self._keys) < self._spill_at:
 
172
        if len(self._nodes) < self._spill_at:
172
173
            return
173
174
        self._spill_mem_keys_to_disk()
174
175
 
203
204
                self._backing_indices[backing_pos] = None
204
205
        else:
205
206
            self._backing_indices.append(new_backing)
206
 
        self._keys = set()
207
207
        self._nodes = {}
208
208
        self._nodes_by_key = None
209
209
 
463
463
            efficient order for the index (keys iteration order in this case).
464
464
        """
465
465
        keys = set(keys)
466
 
        local_keys = keys.intersection(self._keys)
 
466
        # Note: We don't use keys.intersection() here. If you read the C api,
 
467
        #       set.intersection(other) special cases when other is a set and
 
468
        #       will iterate the smaller of the two and lookup in the other.
 
469
        #       It does *not* do this for any other type (even dict, unlike
 
470
        #       some other set functions.) Since we expect keys is generally <<
 
471
        #       self._nodes, it is faster to iterate over it in a list
 
472
        #       comprehension
 
473
        nodes = self._nodes
 
474
        local_keys = [key for key in keys if key in nodes]
467
475
        if self.reference_lists:
468
476
            for key in local_keys:
469
 
                node = self._nodes[key]
 
477
                node = nodes[key]
470
478
                yield self, key, node[1], node[0]
471
479
        else:
472
480
            for key in local_keys:
473
 
                node = self._nodes[key]
 
481
                node = nodes[key]
474
482
                yield self, key, node[1]
475
483
        # Find things that are in backing indices that have not been handled
476
484
        # yet.
586
594
 
587
595
        For InMemoryGraphIndex the estimate is exact.
588
596
        """
589
 
        return len(self._keys) + sum(backing.key_count() for backing in
 
597
        return len(self._nodes) + sum(backing.key_count() for backing in
590
598
            self._backing_indices if backing is not None)
591
599
 
592
600
    def validate(self):