Re: [PATCH v2.1 resend] rev-list: estimate number of bisection step left

From: Christian Couder <chriscool@tuxfamily.org>
Date: Feb 21, 2009, 17:12 UTC
Message-ID: <200902211812.56593.chriscool@tuxfamily.org>
In-Reply-To: <7vy6w0qgwr.fsf@gitster.siamese.dyndns.org>

Le samedi 21 février 2009, Junio C Hamano a écrit :

Show 11 quoted lines

> Christian Couder <chriscool@tuxfamily.org> writes:
> > Here is a table to help analyse what should be the best estimate for
> > the number of bisect steps left.
> > ...
> > So the algorithm used in this patch calculates 2^n and x, and then
> > choose between returning n - 1 and n.
>
> Two dumb questions about the math (because I suck at math).
>
>  - Do you mean by "best estimate" the best case scenario, or something
>    else (perhaps "the most accurate")?

I mean the number of steps that has the highest frequency of occurrence, if we suppose that:

1) we are in the linear case, and that
2) the first bad revision has an equal chance of being any of the unknown 
(Ux) and the bad (B) revisions.

>  - Is computing based on linear history a good enough approximation?

I think so. Before I sent patch v1, I tested it on some non linear cases and it worked quite well in those cases as well. I think the bisect algorithm tries as best as possible to remove half the revisions from the set of the possible first bad revisions and this means that all the algorithms based on log2(all) should be quite good in any case.

Show 5 quoted lines

> I am not advocating to make things more precise nor saying your math is
> flawed.  I'd prefer simpler code for things like this --- after all, my
> understanding of this whole exercise is to give "this is more or less the
> number you should expect" ballpack figure and nothing more (correct me if
> that is not what you are aiming for).

Yes, that's what I am aiming for. And I thought that my first patch was quite good at doing that, so when you said that "at the very low end the estimate is a bit too optimistic", I had another look and found out that for "all == 3" indeed the algorithm gave 0 when 1 was better, because 1 should happen on average 2 times out of 3.

So I came up with the algorithm in v2 which is better because it should always give the best estimate (supposing 1) and 2)). It's also not much more complex compared to v1 or anything based on log2(all), so I don't see any reason to use something else.

Regards, Christian.