164
148
:param references: An iterable of iterables of keys. Each is a
165
149
reference to another key.
166
150
:param value: The value to associate with the key. It may be any
167
bytes as long as it does not contain \\0 or \\n.
151
bytes as long as it does not contain \0 or \n.
169
# Ensure that 'key' is a StaticTuple
170
key = static_tuple.StaticTuple.from_sequence(key).intern()
171
# we don't care about absent_references
172
node_refs, _ = self._check_key_ref_value(key, references, value)
173
if key in self._nodes:
174
raise errors.BadIndexDuplicateKey(key, self)
175
self._nodes[key] = static_tuple.StaticTuple(node_refs, value)
176
if self._nodes_by_key is not None and self._key_length > 1:
177
self._update_nodes_by_key(key, value, node_refs)
178
if len(self._nodes) < self._spill_at:
153
index.GraphIndexBuilder.add_node(self, key, value, references=references)
154
if len(self._keys) < self._spill_at:
180
self._spill_mem_keys_to_disk()
182
def _spill_mem_keys_to_disk(self):
183
"""Write the in memory keys down to disk to cap memory consumption.
185
If we already have some keys written to disk, we will combine them so
186
as to preserve the sorted order. The algorithm for combining uses
187
powers of two. So on the first spill, write all mem nodes into a
188
single index. On the second spill, combine the mem nodes with the nodes
189
on disk to create a 2x sized disk index and get rid of the first index.
190
On the third spill, create a single new disk index, which will contain
191
the mem nodes, and preserve the existing 2x sized index. On the fourth,
192
combine mem with the first and second indexes, creating a new one of
193
size 4x. On the fifth create a single new one, etc.
195
if self._combine_backing_indices:
196
(new_backing_file, size,
197
backing_pos) = self._spill_mem_keys_and_combine()
199
new_backing_file, size = self._spill_mem_keys_without_combining()
200
# Note: The transport here isn't strictly needed, because we will use
201
# direct access to the new_backing._file object
202
new_backing = BTreeGraphIndex(transport.get_transport_from_path('.'),
204
# GC will clean up the file
205
new_backing._file = new_backing_file
206
if self._combine_backing_indices:
207
if len(self._backing_indices) == backing_pos:
208
self._backing_indices.append(None)
209
self._backing_indices[backing_pos] = new_backing
210
for backing_pos in range(backing_pos):
211
self._backing_indices[backing_pos] = None
213
self._backing_indices.append(new_backing)
215
self._nodes_by_key = None
217
def _spill_mem_keys_without_combining(self):
218
return self._write_nodes(self._iter_mem_nodes(), allow_optimize=False)
220
def _spill_mem_keys_and_combine(self):
221
iterators_to_combine = [self._iter_mem_nodes()]
156
iterators_to_combine = [iter(sorted(self._iter_mem_nodes()))]
223
158
for pos, backing in enumerate(self._backing_indices):
224
159
if backing is None:
386
311
self.row_lengths = []
387
312
# Loop over all nodes adding them to the bottom row
388
313
# (rows[-1]). When we finish a chunk in a row,
389
# propagate the key that didn't fit (comes after the chunk) to the
314
# propogate the key that didn't fit (comes after the chunk) to the
390
315
# row above, transitively.
391
316
for node in node_iterator:
392
317
if key_count == 0:
393
318
# First key triggers the first row
394
319
rows.append(_LeafBuilderRow())
321
# TODO: Flattening the node into a string key and a line should
322
# probably be put into a pyrex function. We can do a quick
323
# iter over all the entries to determine the final length,
324
# and then do a single malloc() rather than lots of
325
# intermediate mallocs as we build everything up.
326
# ATM 3 / 13s are spent flattening nodes (10s is compressing)
396
327
string_key, line = _btree_serializer._flatten_node(node,
397
328
self.reference_lists)
398
self._add_key(string_key, line, rows, allow_optimize=allow_optimize)
329
self._add_key(string_key, line, rows)
399
330
for row in reversed(rows):
400
331
pad = (type(row) != _LeafBuilderRow)
401
332
row.finish_node(pad=pad)
333
result = tempfile.NamedTemporaryFile()
402
334
lines = [_BTSIGNATURE]
403
335
lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
404
336
lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
405
337
lines.append(_OPTION_LEN + str(key_count) + '\n')
406
338
row_lengths = [row.nodes for row in rows]
407
339
lines.append(_OPTION_ROW_LENGTHS + ','.join(map(str, row_lengths)) + '\n')
408
if row_lengths and row_lengths[-1] > 1:
409
result = tempfile.NamedTemporaryFile(prefix='bzr-index-')
411
result = cStringIO.StringIO()
412
340
result.writelines(lines)
413
341
position = sum(map(len, lines))
583
497
for value in key_dict.itervalues():
584
yield (self, ) + tuple(value)
498
yield (self, ) + value
586
500
yield (self, ) + key_dict
588
def _get_nodes_by_key(self):
589
if self._nodes_by_key is None:
591
if self.reference_lists:
592
for key, (references, value) in self._nodes.iteritems():
593
key_dict = nodes_by_key
594
for subkey in key[:-1]:
595
key_dict = key_dict.setdefault(subkey, {})
596
key_dict[key[-1]] = key, value, references
598
for key, (references, value) in self._nodes.iteritems():
599
key_dict = nodes_by_key
600
for subkey in key[:-1]:
601
key_dict = key_dict.setdefault(subkey, {})
602
key_dict[key[-1]] = key, value
603
self._nodes_by_key = nodes_by_key
604
return self._nodes_by_key
606
502
def key_count(self):
607
503
"""Return an estimate of the number of keys in this index.
609
505
For InMemoryGraphIndex the estimate is exact.
611
return len(self._nodes) + sum(backing.key_count() for backing in
507
return len(self._keys) + sum(backing.key_count() for backing in
612
508
self._backing_indices if backing is not None)
614
510
def validate(self):
615
511
"""In memory index's have no known corruption at the moment."""
618
class _LeafNode(dict):
514
class _LeafNode(object):
619
515
"""A leaf node for a serialised B+Tree index."""
621
__slots__ = ('min_key', 'max_key', '_keys')
623
517
def __init__(self, bytes, key_length, ref_list_length):
624
518
"""Parse bytes to create a leaf node object."""
625
519
# splitlines mangles the \r delimiters.. don't use it.
626
key_list = _btree_serializer._parse_leaf_lines(bytes,
627
key_length, ref_list_length)
629
self.min_key = key_list[0][0]
630
self.max_key = key_list[-1][0]
632
self.min_key = self.max_key = None
633
super(_LeafNode, self).__init__(key_list)
634
self._keys = dict(self)
637
"""Return a sorted list of (key, (value, refs)) items"""
643
"""Return a sorted list of all keys."""
520
self.keys = dict(_btree_serializer._parse_leaf_lines(bytes,
521
key_length, ref_list_length))
649
524
class _InternalNode(object):
650
525
"""An internal node for a serialised B+Tree index."""
652
__slots__ = ('keys', 'offset')
654
527
def __init__(self, bytes):
655
528
"""Parse bytes to create an internal node object."""
656
529
# splitlines mangles the \r delimiters.. don't use it.
685
556
the initial read (to read the root node header) can be done
686
557
without over-reading even on empty indices, and on small indices
687
558
allows single-IO to read the entire index.
688
:param unlimited_cache: If set to True, then instead of using an
689
LRUCache with size _NODE_CACHE_SIZE, we will use a dict and always
690
cache all leaf nodes.
691
:param offset: The start of the btree index data isn't byte 0 of the
692
file. Instead it starts at some point later.
694
560
self._transport = transport
695
561
self._name = name
696
562
self._size = size
697
563
self._file = None
698
self._recommended_pages = self._compute_recommended_pages()
564
self._page_size = transport.recommended_page_size()
699
565
self._root_node = None
700
self._base_offset = offset
701
self._leaf_factory = _LeafNode
702
566
# Default max size is 100,000 leave values
703
567
self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
705
self._leaf_node_cache = {}
706
self._internal_node_cache = {}
708
self._leaf_node_cache = lru_cache.LRUCache(_NODE_CACHE_SIZE)
709
# We use a FIFO here just to prevent possible blowout. However, a
710
# 300k record btree has only 3k leaf nodes, and only 20 internal
711
# nodes. A value of 100 scales to ~100*100*100 = 1M records.
712
self._internal_node_cache = fifo_cache.FIFOCache(100)
568
self._leaf_node_cache = lru_cache.LRUCache(_NODE_CACHE_SIZE)
569
self._internal_node_cache = lru_cache.LRUCache()
713
570
self._key_count = None
714
571
self._row_lengths = None
715
572
self._row_offsets = None # Start of each row, [-1] is the end
739
604
:return: A dict of {node_pos: node}
606
if len(nodes) > cache._max_cache:
607
trace.mutter('Requesting %s > %s nodes, not all will be cached',
608
len(nodes), cache._max_cache)
742
start_of_leaves = None
743
610
for node_pos, node in self._read_nodes(sorted(nodes)):
744
611
if node_pos == 0: # Special case
745
612
self._root_node = node
747
if start_of_leaves is None:
748
start_of_leaves = self._row_offsets[-2]
749
if node_pos < start_of_leaves:
750
self._internal_node_cache[node_pos] = node
752
self._leaf_node_cache[node_pos] = node
614
cache.add(node_pos, node)
753
615
found[node_pos] = node
756
def _compute_recommended_pages(self):
757
"""Convert transport's recommended_page_size into btree pages.
759
recommended_page_size is in bytes, we want to know how many _PAGE_SIZE
760
pages fit in that length.
762
recommended_read = self._transport.recommended_page_size()
763
recommended_pages = int(math.ceil(recommended_read /
765
return recommended_pages
767
def _compute_total_pages_in_index(self):
768
"""How many pages are in the index.
770
If we have read the header we will use the value stored there.
771
Otherwise it will be computed based on the length of the index.
773
if self._size is None:
774
raise AssertionError('_compute_total_pages_in_index should not be'
775
' called when self._size is None')
776
if self._root_node is not None:
777
# This is the number of pages as defined by the header
778
return self._row_offsets[-1]
779
# This is the number of pages as defined by the size of the index. They
780
# should be indentical.
781
total_pages = int(math.ceil(self._size / float(_PAGE_SIZE)))
784
def _expand_offsets(self, offsets):
785
"""Find extra pages to download.
787
The idea is that we always want to make big-enough requests (like 64kB
788
for http), so that we don't waste round trips. So given the entries
789
that we already have cached and the new pages being downloaded figure
790
out what other pages we might want to read.
792
See also doc/developers/btree_index_prefetch.txt for more details.
794
:param offsets: The offsets to be read
795
:return: A list of offsets to download
797
if 'index' in debug.debug_flags:
798
trace.mutter('expanding: %s\toffsets: %s', self._name, offsets)
800
if len(offsets) >= self._recommended_pages:
801
# Don't add more, we are already requesting more than enough
802
if 'index' in debug.debug_flags:
803
trace.mutter(' not expanding large request (%s >= %s)',
804
len(offsets), self._recommended_pages)
806
if self._size is None:
807
# Don't try anything, because we don't know where the file ends
808
if 'index' in debug.debug_flags:
809
trace.mutter(' not expanding without knowing index size')
811
total_pages = self._compute_total_pages_in_index()
812
cached_offsets = self._get_offsets_to_cached_pages()
813
# If reading recommended_pages would read the rest of the index, just
815
if total_pages - len(cached_offsets) <= self._recommended_pages:
816
# Read whatever is left
818
expanded = [x for x in xrange(total_pages)
819
if x not in cached_offsets]
821
expanded = range(total_pages)
822
if 'index' in debug.debug_flags:
823
trace.mutter(' reading all unread pages: %s', expanded)
826
if self._root_node is None:
827
# ATM on the first read of the root node of a large index, we don't
828
# bother pre-reading any other pages. This is because the
829
# likelyhood of actually reading interesting pages is very low.
830
# See doc/developers/btree_index_prefetch.txt for a discussion, and
831
# a possible implementation when we are guessing that the second
832
# layer index is small
833
final_offsets = offsets
835
tree_depth = len(self._row_lengths)
836
if len(cached_offsets) < tree_depth and len(offsets) == 1:
837
# We haven't read enough to justify expansion
838
# If we are only going to read the root node, and 1 leaf node,
839
# then it isn't worth expanding our request. Once we've read at
840
# least 2 nodes, then we are probably doing a search, and we
841
# start expanding our requests.
842
if 'index' in debug.debug_flags:
843
trace.mutter(' not expanding on first reads')
845
final_offsets = self._expand_to_neighbors(offsets, cached_offsets,
848
final_offsets = sorted(final_offsets)
849
if 'index' in debug.debug_flags:
850
trace.mutter('expanded: %s', final_offsets)
853
def _expand_to_neighbors(self, offsets, cached_offsets, total_pages):
854
"""Expand requests to neighbors until we have enough pages.
856
This is called from _expand_offsets after policy has determined that we
858
We only want to expand requests within a given layer. We cheat a little
859
bit and assume all requests will be in the same layer. This is true
860
given the current design, but if it changes this algorithm may perform
863
:param offsets: requested offsets
864
:param cached_offsets: offsets for pages we currently have cached
865
:return: A set() of offsets after expansion
867
final_offsets = set(offsets)
869
new_tips = set(final_offsets)
870
while len(final_offsets) < self._recommended_pages and new_tips:
874
first, end = self._find_layer_first_and_end(pos)
877
and previous not in cached_offsets
878
and previous not in final_offsets
879
and previous >= first):
880
next_tips.add(previous)
882
if (after < total_pages
883
and after not in cached_offsets
884
and after not in final_offsets
887
# This would keep us from going bigger than
888
# recommended_pages by only expanding the first offsets.
889
# However, if we are making a 'wide' request, it is
890
# reasonable to expand all points equally.
891
# if len(final_offsets) > recommended_pages:
893
final_offsets.update(next_tips)
897
def clear_cache(self):
898
"""Clear out any cached/memoized values.
900
This can be called at any time, but generally it is used when we have
901
extracted some information, but don't expect to be requesting any more
904
# Note that we don't touch self._root_node or self._internal_node_cache
905
# We don't expect either of those to be big, and it can save
906
# round-trips in the future. We may re-evaluate this if InternalNode
907
# memory starts to be an issue.
908
self._leaf_node_cache.clear()
910
def external_references(self, ref_list_num):
911
if self._root_node is None:
912
self._get_root_node()
913
if ref_list_num + 1 > self.node_ref_lists:
914
raise ValueError('No ref list %d, index has %d ref lists'
915
% (ref_list_num, self.node_ref_lists))
918
for node in self.iter_all_entries():
920
refs.update(node[3][ref_list_num])
923
def _find_layer_first_and_end(self, offset):
924
"""Find the start/stop nodes for the layer corresponding to offset.
926
:return: (first, end)
927
first is the first node in this layer
928
end is the first node of the next layer
931
for roffset in self._row_offsets:
938
def _get_offsets_to_cached_pages(self):
939
"""Determine what nodes we already have cached."""
940
cached_offsets = set(self._internal_node_cache.keys())
941
cached_offsets.update(self._leaf_node_cache.keys())
942
if self._root_node is not None:
943
cached_offsets.add(0)
944
return cached_offsets
946
def _get_root_node(self):
947
if self._root_node is None:
948
# We may not have a root node yet
949
self._get_internal_nodes([0])
950
return self._root_node
952
618
def _get_nodes(self, cache, node_indexes):
1004
663
"iter_all_entries scales with size of history.")
1005
664
if not self.key_count():
1007
if self._row_offsets[-1] == 1:
1008
# There is only the root node, and we read that via key_count()
1009
if self.node_ref_lists:
1010
for key, (value, refs) in self._root_node.all_items():
1011
yield (self, key, value, refs)
1013
for key, (value, refs) in self._root_node.all_items():
1014
yield (self, key, value)
1016
666
start_of_leaves = self._row_offsets[-2]
1017
667
end_of_leaves = self._row_offsets[-1]
1018
needed_offsets = range(start_of_leaves, end_of_leaves)
1019
if needed_offsets == [0]:
1020
# Special case when we only have a root node, as we have already
1022
nodes = [(0, self._root_node)]
1024
nodes = self._read_nodes(needed_offsets)
668
needed_nodes = range(start_of_leaves, end_of_leaves)
1025
669
# We iterate strictly in-order so that we can use this function
1026
670
# for spilling index builds to disk.
1027
671
if self.node_ref_lists:
1028
for _, node in nodes:
1029
for key, (value, refs) in node.all_items():
672
for _, node in self._read_nodes(needed_nodes):
673
for key, (value, refs) in sorted(node.keys.items()):
1030
674
yield (self, key, value, refs)
1032
for _, node in nodes:
1033
for key, (value, refs) in node.all_items():
676
for _, node in self._read_nodes(needed_nodes):
677
for key, (value, refs) in sorted(node.keys.items()):
1034
678
yield (self, key, value)
1115
759
output.append(cur_out)
1118
def _walk_through_internal_nodes(self, keys):
1119
"""Take the given set of keys, and find the corresponding LeafNodes.
1121
:param keys: An unsorted iterable of keys to search for
1122
:return: (nodes, index_and_keys)
1123
nodes is a dict mapping {index: LeafNode}
1124
keys_at_index is a list of tuples of [(index, [keys for Leaf])]
1126
# 6 seconds spent in miss_torture using the sorted() line.
1127
# Even with out of order disk IO it seems faster not to sort it when
1128
# large queries are being made.
1129
keys_at_index = [(0, sorted(keys))]
1131
for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
1132
node_indexes = [idx for idx, s_keys in keys_at_index]
1133
nodes = self._get_internal_nodes(node_indexes)
1135
next_nodes_and_keys = []
1136
for node_index, sub_keys in keys_at_index:
1137
node = nodes[node_index]
1138
positions = self._multi_bisect_right(sub_keys, node.keys)
1139
node_offset = next_row_start + node.offset
1140
next_nodes_and_keys.extend([(node_offset + pos, s_keys)
1141
for pos, s_keys in positions])
1142
keys_at_index = next_nodes_and_keys
1143
# We should now be at the _LeafNodes
1144
node_indexes = [idx for idx, s_keys in keys_at_index]
1146
# TODO: We may *not* want to always read all the nodes in one
1147
# big go. Consider setting a max size on this.
1148
nodes = self._get_leaf_nodes(node_indexes)
1149
return nodes, keys_at_index
1151
762
def iter_entries(self, keys):
1152
763
"""Iterate over keys within the index.
1191
802
needed_keys = keys
1192
803
if not needed_keys:
1194
nodes, nodes_and_keys = self._walk_through_internal_nodes(needed_keys)
805
# 6 seconds spent in miss_torture using the sorted() line.
806
# Even with out of order disk IO it seems faster not to sort it when
807
# large queries are being made.
808
needed_keys = sorted(needed_keys)
810
nodes_and_keys = [(0, needed_keys)]
812
for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
813
node_indexes = [idx for idx, s_keys in nodes_and_keys]
814
nodes = self._get_internal_nodes(node_indexes)
816
next_nodes_and_keys = []
817
for node_index, sub_keys in nodes_and_keys:
818
node = nodes[node_index]
819
positions = self._multi_bisect_right(sub_keys, node.keys)
820
node_offset = next_row_start + node.offset
821
next_nodes_and_keys.extend([(node_offset + pos, s_keys)
822
for pos, s_keys in positions])
823
nodes_and_keys = next_nodes_and_keys
824
# We should now be at the _LeafNodes
825
node_indexes = [idx for idx, s_keys in nodes_and_keys]
827
# TODO: We may *not* want to always read all the nodes in one
828
# big go. Consider setting a max size on this.
830
nodes = self._get_leaf_nodes(node_indexes)
1195
831
for node_index, sub_keys in nodes_and_keys:
1196
832
if not sub_keys:
1198
834
node = nodes[node_index]
1199
835
for next_sub_key in sub_keys:
1200
if next_sub_key in node:
1201
value, refs = node[next_sub_key]
836
if next_sub_key in node.keys:
837
value, refs = node.keys[next_sub_key]
1202
838
if self.node_ref_lists:
1203
839
yield (self, next_sub_key, value, refs)
1205
841
yield (self, next_sub_key, value)
1207
def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
1208
"""Find the parent_map information for the set of keys.
1210
This populates the parent_map dict and missing_keys set based on the
1211
queried keys. It also can fill out an arbitrary number of parents that
1212
it finds while searching for the supplied keys.
1214
It is unlikely that you want to call this directly. See
1215
"CombinedGraphIndex.find_ancestry()" for a more appropriate API.
1217
:param keys: A keys whose ancestry we want to return
1218
Every key will either end up in 'parent_map' or 'missing_keys'.
1219
:param ref_list_num: This index in the ref_lists is the parents we
1221
:param parent_map: {key: parent_keys} for keys that are present in this
1222
index. This may contain more entries than were in 'keys', that are
1223
reachable ancestors of the keys requested.
1224
:param missing_keys: keys which are known to be missing in this index.
1225
This may include parents that were not directly requested, but we
1226
were able to determine that they are not present in this index.
1227
:return: search_keys parents that were found but not queried to know
1228
if they are missing or present. Callers can re-query this index for
1229
those keys, and they will be placed into parent_map or missing_keys
1231
if not self.key_count():
1232
# We use key_count() to trigger reading the root node and
1233
# determining info about this BTreeGraphIndex
1234
# If we don't have any keys, then everything is missing
1235
missing_keys.update(keys)
1237
if ref_list_num >= self.node_ref_lists:
1238
raise ValueError('No ref list %d, index has %d ref lists'
1239
% (ref_list_num, self.node_ref_lists))
1241
# The main trick we are trying to accomplish is that when we find a
1242
# key listing its parents, we expect that the parent key is also likely
1243
# to sit on the same page. Allowing us to expand parents quickly
1244
# without suffering the full stack of bisecting, etc.
1245
nodes, nodes_and_keys = self._walk_through_internal_nodes(keys)
1247
# These are parent keys which could not be immediately resolved on the
1248
# page where the child was present. Note that we may already be
1249
# searching for that key, and it may actually be present [or known
1250
# missing] on one of the other pages we are reading.
1252
# We could try searching for them in the immediate previous or next
1253
# page. If they occur "later" we could put them in a pending lookup
1254
# set, and then for each node we read thereafter we could check to
1255
# see if they are present.
1256
# However, we don't know the impact of keeping this list of things
1257
# that I'm going to search for every node I come across from here on
1259
# It doesn't handle the case when the parent key is missing on a
1260
# page that we *don't* read. So we already have to handle being
1261
# re-entrant for that.
1262
# Since most keys contain a date string, they are more likely to be
1263
# found earlier in the file than later, but we would know that right
1264
# away (key < min_key), and wouldn't keep searching it on every other
1265
# page that we read.
1266
# Mostly, it is an idea, one which should be benchmarked.
1267
parents_not_on_page = set()
1269
for node_index, sub_keys in nodes_and_keys:
1272
# sub_keys is all of the keys we are looking for that should exist
1273
# on this page, if they aren't here, then they won't be found
1274
node = nodes[node_index]
1275
parents_to_check = set()
1276
for next_sub_key in sub_keys:
1277
if next_sub_key not in node:
1278
# This one is just not present in the index at all
1279
missing_keys.add(next_sub_key)
1281
value, refs = node[next_sub_key]
1282
parent_keys = refs[ref_list_num]
1283
parent_map[next_sub_key] = parent_keys
1284
parents_to_check.update(parent_keys)
1285
# Don't look for things we've already found
1286
parents_to_check = parents_to_check.difference(parent_map)
1287
# this can be used to test the benefit of having the check loop
1289
# parents_not_on_page.update(parents_to_check)
1291
while parents_to_check:
1292
next_parents_to_check = set()
1293
for key in parents_to_check:
1295
value, refs = node[key]
1296
parent_keys = refs[ref_list_num]
1297
parent_map[key] = parent_keys
1298
next_parents_to_check.update(parent_keys)
1300
# This parent either is genuinely missing, or should be
1301
# found on another page. Perf test whether it is better
1302
# to check if this node should fit on this page or not.
1303
# in the 'everything-in-one-pack' scenario, this *not*
1304
# doing the check is 237ms vs 243ms.
1305
# So slightly better, but I assume the standard 'lots
1306
# of packs' is going to show a reasonable improvement
1307
# from the check, because it avoids 'going around
1308
# again' for everything that is in another index
1309
# parents_not_on_page.add(key)
1310
# Missing for some reason
1311
if key < node.min_key:
1312
# in the case of bzr.dev, 3.4k/5.3k misses are
1313
# 'earlier' misses (65%)
1314
parents_not_on_page.add(key)
1315
elif key > node.max_key:
1316
# This parent key would be present on a different
1318
parents_not_on_page.add(key)
1320
# assert key != node.min_key and key != node.max_key
1321
# If it was going to be present, it would be on
1322
# *this* page, so mark it missing.
1323
missing_keys.add(key)
1324
parents_to_check = next_parents_to_check.difference(parent_map)
1325
# Might want to do another .difference() from missing_keys
1326
# parents_not_on_page could have been found on a different page, or be
1327
# known to be missing. So cull out everything that has already been
1329
search_keys = parents_not_on_page.difference(
1330
parent_map).difference(missing_keys)
1333
843
def iter_entries_prefix(self, keys):
1334
844
"""Iterate over keys within the index using prefix matching.
1513
1019
"""Read some nodes from disk into the LRU cache.
1515
1021
This performs a readv to get the node data into memory, and parses each
1516
node, then yields it to the caller. The nodes are requested in the
1022
node, the yields it to the caller. The nodes are requested in the
1517
1023
supplied order. If possible doing sort() on the list before requesting
1518
1024
a read may improve performance.
1520
1026
:param nodes: The nodes to read. 0 - first node, 1 - second node etc.
1523
# may be the byte string of the whole file
1525
# list of (offset, length) regions of the file that should, evenually
1526
# be read in to data_ranges, either from 'bytes' or from the transport
1528
base_offset = self._base_offset
1529
1030
for index in nodes:
1530
offset = (index * _PAGE_SIZE)
1031
offset = index * _PAGE_SIZE
1531
1032
size = _PAGE_SIZE
1533
1034
# Root node - special case
1535
1036
size = min(_PAGE_SIZE, self._size)
1537
# The only case where we don't know the size, is for very
1538
# small indexes. So we read the whole thing
1539
bytes = self._transport.get_bytes(self._name)
1540
num_bytes = len(bytes)
1541
self._size = num_bytes - base_offset
1542
# the whole thing should be parsed out of 'bytes'
1543
ranges = [(start, min(_PAGE_SIZE, num_bytes - start))
1544
for start in xrange(base_offset, num_bytes, _PAGE_SIZE)]
1038
stream = self._transport.get(self._name)
1039
start = stream.read(_PAGE_SIZE)
1040
# Avoid doing this again
1041
self._size = len(start)
1042
size = min(_PAGE_SIZE, self._size)
1547
if offset > self._size:
1548
raise AssertionError('tried to read past the end'
1549
' of the file %s > %s'
1550
% (offset, self._size))
1551
1044
size = min(size, self._size - offset)
1552
ranges.append((base_offset + offset, size))
1045
ranges.append((offset, size))
1555
elif bytes is not None:
1556
# already have the whole file
1557
data_ranges = [(start, bytes[start:start+size])
1558
for start, size in ranges]
1559
elif self._file is None:
1048
if self._file is None:
1560
1049
data_ranges = self._transport.readv(self._name, ranges)
1562
1051
data_ranges = []
added
removed
bzrlib/btree_index.py
