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

[Jon Seymour <jon.seymour@gmail.com>]

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