[Monotone-devel] Toposort Speedup

[Thomas Moschny]

Hi all,

while disucussing this with one of my collegues, an idea came up on how to 
make the topological sorting of revisions an operation that is not more 
complex than a simple integer sort.

The idea is to store the maximum of the maximal distances to the roots of the 
revision graph for every revision together with that revision. As we always 
have all ancestors for a revision in the local revision graph, this number 
(let's call it the 'height') is a constant for that revision and need only be 
computed once.

Now, if you have a set of revisions, you can topologically sort them by simply 
sorting them according to their heights.

I am not sure how often a topological sort is performed during normal monotone 
usage. However, the heights can be advantageous in other operations, too, for 
example while traversing the revision graph (thereby preserving a topological 
order), or while determining common ancestors.

Here's one possible way how to compute the heights:

Start by assigning a height of 0 to all root revisions, and put them into the 
set R. Now:

  for every r in R:
    remove r from R
    for every c in children(r):
      if all parents of c have already a height assigned:
        height(c) = height(r) + 1
        put c into R

As pointed out by Nathaniel on IRC, one downside of the whole idea might be, 
that the way in which nearby revisions are clustered differs from that of the 
currently used algorithm. However, I am not sure about the impact that may 
have or not have. 

Comments?

- Thomas

pgp49JhoFUmBo.pgp
Description: PGP signature