[MERGE/RFC] Add dotted-decimal revision numbers to merge_sorted output

[Robert Collins]

On Wed, 2006-09-06 at 22:43 -0500, John Arbash Meinel wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1


> Actually, I always thought they were based on the source. And I thought
> that is what I just outlined.

We discussed lying and counting from the merge point but pretending it
was from the revision before. Anyhow, we seem

> I think numbering off of the ancestor works just fine, and gives very
> reasonable numbers.

to be in agreement now.

Performance wise the new code is slow:

Old:
python -m timeit -s 'from bzrlib.tsort import merge_sort; import
bzrlib.branch; import bzrlib.plugin;bzrlib.plugin.load_plugins(); b =
bzrlib.branch.Branch.open("."); tip = b.last_revision(); g =
b.repository.get_revision_graph(tip); ' 'sorted = list(merge_sort(g,
tip))' 
10 loops, best of 3: 172 msec per loop

With this patch:
python -m timeit -s 'from bzrlib.tsort import merge_sort; import
bzrlib.branch; import bzrlib.plugin;bzrlib.plugin.load_plugins(); b =
bzrlib.branch.Branch.open("."); tip = b.last_revision(); g =
b.repository.get_revision_graph(tip); ' 'sorted = list(merge_sort(g,
tip, generate_revno=True))'
10 loops, best of 3: 250 msec per loop

250/172=1.4534883720

So its going to add 50% to the call time to merge_sort.

This is probably fixable to a large degree: removing the backwards
compatability option saves a few ms, we might be able to save a parent
lookup with some care.

However, at the real world level, log is not fast enough to be affected
by this : log in a branch with 7K revisions is several orders of
magnitude slower than 80ms.

Rob

-- 
GPG key available at: <http://www.robertcollins.net/keys.txt>.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 191 bytes
Desc: This is a digitally signed message part
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20060907/df9dcb39/attachment.pgp