Rev 26: Add an LRU cache for leaf values rather than leaf nodes. in http://bzr.arbash-meinel.com/plugins/index2
John Arbash Meinel
john at arbash-meinel.com
Wed Jul 2 20:50:08 BST 2008
At http://bzr.arbash-meinel.com/plugins/index2
------------------------------------------------------------
revno: 26
revision-id: john at arbash-meinel.com-20080702195000-hgd1exet98nfxt7e
parent: john at arbash-meinel.com-20080702182656-cudnvqe2kfstxits
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: index2
timestamp: Wed 2008-07-02 14:50:00 -0500
message:
Add an LRU cache for leaf values rather than leaf nodes.
Add a bunch more hit/miss rate metrics.
It turns out that the critical path for iter_ancestry() is the miss rate.
However, when searching, any node that misses in an index is not requested
again from that index. However, it does cause us to load the leaf node
where it *might* have hit. Causing us to repeatedly load the missing nodes.
So we do need to cache leaf nodes, so we can answer 'missing' results quickly.
Blooms don't answer the question fast enough yet, or at least they
don't have a very high hit rate for filtering out new requests.
Out of 58,000 actual misses, blooms only caught 6000.
-------------- next part --------------
=== modified file 'btree_index.py'
--- a/btree_index.py 2008-07-02 18:26:56 +0000
+++ b/btree_index.py 2008-07-02 19:50:00 +0000
@@ -41,6 +41,9 @@
_PAGE_SIZE = 4096
bloom_hits = 0
+leaf_value_hits = 0
+missing_hits = 0 # Found this key cached as missing
+miss_attempts = 0 # Missed this entry while looking up
class NodeBloom(BloomSHA1):
@@ -356,6 +359,9 @@
return nodes, bloom
+_key_not_present = object()
+
+
class BTreeGraphIndex(object):
"""Access to nodes via the standard GraphIndex interface for B+Tree's.
@@ -363,7 +369,7 @@
memory except when very large walks are done.
"""
- _default_use_blooms = False
+ _default_use_blooms = True
def __init__(self, transport, name, size=None):
"""Create a B+Tree index object on the index name.
@@ -381,6 +387,8 @@
self._size = size
self._page_size = transport.recommended_page_size()
self._root_node = None
+ # Default max size is 100,000 leave values
+ self._leaf_value_cache = lru_cache.LRUCache(1000*1000)
self._leaf_node_cache = lru_cache.LRUCache()
self._internal_node_cache = lru_cache.LRUCache()
self._key_count = None
@@ -453,7 +461,14 @@
def _get_leaf_nodes(self, node_indexes):
"""Get a bunch of nodes, from cache or disk."""
- return self._get_nodes(self._leaf_node_cache, node_indexes)
+ # nodes = self._get_nodes(self._leaf_node_cache, node_indexes)
+ found = {}
+ for node_pos, node in self._read_nodes(sorted(node_indexes)):
+ found[node_pos] = node
+ for key, value in node.keys.iteritems():
+ if key not in self._leaf_value_cache:
+ self._leaf_value_cache[key] = value
+ return found
def iter_all_entries(self):
"""Iterate over all keys within the index.
@@ -566,22 +581,39 @@
# in sorted order anyway. Though we could filter at the bloom level
# without sorting. *But* is the top level bloom going to restrict
# enough keys that we care?
- if self._use_blooms:
- keys = frozenset(keys)
- else:
- keys = sorted(keys)
+ keys = frozenset(keys)
if not keys:
return
if not self.key_count():
return
- nodes_and_keys = [(0, keys)]
+ # Find all the keys that are already in our value cache
+ global leaf_value_hits, missing_hits, miss_attempts
+ needed_keys = []
+ for key in keys:
+ value = self._leaf_value_cache.get(key, None)
+ if value is not None:
+ if value is not _key_not_present:
+ leaf_value_hits += 1
+ # This key is known not to be here, skip it
+ value, refs = value
+ if self.node_ref_lists:
+ yield (self, key, value, refs)
+ else:
+ yield (self, key, value)
+ else:
+ missing_hits += 1
+ else:
+ needed_keys.append(key)
+ needed_keys = sorted(needed_keys)
+
+ nodes_and_keys = [(0, needed_keys)]
row_offset = 0
if self._use_blooms:
global bloom_hits
if len(self._row_lengths) > 1:
# no internal nodes, and thus no blooms in a length-1 b+tree.
- bloom_raw_offsets = NodeBloom.get_raw_offsets(keys)
+ bloom_raw_offsets = NodeBloom.get_raw_offsets(needed_keys)
for row_length in self._row_lengths[:-1]:
node_indexes = [idx for idx, s_keys in nodes_and_keys]
nodes = self._get_internal_nodes(node_indexes)
@@ -596,10 +628,8 @@
remaining_sub_keys = [sub_key for sub_key in sub_keys
if node.bloom.contains_raw_offset(bloom_raw_offsets[sub_key])]
bloom_hits += len(sub_keys) - len(remaining_sub_keys)
- if isinstance(sub_keys, frozenset):
- sub_keys = sorted(remaining_sub_keys)
- else:
- sub_keys = remaining_sub_keys
+ sub_keys = remaining_sub_keys
+ # For misses at this level, do we want to cache that fact?
positions = self._multi_bisect_right(sub_keys, node.keys)
node_offset = row_offset + node.offset
next_nodes_and_keys.extend([(node_offset + pos, s_keys)
@@ -621,6 +651,9 @@
yield (self, key, value, refs)
else:
yield (self, key, value)
+ else:
+ miss_attempts += 1
+ self._leaf_value_cache[key] = _key_not_present
def iter_entries_prefix(self, keys):
"""Iterate over keys within the index using prefix matching.
=== modified file 'indexbench.py'
--- a/indexbench.py 2008-07-02 18:17:46 +0000
+++ b/indexbench.py 2008-07-02 19:50:00 +0000
@@ -13,6 +13,7 @@
from bzrlib.graph import Graph
from bzrlib.commands import Command
from bzrlib.option import Option, ListOption
+from bzrlib.revision import NULL_REVISION
from bzrlib.lsprof import profile
@@ -42,15 +43,27 @@
def profile_fixture(class_name, fixture_name, fixture, *args, **kwargs):
"""Profile a fixture."""
- _, stats = profile(fixture, *args, **kwargs)
- output = file(class_name + '.' + fixture_name + '.callgrind', 'wb')
- stats.calltree(output)
- output.close()
+ value, stats = profile(fixture, *args, **kwargs)
+ fname = class_name + '.' + fixture_name + '.txt'
+ stats.save(fname)
+ return value
def run_fixture(class_name, fixture_name, fixture, *args, **kwargs):
- fixture(*args, **kwargs)
-
+ return fixture(*args, **kwargs)
+
+def reset_hit_counts():
+ btree_index.bloom_hits = 0
+ btree_index.missing_hits = 0
+ btree_index.leaf_value_hits = 0
+ btree_index.miss_attempts = 0
+
+def hits():
+ return "bloom(%d) missing(%d) leaf_value(%d) miss_attempts(%d)" % (
+ btree_index.bloom_hits,
+ btree_index.missing_hits,
+ btree_index.leaf_value_hits,
+ btree_index.miss_attempts)
def time_index(names, source, factory, builder, target, label, name_keys,
text_keys, use_drop_cache, fixtures, lsprof, tip_revision_id, ancestry):
@@ -104,7 +117,7 @@
text_names = [name for name in names if name.endswith('.tix')]
text_indices = [index for name, index in iter_indices(text_names, target, factory)]
text_index = CombinedGraphIndex(text_indices)
- btree_index.bloom_hits = 0
+ reset_hit_counts()
drop_cache()
now = time.time()
# VersionedFiles can do multi-key extraction, so we can use that.
@@ -113,34 +126,59 @@
vf = KnitVersionedFiles(index, None)
vf._get_components_positions(text_keys)
finish = time.time()
- print "%s: get_components_positions(%d) in %0.3f, bloom(%d)" % (label, len(text_keys),
- finish - now, btree_index.bloom_hits)
+ print "%s: get_components_positions(%d) in %0.3f, %s" % (label, len(text_keys),
+ finish - now, hits())
# follow a revision graph
if 'revision' in fixtures:
- rev_names = [name for name in names if name.endswith('.rix')]
- # reopen indices
- rev_indices = [index for name, index in iter_indices(rev_names, target, factory)]
- rev_index = CombinedGraphIndex(rev_indices)
- btree_index.bloom_hits = 0
- drop_cache()
- now = time.time()
- # VersionedFiles can do multi-key extraction, so we can use that.
- index = _KnitGraphIndex(rev_index, lambda:True, deltas=True, parents=True)
- vf = KnitVersionedFiles(index, None)
- graph = Graph(vf)
- test_ancestry = dict(graph.iter_ancestry([tip_revision_id]))
- finish = time.time()
- print "%s: search_from_revid in %0.3f, bloom(%d)" % (label, finish - now, btree_index.bloom_hits)
- if test_ancestry != ancestry:
+ test_ancestry = run(label, 'revision', revision_search, label,
+ drop_cache, names, target, factory,
+ tip_revision_id)
+ # ancestry that we were given is plain {revision_id: (parent_ids,)}
+ # test_ancestry is {(revision_id,): ((parent_ids,),)} so we need to
+ # adapt it back
+ filtered_test_ancestry = {}
+ for rev_key, parent_keys in test_ancestry.iteritems():
+ if parent_keys is None:
+ filtered_test_ancestry[rev_key[0]] = None
+ else:
+ # ancestry also has null: in its entries, so we need to add
+ # that in
+ parent_ids = tuple([p[0] for p in parent_keys])
+ if not parent_ids:
+ parent_ids = (NULL_REVISION,)
+ filtered_test_ancestry[rev_key[0]] = parent_ids
+ filtered_test_ancestry[NULL_REVISION] = ()
+ if filtered_test_ancestry != ancestry:
print "**** Warning ancestry incorrect."
+ import pdb; pdb.set_trace()
# pathologic miss-lookups: ask each index of each type for the keys held by the
# others of that type
if 'miss' in fixtures:
run(label, 'miss', miss_torture, label, drop_cache, names, target, factory, name_keys)
print "%s: -------Done---------" % (label,)
+
+def revision_search(label, drop_cache, names, target, factory, tip_revision_id):
+ rev_names = [name for name in names if name.endswith('.rix')]
+ # reopen indices
+ rev_indices = [index for name, index in iter_indices(rev_names, target, factory)]
+ rev_index = CombinedGraphIndex(rev_indices)
+ reset_hit_counts()
+ drop_cache()
+ now = time.time()
+ # VersionedFiles can do multi-key extraction, so we can use that.
+ index = _KnitGraphIndex(rev_index, lambda:True, deltas=True, parents=True)
+ vf = KnitVersionedFiles(index, None)
+ graph = Graph(vf)
+ test_ancestry = dict(graph.iter_ancestry([(tip_revision_id,)]))
+ finish = time.time()
+ print "%s: search_from_revid in %0.3f found %d, %s" % (label,
+ finish - now, len(test_ancestry), hits())
+ return test_ancestry
+
+
def miss_torture(label, drop_cache, names, target, factory, name_keys):
- btree_index.bloom_hits = 0
+ reset_hit_counts()
drop_cache()
now = time.time()
for name, index in iter_indices(names, target, factory):
@@ -152,7 +190,7 @@
for node in index.iter_entries(other_keys):
pass
finish = time.time()
- print "%s: miss torture in %0.3f, bloom(%d)" % (label, finish - now, btree_index.bloom_hits)
+ print "%s: miss torture in %0.3f, %s" % (label, finish - now, hits)
class cmd_indexbench(Command):
More information about the bazaar-commits
mailing list