Shrink algorithm bake-off

Greg Ward greg at gerg.ca
Wed Jan 20 21:14:41 CST 2010


The last thread on shrink-revlog petered out when Benoit posted two
more toposort algorithms for me to try: "reverse postorder" and
"postorder reverse".  (The difference is whether they start at the
heads or the roots.)  IIRC, Benoit said that "postorder reverse" is
equivalent to parent delta.  I didn't have time to look at his patch
or compare the algorithms then; now I do.

So I now have a stack of patches to shrink-revlog.py that allows us to
add new sort algorithms by adding toposort_X() functions.  And now I
have toposort_branchsort() (the original), toposort_parentdelta
(mine), toposort_reversepostorder() (Benoit), and
toposort_postorderreverse() (also Benoit).

Ultimately, I think it would be best if we had one super-duper
toposort algorithm that works best all of the time.  It'll be easier
to figure out the winner if we can easily do head-to-head
competitions, hence the pluggable toposort idea.  So I'm about to send
my patches in.  I'm not sure that they should ever be pushed exactly
as-is, but anyone who likes playing around with toposorts could apply
them locally.  That should make it easier to compare different
algorithms.

OTOH, if everyone thinks that supporting lots of toposort algorithms
is a great idea, then maybe these patches should go straight in.  Then
when we figure out which one usually works best, make it the default.

Greg


More information about the Mercurial-devel mailing list