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.
By refactoring the code in tsort.TopoSorte r.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.