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

From: Jon Seymour <jon.seymour@gmail.com>
Date: Jun 20, 2005, 10:29 UTC
Message-ID: <2cfc403205062003292db2b457@mail.gmail.com>
In-Reply-To: <2cfc40320506192030290187af@mail.gmail.com>

On 6/20/05, Jon Seymour <jon.seymour@gmail.com> wrote:

Show 11 quoted lines

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