← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/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/index.py
93
93
        :param key_elements: The number of bytestrings in each key.
94
94
        """
95
95
        self.reference_lists = reference_lists
96
 
        self._keys = set()
97
96
        # A dict of {key: (absent, ref_lists, value)}
98
97
        self._nodes = {}
 
98
        # Keys that are referenced but not actually present in this index
 
99
        self._absent_keys = set()
99
100
        self._nodes_by_key = None
100
101
        self._key_length = key_elements
101
102
        self._optimize_for_size = False
165
166
            return
166
167
        key_dict = self._nodes_by_key
167
168
        if self.reference_lists:
168
 
            key_value = key, value, node_refs
 
169
            key_value = StaticTuple(key, value, node_refs)
169
170
        else:
170
 
            key_value = key, value
 
171
            key_value = StaticTuple(key, value)
171
172
        for subkey in key[:-1]:
172
173
            key_dict = key_dict.setdefault(subkey, {})
173
174
        key_dict[key[-1]] = key_value
226
227
            # There may be duplicates, but I don't think it is worth worrying
227
228
            # about
228
229
            self._nodes[reference] = ('a', (), '')
 
230
        self._absent_keys.update(absent_references)
 
231
        self._absent_keys.discard(key)
229
232
        self._nodes[key] = ('', node_refs, value)
230
 
        self._keys.add(key)
231
233
        if self._nodes_by_key is not None and self._key_length > 1:
232
234
            self._update_nodes_by_key(key, value, node_refs)
233
235
 
242
244
        lines = [_SIGNATURE]
243
245
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
244
246
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
245
 
        lines.append(_OPTION_LEN + str(len(self._keys)) + '\n')
 
247
        key_count = len(self._nodes) - len(self._absent_keys)
 
248
        lines.append(_OPTION_LEN + str(key_count) + '\n')
246
249
        prefix_length = sum(len(x) for x in lines)
247
250
        # references are byte offsets. To avoid having to do nasty
248
251
        # polynomial work to resolve offsets (references to later in the
462
465
                node_value = value
463
466
            self._nodes[key] = node_value
464
467
        # cache the keys for quick set intersections
465
 
        self._keys = set(self._nodes)
466
468
        if trailers != 1:
467
469
            # there must be one line - the empty trailer line.
468
470
            raise errors.BadIndexData(self)
483
485
            raise ValueError('No ref list %d, index has %d ref lists'
484
486
                % (ref_list_num, self.node_ref_lists))
485
487
        refs = set()
486
 
        for key, (value, ref_lists) in self._nodes.iteritems():
 
488
        nodes = self._nodes
 
489
        for key, (value, ref_lists) in nodes.iteritems():
487
490
            ref_list = ref_lists[ref_list_num]
488
 
            refs.update(ref_list)
489
 
        return refs - self._keys
 
491
            refs.update([ref for ref in ref_list if ref not in nodes])
 
492
        return refs
490
493
 
491
494
    def _get_nodes_by_key(self):
492
495
        if self._nodes_by_key is None:
619
622
 
620
623
    def _iter_entries_from_total_buffer(self, keys):
621
624
        """Iterate over keys when the entire index is parsed."""
622
 
        keys = keys.intersection(self._keys)
 
625
        # Note: See the note in BTreeBuilder.iter_entries for why we don't use
 
626
        #       .intersection() here
 
627
        nodes = self._nodes
 
628
        keys = [key for key in keys if key in nodes]
623
629
        if self.node_ref_lists:
624
630
            for key in keys:
625
 
                value, node_refs = self._nodes[key]
 
631
                value, node_refs = nodes[key]
626
632
                yield self, key, value, node_refs
627
633
        else:
628
634
            for key in keys:
629
 
                yield self, key, self._nodes[key]
 
635
                yield self, key, nodes[key]
630
636
 
631
637
    def iter_entries(self, keys):
632
638
        """Iterate over keys within the index.
1506
1512
            defined order for the result iteration - it will be in the most
1507
1513
            efficient order for the index (keys iteration order in this case).
1508
1514
        """
1509
 
        keys = set(keys)
 
1515
        # Note: See BTreeBuilder.iter_entries for an explanation of why we
 
1516
        #       aren't using set().intersection() here
 
1517
        nodes = self._nodes
 
1518
        keys = [key for key in keys if key in nodes]
1510
1519
        if self.reference_lists:
1511
 
            for key in keys.intersection(self._keys):
1512
 
                node = self._nodes[key]
 
1520
            for key in keys:
 
1521
                node = nodes[key]
1513
1522
                if not node[0]:
1514
1523
                    yield self, key, node[2], node[1]
1515
1524
        else:
1516
 
            for key in keys.intersection(self._keys):
1517
 
                node = self._nodes[key]
 
1525
            for key in keys:
 
1526
                node = nodes[key]
1518
1527
                if not node[0]:
1519
1528
                    yield self, key, node[2]
1520
1529
 
1594
1603
 
1595
1604
        For InMemoryGraphIndex the estimate is exact.
1596
1605
        """
1597
 
        return len(self._keys)
 
1606
        return len(self._nodes) - len(self._absent_keys)
1598
1607
 
1599
1608
    def validate(self):
1600
1609
        """In memory index's have no known corruption at the moment."""