Re: git pull on Linux/ACPI release tree

[Linus Torvalds]

On Tue, 10 Jan 2006, Linus Torvalds wrote:
> 
> 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.

Actually, the way I think of it is akin to the "light cones" in physics. A 
point in space-time doesn't define a fully ordered "before and after": but 
it _does_ describe a "light cone" which tells you what is reachable from 
that point, and what that point reaches. Within those cones, that 
particular point ("commit") has a strict ordering.

And exactly as in physics, in git there's a lot of space that is _not_ 
ordered by that commit. And the way to bisect is basically to find the 
right points in "git space" to create the right "light cone" that you 
find the point where the git space that is reachable from that commit has 
the same volume as the git space that isn't reachable.

And maybe that makes more sense to you (if you're into physics), or maybe 
it makes less sense to you.

Now, since we always search the "git space" in the cone that is defined by 
"reachable from the bad commit, but not reachable from any good commit", 
the way we handle "bad" and "good" is actually not a mirror-image. If we 
fine a new _bad_ commit, we know that it was reachable from the old bad 
commit, and thus the old bad commit is now uninteresting: the new bad 
commit forms a "past light cone" that is a strict subset of the old one, 
so we can totally discard the old bad commit from any future 
consideration. It doesn't tell us anything new.

In contrast, if we find a new _good_ commit, the "past light cone" (aka 
"set of commits reachable from it") is -not- necessarily a proper superset 
of the previous set of good commits, so when we find a good commit, we 
still need to carry the _other_ good commits around, and the "known good" 
universe is the _union_ of all the "good commit past lightcones".

Then the "unknown space" is the set difference of the "past lightcone of 
the bad commit" and of this "union of past lightcones of good commits". 
It's the space that is reachable from the known-bad commit, but not 
reachable from any known-good commit.

So this means that when doing bisection, what we want to do is find the 
point in git space that has _new_ "reachability" within that unknown space 
that is as close to half that volume as space as possible. And that's 
exactly what "git-rev-list --bisect" calculates.

So every time, we try to either move the "known bad" light-cone down in 
time in the unknown space, _or_ we add a new "known good" light-cone. In 
either case, the "unknown git space" keeps shrinking by half each time.

("by half" is not exact, because git space is not only quanticized, it 
also has a rather strange "distance function". In other words, we're 
talking about a rather strange space. The good news is that the space is 
small enough that we can just enumerate every quantum and simply 
calculate the volume it defines in that space. IOW, we do a very 
brute-force thing, and it works fine).

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