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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[Index of Archives]
[Kernel Newbies]
[Netfilter]
[Bugtraq]
[Photo]
[Stuff]
[Gimp]
[Yosemite News]
[MIPS Linux]
[ARM Linux]
[Linux Security]
[Linux RAID]
[Video 4 Linux]
[Linux for the blind]
[Linux Resources]
