bzr branch is slow and memory-hungry (just a data point)

[Aaron Bentley]

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

Martin Pool wrote:
> Even aside from storage, for moderately small trees like bzr the
> current merge is very slow; I think because it's doing a lot of slow
> graph traversal, even when I give an explicit base.  Maybe this is
> just a bug?  At any rate when we switch to weaves it should be better.

I'm in the middle of rewriting the common-ancestor picker.  Probably be
done some time this week.  I'm passing unit tests right now, but not
real-world tests.  The result should scale linearly.

When you specify a base, we have to manually check whether it's an
ancestor.  That's probable the delay you're seeing.  Checking
revision_history first would be a fairly easy optimization.

But we should try to address the problem of graph traversal being slow
in general.  I think we could speed things up considerably by caching
ancestry data.

We could really optimize things if we stored:
1. revision
2. max distance from root node
3. revision parents

This wouldn't change the fact that we're scaling O(n), but it would
decimate the constant.  So the amount of graph traversal is the same,
but it's much, much faster.

Aaron
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFDH4DN0F+nu1YWqI0RAlONAJ4/cuK+jRG76OeIOY/yZkfujONJJgCfXX1J
QRU7WWWSQU6ks4faX27qjYs=
=REB9
-----END PGP SIGNATURE-----