Le mardi 14 octobre 2008, H. Peter Anvin a écrit : > 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. Yeah, it tries to find the first non skipped commit among the best possible bisection points. And if you have a linear history the best bisection points are in the middle of the good and bad commits. > 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. It looks like a great alternative algorithm but as the current bisect skip is implemented in shell, I think that it might be too difficult or inefficient to implement something like that in shell. I think it might be better to try a more simple alternative algorithm first like removing all skipped commits from the sorted list of possible bisection point (the list is sorted because best commits from a bisection point are first) and trying the commit at one third (or another fixed ration) of the best commit. Regards, Christian. > -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 -- 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
