Re: Is there interest in a n-sect tool?

Mike Hommey [off-list ref] writes:

- I have a script that, for a given git-cinnabar commit, clones
  those four mercurial repositories, and determines a global state
  for the resulting repositories. (for example, the sha1sum of all
  the sha1s of the remote refs for all repositories)
- The script is run for the earliest commit and gives a sha1.
- Then I bisect run with a script wrapping the other, returning 0
  when the state is the same as the one for the earliest commit,
  or 1 otherwise.
- The result of that first bisection is the first state change.
- Then I bisect run again, using the state of the result of that first
  bisect instead of the earliest commit.
- The result of that second bisection is the second state change.
- And so on...

I do, in fact, cache the states for each iteration of each bisect,
so that I can do some smarter decisions than just start from the last
bisection for the next one.

I don't have that many state changes to track, but I do have different
kind of states that I want to track down, so I will be running this
a couple more times.

The question is, is there sufficient interest in a generic n-sect tool
for me to justify spending the time to do it properly, vs. just doing
the minimalist thing I did to make it work for my use case.

After reading the above a few times, I still am not sure what you
mean by n-sect (as opposed to bi-sect), especially given that you
sounded as if you consider the straight "bisect" is about having
only two states, bad/good, new/old, or black/white.  "Bi" in the
word "bisect" refers to the search going by dividing the space into
two to find state transition, and does not necessarily mean there
are two states (hence implying a single state transition between the
two).  If you have three states, black/gray/white, that linearly
transitions states twice (i.e. one part of the history is
continuously black, and at one boundary it turns gray and continues
to be gray, until at another boundary it turns white and continues
to be white to the other end), you would still "bi"-sect to find
these two transition points.  You start from a black A and a white
Z, pick a midpoint M that tests to be gray and know the transition
point from black to gray exists somewhere between A and M, while the
other transision point from gray to white exists somewhere between M
and Z.  Is that the kind of search you are talking about?

Or you may be talking about a search where there are multiple (as
opposed to 1) independent bistate traits.  E.g. if you have two such
traits, perhaps you have four states in total: both bad (BB), the
first trait is bad and the second trait is good (BG), good and bad
(GB) and both good (GG).  You can tell which one of these four state
a given commit is in by running your test once.  You start from two
endpoints, one commit that used to give you GG (i.e. the system
wasn't broken for both) and the other that gives you BB (i.e. the
system is broken for both).

In such a case, in order to find a transition for the first trait to
go from good to bad (GG goes to either BG or BB), you can do the
straight bisection, but after finishing the first bisection, it
feels wasteful to do a similar bisection to find a transition for
the other trait to go from good to bad (GG goes to either GB or BB),
without taking advantage of what you already have learned from the
first bisection session.

Is that the problem you are solving?

If that is the problem you are solving, I think you actually can
reuse what learned in the first bisection directly when you start
your second bisection without changing the current system.  "git
bisect good" and "git bisect bad" takes zero or more commit object
names to mark that commit to be good or bad (they default to HEAD if
you do not give any), so when you start the second bisection run for
the second variable, you can tell "git bisect good" all the commits
that was good for the second trait you tested in the first bisect
run you did to find the breakage for the first trait, and similarly,
you can tell "git bisect bad" all the ones that you know are broken
with respect to the second trait.  After that, you would do the
straight bisection for the second trait.  If you have more than 2
traits that are independent and you can test at once, you would be
walking the graph painted in 8 colors, but the principle would be
the same.  The bisection run for the third trait would take
advantage of the knowledge you already have for many commits that
you have visited during the two previous bisection you did for the
first two traits.

I wouldn't call that n-section, though.  That's just n independent
bisections running in parallel.

On Mon, Jan 18, 2016 at 12:43:35AM -0800, Junio C Hamano wrote:

Mike Hommey [off-list ref] writes:

quoted

- I have a script that, for a given git-cinnabar commit, clones
  those four mercurial repositories, and determines a global state
  for the resulting repositories. (for example, the sha1sum of all
  the sha1s of the remote refs for all repositories)
- The script is run for the earliest commit and gives a sha1.
- Then I bisect run with a script wrapping the other, returning 0
  when the state is the same as the one for the earliest commit,
  or 1 otherwise.
- The result of that first bisection is the first state change.
- Then I bisect run again, using the state of the result of that first
  bisect instead of the earliest commit.
- The result of that second bisection is the second state change.
- And so on...

I do, in fact, cache the states for each iteration of each bisect,
so that I can do some smarter decisions than just start from the last
bisection for the next one.

I don't have that many state changes to track, but I do have different
kind of states that I want to track down, so I will be running this
a couple more times.

The question is, is there sufficient interest in a generic n-sect tool
for me to justify spending the time to do it properly, vs. just doing
the minimalist thing I did to make it work for my use case.

After reading the above a few times, I still am not sure what you
mean by n-sect (as opposed to bi-sect), especially given that you
sounded as if you consider the straight "bisect" is about having
only two states, bad/good, new/old, or black/white.  "Bi" in the
word "bisect" refers to the search going by dividing the space into
two to find state transition, and does not necessarily mean there
are two states (hence implying a single state transition between the
two).  If you have three states, black/gray/white, that linearly
transitions states twice (i.e. one part of the history is
continuously black, and at one boundary it turns gray and continues
to be gray, until at another boundary it turns white and continues
to be white to the other end), you would still "bi"-sect to find
these two transition points.  You start from a black A and a white
Z, pick a midpoint M that tests to be gray and know the transition
point from black to gray exists somewhere between A and M, while the
other transision point from gray to white exists somewhere between M
and Z.  Is that the kind of search you are talking about?

Yes, it is. Somehow, I was thinking of the result once you're done
bisecting, not the process itself of cutting history in two parts.

Anyways, 

(...)
If that is the problem you are solving, I think you actually can
reuse what learned in the first bisection directly when you start
your second bisection without changing the current system.  "git
bisect good" and "git bisect bad" takes zero or more commit object
names to mark that commit to be good or bad (they default to HEAD if
you do not give any), so when you start the second bisection run for
the second variable, you can tell "git bisect good" all the commits
that was good for the second trait you tested in the first bisect
run you did to find the breakage for the first trait, and similarly,
you can tell "git bisect bad" all the ones that you know are broken
with respect to the second trait.  After that, you would do the
straight bisection for the second trait.  If you have more than 2
traits that are independent and you can test at once, you would be
walking the graph painted in 8 colors, but the principle would be
the same.  The bisection run for the third trait would take
advantage of the knowledge you already have for many commits that
you have visited during the two previous bisection you did for the
first two traits.

Seems like, while you seemed to associate this paragraph with the
other interpretation, this would work in both cases. This might, in
fact, be less cumbersome than what I'm currently doing... I'll test it
for my next run, since I do need one :)

That being said, while I can do these things locally with my own
scripts, as a user, I would have found it useful if git bisect (and
especially git bisect run) would support this out of the box. The
question remains whether it would be useful to more people than
just me.

Cheers,

Mike

On Mon, Jan 18, 2016 at 05:58:35PM +0900, Mike Hommey wrote:

On Mon, Jan 18, 2016 at 12:43:35AM -0800, Junio C Hamano wrote:

quoted

Mike Hommey [off-list ref] writes:

quoted

- I have a script that, for a given git-cinnabar commit, clones
  those four mercurial repositories, and determines a global state
  for the resulting repositories. (for example, the sha1sum of all
  the sha1s of the remote refs for all repositories)
- The script is run for the earliest commit and gives a sha1.
- Then I bisect run with a script wrapping the other, returning 0
  when the state is the same as the one for the earliest commit,
  or 1 otherwise.
- The result of that first bisection is the first state change.
- Then I bisect run again, using the state of the result of that first
  bisect instead of the earliest commit.
- The result of that second bisection is the second state change.
- And so on...

I do, in fact, cache the states for each iteration of each bisect,
so that I can do some smarter decisions than just start from the last
bisection for the next one.

I don't have that many state changes to track, but I do have different
kind of states that I want to track down, so I will be running this
a couple more times.

The question is, is there sufficient interest in a generic n-sect tool
for me to justify spending the time to do it properly, vs. just doing
the minimalist thing I did to make it work for my use case.

After reading the above a few times, I still am not sure what you
mean by n-sect (as opposed to bi-sect), especially given that you
sounded as if you consider the straight "bisect" is about having
only two states, bad/good, new/old, or black/white.  "Bi" in the
word "bisect" refers to the search going by dividing the space into
two to find state transition, and does not necessarily mean there
are two states (hence implying a single state transition between the
two).  If you have three states, black/gray/white, that linearly
transitions states twice (i.e. one part of the history is
continuously black, and at one boundary it turns gray and continues
to be gray, until at another boundary it turns white and continues
to be white to the other end), you would still "bi"-sect to find
these two transition points.  You start from a black A and a white
Z, pick a midpoint M that tests to be gray and know the transition
point from black to gray exists somewhere between A and M, while the
other transision point from gray to white exists somewhere between M
and Z.  Is that the kind of search you are talking about?

Yes, it is. Somehow, I was thinking of the result once you're done
bisecting, not the process itself of cutting history in two parts.

Let me add that in my use case, I don't know how many states there are
when I start. I only know there are at least two.

Mike

Mike Hommey [off-list ref] writes:

On Mon, Jan 18, 2016 at 12:43:35AM -0800, Junio C Hamano wrote:
...

quoted

two).  If you have three states, black/gray/white, that linearly
transitions states twice (i.e. one part of the history is
continuously black, and at one boundary it turns gray and continues
to be gray, until at another boundary it turns white and continues
to be white to the other end), you would still "bi"-sect to find
these two transition points....
...  Is that the kind of search you are talking about?

Yes, it is. Somehow, I was thinking of the result once you're done
bisecting, not the process itself of cutting history in two parts.

I am not sure what you meant by "Yes it is"; is the above (i.e. in a
history whose one part is painted continuously in black, one part
continuously in gray and the remainder in white where white and
black never touch, find the transition between black and gray and
the transition between gray and white) the kind of search you are
talking about?  Judging from the remainder of your message, I had an
impression that you are solving a different problem where you want
to find transitions for N distinct traits (i.e. 2^N combinations,
not N distinct colors like black-gray-white).

That being said, while I can do these things locally with my own
scripts, as a user, I would have found it useful if git bisect (and
especially git bisect run) would support this out of the box. The
question remains whether it would be useful to more people than
just me.

Hmm, sorry.  For the two-trait example I gave (that can be extended
to N-trait), I can sort of see how the UI might look and I can say
it might be useful [*1*], but not with this, and especially that you
do not necessarily know all the traits whose transition points you
might be interested in a-priori--all of that makes the problem
definition fuzzy to me, and I cannot imagine what kind of user
interaction you would be envisioning to solve what kind of problem,
so I cannot even say it is a good idea or a bad idea.


[Footnote]

*1* I suppose a possible UI for the N-trait bisection might go like
    this.  You start from just a single trait (good for your test #1
    passing, bad for your test #1 failing).  You start with:

    $ git bisect start
    $ git bisect good A
    $ git bisect bad Z

    and Git would give you a commit (let's call it M) to test.  You
    test and find that test #1 passes, but at the same time you find
    that test #2 does not pass.  You do not know if test #2 passes
    or fails at A nor Z.  At this point, you would decide to call
    "test #2 passes" as good2, "test #2 fails" as bad2.  We now have
    two independent traits (good/bad and good2/bad2), and mark M as
    good and bad2:

    $ git bisect add-trait new/old/unknown=good2/bad2/unknown2
    $ git bisect state good bad2

    Then Git would check out another one (let's call it G) for you
    to test and you record the result from two tests.

    $ git bisect state good good2

    As you continue, Git will find the transition between good to
    bad (or it may find the transition between good2 to bad2
    earlier) and would tell you things like "commit F is the first
    bad commit" or "commit K is the first bad2 commit".

    If that is the kind of "out-of-box" behaviour for finding state
    transitions for N-traits simultaneously, I can say that may be
    interesting (note that interesting and useful are two different
    things ;-).

    If the cost to _prepare_ a revision to be tested is far greater
    than an incremental cost to perform one more test after the
    revision is already prepared to be tested, allowing a session
    like that might be an overall win and it could even be a huge
    win (i.e. imagine that compilation of the whole system to be
    tested takes very long, but once the binary to be tested is
    built, the time it takes to run each individual test is
    negligible---if you have ten tests in your test suite, even if
    you start out to find breakage in your test #1 like the above
    example, it may be more efficient if you test all ten tests, not
    just test #1, once you built the system to run test #1 for the
    purpose of bisecting to find the breakage of that particular
    test).

    But I am not sure that is the kind of problem you are trying to
    solve in the first place, so...

On Mon, Jan 18, 2016 at 07:54:21PM -0800, Junio C Hamano wrote:

Mike Hommey [off-list ref] writes:

quoted

On Mon, Jan 18, 2016 at 12:43:35AM -0800, Junio C Hamano wrote:
...

quoted

two).  If you have three states, black/gray/white, that linearly
transitions states twice (i.e. one part of the history is
continuously black, and at one boundary it turns gray and continues
to be gray, until at another boundary it turns white and continues
to be white to the other end), you would still "bi"-sect to find
these two transition points....
...  Is that the kind of search you are talking about?

Yes, it is. Somehow, I was thinking of the result once you're done
bisecting, not the process itself of cutting history in two parts.

I am not sure what you meant by "Yes it is"; is the above (i.e. in a
history whose one part is painted continuously in black, one part
continuously in gray and the remainder in white where white and
black never touch, find the transition between black and gray and
the transition between gray and white) the kind of search you are
talking about?  Judging from the remainder of your message, I had an
impression that you are solving a different problem where you want
to find transitions for N distinct traits (i.e. 2^N combinations,
not N distinct colors like black-gray-white).

No, I'm really after N distinct colors, where I don't know N in advance.

quoted

That being said, while I can do these things locally with my own
scripts, as a user, I would have found it useful if git bisect (and
especially git bisect run) would support this out of the box. The
question remains whether it would be useful to more people than
just me.

Hmm, sorry.  For the two-trait example I gave (that can be extended
to N-trait), I can sort of see how the UI might look and I can say
it might be useful [*1*], but not with this, and especially that you
do not necessarily know all the traits whose transition points you
might be interested in a-priori--all of that makes the problem
definition fuzzy to me, and I cannot imagine what kind of user
interaction you would be envisioning to solve what kind of problem,
so I cannot even say it is a good idea or a bad idea.

How about something like this:

$ git bisect start
$ git bisect state black A
$ git bisect state white Z

Git then gives you commit M to test, between A and Z. Now, you test M,
and the result is that it's neither black or white, but gray, so you
would do:

$ git bisect state gray

Git then gives you commit G, between A and M, which you test, and it's
gray. So the state map, as of now is:

A - black
G - gray
M - gray
Z - white

As of now, Git is still looking for the first gray, so it gives you
commit D, between A and G, etc. until you find the first gray.

Once we're done finding the first gray, Git now wants you to find the
first black, so goes back to bisecting between M and Z.

Once all transitions are found, it outputs something like:
<sha1> is the first gray commit
$(git diff-tree --pretty <sha1>)

<sha1_2> is the first white commit
$(git diff-tree --pretty <sha1_2>)

At any point, there could be additional intermediate states that we
find, in which case Git would bisect them.

How does that sound?

Mike