Rev 3770: A bit of doc updates, start putting in tests for current behavior. in http://bzr.arbash-meinel.com/branches/bzr/1.8-dev/btree_buffer

John Arbash Meinel john at arbash-meinel.com
Tue Oct 14 20:02:46 BST 2008


At http://bzr.arbash-meinel.com/branches/bzr/1.8-dev/btree_buffer

------------------------------------------------------------
revno: 3770
revision-id: john at arbash-meinel.com-20081014190226-xns3yk2nti9p96zd
parent: john at arbash-meinel.com-20081009205450-z4k6rnvj5j1tqcmu
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: btree_buffer
timestamp: Tue 2008-10-14 14:02:26 -0500
message:
  A bit of doc updates, start putting in tests for current behavior.
-------------- next part --------------
=== modified file 'bzrlib/btree_index.py'
--- a/bzrlib/btree_index.py	2008-10-09 20:54:50 +0000
+++ b/bzrlib/btree_index.py	2008-10-14 19:02:26 +0000
@@ -607,7 +607,7 @@
         self._name = name
         self._size = size
         self._file = None
-        self._page_size = transport.recommended_page_size()
+        self._recommended_pages = self._compute_recommended_pages()
         self._root_node = None
         # Default max size is 100,000 leave values
         self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
@@ -666,6 +666,35 @@
             found[node_pos] = node
         return found
 
+    def _compute_recommended_pages(self):
+        """Given the transport's recommended_page_size, determine num pages."""
+        recommended_read = self._transport.recommended_page_size()
+        recommended_pages = int(math.ceil(recommended_read /
+                                          float(_PAGE_SIZE)))
+        return recommended_pages
+
+    def _compute_num_pages(self):
+        """Determine the offset to the last page in this index."""
+        if self._size is None:
+            raise AssertionError('_compute_num_pages should not be called'
+                                 ' when self._size is None')
+        if self._root_node is not None:
+            # This is the number of pages as defined by the header
+            return self._row_offsets[-1]
+        # This is the number of pages as defined by the size of the index. They
+        # should be indentical.
+        num_pages = int(math.ceil(self._size / float(_PAGE_SIZE)))
+        return num_pages
+
+    def _get_cached_nodes(self):
+        """Determine what nodes we already have cached."""
+        # XXX: Update the LRUCache interface to have a .keys() attribute
+        cached_nodes = set(self._internal_node_cache._cache.keys())
+        cached_nodes.update(self._leaf_node_cache._cache.keys())
+        if self._root_node is not None:
+            cached_nodes.add(0)
+        return cached_nodes
+
     def _expand_nodes(self, node_indexes):
         """Find extra nodes to download.
 
@@ -675,94 +704,85 @@
         out what other pages we might want to read.
 
         :param node_indexes: The nodes that have been requested to read.
-        # :param recommended_size: The size of download we want, this assumes
-        #     that readv() is accomplished in a single round trip (which is true
-        #     for http and bzr+ssh, and sftp uses async to get close
-        #     performance.)
-        # :param max_page: The last possible page to read, possibly max_size is
-        # better?
         :return: A new list of nodes to download
         """
-        trace.note('request: %s\tnodes: %s', self._name[-14:], node_indexes)
-        # return node_indexes
+        if 'index' in debug.debug_flags:
+            trace.mutter('expanding: %s\tnodes: %s', self._name, node_indexes)
 
-        # TODO: This could be cached
-        recommended_read = self._transport.recommended_page_size()
-        recommended_pages = int(math.ceil(recommended_read /
-                                          float(_PAGE_SIZE)))
-        # Disable the algorithm
-        # recommended_pages = 1
-        if len(node_indexes) >= recommended_pages:
+        if len(node_indexes) >= self._recommended_pages:
             # Don't add more, we are already requesting more than enough
+            if 'index' in debug.debug_flags:
+                trace.mutter('  not expanding large request (%s >= %s)',
+                             len(node_indexes), self._recommended_pages)
             return node_indexes
         if self._size is None:
             # Don't try anything, because we don't know where the file ends
+            if 'index' in debug.debug_flags:
+                trace.mutter('  not expanding without knowing index size')
             return node_indexes
+        # TODO: Should this be cached instead?
+        num_pages = self._compute_num_pages()
         # The idea here is to get nodes "next to" the ones we are already
         # getting.
-        max_page = int(math.ceil(self._size / float(_PAGE_SIZE)))
-        # XXX: Update the LRUCache interface to have a .keys() attribute
-        cached_nodes = set(self._internal_node_cache._cache.keys())
-        cached_nodes.update(self._leaf_node_cache._cache.keys())
-        if self._root_node is not None:
-            cached_nodes.add(0)
+        cached_nodes = self._get_cached_nodes()
 
-        # if len(cached_nodes) < 2: # We haven't read enough to justify expansion
+        # if len(cached_nodes) < 2:
+        #     # We haven't read enough to justify expansion
         #     return node_indexes
 
         # If reading recommended_pages would read the rest of the index, just
         # do so.
-        if max_page - len(cached_nodes) <= recommended_pages:
-            # Just read the whole thing
-            # NOTE: this breaks a little bit with the distinction between index
-            # nodes and leaf nodes (as they are cached separately). It is
-            # still worthwhile to read it all, but we need to figure out what
-            # cache we should really put things in when we are done.
-            # However, we may not have read the index header yet to know where
-            # the internal nodes break from where the leaf nodes. We are sure
-            # to know *after* we've done the read.
-            # This also does the wrong thing if there are bloom pages.
-
-            # Further, this gives the wrong results because we have 2 caches to
-            # worry about...
+        if num_pages - len(cached_nodes) <= self._recommended_pages:
+            # Read whatever is left
             if cached_nodes:
-                return [x for x in xrange(max_page) if x not in cached_nodes]
-            return range(max_page)
+                expanded = [x for x in xrange(num_pages)
+                               if x not in cached_nodes]
+            else:
+                expanded = range(num_pages)
+            if 'index' in debug.debug_flags:
+                trace.mutter('  reading all unread pages: %s', expanded)
+            return expanded
 
-        needed_nodes = recommended_pages - len(node_indexes)
+        needed_nodes = self._recommended_pages - len(node_indexes)
         final_nodes = set(node_indexes)
-        if node_indexes == [0]:
-            # Special case when we are reading the root node, just read the
-            # first N pages along with the root node
+        if self._root_node is None:
+            # ATM on the first read of the root node of a large index, we don't
+            # bother pre-reading any other pages. This is because the
+            # likelyhood of actually reading interesting pages is very low.
+            # See doc/developers/btree_index_prefetch.txt for a discussion, and
+            # a possible implementation when we are guessing that the second
+            # layer index is small
             final_nodes = node_indexes
-            # for index in xrange(1, max_page):
-            #     if index not in final_nodes and index not in cached_nodes:
-            #         final_nodes.add(index)
-            #         if len(final_nodes) >= recommended_pages:
-            #             break
         else:
+            # Expand requests to neighbors until we have at least
+            # recommended_pages to request. We only want to expand requests
+            # within a given layer.
             new_tips = set(final_nodes)
-            while len(final_nodes) < recommended_pages and new_tips:
+            while len(final_nodes) < self._recommended_pages and new_tips:
                 next_tips = set()
-                for pos in sorted(new_tips):
+                for pos in new_tips:
                     if pos > 0:
                         previous = pos - 1
                         if (previous not in cached_nodes
                             and previous not in final_nodes):
-                            final_nodes.add(previous)
                             next_tips.add(previous)
                     after = pos + 1
-                    if after < max_page:
+                    if after < num_pages:
                         if (after not in cached_nodes
                             and after not in final_nodes):
-                            final_nodes.add(after)
-                            next_tips.add(previous)
+                            next_tips.add(after)
+                    # This would keep us from going bigger than
+                    # recommended_pages by only expanding the first nodes.
+                    # However, if we are making a 'wide' request, it is
+                    # reasonable to expand all points equally.
                     # if len(final_nodes) > recommended_pages:
                     #     break
+                final_nodes.update(next_tips)
                 new_tips = next_tips
 
         final_nodes = sorted(final_nodes)
-        trace.note('\t\t%s', final_nodes)
+        if 'index' in debug.debug_flags:
+            trace.mutter('expanded:  %s', final_nodes)
         return final_nodes
 
     def _get_nodes(self, cache, node_indexes):
@@ -1116,6 +1136,16 @@
             self._get_root_node()
         return self._key_count
 
+    def _compute_row_offsets(self):
+        """Fill out the _row_offsets attribute based on _row_lengths."""
+        offsets = []
+        row_offset = 0
+        for row in self._row_lengths:
+            offsets.append(row_offset)
+            row_offset += row
+        offsets.append(row_offset)
+        self._row_offsets = offsets
+
     def _parse_header_from_bytes(self, bytes):
         """Parse the header from a region of bytes.
 
@@ -1157,13 +1187,7 @@
                 if len(length)])
         except ValueError:
             raise errors.BadIndexOptions(self)
-        offsets = []
-        row_offset = 0
-        for row in self._row_lengths:
-            offsets.append(row_offset)
-            row_offset += row
-        offsets.append(row_offset)
-        self._row_offsets = offsets
+        self._compute_row_offsets()
 
         # calculate the bytes we have processed
         header_end = (len(signature) + sum(map(len, lines[0:4])) + 4)

=== modified file 'bzrlib/tests/test_btree_index.py'
--- a/bzrlib/tests/test_btree_index.py	2008-08-28 20:13:31 +0000
+++ b/bzrlib/tests/test_btree_index.py	2008-10-14 19:02:26 +0000
@@ -996,3 +996,125 @@
                                      (4, ['g', 'h'])],
                                     ['a', 'b', 'd', 'e', 'g', 'h'],
                                     ['c', 'd', 'f', 'g'])
+
+
+class TestExpandNodes(tests.TestCase):
+
+    def make_index(self, size, recommended_pages=None):
+        """Make an index with a generic size.
+
+        This doesn't actually create anything on disk, it just primes a
+        BTreeGraphIndex with the recommended information.
+        """
+        index = btree_index.BTreeGraphIndex(get_transport('memory:///'),
+                                            'test-index', size=size)
+        if recommended_pages is not None:
+            index._recommended_pages = recommended_pages
+        return index
+
+    def set_cached_nodes(self, index, cached_nodes):
+        """Modify the index to give a canned answer for _get_cached_nodes()."""
+        def _get_cached_nodes():
+            cached = set(cached_nodes)
+            return cached
+        index._get_cached_nodes = _get_cached_nodes
+
+    def prepare_index(self, index, node_ref_lists, key_length, key_count,
+                      row_lengths, cached_nodes):
+        """Setup the BTreeGraphIndex with some pre-canned information."""
+        index.node_ref_lists = node_ref_lists
+        index._key_length = key_length
+        index._key_count = key_count
+        index._row_lengths = row_lengths
+        index._compute_row_offsets()
+        index._root_node = btree_index._InternalNode('internal\noffset=0\n')
+        self.set_cached_nodes(index, cached_nodes)
+
+    def make_100_node_index(self):
+        index = self.make_index(4096*100, 6)
+        self.prepare_index(index, node_ref_lists=0, key_length=1,
+                           key_count=1000, row_lengths=[1, 99],
+                           cached_nodes=[0])
+        return index
+
+    def assertNumPages(self, expected_pages, index, size):
+        index._size = size
+        self.assertEqual(expected_pages, index._compute_num_pages())
+
+    def assertExpandNodes(self, expected, index, node_indexes):
+        self.assertEqual(expected, index._expand_nodes(node_indexes))
+
+    def test_default_recommended_pages(self):
+        index = self.make_index(None)
+        # local transport recommends 4096 byte reads, which is 1 page
+        self.assertEqual(1, index._recommended_pages)
+
+    def test__compute_num_pages(self):
+        index = self.make_index(None)
+        self.assertNumPages(1, index, 1024)
+        self.assertNumPages(1, index, 4095)
+        self.assertNumPages(1, index, 4096)
+        self.assertNumPages(2, index, 4097)
+        self.assertNumPages(2, index, 8192)
+        self.assertNumPages(76, index, 4096*75 + 10)
+
+    def test_unknown_size(self):
+        # We should not expand if we don't know the file size
+        index = self.make_index(None, 10)
+        self.assertExpandNodes([0], index, [0])
+        self.assertExpandNodes([1, 4, 9], index, [1, 4, 9])
+
+    def test_more_than_recommended(self):
+        index = self.make_index(4096*100, 2)
+        self.assertExpandNodes([1, 10], index, [1, 10])
+        self.assertExpandNodes([1, 10, 20], index, [1, 10, 20])
+
+    def test_read_all_from_root(self):
+        index = self.make_index(4096*10, 20)
+        self.assertExpandNodes(range(10), index, [0])
+
+    def test_read_all_when_cached(self):
+        # We've read enough that we can grab all the rest in a single request
+        index = self.make_index(4096*10, 5)
+        self.prepare_index(index, node_ref_lists=0, key_length=1,
+                           key_count=1000, row_lengths=[1, 9],
+                           cached_nodes=[0, 1, 2, 5, 6])
+        # It should fill the remaining nodes, regardless of the one requested
+        self.assertExpandNodes([3, 4, 7, 8, 9], index, [3])
+        self.assertExpandNodes([3, 4, 7, 8, 9], index, [8])
+        self.assertExpandNodes([3, 4, 7, 8, 9], index, [9])
+
+    def test_no_root_node(self):
+        index = self.make_index(4096*10, 5)
+        self.assertExpandNodes([0], index, [0])
+
+    def test_include_neighbors(self):
+        index = self.make_100_node_index()
+        # We expand in both directions, until we have at least 'recommended'
+        # pages
+        self.assertExpandNodes([9, 10, 11, 12, 13, 14, 15], index, [12])
+        self.assertExpandNodes([88, 89, 90, 91, 92, 93, 94], index, [91])
+        # If we hit an 'edge' we continue in the other direction
+        self.assertExpandNodes([1, 2, 3, 4, 5, 6], index, [2])
+        self.assertExpandNodes([94, 95, 96, 97, 98, 99], index, [98])
+
+        # Requesting many nodes will expand all locations equally
+        self.assertExpandNodes([1, 2, 3, 80, 81, 82], index, [2, 81])
+        self.assertExpandNodes([1, 2, 3, 9, 10, 11, 80, 81, 82], index,
+                               [2, 10, 81])
+
+    def test_expand_to_cached(self):
+        index = self.make_100_node_index()
+        self.set_cached_nodes(index, [0, 10, 19])
+        self.assertExpandNodes([11, 12, 13, 14, 15, 16], index, [11])
+        self.assertExpandNodes([11, 12, 13, 14, 15, 16], index, [12])
+        self.assertExpandNodes([12, 13, 14, 15, 16, 17, 18], index, [15])
+        self.assertExpandNodes([13, 14, 15, 16, 17, 18], index, [16])
+        self.assertExpandNodes([13, 14, 15, 16, 17, 18], index, [17])
+        self.assertExpandNodes([13, 14, 15, 16, 17, 18], index, [18])
+
+    def test_expand_limited(self):
+        index = self.make_100_node_index()
+        self.set_cached_nodes(index, [0, 10, 12])
+        # We don't go into an endless loop if we are bound by cached nodes
+        self.assertExpandNodes([11], index, [11])

=== renamed file 'doc/developers/btree_index_request_expansion.txt' => 'doc/developers/btree_index_prefetch.txt'
--- a/doc/developers/btree_index_request_expansion.txt	2008-10-07 21:41:12 +0000
+++ b/doc/developers/btree_index_prefetch.txt	2008-10-14 19:02:26 +0000
@@ -1,6 +1,6 @@
-=============================
-BTree Index Request Expansion
-=============================
+====================
+BTree Index Prefetch
+====================
 
 This document outlines how we decide to pre-read extra nodes in the btree
 index.
@@ -11,7 +11,7 @@
 
 Because of the latency involved in making a request, it is often better to make
 fewer large requests, rather than more small requests, even if some of the
-extra data will be wasted. 
+extra data will be wasted.
 
 Example
 -------
@@ -123,7 +123,7 @@
 
 * We generally assume locality of reference. So if we are currently reading
   page 10, we are more likely to read page 9 or 11 than we are page 20.
-  
+
 * However, locality of reference only really holds within a layer. If we are
   reading the last node in a layer, we are unlikely to read the first node of
   the next layer. In fact, we are most likely to read the *last* node of the
@@ -176,7 +176,7 @@
   This is because a command like ``bzr pack`` will combine everything into a
   single large file. Commands like ``bzr commit`` will create an index with a
   single new record, though these will be packaged together by autopack.
-  Commands like ``bzr push`` and ``bzr pull`` will create indexes with more 
+  Commands like ``bzr push`` and ``bzr pull`` will create indexes with more
   records, but these are unlikely to be a significant portion of the history.
   Consider bzr has 20,000 revisions, a single push/pull is likely to only be
   100-200 revisions, or 1% of the history.
@@ -235,6 +235,11 @@
   powers of 100, etc. The basic idea is that if we are *close* to a layer
   split, go ahead and read a small number of extra pages.
 
+* The previous discussion applies whenever we have an upper layer that is not
+  completely full. So the pages referenced by the last node from the upper
+  layer will often not have a full 100-way fan out. Probably not worthwhile
+  very often, though.
+
 
 Suggested Algorithm
 ===================



More information about the bazaar-commits mailing list