Merge lp:~jameinel/bzr/2.1.0b4-convert-kg-heads into lp:bzr

[John A Meinel]

[John A Meinel (jameinel)]

See this graph:
http://launchpadlibrarian.net/36247556/conversion_times.png

For the net effect of this patch. In converting mysql from 1.9 => 2a it cuts the time for the conversion approx 2:1.

The basic observation was that we spend *way* too much time graph walking during the conversion. Part of that was because we didn't pass *any* graph object down, so we didn't have any benefit of caching, etc. So for all heads() requests we paid the full api layering (translating back and forth from strings <=> tuples for all entries in the history, etc.)

Anyway, we have a very fast heads implementation, so lets use it. I put in the check:

if ... len(revision_ids) > 100:

in there, so that we don't *always* load the full history for small conversion updates. However, for anything more than that, we probably get a net win out of loading the whole ancestry and using the faster heads implementation.

I wish there was a way I could put the image inline, like I used to be able to do with Thunderbird sending requests via Bundle Buggy. (At least, people using email clients would see the image right away...)

[Robert Collins (lifeless)]

I'm not sure that 100 is the right figure, could you do some timing data
on e.g. emacs and put forward a change to that figure if its wrong?

This branch can land now however.

 review: approve
 merge: approve

review: Approve

[John A Meinel (jameinel)]

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

Robert Collins wrote:
> Review: Approve
> I'm not sure that 100 is the right figure, could you do some timing data
> on e.g. emacs and put forward a change to that figure if its wrong?
>
> This branch can land now however.
>
> review: approve
> merge: approve
>

So I don't think there is going to be an ideal value that is always correct.

The emacs history is going to be very different from mysql, for example.
(I've got about 70k mysql revs, but the mainline is only 2k-4k long
depending on the branch.)

However, repo.revisions.get_known_graph_ancestry([tip])

Takes somewhere between 0.5 to 1.0s. Conversions I've done are around 3
revs per second. This heads is about 2x faster, so if we assume

3r/s * 1.0s / 0.5 = 6revs.

So somewhere around 6 revs it will be faster to just load the whole
revision graph.

As mentioned, there are lots of variables. (I think Emacs heads() is
going to generally be cheaper because it is more linear, though it may
be more expensive because then you have to walk more revs?)

I could drop it to 10 revs if you would prefer. Adding 1.0s is pretty
trivial, and we only do this on 'local' access. (IDS only works on
file=>file, and it is being done on the 'source' side for smart streaming.)

Were you thinking the number should be bigger or smaller?

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

iEYEARECAAYFAksT7JQACgkQJdeBCYSNAANbMgCfcqUZg3F6mfUsOGfCpdwjnKx/
0bcAn1QsHYKA4FW2cKvYnw5jnGj6OM6w
=QFMf
-----END PGP SIGNATURE-----

[Robert Collins (lifeless)]

So, all I knew was that 100 was a WAG :)

If the tradeoff point is 6 revisions on mysql, it would be great to also
have a figure for where it is on emacs, then we could triangulate.
However, it seems like 25 or 50 or something might be better for now
until we have more more data.

-Rob

[John A Meinel (jameinel)]

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

Robert Collins wrote:
> So, all I knew was that 100 was a WAG :)
>
> If the tradeoff point is 6 revisions on mysql, it would be great to also
> have a figure for where it is on emacs, then we could triangulate.
> However, it seems like 25 or 50 or something might be better for now
> until we have more more data.
>
> -Rob
>

I'm having some difficulty downloading the emacs source. My laptop seems
to like to hiccup on new network connections periodically, and the time
to download all of emacs is outside of that time. I do have it
downloading on my server, which is a bit underpowered.

It did show our limitations over HTTP, as I hit 335MB downloaded, but
the repo is only about 206MB total. The download is also *very* choppy,
but that machine is woefully underpowered. (P-III 700MHz.)

Anyway, emacs seems to be 3.5s. So if you go with the same 50% +
3revs/sec you end up with 21.

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

iEYEARECAAYFAksWev8ACgkQJdeBCYSNAAMv/wCeNGBEQdhdpOYKy+YcbBZ4E/Rs
MOwAnjyuNYtmU5wJ+Uh3azUscM0inIJV
=oHv6
-----END PGP SIGNATURE-----

=== modified file 'NEWS'
--- NEWS	2009-11-27 10:43:47 +0000
+++ NEWS	2009-11-30 03:50:26 +0000
@@ -53,6 +53,10 @@
   etc. Now only change slashes if there is something being glob expanded.
   (John Arbash Meinel, #485771)
 
+* Use our faster ``KnownGraph.heads()`` functionality when computing the
+  new rich-root heads. This can cut a conversion time in half (mysql from
+  13.5h => 6.2h) (John Arbash Meinel, #487632)
+
 Improvements
 ************
 

=== modified file 'bzrlib/fetch.py'
--- bzrlib/fetch.py	2009-08-07 04:29:36 +0000
+++ bzrlib/fetch.py	2009-11-30 03:50:26 +0000
@@ -28,6 +28,8 @@
 from bzrlib.lazy_import import lazy_import
 lazy_import(globals(), """
 from bzrlib import (
+    graph as _mod_graph,
+    static_tuple,
     tsort,
     versionedfile,
     )
@@ -36,10 +38,10 @@
 from bzrlib import (
     errors,
     symbol_versioning,
+    ui,
     )
 from bzrlib.revision import NULL_REVISION
 from bzrlib.trace import mutter
-import bzrlib.ui
 
 
 class RepoFetcher(object):
@@ -96,7 +98,7 @@
         # assert not missing
         self.count_total = 0
         self.file_ids_names = {}
-        pb = bzrlib.ui.ui_factory.nested_progress_bar()
+        pb = ui.ui_factory.nested_progress_bar()
         pb.show_pct = pb.show_count = False
         try:
             pb.update("Finding revisions", 0, 2)
@@ -123,7 +125,7 @@
             raise errors.IncompatibleRepositories(
                 self.from_repository, self.to_repository,
                 "different rich-root support")
-        pb = bzrlib.ui.ui_factory.nested_progress_bar()
+        pb = ui.ui_factory.nested_progress_bar()
         try:
             pb.update("Get stream source")
             source = self.from_repository._get_source(
@@ -251,13 +253,22 @@
         # yet, and are unlikely to in non-rich-root environments anyway.
         root_id_order.sort(key=operator.itemgetter(0))
         # Create a record stream containing the roots to create.
-        from bzrlib.graph import FrozenHeadsCache
-        graph = FrozenHeadsCache(graph)
+        if len(revs) > 100:
+            graph = _get_rich_root_heads_graph(self.source_repo, revs)
         new_roots_stream = _new_root_data_stream(
             root_id_order, rev_id_to_root_id, parent_map, self.source, graph)
         return [('texts', new_roots_stream)]
 
 
+def _get_rich_root_heads_graph(source_repo, revision_ids):
+    """Get a Graph object suitable for asking heads() for new rich roots."""
+    st = static_tuple.StaticTuple
+    revision_keys = [st(r_id).intern() for r_id in revision_ids]
+    known_graph = source_repo.revisions.get_known_graph_ancestry(
+                    revision_keys)
+    return graph.GraphThunkIdsToKeys(known_graph)
+
+
 def _new_root_data_stream(
     root_keys_to_create, rev_id_to_root_id_map, parent_map, repo, graph=None):
     """Generate a texts substream of synthesised root entries.

=== modified file 'bzrlib/graph.py'
--- bzrlib/graph.py	2009-09-14 01:48:28 +0000
+++ bzrlib/graph.py	2009-11-30 03:50:26 +0000
@@ -1679,6 +1679,19 @@
     return result
 
 
+class GraphThunkIdsToKeys(object):
+    """Forwards calls about 'ids' to be about keys internally."""
+
+    def __init__(self, graph):
+        self._graph = graph
+
+    def heads(self, ids):
+        """See Graph.heads()"""
+        as_keys = [(i,) for i in ids]
+        head_keys = self._graph.heads(as_keys)
+        return set([h[0] for h in head_keys])
+
+
 _counters = [0,0,0,0,0,0,0]
 try:
     from bzrlib._known_graph_pyx import KnownGraph

=== modified file 'bzrlib/repository.py'
--- bzrlib/repository.py	2009-11-19 15:06:47 +0000
+++ bzrlib/repository.py	2009-11-30 03:50:26 +0000
@@ -26,6 +26,7 @@
     chk_map,
     debug,
     errors,
+    fetch as _mod_fetch,
     fifo_cache,
     generate_ids,
     gpg,
@@ -2668,8 +2669,8 @@
         for ((revision_id,), parent_keys) in \
                 self.revisions.get_parent_map(query_keys).iteritems():
             if parent_keys:
-                result[revision_id] = tuple(parent_revid
-                    for (parent_revid,) in parent_keys)
+                result[revision_id] = tuple([parent_revid
+                    for (parent_revid,) in parent_keys])
             else:
                 result[revision_id] = (_mod_revision.NULL_REVISION,)
         return result
@@ -3412,8 +3413,7 @@
                    provided a default one will be created.
         :return: None.
         """
-        from bzrlib.fetch import RepoFetcher
-        f = RepoFetcher(to_repository=self.target,
+        f = _mod_fetch.RepoFetcher(to_repository=self.target,
                                from_repository=self.source,
                                last_revision=revision_id,
                                fetch_spec=fetch_spec,
@@ -3819,13 +3819,15 @@
                 basis_id, delta, current_revision_id, parents_parents)
             cache[current_revision_id] = parent_tree
 
-    def _fetch_batch(self, revision_ids, basis_id, cache):
+    def _fetch_batch(self, revision_ids, basis_id, cache, a_graph=None):
         """Fetch across a few revisions.
 
         :param revision_ids: The revisions to copy
         :param basis_id: The revision_id of a tree that must be in cache, used
             as a basis for delta when no other base is available
         :param cache: A cache of RevisionTrees that we can use.
+        :param a_graph: A Graph object to determine the heads() of the
+            rich-root data stream.
         :return: The revision_id of the last converted tree. The RevisionTree
             for it will be in cache
         """
@@ -3895,10 +3897,9 @@
         from_texts = self.source.texts
         to_texts = self.target.texts
         if root_keys_to_create:
-            from bzrlib.fetch import _new_root_data_stream
-            root_stream = _new_root_data_stream(
+            root_stream = _mod_fetch._new_root_data_stream(
                 root_keys_to_create, self._revision_id_to_root_id, parent_map,
-                self.source)
+                self.source, graph=a_graph)
             to_texts.insert_record_stream(root_stream)
         to_texts.insert_record_stream(from_texts.get_record_stream(
             text_keys, self.target._format._fetch_order,
@@ -3961,13 +3962,20 @@
         cache[basis_id] = basis_tree
         del basis_tree # We don't want to hang on to it here
         hints = []
+        if self._converting_to_rich_root and len(revision_ids) > 100:
+            a_graph = _mod_fetch._get_rich_root_heads_graph(self.source,
+                                                            revision_ids)
+        else:
+            a_graph = None
+
         for offset in range(0, len(revision_ids), batch_size):
             self.target.start_write_group()
             try:
                 pb.update('Transferring revisions', offset,
                           len(revision_ids))
                 batch = revision_ids[offset:offset+batch_size]
-                basis_id = self._fetch_batch(batch, basis_id, cache)
+                basis_id = self._fetch_batch(batch, basis_id, cache,
+                                             a_graph=a_graph)
             except:
                 self.target.abort_write_group()
                 raise
@@ -4446,8 +4454,7 @@
         fetching the inventory weave.
         """
         if self._rich_root_upgrade():
-            import bzrlib.fetch
-            return bzrlib.fetch.Inter1and2Helper(
+            return _mod_fetch.Inter1and2Helper(
                 self.from_repository).generate_root_texts(revs)
         else:
             return []

=== modified file 'bzrlib/tests/test_graph.py'
--- bzrlib/tests/test_graph.py	2009-08-04 04:36:34 +0000
+++ bzrlib/tests/test_graph.py	2009-11-30 03:50:26 +0000
@@ -1582,6 +1582,24 @@
         self.assertCollapsed(d, d)
 
 
+class TestGraphThunkIdsToKeys(tests.TestCase):
+
+    def test_heads(self):
+        # A
+        # |\
+        # B C
+        # |/
+        # D
+        d = {('D',): [('B',), ('C',)], ('C',):[('A',)],
+             ('B',): [('A',)], ('A',): []}
+        g = _mod_graph.Graph(_mod_graph.DictParentsProvider(d))
+        graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
+        self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'A'])))
+        self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'B'])))
+        self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'C'])))
+        self.assertEqual(['B', 'C'], sorted(graph_thunk.heads(['B', 'C'])))
+
+
 class TestPendingAncestryResultGetKeys(TestCaseWithMemoryTransport):
     """Tests for bzrlib.graph.PendingAncestryResult."""