Code review comment for lp:~jameinel/bzr/1.19-known-graph-sorted

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

Vincent Ladeuil wrote:
>>>>>> "robert" == Robert Collins writes:
>
> > What impact will this have on things like my
> > all-ubuntu repository (16K unrelated branches in one
> > repo) ?

It should perform approximately the same or better.

The 'find_ancestors()' code doesn't grab arbitrary node => parent
mappings, only ones that are in the ancestry of the keys that were
requested.

As such it is the same as repeated get_parent_map() calls, just without
the repeats.

The merge_sort() code is simply the same algorithm, just 3-7x faster
(depending on whether you count the time to build the KnownGraph).

Again, all of this code has the same "look at only the ancestry
requested" that the current code has. So there shouldn't be a blowout
from having lots of unrelated history. It just may not be a whole lot
faster because the other history is 'in the way'.

>
> Just you tells us ! :-)
>
> But from the discussion with John, it should either improves
> things (I'm 90% confident here)... or provide us with very nice
> data ! I, for one, will love to have such a repo around to play
> with...
>
> @John, how did you measure your progress ? Still using
> time_graph.py ? Is it time to enhance it ?

No. I did have another helper here, but mostly this is tested with:

$ PYTHONPATH=../bzr/work TIMEIT -s "from bzrlib import branch,
repository, tsort, graph
b = branch.Branch.open('bzr-2a-extra/bzr.dev')
b.lock_read()
l_rev = b.last_revision()
p_map, missing =
b.repository.revisions._index._graph_index.find_ancestry([(l_rev,)], 0)
b.unlock()
" "kg = graph.KnownGraph(p_map);
for n in kg.merge_sort((l_rev,)):
  n.key, n.revno, n.end_of_merge, n.merge_depth
"

Or just simply running:
  time bzr log -n0 -r -10..-1 >/dev/null
John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkqKrUUACgkQJdeBCYSNAAMeogCfTHUrwZBQq2HWwKvQ3cLzrfeW
50gAoJxEtAiADlvkdtA/sP+ixeBfJebv
=XbkW
-----END PGP SIGNATURE-----