Re: git pull on Linux/ACPI release tree

[Linus Torvalds <torvalds@osdl.org>]

On Tue, 10 Jan 2006, Johannes Schindelin wrote:
> > 
> > Think of it as doing a binary search in a 2-dimensional surface - you 
> > can't linearize the plane, but you can decide to test first one half of 
> > the surface, and then depending on whether it was there, you can halve 
> > that surface etc.. 
> 
> How?
> 
> If you bisect, you test a commit. If the commit is bad, you assume *all* 
> commits before that as bad. If it is good, you assume *all* commits after 
> that as good.

No, that's not how bisect works at all.

It's true that if a commit is bad, then all the commits _reachable_ from 
that commit are considered bad. 

And it's true that if a commit is good, then all commits that _reach_ that 
commit are considered good.

But that doesn't mean that there is an ordering. The commits that fall 
into the camp of being "neither good nor bad" are _not_ ordered. There are 
commits in there that are not directly reachable from the good commit.

> Now, if you have a 2-dimensional surface, you don't have a *point*, but 
> typically a *line* separating good from bad.

Exactly. 

And a git graph is not really a two-dimensional surface, but exactly was 
with a 2-dimensional surface, it is _not_ enough to have a *point* to 
separate the good from bad.

You need to have a _set of points_ to separate the good from the bad. You 
can think of it as a line that bisects the surface: if you were to print 
out the development graph, the set of points literally _do_ form a virtual 
line across the development surface.

(Actually, you can't in general print out the development graph on a 
2-dimensional paper without having development lines that cross each 
other, but you could actually do it in three dimensions, where the 
"boundary" between good and bad is actually a 2-dimensional surface in 
3-dimensional space).

But to describe the surface of "known good", you actually just need a list 
of known good commits, and the "commits reachable from those commits" 
_becomes_ the surface.

> Further, the comparison with 2 dimensions is particularly bad.

No it is not. It's a very good comparison.

In a linearized model (one-dimensional, fully ordered set), the only thing 
you need for bisection is two points: the beginning and the end.

In the git model, you need _many_ points to describe the area being 
bisected. Exactly the same way as if you were to bisect a 2-dimensional 
surface.

Now, the git history is _not_ really a two-dimensional surface, so it's 
just an analogy, not an exact identity. But from a visualization 
standpoint, it's a good way to think of each "git bisect" as adding a 
_line_ on the surface rather than a point on a linear line.

> So, how is bisect supposed to work if you don't have one straight 
> development line from bad to good?

Read the code.

I'm pretty proud of it. It's simple, and it's obvious once you think about 
it, but it is pretty novel as far as I know. BK certainly had nothing 
similar, not have I heard of anythign else that does it. Git _might_ be 
the first thing that has ever done it, although it's simple enough that I 
wouldn't be surprised if others have too.

			Linus
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/