[MERGE] Don't use set.difference_update()

John Arbash Meinel john at arbash-meinel.com
Wed Jul 25 22:32:47 BST 2007


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

I was doing some profiling and ran across some of the bugs in
Repository.get_revision_graph()

Specifically, the current code does:

    def get_revision_graph(self, revision_id=None):
        """Return a dictionary containing the revision graph.

        :param revision_id: The revision_id to get a graph from. If None, then
        the entire revision graph is returned. This is a deprecated mode of
        operation and will be removed in the future.
        :return: a dictionary of revision_id->revision_parents_list.
        """
        # special case NULL_REVISION
        if revision_id == _mod_revision.NULL_REVISION:
            return {}
        revision_id = osutils.safe_revision_id(revision_id)
        a_weave = self._get_revision_vf()
        entire_graph = a_weave.get_graph()
        if revision_id is None:
            return a_weave.get_graph()
        elif revision_id not in a_weave:
            raise errors.NoSuchRevision(self, revision_id)
        else:
            # add what can be reached from revision_id
            result = {}
            pending = set([revision_id])
            while len(pending) > 0:
                node = pending.pop()
                result[node] = tuple(a_weave.get_parents(node))
                for revision_id in result[node]:
                    if revision_id not in result:
                        pending.add(revision_id)
            return result

Notice that it always calls 'a_weave.get_graph()' unconditionally. Even though
it uses a different method if there is a list of revisions, and calls it
*again* if there isn't.

But I also noticed that VersionedFile.get_graph() can actually take a list of
version ids, and it will do the filtering for you.

Robert recently changed the get_graph() code, so that it uses iter_parents()
rather than repeatedly calling get_parents().

So I switched the code over to use it. And man was it slow.

Specifically, the current code (which calls get_graph() when it doesn't need
to) takes ~366ms.

Just removing that get_graph() call drops it to around 254ms.

Switching to use get_graph([revision_id]) makes it take 2984ms. Almost 6 times
slower.
The difference seems to be the 1100 calls to difference_update() which takes
2.64 seconds.

The attached patch drops it down to 229ms.

I had been working on a version that pushed get_graph() down into Knit where it
could use a more direct access to _KnitIndex. So that rather than multiple
calls to get_parents() it would grab a dict with no missing parents, and then
return entries as appropriate.

I also noticed that doing:
pending.update(p for p in parents if not in result)

is slower than doing
for p in parents:
  if p in result:
    continue
  pending.add(p)

I'm guessing that 'not in' is more expensive than 'in + continue'.

I'm also guessing that set.difference_update() iterates other and removes
entries that are present in this. Rather than doing the reverse (going through
'this' an removing ones that are present in other). And since 'pending' is
generally going to be a lot smaller than 'result', this causes pathological
behavior.



If you just do:

	dict((v, info[4]) for v, info in idx._cache.iteritems)

To get the list of parents with ghosts, it takes about 35ms. Ie, really fast.
If you decide to filter so that you don't include ghosts, you can do:

	dict((v, [p for p in info[4] if p in idx._cache])
	     for v, info in idx._cache.iteritems)

This takes about 150ms.

So we pay about 4x to check for any ghosts, in a graph that doesn't have any
ghosts in it. And '_KnitIndex.get_parents()' does that same check for each call.

It seems like it might be a better trade off to build up a graph of what
entries are actually ghosts when we read the index, rather than look after the
fact.

I think it would be pretty easy to change the parser. For one thing, if it
parses an offset, it knows that entry cannot be a ghost. And then it only has
to check to see if a new record was originally marked as a ghost (ghost filling).

It adds an extra dictionary check, but it is one for a dictionary that is
typically empty, and at a minimum is small.



Overall, a lot of commands require Repository.get_revision_graph() and this
improves it to 2x. It also improves VF.get_graph() for whenever that is used.

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

iD8DBQFGp8F+JdeBCYSNAAMRAqr7AKDFpwWbqGyGYro/kUpnZkE3nhqBoACfaUdK
SbHepZKluJd+WeUvHzM/lL8=
=ZlhX
-----END PGP SIGNATURE-----
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: remove_get_revision_graph_redundancy.patch
Url: https://lists.ubuntu.com/archives/bazaar/attachments/20070725/7cf51a78/attachment-0001.diff 


More information about the bazaar mailing list