Re: git-rev-list: "--bisect" flag

From: Jon Seymour <jon.seymour@gmail.com>
Date: Jun 20, 2005, 03:27 UTC
Message-ID: <2cfc403205061920272ee47166@mail.gmail.com>
In-Reply-To: <Pine.LNX.4.58.0506192002240.2268@ppc970.osdl.org>

Show 7 quoted lines

> 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/