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

From: Jon Seymour <[email-masked]>
Date: Mon, 20 Jun 2005 20:29:56 +1000

On 6/20/05, Jon Seymour <[email-masked]> wrote:
> > 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.
> 
> Correction - at each node, send all mass received from _children_
> 

This is a little too simple. It would work if the all nodes in the
visible graph were all connected to the base of an epoch. However, the
pruning behaviour of known goods effectively installs blockages into
the network and causes "backflow" which complicates things somewhat -
a plumbers nightmare!

I am exploring another variation of the idea which is even simpler.
Experimentally it seems quite similar to your average case
performance, but doesn't yet approach your low std deviations.
However, I think I know why that is, so I will, after a few games of
pool and a similar number of beers, have another crack at it.

jon.
-- 
homepage: http://www.zeta.org.au/~jon/
blog: http://orwelliantremors.blogspot.com/