Re: Feature request: don't require both bad and good when bisecting

From: Andreas Ericsson <ae@op5.se>
Date: Mar 19, 2012, 14:45 UTC
Message-ID: <4F67468B.4070502@op5.se>
In-Reply-To: <20120318212957.GS1219@chaosreigns.com>

On 03/18/2012 10:29 PM, darxus@chaosreigns.com wrote:

Show 6 quoted lines

> I'd like to be able to tell get only that I know the latest commit is bad,
> and have it go find a good commit, then do the bisecting.  Maybe something
> like the opposite of a binary search, start with the last commit, then
> second to last, then 4th to last, 8th to last, etc., till it finds a good
> commit.
>

Assuming the good commit is the 13'th from HEAD, you'd get the same nr of attempts by just specifying a commit 100 revisions in the past and doing the already implemented binary search as you would from trying 4 commits at a time to get at the good one.

Binary search is a "divide and conquer" algorithm (running in O(log n) time), so it handles extremely large datasets very efficiently. As such, it's (almost) always easier to just specify a revision really far back in history and let it get to work. If you specify a range of 1000000 commits, it will take 20 attempts to find the right one ("git bisect" has to exclude all possible candidates for both sides, so it always runs in worst-case time, even when it hits the correct commit on the first check).

-- 
Andreas Ericsson                   andreas.ericsson@op5.se
OP5 AB                             www.op5.se
Tel: +46 8-230225                  Fax: +46 8-230231

Considering the successes of the wars on alcohol, poverty, drugs and
terror, I think we should give some serious thought to declaring war
on peace.