I recently had the unhappy experience of trying to bisect a tree with a
large region of the history obscured by auxilliary bugs. "git bisect
skip" will stay in the central region, thus being largely useless.
I was thinking about how to possibly do it better. This is something I
came up with, and thought it might be interesing.
a. we obviously cannot move the start and end (good and bad) markers,
since they have not been shown one way or the other.
b. however, the practice of testing the centermost point is merely the
*optimal*, corresponding to 1 bit of information per iteration. An
off-center test is also possible (as long as the value depends on both
endpoints, and isn't fixed from one of the endpoints; in that case we
have a linear search), corresponding to a smaller amount of information
- for example, sampling at the one-quarter point corresponds to
3/4*log2(3/4) + 1/4*log2(1/4) =~ 0.811 bits of information.
I would suggest something based on the following algorithm:
Given an interval with a certain number of skip points, subdivide the
interval into subintervals each separated by a skip point. Pick the
centermost point of the *largest* of these intervals. If there is more
than one largest interval, choose the one centermost point that ends up
being centermost in the overall interval.
This algorithm obviously needs some adjustment (as does plain binary
search) in order to deal with a branched history, but I thought it might
be an interesting starting point. It has the desirable property that it
can make forward progress even in the presence of skip points, and that
it avoids needlessly searching close to skip points.
-hpa
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
