[MERGE] btree prefetch

[John Arbash Meinel]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Martin Pool wrote:
> Martin Pool has voted tweak.
> Status is now: Conditionally approved
> Comment:
> 
> +    def _compute_recommended_pages(self):
> +        """Given the transport's recommended_page_size, determine num
> pages."""
> 
> So below you use the term 'num pages' to mean the number of pages in the
> index; what this seems to mean is the number of pages to try to read in
> each read.

Right 'num pages' is the number of pages that fit in
'recommended_page_size' I changed it to:

"""Convert transport's recommended_page_size into btree pages.

recommended_page_size is in bytes, we want to know how many _PAGE_SIZE
pages fit in that length.
"""


> +    def _compute_num_pages(self):
> +        """Determine the offset to the last page in this index."""
> 
> This docstring seems inconsistent with the method name.
> It's actually the number of pages in the index file?

Right. I either compute it via the number of bytes for the file (saved
in the pack-names file), or I return the value stored in the header. It
is mostly meant for the case where we haven't read the header yet, and
want an estimate on how we should do pre-fetch.


> +    def _expand_nodes(self, node_indexes):
> +        """Find extra nodes to download.
> +
> +        The idea is that we always want to make big-enough requests
> (like 64kB
> +        for http), so that we don't waste round trips. So given the
> entries
> +        that we already have cached, and the new nodes being
> downloaded, figure
> +        out what other pages we might want to read.
> +
> +        :param node_indexes: The nodes that have been requested to read.
> +        :return: A new list of nodes to download
> +        """
> 
> A pointer to the doc file would be good here.

done

> 
> +        if 'index' in debug.debug_flags:
> +            trace.mutter('expanding: %s\tnodes: %s', self._name,
> node_indexes)
> +
> +        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
> +        num_pages = self._compute_num_pages()
> 
> Maybe change this and the method to 'total_pages'?

Done

> 
> +        # The idea here is to get nodes "next to" the ones we are already
> +        # getting.
> +        cached_keys = self._get_cached_keys()
> +
> 
> How does that comment relate to the code that follows?

I think it related to the overall code but I'll remove it because it
doesn't relate directly to the next line.

> 
> +        # If reading recommended_pages would read the rest of the
> index, just
> +        # do so.
> +        if num_pages - len(cached_keys) <= self._recommended_pages:
> +            # Read whatever is left
> +            if cached_keys:
> +                expanded = [x for x in xrange(num_pages)
> +                               if x not in cached_keys]
> +            else:
> +                expanded = range(num_pages)
> 
> It looks like you're searching for integers in a set of key tuples, which
> would presumably never match?

The key for a page is actually the integer offset. (So the page at bytes
4096-8191 is at offset 1 and uses key == 1.)

I called it "_get_cached_keys" because I'm not getting the bytes to the
pages themselves (to say get_cached_pages). "get_cached_offsets" doesn't
quite work either. Perhaps "get_offsets_to_cached_pages" ?

The code, in general, is bad about terminology. Sometimes calling it
'nodes', sometimes calling it 'pages', etc. I'll do a pass which changes
references to the *key* for a page to use terms like "offset".

There is also the possibility to use the "node_index" terminology, but
as the class is a BTreeIndex, that is double-overloading 'index' as well...



> 
> 
> +            # Expand requests to neighbors until we have at least
> +            # recommended_pages to request. We only want to expand
> requests
> +            # within a given layer. We cheat a little bit and assume all
> +            # requests will be in the same layer. This is true given the
> +            # current design, but if it changes this algorithm may perform
> +            # oddly.
> +            final_nodes = set(node_indexes)
> +            first = end = None
> +            new_tips = set(final_nodes)
> +            while len(final_nodes) < self._recommended_pages and new_tips:
> +                next_tips = set()
> +                for pos in new_tips:
> +                    if first is None:
> +                        first, end = self._find_layer_first_and_end(pos)
> +                    previous = pos - 1
> +                    if (previous > 0
> +                        and previous not in cached_keys
> +                        and previous not in final_nodes
> +                        and previous >= first):
> +                        next_tips.add(previous)
> +                    after = pos + 1
> +                    if (after < num_pages
> +                        and after not in cached_keys
> +                        and after not in final_nodes
> +                        and after < end):
> +                        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
> 
> This section above is the kind of place where it might be good to split it
> into a separate, perhaps pure function, that could be more easily tested
> or reasoned-about in isolation.  This method is still pretty readable so
> it's just something to think about next time.

I did go ahead and put it into a helper function. In the end, it is more
"worker" code than policy code. Which hopefully will help make
_expand_offsets() more obvious that it is 'policy' code.


> @@ -0,0 +1,294 @@
> +====================
> +BTree Index Prefetch
> +====================
> +
> +This document outlines how we decide to pre-read extra nodes in the btree
> +index.
> +
> +
> 
> You should link this in to doc/developers/index.txt
> 
> I think I read this document when you were thinking about implementing
> this algorithm?

Probably. I did update it a couple of times since.

> 
> +Algorithm
> +=========
> +
> +This is the basic outline of the algorithm.
> 
> The algorithm seems reasonable and is well explained.

Thanks.

John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkkHaiQACgkQJdeBCYSNAAMqggCgxN8K7n0kljl2EyUJ/Uz373qj
V5AAoKv/zDMDJr+kIQz35Qk8V8SgdMkq
=OcRz
-----END PGP SIGNATURE-----