From: Jon Seymour Date: Mon, 20 Jun 2005 03:27:21 GMT Subject: Re: git-rev-list: "--bisect" flag Message-ID: <2cfc403205061920272ee47166@mail.gmail.com> In-Reply-To: > Well, it depends on how nasty it ends up being. I thought my stupid > algorithm would suck horribly, but considering that it can trivially > bisect all of the git history so far in basically zero time, it doesn't > seem to be that bad. You're more likely to have problems with having to > bring in all the commits from disk in the cold-cache case than you are to > have problems with the current algorithm performance. > I'll give you a sketch of the algorithm. First, recall that merge-order code uses an incremental topological sort whose key idea is to employ a conservation of mass analogy. A similar analogy can help here. 1. count all visible nodes [ i.e. nodes that git-rev-list would print ], call this value N 2. at the top node inject N units of mass 3. traverse the visible graph, in topological order 4. at each node, send all the mass received from parents minus 1 unit onto visible parents. Record how much mass you have sent downstream. Keep a record of the nodes that have seen nearest to half of that mass. 5. when the traversal completes, choose the node that saw closest to 1/2 of the original mass [ or pick one at random if there is more than one ]. It must be able to reach close to 1/2 of the visible graph, 'cos all that mass it has seen has to drain somewhere! This algorithm is demonstrably O(V+E) because the traversal is O(V+E) My intention is to add this algorithm to my refactored epoch.c/traversal.c, since this is a much better framework for doing traversals than the current epoch.c. Do you have any objections to me doing that? jon. -- homepage: http://www.zeta.org.au/~jon/ blog: http://orwelliantremors.blogspot.com/