Code review comment for lp:~mkbosmans/bzr/topo_sort

Revision history for this message
Maarten Bosmans (mkbosmans) wrote :

By refactoring the code in tsort.TopoSorter.iter_topo_order a performance improvement of 40% can be achieved.
The runtime to sort the graph of bzr.dev went from 620 ms to 380 ms on my computer. The slightly modified algorithm is also a bit more readable by flattening out a while loop.

A further improvement to 260 ms can be achieved by using a completely different algorithm for tsort.topo_sort. I'm not shure whether this second improvement is enough to warrant two algorithms, but it probably is because it's quite easy to understand and follow. The faster algorithm cannot be used for the iterator because almost all the works takes place before the first element can be yielded.

« Back to merge proposal