Improve performance of tsort.topo_sort

[Maarten Bosmans]

Thanks for the review, Martin.

On Wed, Jul 29, 2009 at 8:57 AM, Martin Pool<mbp at sourcefrog.net> wrote:
> Can I suggest that in general you proposed changes by pushing a bzr
> branch to Launchpad and then using the 'propose merge' link, because
> that way your change is tracked through to completion and not lost -
> like filing a bug vs just mentioning it in mail.

OK, I'll try that.

> The test claims that part of the contract of tsort is that when there
> is a tie it returns the items in lexicographical order.  (I guess
> actually it means Python object comparison order.)  It is nice to have
> the sorts be deterministic from their input rather than depending on
> unpredictable behaviour of Python dicts or sets, which would tend to
> cause varying behaviour and therefore make any bugs hard to reproduce.
>  If giving this up made the code much faster it may be worthwhile, but
> it should be a conscious choice.  It may not be too slow to sort
> nochildnodes in your code?  (Or eventually we could use a heap or
> something.)

Well, the comments on top of topo_sort imply that an exact ordering is
not garantueed:
#def topo_sort(graph):
#    The result is a list of node names, such that all parents come before
#    their children.
So I think that the test right now relies on an implementation detail.

The reason I'm looking into topo_sort is to add sorting capability.
(see https://bugs.launchpad.net/bzr-gtk/+bug/321389 , a solution for
this bug has to fix merge_sort, but I figured that topo_sort was
easier to start with) The patch not only makes topo_sort faster, but
it's also easier to add arbitrary sorting capability to the
topological sort.

The line "node_name = nochildnodes.pop()" from the patch is where the
magic happens. You can choose any of the nochildnodes and the returned
list will still be topologically sorted. So sorting by Python
comparison order is easily done by replacing this line with:
        node_name = max(nochildnodes)
        nochildnodes.remove(node_name)
It's a bit slower, but still a 2x speedup.

> The algorithm looks pretty much correct to me.
>
> It is a bit unfortunate to have two implementations of tsort, but
> perhaps it's best if the all-at-once once can be much faster than the
> incremental implementation.

It's of course possible to use the same algorithm for
TopoSorter.iter_topo_order. Instead of returning the reversed list you
can just pop the last element from the not-reversed list and yield it.
The places where the iterator is used in Bzr, it seems to go through
the whole list anyway, so the bit larger upfront costs of generating
the nchildren list is worth it, I think.

> If being an object causes a significant slowdown perhaps the
> iter_topo_sorted generator could be changed into a plain generator,
> rather than a generator on an object.

Well, the whole point of constructing an object with self variables
and all is a bit lost on me. A simple function like topo_sort and
perhaps topo_sort_iter would suffice. Note that to make MergeSorter
faster a lot of variables where made local in bzr.dev rev 2432.

I don't know whether the Sorter classes are part of externally visible
api, but otherwise I would suggest to just have topo_sort, merge_sort
and two new topo_sort_iter and merge_sort_iter functions. The few
places in Bzr that use the Sorter classes can then be converted. This
would greatly enhance the readability of the tsort code.

Maarten