Re: Changing topo sort behaviour

Greg Ward wrote:
> Hi, me again.  So, the good news is that cvs2hg is working pretty
> well: it's got 5 or 6 passing tests, and I can run a moderate-sized
> real-world CVS repository through it and verify the results.  Runtime
> and memory usage are both comparable to cvs2svn.  So we're looking
> good for strict correctness.

Sounds good!

> But there's an optimization problem: Mercurial can be quite sensitive
> to the order in which changesets are added to the repository. [...]

Yes, I'm aware of this issue.

> I spent some time last night reading RevisionTopologicalSortPass, and
> I'm unclear on what value it adds.  I mean, where does it sort? [...]

The changesets are sorted when they come out of
ChangesetGraph.consume_nopred_nodes(), and the sort order is ultimately
determined by _NoPredNodes._compare().

This is a topological sort, so in the general case there is more than
one node that has no predecessors and could therefore be output.
consume_nopred_nodes() decides which of these "NoPredNodes" to output
first.  As you can see, the ordering is based primarily on the range of
timestamps of individual CVSItems contained within the proto-changesets.

Now, part of the reason for choosing among the many topological
orderings of the changesets is that Subversion wants to assign integers
r1, r2, etc. to changesets.  But part of the reason is that it helps
break cycles in the CVS dependency graph in a way that is hopefully the
most "sensible".  You will note that there are several topological
sorts; the first involves only RevisionChangesets, then only
SymbolChangesets, then all Changesets.  This is because the dependencies
among RevisionChangesets are the most well defined (since only CVS
revisions have associated metadata), whereas CVS doesn't provide much
evidence at all which branch and tag creations were actually made
together.  So we toposort the RevisionChangesets first and impose a
definite order on them, then the RevisionChangesets provide the
"backbone" onto which the SymbolChangesets are hung.

After RevisionTopologicalSortPass, the order of the RevisionChangesets
is rigidly defined by putting them in a row and making each one depend
on the one to its left.  Mechanically, this is done by converting the
RevisionChangesets into OrderedChangesets.  (After this pass, the
timestamps are not really used.)

This is obviously more rigid than required by cvs2hg, and in fact
retaining the ordering of OrderedChangesets would lead to the Mercurial
inefficiencies from jumping around from branch to branch.

The question is, how to change this?  I don't think you want to skip the
chronological ordering altogether, because it helps the heuristic that
decides which SymbolChangesets to break up to break cycles in the
dependency graph.  (E.g., one pass splits up any SymbolChangeset that
leads from a higher-numbered OrderedChangeset to a lower-numbered one.)
 So I guess the best approach would be to use some kind of chronological
or partial chronological ordering during the intermediate passes but
then revert to a "follow-the-branch" ordering sometime before generating
the output.

I don't have time now to think more deeply about how to do this, but if
you need help get back in touch with me.

> So, if I come up with a variant of RevisionTopologicalSortPass, how do
> I use it?  Obviously for testing, I can just edit the passes list at
> the bottom of passes.py, but what about production use?  I need to
> expose this knob to the options file somehow, and I don't see an
> obvious way.  *Is* there way for users to replace an entire pass?

This hasn't been needed yet, but it would be easy.  The "passes" array
at the bottom of passes.py would be defined by the individual main()
variants based on what they need.  The management of "artifacts" (i.e.,
temporary files) is fully automated; the individual passes only have to
tell what artifacts they need via their register_artifacts() methods.

Michael

------------------------------------------------------
http://cvs2svn.tigris.org/ds/viewMessage.do?dsForumId=1667&dsMessageId=2380954

To unsubscribe from this discussion, e-mail: [[email protected]].