Incremental merge_sorted?

[Aaron Bentley]

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

One of the new bottlenecks show_logs is merge_sorted.  It scales with
the size of the revision graph.  So on my 1000-commit tree, lsprof says
the _push_node and _pop_node operations take .0409 and .0286 s
respectively, out of .2515 s spent in _show_log

This is particularly silly for 'bzr log -r -5..', but also bad for the
log|less case.

Solving the problem for the '-r -5..' case could be done by trimming the
graph.  But I don't see how to solve it in the general case, except by
making the process incremental.

In fact, my lsprof says that of .2515 seconds, .0968 are spent in
get_revision_graph, and .1173 are spent in merge_sorted, so this
topological sorting is dominating the log time.  Particularly nasty
since two of our three log formatters suppress merges, anyhow.

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

iD8DBQFElEYQ0F+nu1YWqI0RAscDAJ9VUjPIJ15kyx3IMpmQ/sk1wHKohwCfWZPu
p5/snFfgyXxo5vP1qqOS1K0=
=BFM4
-----END PGP SIGNATURE-----