children, n^2 and solutions?

Jason Harris jason at jasonfharris.com
Sun Jul 25 20:13:27 CDT 2010


Hi All,

About 4 days Martin added that patch for allowing the keyword "children" in the log command. I added "children" since I needed it in MacHg and it made things **much** simpler in my total rewrite of the Graph drawing part of MacHg. (I am doing a complete rewrite of the way the graphs are propagated froward and backward in history from a central point so the graph history is stable as the user scrolls. This is one of the most trafficked bugs I have in MacHg and I think it annoys  real users the most. See issue: http://bitbucket.org/jfh/machg/issue/31/p2d2-the-graph-jiggles-back-and-forth)

Well Dan Villiom Podlaski Christiansen pointed out that the children keyword via changectx.children() inspects all changesets following the one called, to see if they are a child. This makes it O(n^2). Sure enough when I tried this on my OpenOffice repository with 260,000 changesets which I use for testing, all my lovely drawing routines all ground to a halt... Whereas things were working really nicely for 2000 change repos. Darn!

So I have looked into trying to make sure I do look aheads and caching at the right time, and then back looking, and then graph extensions when things change, and then redoing the graph extension layouts, and lots more details... and well its pretty painful... So at this stage I am wondering if it is possible to make Mercurial store the child information in the revlog or internally somewhere in a persistent way? Would this be insanely difficult?

It seems like a generally useful thing to be able to report to a user all the children of a revision, and thus it would be nice to be able to do this in a timely manner (ie not O(n^2))... Is anyone able to help me on this issue? :)

Thanks in advance!
   Jason


More information about the Mercurial-devel mailing list