/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

  • Committer: John Arbash Meinel
  • Date: 2010-08-03 20:56:39 UTC
  • mto: This revision was merged to the branch mainline in revision 5390.
  • Revision ID: john@arbash-meinel.com-20100803205639-k23colcozyd14440
Implement a custom parser for chk btree leaves.

The basic parsing is actually quicker (47us to build this new structure vs 110us)
Most likely because we have 1 malloc rather than N per leaf.
Memory size is also much smaller. We'll lose a little bit if we
convert back and forth from keys, etc.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/btree_index.py
33
33
    osutils,
34
34
    static_tuple,
35
35
    trace,
 
36
    transport,
36
37
    )
37
38
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
38
 
from bzrlib.transport import get_transport
39
39
 
40
40
 
41
41
_BTSIGNATURE = "B+Tree Graph Index 2\n"
193
193
            new_backing_file, size = self._spill_mem_keys_without_combining()
194
194
        # Note: The transport here isn't strictly needed, because we will use
195
195
        #       direct access to the new_backing._file object
196
 
        new_backing = BTreeGraphIndex(get_transport('.'), '<temp>', size)
 
196
        new_backing = BTreeGraphIndex(transport.get_transport('.'),
 
197
                                      '<temp>', size)
197
198
        # GC will clean up the file
198
199
        new_backing._file = new_backing_file
199
200
        if self._combine_backing_indices:
604
605
class _LeafNode(object):
605
606
    """A leaf node for a serialised B+Tree index."""
606
607
 
607
 
    __slots__ = ('keys', 'min_key', 'max_key')
 
608
    __slots__ = ('_keys', 'min_key', 'max_key')
608
609
 
609
610
    def __init__(self, bytes, key_length, ref_list_length):
610
611
        """Parse bytes to create a leaf node object."""
616
617
            self.max_key = key_list[-1][0]
617
618
        else:
618
619
            self.min_key = self.max_key = None
619
 
        self.keys = dict(key_list)
 
620
        self._keys = dict(key_list)
 
621
 
 
622
    def __len__(self):
 
623
        return len(self._keys)
 
624
 
 
625
    def __contains__(self, key):
 
626
        return key in self._keys
 
627
 
 
628
    def __getitem__(self, key):
 
629
        return self._keys[key]
 
630
 
 
631
    def all_items(self):
 
632
        """Return a sorted list of (key, (value, refs)) items"""
 
633
        items = self._keys.items()
 
634
        items.sort()
 
635
        return items
 
636
 
 
637
    def all_keys(self):
 
638
        """Return a sorted list of all keys."""
 
639
        keys = self._keys.keys()
 
640
        keys.sort()
 
641
        return keys
620
642
 
621
643
 
622
644
class _InternalNode(object):
671
693
        self._recommended_pages = self._compute_recommended_pages()
672
694
        self._root_node = None
673
695
        self._base_offset = offset
 
696
        self._leaf_klass = _LeafNode
674
697
        # Default max size is 100,000 leave values
675
698
        self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
676
699
        if unlimited_cache:
949
972
        """Cache directly from key => value, skipping the btree."""
950
973
        if self._leaf_value_cache is not None:
951
974
            for node in nodes.itervalues():
952
 
                for key, value in node.keys.iteritems():
 
975
                for key, value in node.all_items():
953
976
                    if key in self._leaf_value_cache:
954
977
                        # Don't add the rest of the keys, we've seen this node
955
978
                        # before.
979
1002
        if self._row_offsets[-1] == 1:
980
1003
            # There is only the root node, and we read that via key_count()
981
1004
            if self.node_ref_lists:
982
 
                for key, (value, refs) in sorted(self._root_node.keys.items()):
 
1005
                for key, (value, refs) in self._root_node.all_items():
983
1006
                    yield (self, key, value, refs)
984
1007
            else:
985
 
                for key, (value, refs) in sorted(self._root_node.keys.items()):
 
1008
                for key, (value, refs) in self._root_node.all_items():
986
1009
                    yield (self, key, value)
987
1010
            return
988
1011
        start_of_leaves = self._row_offsets[-2]
998
1021
        # for spilling index builds to disk.
999
1022
        if self.node_ref_lists:
1000
1023
            for _, node in nodes:
1001
 
                for key, (value, refs) in sorted(node.keys.items()):
 
1024
                for key, (value, refs) in node.all_items():
1002
1025
                    yield (self, key, value, refs)
1003
1026
        else:
1004
1027
            for _, node in nodes:
1005
 
                for key, (value, refs) in sorted(node.keys.items()):
 
1028
                for key, (value, refs) in node.all_items():
1006
1029
                    yield (self, key, value)
1007
1030
 
1008
1031
    @staticmethod
1169
1192
                continue
1170
1193
            node = nodes[node_index]
1171
1194
            for next_sub_key in sub_keys:
1172
 
                if next_sub_key in node.keys:
1173
 
                    value, refs = node.keys[next_sub_key]
 
1195
                if next_sub_key in node:
 
1196
                    value, refs = node[next_sub_key]
1174
1197
                    if self.node_ref_lists:
1175
1198
                        yield (self, next_sub_key, value, refs)
1176
1199
                    else:
1244
1267
            # sub_keys is all of the keys we are looking for that should exist
1245
1268
            # on this page, if they aren't here, then they won't be found
1246
1269
            node = nodes[node_index]
1247
 
            node_keys = node.keys
1248
1270
            parents_to_check = set()
1249
1271
            for next_sub_key in sub_keys:
1250
 
                if next_sub_key not in node_keys:
 
1272
                if next_sub_key not in node:
1251
1273
                    # This one is just not present in the index at all
1252
1274
                    missing_keys.add(next_sub_key)
1253
1275
                else:
1254
 
                    value, refs = node_keys[next_sub_key]
 
1276
                    value, refs = node[next_sub_key]
1255
1277
                    parent_keys = refs[ref_list_num]
1256
1278
                    parent_map[next_sub_key] = parent_keys
1257
1279
                    parents_to_check.update(parent_keys)
1264
1286
            while parents_to_check:
1265
1287
                next_parents_to_check = set()
1266
1288
                for key in parents_to_check:
1267
 
                    if key in node_keys:
1268
 
                        value, refs = node_keys[key]
 
1289
                    if key in node:
 
1290
                        value, refs = node[key]
1269
1291
                        parent_keys = refs[ref_list_num]
1270
1292
                        parent_map[key] = parent_keys
1271
1293
                        next_parents_to_check.update(parent_keys)
1545
1567
                    continue
1546
1568
            bytes = zlib.decompress(data)
1547
1569
            if bytes.startswith(_LEAF_FLAG):
1548
 
                node = _LeafNode(bytes, self._key_length, self.node_ref_lists)
 
1570
                node = self._leaf_klass(bytes, self._key_length,
 
1571
                                        self.node_ref_lists)
1549
1572
            elif bytes.startswith(_INTERNAL_FLAG):
1550
1573
                node = _InternalNode(bytes)
1551
1574
            else: